ГРУППА 101 и 106. МАТЕМАТИКА.  ТЕМА  «Элементы комбинаторики: перестановки, сочетания и размещения.»

Основная часть

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

Слово «комбинаторика» происходит от латинского слова «combinare», что в переводе на русский означает – «сочетать», «соединять». Комбинаторные задачи возникли и в связи с такими играми, как шашки, шахматы, домино, карты, кости и т.д. 

Термин "комбинаторика" был введён знаменитым Готфридом Вильгельмом Лейбницем, - всемирно известным немецким учёным.

Комбинаторные задачи делятся на  :задачи на перестановки, задачи на размещение, задачи на сочетание

Определение: Факториал – это произведение всех натуральных чисел от 1 до n.

Обозначение: n! = 1 · 2 · 3 · ... · n. Читается: «эн факториал».

Пример: 4! = 1 · 2 · 3 · 4 = 24.

Кроме того: 0! = 1.

Задачи на перестановки

1.Сколькими способами можно расставить 3 различные книги на книжной полке?

Это задача на перестановки.

Решение: Выбираем одну из 3-х книг и ставим на первое место. Это можно сделать 3-мя способами.

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

Третью книгу мы можем выбрать 1 способом.

Получится 3·2·1=6 способов.

Ответ: 6.

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

Формула        P_n = n!

Типичная смысловая нагрузка: «Сколькими способами можно переставить n объектов?»

Пример 1. Сколькими способами можно расставить 8 участников финального забега на восьми беговых дорожках?

Решение: P₈= 8!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 = 40320.

Ответ: 40320.

Пример 2. Сколькими способами можно составить расписание на один день, если в этот день предусмотрено 6 уроков по 6 разным предметам?

Решение: P₆= 6!=1 ∙2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 = 720.

Ответ: 720.

Пример 3. Сколькими различными способами можно разместить на скамейке 10 человек?

Решение: P₈= 8!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 ∙ 9 ∙ 10 = 3628800.

Ответ: 3628800.

Пример 4. Сколько слов можно получить, переставляя буквы в слове Гора?

Решение: P₄= 4!=1 ∙2 ∙ 3 ∙ 4 = 24.

Ответ: 24.

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

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

P₅= 5!=1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 = 120.

Ответ: 120.

Задачи на размещения

1.Имеется 5 книг и одна полка, такая что на ней вмещается лишь 3 книги.

Сколькими способами можно расставить на полке 3 книги?

Это задача на размещение.

Решение: Выбираем одну из 5-ти книг и ставим на первое место на полке. Это можно сделать 5-ю способами.

Вторую книгу мы можем выбрать 4-мя способами и поставить рядом с одной из 5-ти возможных первых.

Таких пар может быть 5·4.

Третью книгу мы можем выбрать 3-мя способами.

Получится 5·4·3 разнообразных троек. Значит всего способов разместить 3 книги из 5-ти 5·4·3 = 60.

Ответ: 60.

Определение:   Размещением из n элементов по k (k≤n) называется любое множество, состоящее из k элементов, взятых в определённом порядке из данных n элементов.

Формула:   A = m!  /(m –n)!

Типичная смысловая нагрузка: «Сколькими способами можно выбрать k объектов и в каждой выборке переставить их местами?»

Пример 1. Учащиеся второго класса изучают 9 предметов. Сколькими способами можно составить расписание на один день, чтобы в нём было 4 различных предмета?

Решение:

Ответ: 3024.

 Пример 2. Сколько трехзначных чисел можно составить из цифр 2, 4, 6, 7, 9?

Решение:

Ответ: 60.

Пример 3. В соревнованиях высшей лиги по футболу участвуют 18 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами могут быть распределены медали между командами?

Решение:

Ответ: 4896.

Пример 4. Сколькими способами можно опустить 5 писем в 11 почтовых ящиков, если в каждый ящик опускают не более одного письма?

Решение:

Ответ:55440.

 

Пример 5. Боря, Дима и Володя сели играть в карты. Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт)

Решение:

42840– способами можно раздать 3 карты игрокам.

Ответ: 42840.

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

Решение:

3024– способами можно рассадить в поезде 4 человека.

Ответ: 3024.

Задачи на сочетания

Сколькими способами можно расставить 3 тома на книжной полке, если выбирать их из имеющихся в наличии внешне неразличимых 5 книг?

Это задача на сочетания.

Решение: Книги внешне неразличимы. Но они различаются, и существенно! Эти книги разные по содержанию. Возникает ситуация, когда важен состав элементов выборки, но несущественен порядок их расположения.

123 124 125 134 135 145

234 235 245

345

Ответ: 10.

Определение:    Сочетанием  из n элементов по k (k<n) называется любое множество, составленное из k элементов, выбранных из данных n элементов (не имеет значения, в каком порядке указаны элементы).

Формула:  С_mⁿ = А_mⁿ  / P_n

Типичная смысловая нагрузка: «Сколькими способами можно выбрать k объектов из n?»

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

Решение:

Ответ: 21.

Пример 2. На тренировках занимаются 12 баскетболистов. Сколько может быть организовано тренером разных стартовых пятерок?

Решение:

Ответ: 792.

Пример 3. В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?

Решение:

Ответ: 1365.

 Пример 4. Сколькими способами из колоды в 36 карт можно выбрать 3 карты?

Решение:

Ответ:7140.

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

