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

Основные элементы комбинаторики, используемые при решении комбинаторных задач, таковы:

1. Правила суммы и произведения;
2. Перестановки без повторений;
3. Размещения без повторений;
4. Сочетания без повторений;
5. Перестановки с повторениями;
6. Размещения с повторениями;
7. Сочетания с повторениями.

Правило произведения

Если элемент a множества $A$ можно выбрать $m$ способами и при каждом из этих выборов элемент $b$ множества $B$ можно выбрать $n$ способами, то упорядоченную пару ($a$;$b$) можно выбрать $m$•$n$ способами.

Правило суммы

Если элемент $a$ из множества $A$ можно выбрать $m$ способами, а элемент $b$ из множества $B$ можно выбрать $n$ способами, то число способов, которыми можно осуществить выбор хотя бы одного элемента $a$ или $b$, равно сумме $m$+$n$.

Предполагается, что выборы $a$ и $b$ взаимно исключительны, то есть ни один из способов выбора элемента a не совпадает со способом выбора элемента $b$. При наличии таких совпадений результат выбора будет равен $m$+$n$-$p$,где $p$-количество совпадений.

При выборе элементов по правилу суммы используется соединитель "или"' (выбираем элемент из первого конечного множества, или из второго, или из третьего и т.д.).

При образовании пары (тройки, четверки и т.д.) элементов по правилу произведения используется соединитель "и"' (из первого множества выбираем первый элемент и к нему присоединяем второй элемент из второго множества — образуется пара, и к паре присоединяем третий элемент из третьего множества — образуется тройка и т.д.).

Количество перестановок без повторений

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

Например, из двухэлементного множества $M2$={$a$,$b$} можно образовать два упорядоченных двухэлементных множества: {$a$,$b$} или {$b$,$a$}.

Формула числа перестановок в комбинаторике: $Pn$ = $n$!

Комбинаторика: правило размещения без повторений

Подмножество, выбираемое из данного множества предметов, называют выборкой. Выборки бывают упорядоченные и неупорядоченные. Для упорядоченной выборки существенен порядок элементов. Иначе говоря, меняя порядок элементов, мы получаем другие выборки. Составим, например, из цифр 1, 2, 3, 4, 5 трехзначные числа: 123, 431, 524 и т.д. Это упорядоченные трехэлементные выборки, отличающиеся составом или порядком элементов.

Размещениями из $n$ элементов по $m$ элементов ($m$≤$n$) называют упорядоченные $m$-элементные выборки из данных $n$ элементов.

Формула размещения без повторений в комбинаторике $n$ по $m$ элементов имеет вид: $A_{n}^{m} =\frac{n!}{\left(n-m\right)!}$.

Сочетания без повторений

Сочетаниями из $n$ элементов по $m$ ($m$≤$n$) в комбинаторике называют неупорядоченные $m$-элементные выборки из данных $n$ элементов. Сочетания отличаются друг от друга хотя бы одним элементом, а порядок элементов не существенен.

Формула cочетания в комбинаторике выглядит следующим образом: $C_{n}^{m} =\frac{n!}{m!\cdot \left(n-m\right)!}$.

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

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

Формула числа размещений с повторениями: $\bar{A}_{n}^{m} =n^{m}$.

Комбинаторика: перестановка с повторением

Рассматриваем мультимножество M, то есть множество, которое может содержать одинаковые элементы.

Пусть заданы предметы $m$-типа. Сколько существует перестановок $n_1$ элементов первого типа, $n_2$ — второго типа и так далее, внутри предмета $m$-типа? Такие перестановки в комбинаторике называют перестановками с повторениями.

Формула числа перестановок с повторениями: $P\left(n_{1} ,n_{2} ,\ldots ,n_{m} \right)=\frac{n!}{n_{1} !\cdot n_{2} !\cdot \ldots \cdot n_{m} !}$, где $n=n_{1} +n_{2} +\ldots +n_{m}$ — общее число элементов множества.

Сочетания с повторениями

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

Формула числа сочетаний с повторениями: $\bar{C}_{n}^{m} =\frac{\left(n+m-1\right)!}{m!\cdot \left(n-1\right)!}$.

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

Разберём еще один пример задачи на размещение в комбинаторике с решением.