Комбинаторика

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

Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Например, сколькими способами могли быть распределены золотая, серебряная и бронзовая медали на Олимпийских играх в Сеуле по баскетболу; или сколькими различными способами можно разместить здания на площади? Задачи такого типа называются комбинаторными.

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

Комбинаторика возникла в XVI веке. В то время в жизни привилегированных слоев общества большое место занимали азартные игры (карты, кости). Были широко распространены лотереи. Возникали вопросы: сколькими способами можно выбросить данное число очков, бросая две или три кости, или сколькими способами можно получить двух королей? Эти и другие проблемы оказались движущей силой в развитии комбинаторики.

Теоретические исследования вопросов комбинаторики предприняли Паскаль и Ферма, Бернулли, Лейбниц и Эйлер и др.

Для инженерных специальностей университета комбинаторные задачи приходится решать в следующих случаях:

при конструировании:

для оптимального размещения элементов системы;

для размещения микросхем на плате или элементов на кристалле;

при трассировке (выборе маршрута);

синтезе схем и проектирования:

при решении вопроса, какой набор стандартных микросхем выбрать, чтобы реализовать разработанную схему устройства;

при разработке схемы на подсхемы для реализации различными блоками и т. д.;

при контроле, выбирая-перебирая последовательность тестирующих сигналов;

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

Общие правила комбинаторики

Рассмотрим некоторые конкретные задачи.

Задача. 1. "Суеверные велосипедисты"

"Опять восьмерка" - воскликнул председатель клуба велосипедистов, - а все потому, что у меня билет № 008. Надо менять номера и проводить перерегистрацию".

Итак, сколько членов было в клубе, если известно, что использованы все трехзначные номера, не содержащие ни одной цифры 8?

00	01	02	....................	09
10	11	12	....................	19
20	21	22	....................	29
30	31	32	....................	39
40	.	.	....................	.
50	.	.	....................	.
60	.	.	....................	.
70	.	.	....................	.
80	.	.	....................	.
90	.	.	....................	.

Для решения этой задачи определим сначала, сколько однозначных номеров не содержит цифру 8? Это 0, 1, 2, 3, 4, 5, 6, 7, 9 - всего девять цифр, а теперь найдем все двузначные номера: их $$9 \times 9 = 81$$ (таблица). За каждым двузначным номером можно поставить любую допустимую цифру, следовательно, $$9 \times 9 \times 9 = 9^3 = 729$$. Значит в клубе было 729 велосипедистов.

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

Сколько членов было в клубе, если номера билетов были трехзначными и не включали цифр 0 и 8? $$8 \times 8 \times 8= 8^3 = 512$$.

Задача 2. "Секретный замок"

В сейфах применяют секретные замки, которые открываются, когда набран шифр. Этот шифр набирают с помощью одного или нескольких дисков. Пусть на диск нанесены 12 букв, а секретное слово-шифр состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим шифра?

Всего попыток $$12 \times 12 \times 12 \times 12 \times 12 = 12^5$$, одна из которых удачная, следовательно неудачных попыток $$12^5 - 1$$.

Задача 3. "Команда космического корабля"

В случае, когда число возможных выборов на каждом шаге зависит от того какие элементы были выбраны ранее, удобно решение изображать в виде "дерева". Сначала из одной точки проводят столько отрезков, сколько различных выборов можно сделать на 1-м шаге. Из конца каждого отрезка проводят столько отрезков, сколько можно сделать на 2-м шаге и т. д. В результате получается "дерево решений".

Рассмотрим задачу о формировании команды космического корабля. Известно, что возникнет вопрос психологической совместимости. Предположим, надо составить команду из 3-х человек: командира, инженера и врача. На место командира есть четыре кандидата: $$а_1, а_2, а_3, а_4$$, на место инженера три - $$b_1, b_2, b_3$$, на место врача три - $$с_1, с_2, с_3$$. Проведенная проверка показала, что $$а_1$$ совместим с $$b_1, b_2, с_2, с_3$$ ; $$а_2$$ совместим с $$b_1, b_2, с_1, с_2, с_3$$ ; $$а_3$$ совместим с $$b_1$$ и $$b_2, с_1, с_3$$ ; $$а_4$$ совместим с $$b_1, b_2, b_3, с_2$$ ; $$b_1$$ не совместим с $$с_3$$ ; $$b_2$$ не совместим с $$с_1$$ ; $$b_3$$ не совместим с $$c_2$$.

