Комбинаторика в нашей жизни

Подведём промежуточный итог, оформим его в виде теоремы.     

Теорема 1 (о выборах 2-х элементов). Если множество  состоит из п элементов, то у него имеется( п(п-1))/2 подмножеств состоящих  из 2-х элементов.      

Пример 3. В классе 27 учеников. К доске  нужно вызвать двоих. Сколькими способами это можно сделать, если: а) первый ученик должен решить задачу по алгебре, а второй – по геометрии; б) они должны быстро стереть с доски?     

Решение. Для стирания с доски порядок  вызова учеников не важен, т. е., к примеру, вызов Коли и затем Кати ничем не отличается от вызова Кати затем Коли. А вот в первом случае порядок существенен (по крайней мере, для Кати и Коли). Тут применимо правило умножения. Учитель сначала вызывает решать алгебраическую задачу одного из 27 учеников, а затем независимым образом вызывает одного из оставшихся 26 учеников решать задачу по геометрии. Получается 27*26 = 702 способа вызова.     

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

Ответ: а) 702;  б) 351.      

Это рассуждение верно и в общем  случае выбора двух элементов из п  данных. Оказывается, что всегда количество выборок  двух элементов без учета  порядка будет ровно в два раза меньше, чем количество выборок с учётом порядка. На рисунке     

В следующем примере поговорим  о выборе трёх элементов из данного  множества.      

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

Решение. Рассуждаем, как в примере 3. В  первом случае важен порядок вызова учеников и применимо правило  умножения. Один из 27 учеников идет решать задачу. Один из оставшихся 26 учеников идёт за мелом, а один из оставшихся 25 будет дежурным в столовой. Получается: 27*26*25 = 17550 способ вызова.     

Количество  выборок 2-х элементов из п данных.     

п(п -1)     

(по  правилу умножения)      

(п(п  -1 ))/2       

 Во втором случае начнём действовать,  вызывая учеников по порядку.  Можно сначала вызывать Пашу, затем Вову и потом Аню. Обозначим  этот вариант (ПВА). Можно вызывать  этих же ребят в другом порядке.  Например, сначала Аню, затем Пашу  и потом Вову (АПВ). Буквы А, П, В можно расставить по порядку Р = 3! Способами. Во всех этих случаях состав хора будет одинаковым. Значит, каждый состав хора при подсчёте, учитывающем порядок вызова учеников, мы возьмём 3! раз. Поэтому количество различных составов хора в 3! раз меньше количества всех вызовов по порядку.     

Итак, число способов, при которых порядок  выбора трёх элементов из 27 не важен, в 3! Раз меньше числа способов, при  которых порядок выбора трёх элементов  из 27 важен. Остаётся лишь учесть, что 3!= 3*2*1 = 6, получить ответ:     

(27*26*25)/6 = 2925 способов.     

Ответ: а)17550;  б)2925.     

Это рассуждение верно и в общем  случае выбора трёх элементов из п  данных. Значит, верна следующая  теорема.     

Теорема 2. (о выборах 3-х элементов).Если множество  состоит из п элементов, то у него имеется( п(п-1)(п-2))/6 подмножеств, состоящих из трёх элементов.     

Достаточно  длинный словесный оборот «количество  выборок двух (трёх) элементов из п данных без учёта порядка» можно  заметно сократить, если ввести для  такого количества выборок специальное название и специальное обозначение.      

Определение 1. Число всех выборок двух элементов  из п данных без учёта обозначают С  и называют числом сочетаний  из п элементов по 2. Число всех выборок трёх элементов из п данных без учёта порядка обозначают С  и называют числом сочетаний из п элементов по 3.     

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

Учитывая  сказанное, теоремы о выборках двух или трёх элементов можно записать в виде следующих формул для числа  сочетаний из п элементов по два  и по три:     

Число всех выборок к элементов из п данных без учета порядка обозначают   и называют числом сочетаний из п элементов по k.     

Теорема 3. Для числа сочетаний из п  элементов по k справедлива формула  . [2]     

-Теорема  3 может быть сформулирована так:  если множество состоит из п элементов, то у него имеется   подмножеств, состоящих из k элементов.     

- Рассмотрим задачу № 3.  (слайд  № 11)     

«Проказница Мартышка, Осел, Козел и косолапый  Мишка затеяли сыграть квартет». Мишке поручили принести со склада 9 каких-нибудь попавшихся под лапы музыкальных инструментов из имеющихся 14 инструментов. Сколько способов выбора есть у Мишки?      

 Решение: найдем количество всех  выборок 9 элементов из 14 данных  без учета порядка, т. е. число  сочетаний из 13 элементов по 8.            

Ответ: 2002.     

Итак, мы изучили понятие «сочетания» на конкретных примерах, сейчас рассмотрим и проанализируем задачи на нахождение числа сочетаний.      

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

3.1. Примеры решения  задач на нахождение  числа сочетаний     

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

1. Имеется три предмета: карандаш, тетрадь и линейка. Сколькими  способами из этих канцелярских  принадлежностей можно выбрать  2 предмета? [2].     

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

б) Решение:    способа.     

2. В  школьной столовой имеются помидоры, огурцы и лук. Сколько различных  салатов можно приготовить, если  в каждый из них должны входить  в равных долях 2 различных  вида овощей? Записать все сочетания  овощей в составленных салатах. [5].     

Решение: Расположим данные овощи по порядку: помидоры, огурцы, лук. Запишем все  сочетания овощей в салатах. Будем  брать поочерёдно каждый овощ (кроме  последнего) и добавлять к нему по одному, только из последующих, поскольку порядок выбора не важен: 1) помидоры, огурцы;      

