Сколькими различными способами можно распределить между пятью клиентами две горящие путевки в турцию

Обновлено: 07.07.2024

Комбинаторика – раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.

Правила сложения и умножения в комбинаторике

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n₁ способами, второе действие n₂ способами, третье – n₃ способами и так до k-го действия, которое можно выполнить n_k способами, то все k действий вместе могут быть выполнены:

Пример 2.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

Сочетания без повторений. Сочетания с повторениями

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

Пример 4.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.

Размещения без повторений. Размещения с повторениями

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

Перестановки без повторений. Перестановки с повторениями

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k

Пример 8.

Составитель преподаватель кафедры высшей математики Ищанов Т.Р.

Занятие №1. Элементы комбинаторики

Практический материал.
1.(6.1.44. Л) Сколько различных трехзначных чисел можно составить из цифр 0; 1; 2; 3; 4 если:
а) цифры не могут повторяться;
б) цифры могут повториться;
в) числа должны быть четными (цифры могут повторяться);
г) число должно делиться на 5 (цифры не могут повторяться)
(Ответ: а) 48; б) 100; в) 60; г) 12)

2. (6.1.2.) Сколько чисел, содержащих не менее трех различных цифр, можно составить из цифр 3; 4; 5; 6; 7? (Ответ: 300.)

3. (6.1.39) Сколько можно составить четырехзначных чисел так, чтобы любые две соседние цифры были различными? (Ответ: 9·9·9·9=6561).

Практический материал.
4. (6.1.9 Л.) Составить различные размещения по два элемента из элементов множества A= и подсчитать их число. (Ответ: 6)

5. (6.1.3 Л) Сколькими способами могут быть распределены три призовых места среди 16 соревнующихся? (Ответ: 3360)

6. (6.1.11. Л) Сколько имеется пятизначных чисел, все цифры у которых различны? Указание: учесть тот факт, что цифры вида 02345, 09782 и т.д. не считаем пятизначными. (Ответ: ).

7. (6.1.12.Л.) Сколькими способами можно составить трехцветный полосатый флаг (три горизонтальных полосы), если имеется материя 5 различных цветов? (Ответ: 60.)

Практический материал.
8.(6.1.20.) Составить различные сочетания по два элемента из элементов множества A= и подсчитать их число. (Ответ: 3.)

10.(6.1.14.Л) Составить различные перестановки из элементов множества A=. (Ответ: 6)

)

12. (1.6.16.Л.) В комнате имеется 7 стульев. Сколькими способами можно разместить на них 7 гостей? 3 гостя? (Ответ: 5040; 210)

Схема выбора с возвращением.

13.(6.1.29.) Из элементов (цифр) 2, 4, 5 составить все размещения и сочетания с повторениями по два элемента. (Ответ: 9; 6)

$\bar A_8^5=8^5=32 768$

14. (6.1.31.Л.) Пять человек вошли в лифт на 1-м этаже девятиэтажного дома. Сколькими способами пассажиры могут выйти из лифта на нужных этажах? (Ответ: )

15. (6.1.59.Л.) В кондитерской имеется 7 видов пирожных. Сколькими способами можно приобрести в ней: а) 3 пирожных одного вида; б) 5 пирожных? (Ответ: а) 7; б) 462)

Комбинаторика – это наука о том, сколько различных комбинаций, удовлетворяющих определенным условиям, можно составить на элементах конечного множества.

Чтобы проводить комбинаторные рассуждения необходимо знать основные правила, схемы и формулы комбинаторики.

Пусть X – конечное множество, а – количество элементов в нем. Будем в этом случае говорить, что объект x из X может быть выбран n способами.

Пусть , , … , – попарно непересекающиеся множества, т.е. при . Тогда, очевидно, выполняется равенство

Доказательство. Воспользуемся правилом суммы. Пусть – множество элементов, из которых выбирается объект x . Для каждого рассмотрим множества , в которых первая компонента совпадает с . Множества попарно не пересекаются и . Тогда множество всех пар есть и (по правилу суммы)

Доказательство проводится методом математической индукции.

Размещения и сочетания

Определение 1 . Набор элементов , ,…, из множества называется выборкой объема r из n элементов (или, иначе, - выборкой ).

Выборка называется упорядоченной , если порядок следования элементов в ней задан.

Замечание. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными.

Если порядок следования элементов не является существенным, то выборка называется неупорядоченной .

В выборках могут допускаться или не допускаться повторения элементов.

Определение 2 . Упорядоченная -выборка, в которой элементы могут повторяться, называется - размещением с повторениями .

Определение 3 . Упорядоченная -выборка, элементы которой попарно различны, называется - размещением без повторений (или, иначе, - размещением ).

