Далее: §3. Методы комбинаторики Вверх: Глава I. Элементы комбинаторики Назад: §1. Выборки и случай

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

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

Правило суммы. Если некоторый объект $A$ можно выбрать $n$ способами, а другой объект $B$ можно выбрать $m$ способами, то выбор "либо $A$, либо $B$" можно осуществить $n+m$ способами.

Правило произведения. Если объект $A$ можно выбрать $n$ способами, а после каждого такого выбора другой объект $B$ можно выбрать (независимо от выбора объекта $A) \quad m$ способами, то пары объектов $A$ и $B$ можно выбрать $n\cdot m$ способами.

Пусть $A$ = {$a_{1}$, $a_{2}$, ..., $a_{n}$}, $B$ = {$b_{1}$, $b_{2}$, ..., $b_{m}$} и $\vert$ А $\vert$ - число элементов множества $A$. Составим декартово произведение $A \times B$ множеств $A$ и $B$, т.е. множество пар ($a_{i}$, $b_{i})$.

$$\begin{tabular}{ll} $a_i \in A, b_i \in B: A\times B =$&$ \{... ..._n ,b_1 ), (a_2 ,b_n ), ..., (a_n ,b_m ) \}. $\\ \end{tabular}$$

Тогда правило произведения записывается следующим образом:

$$\left\vert {A\times B} \right\vert = \left\vert A \right\vert \cdot \left\vert B \right\vert.$$

Пример 6. Сколько существует двузначных чисел?

Решение. Поскольку в двузначном числе цифра, обозначающая число десятков, должна быть отлична от нуля, то $A$ = {1, 2, ..., 9}, $B$ = {0, 1, 2, ..., 9} и $A\times B = \left\{ {10, 11, ..., 19,{\rm }..., 90, 91, ..., 99} \right\}, \lef... ...s B \right\vert = \left\vert A \right\vert \cdot \left\vert B \right\vert = 90.$

Выборки элементов без повторений

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

Число размещений из $n$ элементов по $m$ обозначим $A_n^m.$ Используя основное правило комбинаторики, получаем

$$A_n^m = n(n - 1)(n - 2)...(n - m + 1) = {\displaystyle n!\over\displaystyle (n - m)!}.$$

Если $m = n$, то $A_n^n$ - число таких размещений, которые отличаются только порядком расположения элементов. Такие размещения называются перестановками. Их число $P_n$ находится по формуле

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

Выборки из $m$ элементов, взятых из данных $n$, отличающихся только составом элементов, называются сочетаниями из $n$ элементов по $m$. Число $C_n^m$ таких сочетаний находится

$$C_n^m = {\displaystyle A_n^m \over\displaystyle P_m } = {\displaystyle n!\over\displaystyle m!(n - m)!}.$$

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

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

$$A_5^2 = {\displaystyle 5!\over\displaystyle (5 - 2)!} = 5 \cdot 4 = 20\ {\text{(словарей)}}.$$

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

Решение. При проведении турнира по круговой системе каждый участник встречался с каждым и порядок их вхождения в пару не важен. Следовательно, по круговой системе потребуется провести $C_8^2 = {\displaystyle \displaystyle 8!\over\displaystyle \displaystyle 2! \cdot 6!} = 28$встреч, а по олимпийской только - 7 (четыре встречи в $\raise.5ex\hbox{$\scriptstyle 1$}\kern-.1em/ \kern-.15em\lower.25ex\hbox{$\scriptstyle 4$}$финала, две - в полуфинале и одна в финале).

Выборки элементов с повторениями

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

Число размещений из $n$ элементов по $m$ с повторениями обозначается $\bar {A}_n^m$ и находится как

$$\bar {A}_n^m = n^m.$$

Число перестановок $P_{m_1,m_2,\ldots ,m_k}$, в которых 1-й элемент повторяется $m_1$ раз, 2-й - $m_2$ раз, а $k$-й - $m_k$ раз, находится следующим образом:

$$P_{m_1,m_2,...,m_k} = {\displaystyle (m_1 + m_2 + ... + m_k )!\over\displaystyle m_1 !m_2 !...m_k !}.$$

Пример 9. Сколько "слов" можно получить, переставляя буквы в слове МАТЕМАТИКА?

Решение. Заметим, что если бы все буквы были различны, то получили бы $P_{10}$ новых "слов", но буква "М" употребляется в "слове" 2 раза, "А" - 3 раза, "Т" - 2 раза, оставшиеся три буквы - по разу. Следовательно, искомое число будет в $P_{2}\cdot P_{3}\cdot P_{2}$ раз меньше, чем $P_{10}$, и равно

$$P_{2,3,2,1,1,1} = {\displaystyle 10!\over\displaystyle 2! \cdot 3! \cdot 2! \cdot 1! \cdot 1! \cdot 1!} = 151200.$$

Число сочетаний с повторениями $\bar {C}_n^m$ из $n$ элементов по $m$ выражается через число сочетаний без повторений:

$$\bar {C}_n^m = C_{n + m - 1}^m .$$

Пример 10. В кафе в продаже имеются 5 сортов пирожных. Сколькими способами 8 студенток могут заказать себе по одному пирожному?

Решение. Зашифруем каждую покупку 8 пирожных единицами по 5 сортам, разделяя сорта нулями. Тогда каждой покупке будет соответствовать упорядоченный набор из 8 единиц и 4 (= 5 - 1) разделительных нулей, а общее число покупок будет соответствовать числу перестановок этих нулей и единиц $P_{8,4}$. Таким образом,

$$\bar {C}_5^8 = P_{8,4} = {\displaystyle 12!\over\displaystyle 8! \cdot 4!} = 495 = C_{5 + 8 - 1}^8 .$$

Вопросы для самоконтроля

1. Основные правила комбинаторики и их иллюстрация на графе.
2. Порядок решения комбинаторных задач.
3. Приведите примеры размещений и перестановок без повторений.
4. Свойства сочетаний без повторений.
5. Как получить треугольник Паскаля, и где он применяется?
6. Приведите примеры выборок с повторениями.
7. Каких выборок больше: с повторениями или без повторений?
8. Что понимают под словом длины $k$ над алфавитом $A$?

Задачи

I 11. В чемпионате России по футболу участвуют 16 команд. Сколькими способами может определиться тройка призеров?

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

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

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

  15. На физмате работают 76 преподавателей. Из них 49 знают английский язык, 32 - немецкий и 15 - оба языка. Сколько преподавателей на физмате не знает ни английского, ни немецкого языков?

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

II 17. В азбуке Морзе буквы представляются последовательностями тире и точек. Сколько символов потребуется, чтобы закодировать буквы русского алфавита?

  18. Какова вероятность выиграть хотя бы один из призов в спортлото?

III 19. Доказать с помощью комбинаторных рассуждений тождество

$$\sum\limits_{k = 0}^n {C_n^k \cdot (m - 1)^{n - k} = m^n.}$$

  20. Доказать тождество

$$\sum {{\displaystyle n!\over\displaystyle n_1 ! \cdot n_2 ! \cdot ... \cdot n_k !} = k^m,}$$

где суммирование распространяется по всем упорядоченным разбиениям $n$ на $k$ слагаемых: $n = n_{1}+n_{2}$ + ...+ $n_{k}$, $n_{i}\ge$ 0 - целые числа.

Далее:§3. Методы комбинаторики Вверх:Глава I. Элементы комбинаторики Назад:§1. Выборки и случай