Тема 1. Элементы комбинаторики

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

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

Правило умножения: если из некоторого конечного множества первый объект (элемент ) можно выбратьспособами, а второй объект (элемент) —способами, то оба объекта (и) в указанном порядке можно выбратьспособами.

Правило сложения: если некоторый объект (элемент ) можно выбратьспособами, а объект (элемент) —способами, причем первые и вторые способы не пересекаются, то любой из объектов (и) можно выбратьспособами.

Основные виды комбинаций — это перестановки, размещения и сочетания.

Выборкой объема k из множества, содержащего n элементов, называется подмножество отобранных любым способом k элементов (k  n). Если порядок расположения элементов выборки принимают во внимание, то выборка называется упорядоченной. Иначе выборка называется неупорядоченной. Если некоторые элементы множества встречаются в выборке несколько раз, то выборка называется выборкой с возвращениями, иначе — выборкой без возвращений.

Из цифр 1, 2, 3, 4, 5 составляют всевозможные двузначные числа. Это пример упорядоченной выборки объема 2 с возвращениями.

Из группы, состоящей из 10 человек, выбирают двух дежурных. Это пример неупорядоченной выборки без возвращений.

Размещением без возвращений из n элементов по k элементов называется упорядоченная выборка без возвращений объема k из множества, содержащего n элементов. Число размещений без возвращений из n элементов по k элементов обозначается и определяется по формуле

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

Примеры:

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

2. Сколько существует различных вариантов выбора четырех кандидатур из девяти специалистов для поездки в четыре различные страны?

3. Сколькими способами можно рассадить четырех студентов на 25 местах?

Искомое число способов равно числу размещений из 25 по 4:

Перестановкой без возвращений из n элементов называется размещение из n элементов по n элементов. Число перестановок без возвращений обозначается P_n и определяется по формуле P_n ==n!

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

Примеры:

1. Сколькими способами можно переставить в очереди пять человек?

2. Сколько различных слов можно составить перестановкой букв из слова алгоритм (без учета их смыслового значения)?

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

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

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

Размещением с возвращениями из n элементов по k элементов называется упорядоченная выборка с возвращениями объема k из множества, содержащего n элементов. Число размещений с возвращениями обозначается и определяется по формуле

Примеры:

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

2. Сколько разных четырехзначных чисел можно составить из цифр 0, 1, 2, если та же самая цифра может повторяться несколько раз?

Из цифр 0, 1, 2 можно составить Но числа, записанные четырьмя цифрами, первая из которых ноль, не являются четырехзначными. Значит, из числа размещений с повторениями надо вычесть число таких выборок, которые начинаются с нуля. Последних столько, сколько трехзначных чисел можно составить из цифр 0, 1, 2 при повторении цифр. Таких чиселПоэтому ответ: 81 – 27 = 54.

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

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

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

Полезны следующие свойства: = 1;= 1;=n; (правило симметрии);(правило Паскаля).

Примеры:

1. Из семи заводов организация должна выбрать три для размещения трех заказов. Сколькими способами можно разместить заказы?

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

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

По формуле сочетаний имеем

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

По формуле сочетаний имеем

Сочетанием с возвращениями из n элементов по k элементов называется неупорядоченная выборка с возвращениями объема k из множества, содержащего n элементов. Число различных сочетаний с возвращениями обозначается и определяется по формуле.

Примеры:

1. Сколько имеется различных целых неотрицательных решений уравнения

Имеем ,. Используя формулу сочетаний с повторениями (возвращениями), имеем.

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

Число равновозможных заказов вычисляется по формуле сочетаний с повторениями

Основные комбинаторные понятия можно свести в следующую схему, представленную на рис. 1.

Рис. 1 Классификация комбинаторных понятий

Вычисления перестановок с повторениями, которые можно сделать из элементов n₁, n₂, n₃, …, n_k определяются по формуле , гдеn₁ + n₂ + … + n_k = n. Причем =P (k, n – k).

Примеры:

1. Сколько различных слов можно получить, переставляя буквы в слове «колобок»?