(рис 5.1)

Сколькими способами при этих условиях может быть составлена команда корабля? По результатам совместимости строится дерево решений (рис 5.1). Итак, всего 11 комбинаций, а без ограничения $$4 \times 3 \times 3 = 36$$.

Упорядоченные множества. Перестановки

Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от $$1$$ до $$n,$$ где $$n$$ - число элементов множества.

Всякое конечное множество можно сделать упорядоченным, если, например, переписать все элементы множества в некоторый список ( $$а, b, c, ....$$.), а затем каждому элементу присвоить номер.

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

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

Пример. Перестановки множества $$A = \left\{ {a, b, c} \right\}$$ из 3-х элементов имеют вид $$A_p = \left\{ {(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)} \right\}$$.

Число перестановок из $$n$$ элементов $$P_n = n$$!

Задача 1. Сколькими способами можно разместить на плате 4 элемента? $$P_4 = 4! = 24$$.

Задача 2. Сколькими способами можно выстроить в линейку 10 человек (5 девушек и 5 юношей) с условием, чтобы девушки и юноши чередовались, первая - девушка? 5 девушек можно разместить $$5$$! способами, а 5 юношей аналогично $$5$$!. Следовательно, всего способов $$(5!)^2 = = (120)^2 = 14400$$.

Перестановка с повторением

Если рассматривать упорядоченные $$k$$ -элементные наборы из множества $$М$$, которые состоят не только из различных элементов множества $$М$$, но содержат некоторые повторяющиеся элементы, то получим перестановки с повторением.

Пусть $$М = \left\{ {S_1, S_2, ..... S_n} \right\}$$ - множество из $$n$$ элементов и $$i_1, i_2, ......i_n$$ - натуральные числа, такие, что их сумма равна $$k$$, а $$k > n$$.

Каждый упорядоченный набор $$k$$ элементов $$\overline {P_k}$$ содержащий элемент $$S_j$$ ровно $$i_j$$ раз ( $$1 \le j \le n$$ ) называется перестановками множества $$М$$ с повторением:

$$\overline {P_k } = \frac{{{\bf{k!}}}}{{{\bf{i}}_{\bf{1}} {\bf{!i}}_2 {\bf{!}}......{\bf{i}}_{\bf{n}} {\bf{!}}}}$$

Примечание: при $$i_1 = i_2 =.......i_n =1$$ получим перестановки множества из $$n$$ элементов без повторений.

Пример. Сколько различных шестизначных чисел можно составить из цифр 1, 1, 1, 5, 5, 9? Подставим в формулу $$\overline {P_6} = 6! / (3!*2!*1!)= 60$$ различных шестизначных чисел.

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

$${\rm{\tilde P}}_{10} = 10! / (2! 3! 2!) = 151200.$$

Перестановки предметов, расположенных в круг

Задача 1. "Хоровод". Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг (рис. 5.2,а)?

Если бы они стояли на месте, то количество способов - $$7! = = 5040$$. Но так как танцующие кружатся, то их положение относительно окружающих не имеет роли, следовательно, важно лишь взаимное расположение. Поэтому перестановки, переходящие друг в друга, надо считать одинаковыми. Но из каждой перестановки можно получить еще 6 путем вращения - 7 мест: $$5040 : 7 = 720$$ различных перестановок девушек в хороводе.

В общем случае, если рассматривать $$n$$ предметов, расположенных в круг, и считать одинаковыми расположения, переходящие друг в друга при вращении, то число различных перестановок равно

$$P_{вр(n)} = (n - 1)!$$

Задача 2. Сколько ожерелий можно составить из 7 бусинок?

По аналогии с предыдущей задачей можно подумать, что 720. Но ожерелье можно не только вращать, но и перевернуть (рис. 5.2,б). Поэтому ответ $$720 : 2 = 360$$, т. е.

