Важнейшие формулы комбинаторики

Рассмотрим пару множеств $ {\rm A}=\left\{ {a_1 ,a_2 \ldots a_n } \right\} , {\rm B}=\left\{ {b_1 ,b_2 \ldots b_m } \right\} $ размерности $n\left( {\rm A} \right)=n$ и $n\left( {\rm B} \right)=m$

Следуя терминологии, принятой в Т.В. каждое из множеств будем называть генеральной совокупностью {Г.С.} объема $n$ и $m$.

Определение Упорядоченное подмножество из $k$ элементов $\left\{ {a_1 \ldots a_k } \right\}$, входящих в Г.С. ${\rm A}=\left\{ {a_1 \ldots a_n } \right\}$ объема $n$, называется выборкой объема $k$ из этой Г.С.

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

Выбор без возвращения Выбранный элемент удаляется из Г.С., выборка не содержит повторений.

Определение

Выборка без возвращения называется размещением ${\rm A}_n^k $

Замечание Две выборки одного объема будут отличаться друг от друга, если они содержат хотя бы по одному различному элементу.

Теорема Число размещений ${\rm A}_n^k $,{для выборки без возвращения} равно

${\rm A}_n^k =\prod\limits_{i=0}^{k-1} {\left( {n-i} \right)} =n\left( {n-1} \right)\ldots \left( {n-k+1} \right)=\frac{n!}{\left( {n-k} \right)!}${1}.

Число различных выборок {для выборки с возвращением} будет равно $\begin{equation} \label{eq1} {\rm N}_n^k =n^k \qquad (1) \end{equation}$

Определение Выборка без повторений объема $n$ из Г.С. объема $n$ называются перестановкой ${\rm P}_n $, {предполагается, что в Г.С. нет повторяющих элементов}.

Теорема Число всех различных перестановок из n элементов может быть подсчитано по формуле

$\begin{equation} \label{eq2} {\rm P}_n =n! \qquad (2) \end{equation}$

легко показать, что ${\rm P}_n ={\rm A}_n^n =\frac{n!}{0!}=n!$

Пусть имеется $m$ Г.С. объема $n_1 \ldots n_m $. Составим различные комбинации так, что из каждой Г.С. в комбинацию входит по одному элементу $\left. {{\begin{array}{c} {a_1 \ldots a_{n1} } \\ {b_1 \ldots b_{n2} } \\ {{\begin{array}{c} \cdots \\ {c_1 \ldots c_{nm} } \\ \end{array} }} \\ \end{array} }} \right\} $ m Г.С.

$\left( {a_i ,b_j ,\ldots c_k } \right)$, где $\begin{array}{c} {i=1\ldots n_1 } \\ {j=1\ldots n_2 } \\ {k=1\ldots n_m } \\ \end{array} $ тогда число комбинаций $\begin{equation} \label{eq3} {\rm N}=n_1 \cdot n_2 \ldots n_m \qquad (3) \end{equation}$

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

Определение Соединения, которые отличаются друг от друга только составом называются сочетаниями и обозначаются $C_n^m $.

Число сочетаний может быть вычислено по формуле $ \begin{equation} \label{eq4} C_n^m =\frac{{\rm A}_n^m }{{\rm P}_m }=\frac{n!}{m!\left( {n-m} \right)!} \qquad (4) \end{equation}$

Определение Перестановки с повторениями. {элементы могут повторяться, но отличаются порядком расположения}

${\rm P}_{n\,k_1 \ldots k_i } =\frac{n!}{k_1 !\ldots k_n !}$(6) ${\begin{array}{c} {a_1 -повтор\,k_1 } \\ {a_2 -повтор\,k_2 } \\ {{\begin{array}{c} \cdots \\ {a_n \ldots k_n } \\ \end{array} }} \\ \end{array} }$

Определение Сочетания с повторениями. {один элемент входит в различные сочетания разное число раз} $\begin{equation} \label{eq5} f_n^m =C\cdot C_n^m =C_{n+m-1}^m =\frac{\left( {n+m-1} \right)\,!}{m\,!\left( {n-1} \right)\,!} \qquad (5) \end{equation}$

Замечание при вычислении факториалов больших чисел пользуются формулой Стирлинга.

$\begin{equation} \label{eq6} n!\approx \sqrt {2\cdot \pi \cdot n} \cdot n^n\cdot e^{-n} \qquad (6) \end{equation}$

Сводка основных формул

  1. Размещения ${\rm A}_n^k =\frac{k!}{\left( {n-k} \right)\,!}$ {состав и порядок}
  2. Перестановки ${\rm P}_n =n!$ {порядок}
  3. Сочетания $C_n^k =\frac{n\,!}{k\,!\left( {n-k} \right)\,!}$ {только состав}
  4. Перестановки с повторениями ${\rm P}_{n,k_1 \ldots k_m } =\frac{n!}{k_1 !\ldots k_m !}$
  5. Сочетание с повторениями $C\cdot C_n^k =C_{n+k-1}^k =\frac{\left( {n+k-1} \right)\,!}{k\,!\left( {n-1} \right)\,!}$
  6. Комбинации ${\rm N}=n_1 \cdot n_2 \cdot n_3 \cdot \ldots \cdot n_k $
  7. Выбор с возвращением ${\rm N}_n^k =n^k$

