» » »

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

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

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

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

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

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


\begin{displaymath}

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


\begin{displaymath}

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

Решение. Поскольку в двузначном числе цифра, обозначающая число десятков, должна быть отлична от нуля, то $A$ = {1, 2, ..., 9}, $B$ = {0, 1, 2, ..., 9} и $A\times

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

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

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


\begin{displaymath}

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


\begin{displaymath}

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


\begin{displaymath}

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

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


\begin{displaymath}A_5^2

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

Решение. При проведении турнира по круговой системе каждый участник встречался с каждым и порядок их вхождения в пару не важен. Следовательно, по круговой системе потребуется провести $C_8^2встреч, а по олимпийской только - 7 (четыре встречи в $\raise.5ex\hbox{$\scriptstyleфинала, две - в полуфинале и одна в финале).

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

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

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


\begin{displaymath}

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


\begin{displaymath}


Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.