Решение: Т.к. двое мальчиков войдут в команду, то остается отобрать 3 из 8. Для выборки важен только состав (по условию все члены команды не различаются по ролям).

Ответ: 56.

Пример 6. В шахматном турнире принимали участие 15 шахматистов, причем каждый из них сыграл только одну партию с каждым из остальных. Сколько всего партий было сыграно в этом турнире?

Решение: В одной игре участвуют 2 человека, следовательно, нужно вычислить, сколькими способами можно отобрать 2-х человек из 15, причем порядок в таких парах не важен.

Ответ: 105.

Пример 7. Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили 2 различных числа? Сколько среди них будет правильных дробей?

Решение: Различных дробей из 6 чисел: 3, 5, 7, 11, 13, 17 можно составитьштук ( способами выбираем два числа из 6, и двумя способами составляем из них дробь, сначала одно число – числитель, другое – знаменатель и наоборот).

Из этих 30 дробей 15 будут правильные.

Ответ: 30; 15.

Пример 8. Боря, Дима и Володя сели играть в карты. Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт)

Решение:

– способами можно извлечь 3 карты из колоды. Теперь рассмотрим, какую-нибудь одну из семи тысяч ста сорока комбинаций, например: король пик, 9 червей , 7 червей. Эти 3 карты можно «переставить» между Борей, Димой и Володей P₃=3!=6способами. Тогда способами можно сдать по одной карте 3-м игрокам.

Ответ:42840.

Получили формулу:     C_mⁿ = m! / (m-n)! n!

Правило сложения комбинаций

Знак «плюс» следует понимать и читать как союз ИЛИ.

Формула:   С_mⁿ  +  C_mⁿ⁺¹ = C_{m +1}ⁿ⁺¹

Задача. Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно выбрать 2-х человек одного пола?

Решение: Условие «выбрать 2-х человек одного пола» подразумевает, что необходимо выбрать двух юношей или двух девушек:

– способами можно выбрать 2-х юношей;

– способами можно выбрать 2-х девушек;

Таким образом, двух человек одного пола (без разницы – юношей или девушек) можно выбрать: способами.

Ответ:123.

Пример 1. В группе 9 человек. Сколько можно образовать разных подгрупп при условии, что в подгруппу входит не менее 2 человек?

Решение: Не менее 2-х человек, т.е. 2+7 или 3+6 или 4+5 человек (5+4, 6+3, 7+2 – те же самые комбинации).

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

Число выборов из 2-х человек:

Число выборов из 3-х человек:

Число выборов из 4-х человек:

Применяем правило сложения: способов.

Ответ: 246.

Правило умножения комбинаций

Знак «умножить» следует понимать и читать как союз И.

Задача.  Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно составить пару из юноши и девушки?

Решение:

– способами можно выбрать 1 юношу;

– способами можно выбрать 1 девушку.

Таким образом, 1-го юношу и 1 девушку можно выбрать: способами.

Ответ:130.

Пример 1. Предприятие может предоставить работу по одной специальности 4 женщинами, по другой – 6 мужчинам, по третьей – 3 работникам независимо от пола. Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?

Решение: Имеем 14 претендентов и 13 рабочих мест. Сначала выберем работников на первую специальность, то есть 4 женщин из 6:

Далее выберем мужчин на вторую специальность:

Осталось 2 женщины, 2 мужчин и 3 вакантных места, которые, по условию, могут занять любые из четырех оставшихся человек.

Это может быть сделано 2 вариантами:

1.     1 женщина и 2 мужчин (выбираем женщину способами)

2.     1 мужчина и 2 женщины (выбираем мужчину способами).

В итоге получаем 15 · 28 · (2+2)=1680.

Ответ: 1680.

Пример 2. Группу из 20 студентов нужно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую – 5 и в третью – 12. Сколькими способами это можно сделать.

Решение: Создавая первую бригаду, отбирают 3 человека из 20, создавая вторую – 5 из оставшихся 17, создавая третью – 12 из оставшихся 12. Для выборок важен только состав (роли членов бригады не различаются).

Создавая сложную выборку (из 3-х бригад), воспользуемся правилом умножения:

способов.

Ответ: 7054320.

Пример 3. Сколькими способами может быть сдана выигрышная комбинация из 2-х карт при игре в «очко»?

Для тех, кто не знает: выигрывает комбинация 10 + ТУЗ (11 очков) = 21 очко и будем считать выигрышной комбинацию из 2-х тузов.

Решение:

способами может быть сдана десятка и туз («каждая десятка с каждым тузом»);

способами может быть сдана пара тузов.

Итого: выигрышные комбинации.

Ответ: 22.

Пример 4. Сколько существует трёхзначных чисел, которые делятся на 5?

Решение:

В разряде сотен можно записать любую из цифр.

В разряде десятков можно выбрать любую из 10 цифр:

По условию, число должно делиться на 5. Число делится на 5, если оно заканчивается на 5 либо на 0. Таким образом, в младшем разряде нас устраивают 2 цифры.

Итого, существует:   трёхзначных чисел, которые делятся на 5.

Ответ: 180.

ЗАДАНИЕ:

1. Запишите определения : перестановки, сочетания и размещения; их формулы.

2. Выпишите формулы сложения и умножения комбинаций.

3. Решите задачи, которые есть в тексте:

     На размещение – 1 – 6

     На сочетания          1 – 6,   8.