$$Р_{\mbox{вр. и пов.}} = \frac{{(n - 1)!}}{2}.$$ (рис 5.2)

Упорядоченные подмножества. Размещения

Упорядоченные $$k$$ -элементные подмножества множества из $$n$$ элементов называются размещениями из $$n$$ элементов по $$k$$.

Различные размещения из $$n$$ по $$k$$ отличаются компонентами либо их порядком. Общее число размещений без повторений из $$n$$ элементов по $$k$$ обозначаются $$А_n^k$$ и равно

$$А_n^k = n(n - 1)......(n - k + 1), n > k.$$

Так как повторение элементов не допускается, то всегда $$n \ge k$$. Будем считать, что при $$k = 0$$ имеем одно размещение (элементы вообще не выбираются), т. е. положим $$A_n^0 = 1$$.

Размещение $$k$$ элементов можно представить себе как заполнение некоторых $$k$$ позиций элементами заданного множества. При этом 1-ю позицию можно заполнить $$n$$ различными способами. После того как 1-я позиция заполнена, элемент для заполнения 2-й позиции можно выбрать $$(n - 1)$$ способами. Если этот процесс продолжить, то после заполнения позиций с 1-й по $$(k - 1)$$ -ю будет иметься $$(n - k + 1)$$ способов заполнения последней $$k$$ -й позиции. Перемножая эти цифры, мы получаем формулу.

В частном случае, когда $$k = n$$, имеем

$$A_n^n = P_n = n!.$$

Пример. Пусть дано множество из четырех элементов $$S = \left\{ {a, b, c, d} \right\}$$. Какие различные размещения по два элемента можно составить и сколько их, т. е. $$A_4^2$$?

Количество размещений $$A_4^2 = 4 \times 3 = 12$$.

Множество размещений $$S_A = \left\{ {(a, b), (a, c), (a, d), (b, a), (b, c), (b, d), (c, a), (c, b), (c, d), (d, a), (d, b), (d, c)} \right\}$$.

Задача. Студенту необходимо сдать 4 экзамена за 8 дней. Сколькими способами можно это сделать, если в один день сдавать не более одного экзамена?

Искомое число способов равно числу четырехэлементных упорядоченных подмножеств (дни сдачи экзаменов) множества из 8 элементов:

$$А_8^4 = 8 \times 7 \times 6 \times 5 = 1680\mbox{ способов}.$$

Размещения с повторением

Любой упорядоченный набор $$k$$ элементов множества, состоящего из $$n$$ элементов называется размещением с повторением $$\tilde {A_n^k}$$ из $$n$$ элементов по $$k$$. Число различных размещений с повторениями есть

$$\tilde {A_n^k} = n^k .$$

Пример. Для множества $$S = \left\{ {a, b, c, d} \right\}$$ предыдущего примера число различных двухэлементных размещений с повторениями $$\tilde {A_4^2} = 4^2 = 16$$. В множество $$S_A$$ к тому, что записано, добавляются следующие элементы $$(а, а), (b, b), (c, c), (d, d)$$.

Задача. Все буквы, цифры, знаки в ЭВМ кодируются двоичными последовательностями определенной длины, компоненты которой равны 0 или 1.

Например:

$$0 - 0\\ 1 - 1\\ 2 - 10\\ 3 - 11\\ 4 - 100\\ 5 - 101\\ 6 - 110\\ \ldots\\ А - 1001$$

Максимальное число символов (букв, цифр, ......), которые могут быть представлены с помощью $$q$$ двоичных символов ( $$q$$ бит) равно числу размещений с повторениями q элементов из множества, содержащего два различных элемента $$\left\{ {0 \mbox{ и } 1} \right\} $$, т. е. $$\tilde A_q^2 = 2^q$$.

Обратная задача. Сколько различных чисел (знаков) может быть записано двоичными словами длиной 4, 8 , 16:

$$2^4 =16$$ $$2^8 = 256$$ $$2^{16} = 65536.$$

Или имеется алфавит из 64 слов. Сколько необходимо разрядов, чтобы закодировать в двоичной системе.

$$N = 64, 64 = 2^q , q = 6.$$