Примеры:

Задача 1. Сколькими способами можно выбрать из студенческой группы в 25 человек троих на профсоюзную конференцию?

Решение. Студенческая группа - генеральная совокупность - ее объем $n(A)=25$ из нее извлекают выборку объема $k=3$. Из условия задачи ясно, что важен только состав} {три студента выбирают}, следовательно, число способов равно числу сочетаний из 25 по 3 {формула 5}. $ C_{25}^3 =\frac{25!}{( {25-3} )!\cdot 3!}=\frac{25!}{22!\cdot 3!}=2300. $

Задача 2. Сколькими способами можно избрать треугольник студенческой группы {старосту, физорга, профорга} в 25 человек?

Решение. Студенческая группа - генеральная совокупность - ее объем $n(A)=25$ из нее извлекают выборку объема $k=3$. Из условия задачи ясно, что важен не только состав, но и порядок} {распределение обязанностей}, следовательно, число способов равно числу размещений из 25 по 3 {формула 1}.

$ A_{25}^3 =\frac{25!}{( {25-3} )!}=\frac{25!}{22!}=13800. $

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

Решение. Генеральная совокупность - количество букв, содержащихся в слове математика - ее объем $n(A)=10$. Из условия задачи ясно, что при составлении различных "слов" объем генеральной совокупности не меняется, а важен только порядок} расположения букв, поэтому количество "слов" равно числу перестановок из 10-и букв {формула 3}.

$ P_{10}^ =10!=151200. $

Задача 4. Сколько существует шестизначных чисел без нуля в записи?

Решение. Генеральная совокупность - количество цифр без нуля $1,2,3,{\ldots}9$ - ее объем $n(A)=9$. Из нее извлекают выборку объема $k=6$. Из условия задачи ясно, что цифры могут повторяться {поскольку не сказано, что цифры различны}. При составлении различных выборок важен не только состав, но и порядок расположения цифр, поэтому количество шестизначных чисел равно числу размещений с повторениями {выбор с возвращением} {формула 2}.

$ N_9^6 =9^6=531441. $

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

Решение. Генеральная совокупность - количество букв, содержащихся в слове математика - ее объем $n(A)=10$. Из условия задачи ясно, что при составлении разных буквосочетаний объем генеральной совокупности не меняется. Здесь - 1 буква "е", 2 буквы "м", 3 буквы "а", 2 буквы "т", 1 буква "и", 1 буква "к". Среди выбираемых элементов есть одинаковые {выборка с возвращением}, чтобы получить разные буквосочетания, важен порядок расположения букв, поэтому количество таких буквосочетаний равно числу перестановок с повторениями из 9-и букв {формула 6}.

$ P_{9,k_1 \ldots k_m } =\frac{n!}{k_1 !\ldots k_m !} = P_{9,1,2,3,2,1,1} =\frac{9!}{1!\cdot 2!\cdot 3!\cdot 2!\cdot 1!\cdot 1!} =15120. $

Задача 6. В кафе имеются торты четырех разных сортов: "Анастасия", "Тайна", "Астория" и "Фантазия". Сколькими способами можно купить 8 тортов?

Решение. Очевидно, что порядок, в котором выбираются торты, значения не имеет, важен только состав {8 тортов}. В выбранную комбинацию могут входить повторяющиеся элементы {например, можно купить все тортики одного сорта}. Следовательно, число способов покупки 8 тортов определяется числом сочетаний с повторениями из 4 элементов по 8 {формула 7}.

$ C\cdot C_n^k =C_{n+k-1}^k =\frac{( {n+k-1} )\,!}{k\,!( {n-1} )\,!} $ $ C\cdot C_4^8 =C_{4+8-1}^8 =\frac{( {4+8-1} )\,!}{8\,!( {4-1} )\,!}=\frac{11!}{8\,!\cdot 3\,!}=165 $

Задача 7. Из Москвы до Новосибирска можно добраться поездом и самолетом. Из Новосибирска в Томск - поездом, самолетом, автобусом, пароходом. Сколькими способами можно осуществить путешествие по маршруту Москва - Новосибирск - Томск?

Решение. Пусть первую генеральную совокупность образуют поезд и самолет, которыми можно добраться из Москвы до Новосибирска, ее объем $n(A)=2$. Вторую генеральную совокупность образуют поезд, самолет, автобус и пароход, которыми можно добраться из Новосибирска в Томск, ее объем $n{B}=4$. Очевидно, что путешествие по маршруту Москва - Новосибирск - Томск обязательно должно производится двумя видами транспорта, причем по одному из каждой генеральной совокупности. Следовательно, число способов будет равно числу комбинаций, образованных двумя элементами, взятыми по одному из каждой генеральной совокупности {формула 4}.

$ {\rm N}=n_A \cdot n_B $

$ {\rm N}=2\cdot 4=8 $