2) помидоры, лук; 3) огурцы, лук.      

Ответ: 3 вида салатов.     

3. Володя  идёт на день рождения к  одноклассникам, двойняшкам Диме  и Ивану. Он хочет подарить  каждому из них по мячу. В  магазине остались для продажи  только 3 мяча разных цветов: белый, чёрный и пятнистый. Сколькими способами, купив 2 мяча, Володя может сделать подарки братьям?     

Решение: По условию задачи предусмотрены  два последовательных выбора: сначала  Володя выбирает 2 мяча из трёх, имеющихся  в магазине, а потом решает, какому из братьев-двойняшек подать каждый из купленных мячей. Два мяча из трёх можно выбрать тремя способами. После этого каждую выбранную пару можно подарить двумя способами ( способа) (порядок важен). Тогда по правилу умножения искомое число способов равно  способов.     

Ответ: 6 способов.     

4. В магазине продают кепки трёх  цветов: белые, красные и синие.  Наташа и Лена покупают себе  по одной кепке. Сколько существует  различных вариантов покупок  для этих девочек?     

Решение: В магазине продаются кепки трёх видов, поэтому девочки могут купить кепки одинаковых цветов, т.е. возможен выбор с повторением. Порядок выбора также важен и должен учитываться. Лена может сделать выборспособами и Наташа также 3 способами. По теореме умножения получаем: вариантов.     

Ответ: 9 вариантов.     

5. Сколько существует способов  выбрать троих ребят из 11 желающих  дежурить по школе?      

Решение: Количество сочетаний из 11 по 3 (порядок  выбора не имеет значения) равно: .     

Ответ: 165 способов.     

6. В 9 «Г» классе 5 человек успешно  занимаются математикой. Сколькими  способами можно выбрать из  них двоих для участия в  математической олимпиаде?     

Решение: Выбираем 2 учащихся из 5, порядок выбора не имеет значения (оба выбранных пойдут на олимпиаду как полностью равноправные); количество способов выбора равно числу сочетаний из 5 по 2:   способов.     

Ответ: 10 способов.     

7. Учащимся  дали список из 10 книг, которые рекомендуется прочитать  во время каникул. Сколькими способами ученик может выбрать из них 6 книг? [9].     

Решение: Выбор 6 из 10 без учёта порядка:  способов.      

Ответ: 210 способов.     

8. В 9 «Г» классе учатся  16 мальчиков  и 10 девочек. Для уборки территории  требуется выделить четырёх мальчиков и трёх девочек. Сколькими способами можно это сделать?     

Решение: Нужно сделать два выбора: 4 мальчиков  из 16 (всего  способов  ) и 3 девочек из 10 (всего способов  ); порядок выбора значения не имеет (все идущие на уборку равноправные). Каждый вариант выбора мальчиков может сочетаться с каждым выбором девочек, поэтому по правилу умножения общее число способов выбора равно:  * =способов.     

Ответ: 218400 способов.     

9. В библиотеке Кате предложили  на выбор из новых поступлений  10 книг и 4 журнала. Сколькими  способами она может выбрать  из них 3 книги и 2 журнала?   

Решение: Нужно сделать два выбора: 3 книги  из 10 ( способов) и 2 журнала из 4 ( способов); порядок выбора не имеет значения. Каждый выбор книг может сочетаться с каждым выбором журналов, поэтому общее число способов выбора по правилу умножения равно:  × = способов.     

Ответ: 720 способов.     

10. В 9 «Б» классе учатся 22 учащихся, в 9 «В» - 19 учащихся, а в 9 «Г»  - 26 учащихся. Для работы на пришкольном  участке надо выделить трёх  учащихся из 9 «Б» класса, двух  – из 9 «В» и одного – из 9 «Г». Сколько существует способов выбора учащихся для работы на пришкольном участке?     

Решение: Выбор из трёх совокупностей без  учёта порядка, каждый вариант выбора из первой совокупности ( ) может сочетаться с каждым вариантом выбора из второй ( ) и с каждым вариантом выбора третьей ( );по правилу умножения получаем:  × × = способов выбора учащихся.      

Ответ: 32522490 способов.     

11. По списку в 9 «Г» классе 16 мальчиков  и 10 девочек. Нужно выбрать  двух дежурных по классу. Сколькими  способами это можно сделать:  а) при условии. Что пару  обязательно должны составить  мальчик и девочка; б) без  указанного условия?      

Решение: а) Выбираем 1 мальчика из 16 и 1 девочку  из 10; общее число способов выбора пары: . б) Выбрать 2 дежурных из 16+10=26 учащихся класса (без учёта порядка) можно:   способами.      

Ответ: а) 160; б) 325.     

12. По  списку в 9 «Г» классе 16 мальчиков  и 10 девочек. Нужно выбрать  двух дежурных по классу. Нужно  выделить группу из трёх человек  для посещения заболевшего одноклассника.  Сколькими способами это можно  сделать, если: а) все члены  этой группы должны быть девочками;  б) все члены этой группы  должны быть мальчиками; в) в  группе должны быть 1 девочка и  2 мальчика; г) в группе должны  быть 2 девочки и 1 мальчик.     

Решение: а) Выбрать 3 девочек из 10 имеющихся  без учёта порядка можно  различными способами. б) Выбрать 3 мальчиков из 16 имеющихся,  без учёта порядка, можно  различными способами. в) Выбрать 1 девочку из 10, а затем 2 мальчика из 16 без учёта порядка можно различными способами. г) Выбрать 2 девочек из 10, а затем 1 мальчика из 16 без учёта порядка можно   различными способами.