ЭЛЕМЕНТЫКОМБИНАТОРИКИ.
Правила суммы и произведения.
Комбинаторика (или теория соединений) – раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, удовлетворяющих тем или иным условиям, можно составить из заданных объектов.
В случае, когда пересечение множеств А и В не пустое, справедливо равенство: n(АÈВ) = n(А) + n(В) – n(АÇВ).
Число элементов в объединении трех множеств можно найти по формуле
n(АÈВÈС) = n(А) + n(В) + n(С) - n(АÇВ) -n(АÇС) - n(ВÇС) - - n(АÇВÇС)
Пример. Из 40 студентов группы 35 человек успешно сдали экзамен по математике, а 37 – по русскому языку. Двое студентов получили неудовлетворительные оценки по обоим предметам. Сколько студентов имеют академическую задолженность?
Решение. Пусть А – множество студентов, получивших неудовлетворительную оценку по математике, тогда n(А) = 40 – 35 = 5; а В – множество студентов, получивших неудовлетворительную оценку по русскому языку, тогда n(В) = 40 – 37 = 3. Тогда число студентов, имеющих академическую задолженность есть n(АÈВ). Значит, n(АÈВ) = n(А) + n(В) - n(АÇВ) = 5 + 3 – 2 = 6.
В случае если АÇВ = Æ, то n(АÈВ) = n(А) + n(В)
В комбинаторике это правило называется правилом суммы и формулируется следующим образом: если элемент х можно выбрать k способами, а элемент у – m способами и, причем ни один способ выбора элемента х не совпадает с каким-либо способом выбора элемента у, то выбор «х или у» можно сделать k + m способами.
Для множеств также справедливо n(А´В) = n(А) × n(В)
В комбинаторике это правило называется правилом произведения и формулируется следующим образом: если элемент х можно выбрать k способами, и если после каждого такого выбора элемент у можно выбрать m способами, то выбор упорядоченной пары (х,у), то есть выбор «и х, и у» можно осуществить k × m способами.
Пример. Из города А в город В ведут 3 дороги, а из В в С ведут 2 дороги. Сколькими способами можно проехать из А в С через В?
Решение. Если обозначить числами 1, 2, 3, а дороги из В в С – буквами х и у, то каждый вариант пути из А в С задается упорядоченной парой и числа и буквы. Но число мы можем выбрать тремя способами, а букву – двумя, поэтому число таких упорядоченных пар равно 3 × 2 = 6.
Размещения.
Пусть n(А) = m. Кортеж длины k (k£m), компонентами которого являются элементы множества А, причем все компоненты являются попарно различными, называется размещением без повторений из m элементов по k элементов.
Для любого множества А такого, что n(А) = m число всевозможных размещений из m элементов по k обозначается 
И вычисляется по формуле 
Пример. В шахматном турнире участвуют 5 школьников и 15 студентов. Сколькими способами могут распределиться места, занятые в турнире школьниками, если известно, что никакие два участника не набрали одинакового количества очков?
Решение. Всего в турнире 20 участников. Следовательно, из 20 мест школьникам принадлежат 5. Поэтому решение задачи связано с образованием всевозможных кортежей длины 5 из элементов множества, в котором 20 элементов, то есть речь идет о размещениях без повторений из 20 элементов по 5 элементов.
Получим 
Пусть n(А) = m. Кортеж длины k, компонентами которого являются элементы множества А, называются размещением с повторениями из m элементов по k элементов.
Для любого множества А такого, что n(А) = m, число возможных размещений с повторениями из m элементов по k обозначается 
и вычисляется по формуле 
.
Пример. Имеется 5 различных стульев и 7 рулонов обивочной ткани различных цветов. Сколькими способами можно осуществить обивку стульев?
Решение. Так как стулья различны, то каждый способ обивки есть кортеж длины 5, составленный из элементов данного множества цветов ткани, содержащего 7 элементов. Значит, всего способов обивки стульев столько, сколько имеется таких кортежей, то есть размещений с повторениями из 7 элементов по 5. Получим 
.
Перестановки.
Пусть n(А) = m. Перестановкой без повторений из m элементов называется всякое упорядоченное m – элементное множество.
Число различных перестановок из m элементов равно произведению последовательных натуральных чисел от 1 до m включительно, то есть 
Пример. Сколько различных пятизначных чисел можно записать с помощью цифр 0, 1, 2, 3, 4, если ни одна цифра в записи числа не повторяется дважды?
Решение. Число всех возможных перестановок из пяти цифр равно Р5 = 5!. А поскольку цифра нуль не может занимать первое место, то искомое число есть:
Р5 - Р4 = 5! – 4! = 120 – 24 = 96.
Перестановкой с повторениями из элементов a, b,…,l, в которой эти элементы повторяются соответственно m1, m2, …, mkраз, называется кортеж длины m = m1 + m2 +…+ mk, среди компонент которого a встречается m1 раз, b - m2 раза и так далее l - mk раз.
Обозначают число перестановок с повторениями символом
Число различных перестановок с повторениями из элементов a, b,…,l, в которой эти элементы повторяются соответственно m1, m2, …, mk раз, определяется по формуле
Пример. Сколько восьмизначных чисел можно записать с помощью цифр 1, 3, 5 при условии, что цифра 1 повторяется в каждом числе четыре раза, цифры 3 и 5 – по 2 раза?
Решение. Искомое число является числом различных перестановок с повторениями из цифр 1, 3, 5, в которых цифра 1 повторяется четыре раза, а цифры 3 и 5 – по два раза. Поэтому по формуле имеем: 
.
Сочетания.
Всякое k-элементное подмножество m-элементного множества (k£m) называется сочетанием без повторений из m элементов по k.
Число различных сочетаний из m элементов по k обозначается символом 
Пример. Сколькими способами можно выбрать из 30 учащихся трех дежурных?
Решение. Так как порядок выбора дежурных не играет роли, то в задаче речь идет о выделении из множества, в котором 30 элементов подмножеств, содержащих по три элемента, то есть о сочетаниях без повторений из тридцати элементов по три.
Следовательно, 
.
Сочетанием с повторениями из данных m различных типов элементов по k элементов называется всякая совокупность содержащая k элементов, каждый из которых является одним из элементов указанных типов.
Число различных сочетаний с повторениями из m элементов по k элементов будем обозначать символом 
.
Число различных сочетаний с повторениями из m типов элементов по k элементов определяется по формуле
Пример. В почтовом отделении продаются открытки четырех видов. Сколькими способами можно купить здесь 9 открыток?
Решение. Число способов купить открытки равно числу различных сочетаний с повторениями из 4 элементов по 9, то есть равно 
.
Число подмножеств конечного множества.
Пусть n(А) = m.
Число всех подмножеств множества А равно 2n.
Упражнение 6.
1. В классе 30 человек, посещающих факультативные занятия по физике и математике. Известно, что углубленно изучают оба предмета 10 человек, а математику – 25. Сколько человек посещают факультативные занятия только по физике?
2. Из 50 студентов 20 знают немецкий язык, а 15 - английский. Каким может быть число студентов, знающих оба языка; знающих хотя бы один язык?
3. Из 100 человек английский язык изучают 28, немецкий – 30, французский - 10 человек, немецкий и французский – 5, немецкий и английский – 15, английский и французский – 6 человек. Все три языка изучают 3 студента. Сколько студентов изучает только один язык? Сколько студентов не изучает ни одного языка?
4.
Задания для самостоятельной работы по теме «Комбинаторика».
1. Расписание одного дня содержит 5 уроков по разным предметам. Определить количество таких расписаний при выборе из 11 предметов.
2. Комиссия состоит из председателя, его заместителя и еще пяти человек. Сколькими способами члены комиссии могут распределить между собой обязанности председателя и заместителя?
3. Сколькими способами можно выбрать трех дежурных из группы в 20 человек?
4. Сколько различных звукосочетаний можно взять на десяти выбранных клавишах рояля, если каждое звукосочетание может содержать от трех до десяти звуков?
5.В вазе стоят 10 красных и 5 розовых гвоздик. Сколькими способами можно выбрать из вазы пять гвоздик одного цвета?
6. Номера трамвайных маршрутов иногда обозначаются двумя цветными фонарями. Какое количество различных маршрутов можно обозначить, если использовать фонари восьми цветов?
7. Чемпионат, в котором участвуют 16 команд, проводится в два круга (т.е. каждая команда дважды встречается с любой другой). Определить, какое количество встреч следует провести.
8. Замок открывается только в том случае, если набран определенный трехзначный номер. Попытка состоит в том, что набирают наугад три цифры из заданных пяти цифр. Угадать номер удалось только на последней из всех возможных попыток. Сколько попыток предшествовало удачной?
9. Из группы в 15 человек выбирают четырех участников эстафеты 800 + 400 + 200 + 100. Сколькими способами можно расставить спортсменов по этапам эстафеты?
10. Команда из пяти человек выступает на соревнованиях по плаванию, в которых участвуют еще 20 спортсменов. Сколькими способами могут распределиться места, занятые членами этой команды?
11. Сколькими способами можно расположить на шахматной доске две ладьи так, чтобы одна не могла взять другую? (Одна ладья может взять другую, если она находится с ней на одной горизонтали или на одной вертикали шахматной доски.)
12. Две ладьи различного цвета расположены на шахматной доске так, что каждая может взять другую. Сколько существует таких расположений?
13. Порядок выступления восьми участников конкурса определяется жребием. Сколько различных исходов жеребьевки при этом возможно?
14. Тридцать человек разбиты на три группы I, II и III по десять человек в каждой. Сколько может быть различных составов групп?
15. Сколько четырехзначных чисел, делящихся на 5, можно составить из цифр 0, 1, 3, 5, 7, если каждое число не должно содержать одинаковых цифр?
16. Сколько различных светящихся колец можно сделать, расположив по окружности 10 разноцветных лампочек (кольца считаются одинаковыми при одинаковом порядке следования цветов)?
17. На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом первый и второй тома не стояли рядом?
18. Четыре стрелка должны поразить восемь мишеней (каждый по две). Сколькими способами они могут распределить мишени между собой?
19. Из группы в 12 человек ежедневно в течение 6 дней выбирают двух дежурных. Определить количество различных списков дежурных, если каждый человек дежурит один раз.
20. Сколько четырехзначных чисел, составленных из цифр 0, 1, 2, 3, 4, 5 содержат цифру 3 (цифры в записи чисел не повторяются)?
21. Десять групп занимаются в десяти расположенных подряд аудиториях. Сколько существует вариантов расписания, при которых группы 1 и 2 находились бы в соседних аудиториях?
22. В турнире участвуют 16 шахматистов. Определить количество различных расписаний первого тура (расписания считаются различными, если отличаются участниками хотя бы одной партии; цвет фигур и номер доски не учитываются).
23. Шесть ящиков различных материалов доставляются на пять этажей стройки. Сколькими способами можно определить материалы по этажам? В скольких вариантах на пятый этаж доставлен какой-либо один материал?
24. Два почтальона должны разнести 10 писем по 10 адресам. Сколькими способами они могут распределить работу?