Замечание. -размещения без повторений называются перестановками множества X .

Определение 4 . Неупорядоченная -выборка, в которой элементы могут повторяться, называется - сочетанием с повторениями .

Определение 5 . Неупорядоченная -выборка элементы, которой попарно различны, называется - сочетанием без повторений (или, иначе, - сочетанием ).

Замечание. Любое -сочетание можно рассматривать, как r -элементное подмножество n -элементного множества.

Пример 1. Пусть , т.е. . Найти какое-либо -сочетание без повторений.

Пример 2. Пусть . Найти все -размещения и -сочетания (с повторениями и без повторений).

а) – множество всех -размещений с повторениями (9 упорядоченных пар);

б) – множество всех -размещений без повторений (6 упорядоченных пар);

в) – множество всех -сочетаний с повторениями (6 неупорядоченных пар);

г) – множество всех -сочетаний без повторений (3 неупорядоченные пары, являющиеся двухэлементными подмножествами трехэлементного множества).

Число -размещений с повторениями будем обозначать , а без повторений – через . Число перестановок n -элементного множества будем обозначать через (т.е. ). Число -сочетаний с повторениями будем обозначать через , а без повторений – через .

Доказательство. Каждое -размещение с повторениями является упорядоченной последовательностью длины r , причем каждый элемент этой последовательности может быть выбран n способами. По правилу произведения получаем

Доказательство. Каждое -размещение без повторений является упорядоченной последовательностью длины r , члены которой попарно различны и выбираются из множества с n элементами. Тогда первый член этой последовательности может быть выбран n способами, после каждого выбора первого члена последовательности второй член может быть выбран способами и так далее до r -го члена последовательности, который может быть выбран способами. По правилу произведения получаем

Доказательство. Каждое -сочетание без повторений можно упорядочить r ! способами. Объединение получаемых таким образом попарно непересекающихся множеств -размещений без повторений для всевозможных -сочетаний без повторений, даст все -размещения без повторений. Тогда (здесь суммирование производится по всевозможным -сочетаниям без повторений), т.е. . Отсюда

Доказательство. Каждому -сочетанию В с повторениями, составленного из элементов множества поставим в соответствие такой вектор длины ( ), состоящий из r единиц и ( ) нулей, что число единиц находящихся между -м и i -м нулями, где , будет равно числу элементов , входящих в сочетание В . Число единиц, стоящих перед первым нулем равно числу элементов , а число единиц, стоящих после -го нуля равно числу элементов , входящих в сочетание В .

Это соответствие между В и будет взаимно однозначным. Поэтому, чтобы подсчитать количество -сочетаний с повторениями, достаточно подсчитать количество векторов .

Количество векторов равно числу r -элементных подмножеств (номеров единичных компонент в этих векторах) ( )-элементного множества (всех номеров компонент в этих векторах), т.е. числу -сочетаний без повторений:

Пример 3. Пусть , , , – -сочетание с повторениями, тогда .

Пример 4. Пусть , , , , тогда .

Правила комбинаторики

В меню столовой имеется 7 первых, 9 вторых и 4 третьих блюда. Сколькими способами можно выбрать обед из трех блюд (первое, второе и третье)?

Допустим, что у вас есть 4 пары туфель, 3 брюк и 2 свитера. Каким числом способов вы можете одеться?

На гору ведут 7 дорог. Сколькими способами турист может подняться на гору и спуститься с нее, если подъем и спуск должны осуществляться по разным дорогам?

Сколькими способами можно поставить на шахматную доску 2 ладьи (белую и черную) так, чтобы они не били друг друга?

Размещения и перестановки без повторений

Сколько слов длиной 4 можно составить, используя только 7 различных букв, если буквы в слове не повторяются?

В чемпионате участвует 16 команд. Сколькими способами могут быть распределены на финише 10 первых мест?

Сколькими способами 4 юношей могут пригласить на танец 4 из 6 девушек?

В чемпионате участвует 16 команд. Сколькими способами могут они быть распределены на финише турнира?

Сколькими способами на шахматной доске можно расставить 8 одинаковых ладей так, чтобы они не били друг друга?

Сколько существует таких перестановок чисел 1, 2, …, n , в которых число 1 стоит перед числом 2, причем числа 1 и 2 не обязательно соседние?

Сочетания без повторений

На чемпионате мира по легкой атлетике проводится полуфинальный забег на 100 метров, в котором участвует 8 спортсменов. Четверо лучших выходят в финал. Сколько существует способов выхода в финал?

У вас есть 15 непрочитанных книг. Каким числом способов вы можете взять с собой в дорогу 3 книги?

На плоскости даны 6 точек, никакие 3 из которых не лежат на одной прямой. Сколько существует треугольников с вершинами в этих точках?

