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

3.1.1. Основные правила комбинаторики

Правило сложения

Пример. Из пункта А в пункт В можно добраться самолетом, поездом и автобусом, причем между этими пунктами существуют 2 авиамаршрута, 1 — железнодорожный и 3 — автобусных. Следовательно, общее число маршрутов между пунктами А и В равно 2+1 + 3 = 6. Обобщая этот пример, можно сформулировать правило сложения.

Если выбор каждого из объектов a_i (i = 1,2,..., k) можно выполнить n_i способами, то выбор «или а₁, или а₂,..., или a_k» можно произвести n=способами.

Правило умножения

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

Заметим, что с каждым из четырех способов заполнения первой лунки может совпасть любой из трех способов заполнения второй. Поэтому общее число способов распределения двух лунок равно 4x3 = 12.

Запишем правило умножения в общем виде.

Если выбор каждого из kобъектов a_i(i= 1,2,...,k) можно осуществить n_i способами, то выбор «и а₁ и а₂,..., и a_k» можно произвести N= способами.

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

Пусть дано множество, состоящее из п элементов. Размещением из п элементов по k (0  k  n) элементов называется упорядоченное подмножество, содержащее k различных элементов данного множества. Эти подмножества отличаются друг от друга или составом элементов, или порядком их распределения. Но число элементов во всех этих подмножествах равно k.

Для определения числа размещений из n элементов по k учтем, что первый элемент подмножества может быть взят п способами, второй — (n— 1) способом,..., k-й элемент — (n—(k— 1)) способами. Отсюда, используя правило умножения, получаем

Здесь n!=1*2*3*…*(n-1)*n и (n-k)!=1*2*3*…*(n-k).

Условимся считать 0!=1, поэтому

Пример. В соревнованиях принимают участие 16 команд. Сколькими способами могут распределиться три первых места, т. е. необходимо найти число всех подмножеств, состоящих из трех элементов, отличающихся составом (номерами команд) или порядком их размещения (подмножества № 1, № 2, № 3 и № 2, № 1, № 3 являются разными). Таким образом, имеем дело с размещением. Тогда искомое число равно

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

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

Пример. Сколькими способами можно расставить 6 различных книг на одной полке? Искомое число способов равно P₆ =6!=1*2*3*4*5*6=720.

Действительно, первую книгу можно выбрать шестью способами, вторую — пятью способами и т.д., последнюю — одним способом. По правилу умножения общее число способов равно 6*5*4*3*2*1 = 720.

3.14. Сочетания

Пусть дано множество, состоящее из п элементов. Сочетанием из п элементов по k (0kn) элементов называется любое подмножество, которое содержит k различных элементов данного множества. Таким образом, различными подмножествами считаются только те, которые отличаются составом элементов. Подмножества, отличающиеся друг от друга лишь порядком следования элементов, не считаются различными.

Число всех возможных сочетаний из n элементов по k обозначается . Так как число перестановок из k равно k!, то число размещений из n элементов по k — будет в k! раз больше, чем число сочетаний из n элементов по k-, т. е. = k!, отсюда

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

Так как порядок выбранных четырех человек не имеет значения, то это можно сделать С245 способами:

Упражнения

1. Имеется 5 видов конвертов без марок и 4 вида марок. Сколькими способами можно выбрать конверт и марку для посылки письма?

Ответ. 20.

2. Из 9 человек надо выбрать 4 человека и разместить их на четырех занумерованных стульях (по 1 человеку на стуле). Сколькими способами это можно сделать?

Ответ. 3024.

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

Ответ. 35.

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

Ответ. 720.