Общее число букв , число различных букв. Число букв «к» равно(элементы первого типа). Число букв «о» равно(элементы второго типа). Число букв «л» равно(элементы третьего типа). Число букв «б» равно(элементы четвертого типа). Применяя для этих данных формулу перестановок с повторениями, получимОбратите внимание, что исходные данные задачи связаны соотношением 2 + 3 + 1 + 1 = 7.

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

Применяя формулу перестановок с повторениями, получим

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

Применяя формулу перестановок с повторениями, получим

Кроме этих основных комбинаторных понятий при решении задач бывает полезным использование понятия пар и комбинаций. Из m элементов множества А={a₁, a₂, …, a_m} и n элементов множества В={b₁, b₂, …, b_n} составляются упорядоченные пары вида (a_i, b_j). Для подсчета числа таких пар нужно перемножить мощности этих множеств, т.е. nm. Если у нас есть k множеств, которые содержат соответственно n₁, n₂, …, n_k элементов и из каждого множества извлекается по одному элементу и помещается на соответствующее место в последовательность длины k, то полученная упорядоченная последовательность из k элементов называется комбинацией. Для подсчета общего числа возможных комбинаций необходимо перемножить между собой количество элементов в этих множествах, т.е. n₁n₂… n_k.

Задания для самостоятельного решения:

1. Для полета на Марс необходимо укомплектовать следующий экипаж космического корабля: командир корабля, первый его помощник, второй помощник, два бортинженера и один врач. Командующая тройка может быть отобрана из числа 25 готовящихся к полету летчиков, два бортинженера — из числа 20 специалистов, в совершенстве знающих устройство космического корабля, и врач — из числа 8 медиков. Сколькими способами можно укомплектовать экипаж исследователей космоса?

2. В киоске продают 5 видов конвертов и 4 вида марок. Сколькими способами можно купить конверт и марку?

3. Сколькими способами можно выбрать гласную и согласную буквы из слова «конверт»?

4. Сколькими способами можно поставить на шахматную доску белую и черную ладьи так, чтобы они не «били» друг друга?

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

6. Сколько существует шестизначных чисел, в записи которых есть хотя бы одна четная цифра?

7. Сколькими способами 8 человек могут встать в очередь к театральной кассе?

8. Имеется 5 одинаковых с виду замков и 5 похожих ключей. Сколько попыток надо сделать, чтобы установить, какой замок открывается каким ключом.

9. Вася собрал 15 васильков и 10 маргариток и решил подарить их двум девочкам — Марго и Рите. Сколькими способами он может разделить свои цветы на два букета, если хочет, чтобы у каждой девочки было хотя бы по одному васильку и не менее двух маргариток?

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

11. На школьном вечере присутствуют 12 юношей и 15 девушек. Сколькими способами можно выбрать из них 4 пары для танца?

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

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

14. Флаги многих государств представляют собой полотнища, состоящие из трех горизонтальных полос различного цвета. Сколько таких трехцветных флагов можно составить, имея в распоряжении материал 6 цветов?

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

16. Сколькими способами можно составить дозор из трех солдат и одного офицера, если всего есть 5 солдат и 3 офицера?

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

18. Сколькими способами можно составить международную команду из 9 человек, если в наличии имеются 3 вида рас.

19. Карты экспресс-оплаты сотового оператора имеют PIN-код из 25 цифр (0 ... 9) и защитный серийный код из 5 цифр (0 ... 4). Какое число карт можно сгенерировать, используя эти данные?

20. Во втором семестре студенты изучают 8 дисциплин. Выясните, сколькими способами можно составить расписание экзаменов на сессию, если в течение ее будут сдаваться 5 дисциплин.

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

22. В продажу поступили открытки 10 разных видов. Сколькими способами можно образовать набор из 12 открыток? из 8 открыток?

23. При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?

24. В качестве памятных сувениров в «Поле Чудес» спонсоры предлагают кофеварки, утюги, телефонные аппараты, духи. Сколькими способами 9 участников игры могут получить эти сувениры? Сколькими способами могут быть выбраны 9 предметов для участников игры?

25. Сколько аккордов можно сыграть с помощью 3 клавиш из 7?

26. Имеется 20 наименований товаров. Сколькими способами их можно распределить по трем магазинам, если известно, что в первый магазин должно быть доставлено 8 наименований, во второй — 7 наименований и в третий — 5 наименований товаров?