схемы размещений и сочетаний без повторений

Сколькими способами 6 различных конфет можно разделить поровну между тремя детьми?

Сколькими способами можно разделить 28 костей домино четырем игрокам так, чтобы каждый получил 7 костей?

Сколькими способами можно расселить 8 студентов по трем комнатам в общежитии: одноместной, трехместной и четырехместной?

Из 10 роз и 8 георгинов составляется букет, содержащий 2 розы и 3 георгина. Сколько можно составить различных букетов?

Сколькими способами в группе из 23 человек можно выбрать старосту, двух его заместителей, физорга и культорга (совмещение должностей невозможно)?

Хоккейная команда состоит из 2 вратарей, 7 защитников, 10 нападающих. Сколькими способами тренер может образовать стартовую шестерку, состоящую из вратаря, 2 защитников и 3 нападающих?

Перестановки с повторениями

Четыре автора должны написать книгу из 17 глав, причем первый и третий авторы должны написать по 5 глав, второй – 4, а четвертый – 3 главы книги. Сколькими способами можно распределить главы между авторами?

Сколько существует восьмизначных чисел, в которых цифра 1 встречается три раза, а цифры 2, 3, 4, 5, 6 по одному разу?

У мамы 2 яблока, 3 груши и 4 апельсина. Каждый день в течение 9 дней подряд она выдает сыну по одному фрукту. Сколькими способами это может быть сделано, если фрукты одного вида неотличимы друг от друга?

Размещения с повторениями

Сколько слов длиной 4 можно составить, используя только 7 различных букв, если буквы в слове могут повторяться?

Сколькими способами 6 различных конфет можно разделить между тремя детьми (не обязательно поровну)?

Сколько существует семизначных телефонных номеров в Москве?

Сколькими способами k различных шаров можно разложить по n различным урнам?

Четыре студента пришли сдавать экзамен по теории вероятностей. Сколькими способами могут быть распределены между ними оценки, если известно, что все они экзамен сдали?

Сочетания с повторениями

В кондитерском отделе имеются пирожные 4 сортов: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно совершить покупку из 7 пирожных?

Сколькими способами 6 одинаковых конфет можно разделить между тремя детьми?

Сколькими способами k одинаковых шаров можно разложить по n различным урнам?

На фестиваль прибыла молодежь 5 континентов. Потребовалось создать делегацию из 8 человек, но так, чтобы в нее входили представители всех континентов. Сколькими способами это может быть сделано?

Разные задачи

На первой из двух параллельных прямых лежит 10 точек, на второй – 20. Сколько существует треугольников с вершинами в этих точках?

На первой из двух параллельных прямых лежит 10 точек, на второй – 20. Проводятся всевозможные отрезки, соединяющие точки первой и второй прямой. Сколько существует точек (внутренних) пересечения этих отрезков?

Сколькими способами можно рассадить за круглым столом четырех мужчин и четырех женщин, чтобы рядом не сидели двое мужчин или две женщины?

Из 12 лотерейных билетов, среди которых находятся 4 выигрышных, берут 6 билетов. Сколькими способами можно взять 6 билетов, чтобы среди них находился хотя бы один выигрышный?

Дано n различных чисел. Сколько последовательностей длины k можно составить, используя только эти числа?

Дано n различных чисел. Сколько неубывающих последовательностей длины k можно составить, используя только эти числа?

Дано n различных чисел. Сколько возрастающих последовательностей длины k можно составить, используя только эти числа ?

ВАРИАНТЫ ДЛЯ САМОПРОВЕРКИ

В автомобиле 7 мест. Каким числом способов 7 человек могут расположиться в автомобиле, если место водителя могут занять только трое из них?

Для несения почетного караула из 10 человек могут быть приглашены офицеры пехотных войск, авиации, артиллерии и морского флота. Сколькими способами можно избрать состав почетного караула?

Сколько 7-значных телефонных номеров не содержат других цифр, кроме 5, 3, 2?

Сколькими способами семья из 4 человек может расположиться за обеденным столом с 6 различными местами для сидения?

У одного человека имеется 11 книг, а у другого – 15. Все книги разные. Каким числом способов они могут обменяться 3 книгами?

Сколькими способами можно разложить 100 одинаковых гвоздей по 5 коробкам?

Имеются 3 экземпляра одной книги, 4 – другой и 8 – третьей. Каким числом способов эти книги можно вручить 15 детям, чтобы каждому досталось по одной книге?

Сколько букетов из 11 гвоздик можно составить, имея гвоздики 3 цветов (гвоздики одного цвета неотличимы друг от друга)?

Сколькими способами можно распределить 7 преподавателей на проверку 20 заочных работ, если каждая работа должна проверяться одним преподавателем?

