Комбинаторика – раздел математики, где ставится вопрос о подсчете числа вариантов выбора элементов из некоторого множества согласно определенным правилам.

В задании №8 в ЕГЭ по информатике присутствуют задачи по теме "Комбинаторика", которые могут быть решены как с помощью формул, так и средствами программирования. Как правило, на динамическое программирование задачи в данном задании отсутствуют. Используя сразу два метода при решении задачи, можно с высокой долей вероятности гарантировать получение верного ответа в случае его совпадения в обоих решениях.

Далее рассмотрим основные понятия и формулы по данной теме.

Размещение

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

${\stackrel{}{A}}_n^k\mathit{=}\frac{n\mathit{!}}{\mathit{(}n\mathit{-}k\mathit{)}\mathit{!}}$

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

Размещение с повторением – упорядоченный набор из k элементов некоторого n-элементного множества.

${\stackrel{‾‾‾}{A}}_n^k\mathit{=}{n}^k$

Перестановка

Перестановка – последовательность и n различных элементов.

$P_n=n!$

Перестановка с повторением

Перестановка с повторением – последовательность, содержащая n элементов из k типов.

$P(n_1,n_2,...,n_k)=\frac{n!}{n_1!\cdot n_2!\cdot ...{\cdot n}_k!}$

$\underset{n_1}{\underbrace{\mathrm{aa...a}}}\underset{n_2}{\underbrace{\mathrm{bb...b}}}...\underset{n_k}{\underbrace{\mathrm{xx...x}}}$

Сочетание

Сочетанием из n элементов по k называются подмножества содержащие k элементов из n.

$C_n^k=\frac{n\mathit{!}}{k\mathit{!}\cdot (n-k)\mathit{!}}$

Следует также упомянуть ряд полезных формул с сочетаниями:

$C_n^k=C_n^{n-k}$

$C_n^k=C_{n-\mathit{1}}^{k-\mathit{1}}+C_{n-\mathit{1}}^k$

$C_n^{\mathit{0}}+C_n^{\mathit{1}}+\mathit{...}+C_n^n={\mathit{2}}^n$

${(x+y)}^n=C_n^{\mathit{0}}\cdot x^n\cdot y^{\mathit{0}}+\mathit{...}+C_n^k\cdot x^{n-k}\cdot y^k+\mathit{...}+C_n^n\cdot x^{\mathit{0}}\cdot y^n$

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

Сочетанием с повторением называются наборы из k элементов n - элементного множества, возможно с повторяющимися элементами. Порядок элементов не учитывается.

${\stackrel{‾‾‾}{C}}_n^k=C_{\mathrm{n+k-1}}^k=\frac{(n+k-\mathit{1})\mathit{!}}{k\mathit{!}\cdot (n-k)\mathit{!}}$

Вычисление факториала и сочетаний в Python

Самостоятельная реализация:

Реализация с использованием библиотеки math:

Генерация комбинаторных списков в Python

Библиотека itertools языка Python содержит функции, позволяющие генерировать комбинаторные списки:

Далее, более детально разберем приведенные выше генераторы:

Декартово произведение (product)

Декартово произведение множества X и множества Y – это множество, содержащее все упорядоченные пары (x, y), в которых x принадлежит множеству X, а y принадлежит множеству Y.

Чтобы вычислить произведение итерируемого объекта умноженного самого на себя, в объекте product можно указать число повторений с помощью параметра repeat.

Например,  product(A, repeat=4) – тоже самое, что и product(A, A, A, A).

tertools.product(*iterables, repeat)

Перестановки (permutations)

Объект permutation возвращает последовательные перестановки элементов в итерируемом объекте. Кортежи перестановок выдаются в лексикографическим порядке в соответствии с порядком итерации входных данных. Таким образом, если входные данные итерируемого объекта отсортированы, то комбинация кортежей будет выдаваться в отсортированном порядке. Параметр r определяет вывод размещений из заданного числа элементов (None = все).

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

itertools.permutations(iterable, r=None)

Сочетания (combinations)

Объект combinations возвращает подпоследовательности длины r из элементов итерируемого объекта, подаваемого на вход.  При этом параметр r не может быть опущен.

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

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

itertools.combinations(iterable, r)

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

Объект combinations_with_replacement возвращает подпоследовательности длины r из элементов итерируемого объекта, подаваемого на вход, при этом отдельные элементы могут повторяться больше одного раза. 

itertools.combinations_with_replacement(iterable, r)

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