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

Рассмотрим пару множеств ${ \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 } .

Число различных выборок { для выборки с возвращением } будет равно

${ \rm N } \_n^k =n^k \qquad (1)$

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

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

${ \rm P } \_n =n! \qquad (2)$

легко показать, что ${ \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}$ тогда число комбинаций

${ \rm N } =n\_1 \cdot n\_2 \ldots n\_m \qquad (3)$

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

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

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

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

${ \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} }$

ОпределениеСочетания с повторениями. { один элемент входит в различные сочетания разное число раз }

$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)$

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

$n!\approx \sqrt { 2\cdot \pi \cdot n } \cdot n^n\cdot e^ { -n } \qquad (6)$

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

1. Размещения ${ \rm A } \_n^k =\frac { n! } { \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$