ВАРИАНТ 4

Сколькими способами 5 человек могут занять места в маршрутном такси с 14 посадочными местами?

Каким числом способов можно купить 10 тетрадей, если в продаже имеются тетради 5 типов?

У дедушки есть 5 различных конфет, которые он дает своим 8 внукам, причем каждый получает или одну конфету, или ничего. Сколькими способами это можно сделать?

ВАРИАНТ 5

На конференции должны выступить докладчики А , В , С и D , причем В не может выступать раньше А . Сколькими способами можно установить очередность выступлений?

У бабушки есть 5 различных фруктов, которые она дает своим 8 внукам. Сколькими способами это можно сделать?

На полке стоят 12 книг в черных переплетах и 8 книг в красных переплетах, причем все книги разные. Сколькими способами можно расставить книги так, чтобы книги в черных переплетах стояли рядом?

Сколько имеется перестановок цифр 0, 1, 2, …, 9 в которых цифра 1 следует непосредственно за цифрой 0?

Для работы в школьном саду необходимо выбрать группу из 15 учеников (девяти-, десяти- и одиннадцатиклассников). Сколькими способами это можно сделать?

Прямоугольная сетка состоит из 5 горизонтальных и 6 вертикальных линий. Сколько прямоугольников в этой сетке?

Вариант 1. (1) ; (2) ; (3) .

Вариант 2. (1) ; (2) ; (3) .

Вариант 3. (1) ; (2) ; (3) .

Вариант 4. (1) ; (2) ; (3) .

Вариант 5. (1) ; (2) ; (3) .

Вариант 6. (1) ; (2) ; (3) .

Комбинаторика (для обучающихся 9 классов) пояснительная записка

. . Место курса в образовательном процессе. Изучение элементов комбинаторики, теории вероятностей, математической статистики в школьном . статистике со всеми их многочисленными приложениями. Комбинаторика — ветвь математики, изучающая комбинации и .

Комбинаторика без повторений содержание

КОМБИНАТОРИКА Некоторые сведения из теории множеств

Методические подходы введения в содержание математического образования основной школы элементов комбинаторики статистики и теории вероятностей о введении элементов комбинаторики статистики и теории вероятностей в содержание математического

. школы элементов комбинаторики, статистики и теории вероятностей О ВВЕДЕНИИ ЭЛЕМЕНТОВ КОМБИНАТОРИКИ, . 4 2 5 2 1 3 3 3 1 16 4 5 6 1 16 3 3 3 З 2 2 15 Приложение Учебники, включающие элементы комбинаторики, статистики, теории вероятностей: 5-6 классы .

Вы можете ознакомиться и скачать Решение задач тема: "Комбинаторика". Презентация содержит 11 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайд 1

Слайд 2

Сколькими способами можно распределить уроки в шести классах между тремя учителями, если каждый учитель будет преподавать в двух классах? Сколькими способами можно распределить уроки в шести классах между тремя учителями, если каждый учитель будет преподавать в двух классах?

Слайд 3

Решение Первый учитель может выбрать два класса из шести различными способами. После выбора первого учителя второй может выбрать два класса из четырех оставшихся различными способами. Тогда два учителя могут выбрать по два класса различными способами. Если они уже сделали выбор, то третий может взять только оставшиеся два класса. Поэтому искомое число Ответ: 90 способов.

Слайд 4

Сколькими различными способами можно выбрать из 15 человек делегацию в составе трех человек? Сколькими различными способами можно выбрать из 15 человек делегацию в составе трех человек?

Слайд 5

Решение Различными будем считать те делегации, которые отличаются хотя бы одним членом. Таким образом, нужно вычислить Ответ:455 способов

Слайд 6

На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек? На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек?

Слайд 7

Решение В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5. Ответ: 15504 варианта

Слайд 8

Встретились 6 друзей, и каждый пожал руку каждому. Сколько всего было рукопожатий? Встретились 6 друзей, и каждый пожал руку каждому. Сколько всего было рукопожатий?

Слайд 9

Решение Каждый пожал руку каждому, то есть каждый человек сделал 5 рукопожатий. Но общее количество рукопожатий, получается по правилу суммы: n1 + n2 + . + n6 = 6 × 5 = 30. Учтём теперь то, что каждое рукопожатие мы посчитали дважды, и получим в результате 15 рукопожатий

Слайд 10

У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги. У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги.

Слайд 11

Решение Так как надо порядок следования книг не имеет значения, то выбор 2 книг - сочетание. Первый человек может выбрать 2 книги способами. Второй человек может выбрать 2 книги. Значит всего по правилу произведения возможно 21*36=756 вариантов

Читайте также: