1. Перестановки

Перестановками называют соединения, которые можно составить из n предметов, меняя всеми возможными способами их порядок.

Число перестановок из n элементов обозначается символом Р_n .

Число всех перестановок из n элементов равно произведению последовательных чисел от 1 до n включительно:

Рn=123…(n-1)n или

Рn=n!

(читается «n-факториал»)

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

Решение: Р₁₀=10!=123…910=3628800 способов.

2. Размещения

Размещениями называют соединения, содержащие по m предметов из числа n данных, различающиеся либо порядком предметов, либо самими предметами.

Число размещений из n элементов по m обозначается символом и вычисляется по формуле:

=n(n-1)(n-2)…[n-(m-1)]

Замечание: Перестановки представляют частный случай размещений из n элементов по n в каждом, т.е. Р_n= .

Тогда = Рn / Рn-m или

=

Замечание: При решении задач часто используется равенство =(n-m)

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

Решение: =Р₁₂=12!=479001600 способов.

3. Сочетания

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

Число сочетаний из n элементов по m обозначается символом и вычисляется по формуле:

= / Рm или

=

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

1 = (0mn). По определению полагают =1 и =1

2 + =

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

Решение: = = = =3003 способов.

Замечание: Еще во II в. до н.э. индийцы умели вычислять числа, которые мы обозначаем через , т.е. сочетания из n элементов, взятых по m, и знали формулу + +…+ =2ⁿ.

В Древней Индии, в Средней Азии и Китае было известно, что числа являются в то же время биномиальными коэффициентами². Детальное изучение свойств биномиальных коэффициентов провел французский математик и философ Б. Паскаль в 1654 г.

Целый ряд комбинаторных задач возникает при разбиении множеств на части: найти, сколькими способами можно число n записать в виде суммы k слагаемых; найти, сколькими способами можно разложить n предметов по k ящикам, и т.д. Обычно задачи теории разбиений и раскладок сводятся к разобранным выше основным задачам комбинаторики.

Комбинаторика не сводится только к подсчету количества тех или иных подмножеств или последовательностей. При решении комбинаторных проблем иногда нужно лишь доказать, что данная проблема имеет решение, или убедиться в отсутствии его. Так, с помощью ЭВМ решена проблема четырех красок: доказано, что любую карту можно раскрасить в четыре цвета так, чтобы никакие две страны, имеющие общую границу, не были окрашены в один и тот же цвет.

В 1970-1980 гг. комбинаторика добилась новых успехов. Комбинаторные задачи физики, химии, биологии, экономики и других наук, которые не поддавались ранее решению из-за трудоемкости вычислений, стали успешно решаться на ЭВМ. В результате этого комбинаторные методы исследования все глубже проникают во многие разделы науки и техники.

Решение типовых задач по комбинаторике

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

Решение:

Если бы все шесть букв слова были различны, то число перестановок было бы равно 6!. Но буква «а» встречается в данном слове три раза, и перестановки только этих трех букв «а» не дают новых способов расположения букв. Поэтому число перестановок букв слова «задача» будет не 6!, а в 3! раз меньше, т.е.

=4∙5∙6=120

Задача 2. У богатого коллекционера было 10 ценных картин. Ему захотелось сделать одному музею подарок. Сколькими вариантами подарка располагает коллекционер: ведь подарить можно любую одну картину, любые две, любые три картины и т.д., можно даже подарить все десять картин?

Решение:

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

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

Тогда число всевозможных способов выбора подарка равно:

+ + + + + + + + +

Поскольку + +…+ =2ⁿ , и, следовательно, + +…+ =2¹⁰ , то

+ + + + + + + + + =2¹⁰- =2¹⁰-1=1024-1=1023

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

Решение:

Если нет никаких ограничений, то 10 человек можно рассадить 10!=3628800 способами. Сколько из этих перестановок запрещено? Будем рассматривать двух человек одной национальности, заключенных в скобки, как единое целое.

1. Тогда

(А, А) (Ш, Ш) (У, У) Ф Ит Ис Ам

можно переставить

7!∙(2!)³=40320 способами.

Помните, что два А могут меняться местами внутри скобок, где бы последние ни расположились, и то же самое верно для двух Ш и двух У. Отсюда и появляется (2!)³.

Итак, имеется 40320 способов, чтобы одновременно англичане сидели рядом, шотландцы сидели рядом и уэльсцы сидели рядом друг с другом.

2. Однако мы можем рассмотреть

(А, А) (Ш, Ш) У У Ф Ит Ис Ам,

где два У не объединены скобками, а расположены произвольно. Это даст нам

8!∙(2!)²=161280 вариантов,

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

161280-40320=120960 способов,

чтобы англичане сидели рядом, шотландцы сидели рядом, но в то же время уэльсцы рядом не сидели.

3. Аналогично, рассмотрим

(А, А) Ш Ш (У, У) Ф Ит Ис Ам,

где два Ш не объединены скобками, а расположены произвольно.

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

4. Так же рассмотрим

А А (Ш, Ш) (У, У) Ф Ит Ис Ам,

где два А не объединены скобками, а расположены произвольно.

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

5. Но мы можем рассмотреть

(А, А) Ш Ш У У Ф Ит Ис Ам,

где и два Ш, и два У располагаются свободно. Это даст нам

9!∙(2!) =725760 случаев,

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

725760-40320-120960-120960=443520 способов,

когда англичане сидят рядом, но при этом шотландцы рядом не сидят и уэльсцы рядом не сидят.

6. Аналогично, рассмотрим

А А (Ш, Ш) У У Ф Ит Ис Ам,

когда в скобки заключены только два Ш.

После вычитания результатов пунктов 1, 2 и 4 получим 443520 способов, когда шотландцы сидят рядом, но при этом англичане рядом не сидят и уэльсцы рядом не сидят.

7. Так же рассмотрим

А А Ш Ш (У, У) Ф Ит Ис Ам,

когда в скобки заключены только два У.

После вычитания результатов пунктов 1, 3 и 4 получим 443520 способов, когда уэльсцы сидят рядом, но при этом англичане рядом не сидят и шотландцы рядом не сидят.

Теперь из первоначального числа всевозможных перестановок 10! вычитаем результаты пунктов 1–7, т.е. перестановки, в которых хотя бы два человека одной национальности оказываются сидящими рядом, и получаем число перестановок, в которых никакие два человека одной национальности не будут сидеть рядом друг с другом:

3628800-40320-120960-120960-120960-443520-443520-443520=1895040

Дополнительные задачи для самостоятельного решения по теме «Комбинаторика»

1. Задача из сборника «Занимательных и приятных математических задач» (автор Баше де Мезириак, 1612 г.).

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

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

3. Сейф запирается на замок, состоящий из 5 дисков, на каждом из которых изображены цифры 0, 1, 2, …, 9. Замок открывается, если на дисках набрана одна определенная комбинация цифр. Хватит ли 10 дней на открытие сейфа, если «рабочий день» продолжается 13 часов, а на набор одной комбинации цифр уходит 5 секунд?

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

5. Сколько диагоналей имеет выпуклый n-угольник?

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

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

8. Известно, что крокодил имеет не более 68 зубов. Доказать, что среди 16¹⁷ крокодилов может не оказаться двух крокодилов с одним и тем же набором зубов.

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

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

11. Автомобильные номера состоят из трех букв (всего используется 30 букв) и четырех цифр (используются все 10 цифр). Сколько автомобилей можно занумеровать таким образом, чтобы никакие два автомобиля не имели одинакового номера?

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

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

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

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

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

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

18. Сколько существует шестизначных чисел, все цифры которых нечетны (1, 3, 5, 7, 9)?

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

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

21. В алфавите племени Бум-Бум шесть букв. Словом является любая последовательность из шести букв, в которой есть хотя бы две одинаковые буквы. Сколько слов в языке племени Бум-Бум?

22. У одного человека было 21 дерево. Деревья были посажены в форме треугольника (На рисунке деревья находятся в точках пересечения прямых). Если владелец деревьев захочет огородить какой-нибудь треугольный участок своей земли с деревьями по углам, то сколькими способами он сможет это сделать?

23. Клерки фирмы «Пилкинс энд Попинджей» решили, что они каждый день будут садиться по трое за один и тот же стол до тех пор, пока какие-либо 3 человека не будут вынуждены сесть за этот стол вторично. Такое же число клерков фирмы «Рэдсон, Робсон энд Росс» решили проделать то же самое, но только не по 3, а по 4 человека. Когда они начали осуществлять свой план, то обнаружилось, что клерки второй фирмы могут продолжать пересаживаться ровно втрое дольше, чем их соседи. Какое наименьшее число клерков могло служить в каждой из двух фирм?