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

Казаков Г.В., Сидоров Р.А.

Размещение

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

Детали

Размещение — это позиционно-зависимое расположение.

Пример: имеется $k$ человек и $n$ мест. Сколько существует способов разместить людей по местам?

\[\begin{equation} A_n^k = \frac{n!}{(n-k)!} \end{equation}\]

Детали

У нас есть $k$ предметов и $n$ свободных мест. Тогда разместить первый предмет мы сможем $n$ способами, второй: $n-1$, третий: $n-2$, … $k$-й: $n-k+1$. Получаем $N = n(n-1)(n-2)\cdot...\cdot(n-k+1)$; для удобства эту формулу представляют в виде $\frac{n!}{(n-k)!}$.

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

Размещение с повторениями (англ. arrangement with repetitions), из $n$ элементов по $k$ — отображение множества $k$ первых натуральных чисел $1,2,...,k$ в данное множество ${a_1,a_2,...,a_n}$.

Детали

Пример: имеется n книг, каждая в k экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?

Число размещений с повторениями из $n$ по $k$

\[\begin{equation} \bar{A}_n^k = nk \end{equation}\]

Сочетание

Число сочетаний (позиционно-независимое расположение) из $n$ по $k$

\[\begin{equation} C_n^k = \frac{n!}{(n-k)!k!} \end{equation}\]

Детали

Отличие размещения от сочетания в том, что элементы сочетания позиционно-независимы т.е., если мы поменяем любые из элементов местами, это будет тот же способ, что и прежде. Количество способов перестановки $k$ элементов между собой равно $k!$, отсюда и получаем формулу $\frac{n!}{(n-k)!k!}$

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

Перестановка (англ. permutation) — упорядоченный набор чисел $1,2,\dots,n$, представляющий собой биекцию на множестве $\{1,2,\dots,n\}$, которая числу $i$ ставит в соответствие $i$-й элемент из набора.

Детали

Пример: имеется $n$ книг. Сколько существует способов переставить книги на полке?

\[\begin{equation} P_n = n! \end{equation}\]

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

Перестановка с повторениями (англ. permutation with repetitions) — те же перестановки, но некоторые элементы могут встречаться несколько раз.

Детали

Пример: имеется набор книг ${a_1,a_2,...,a_n}$, каждая из которых имеется в $k_1,k_2,...,k_n$ экземплярах соответственно. Сколько существует способов переставить книги на полке?

\[\begin{equation} \bar{P}_n = \frac{(k_1+k_2+...+k_n)!}{k_1!k_2!...k_n!} \end{equation}\]

Детали

\[\begin{align} &P_{[ABC]} &&=&& (1+1+1)! = 6 && [ABC], [ACB], [BAC], [BCA], [CAB], [CBA]\\ &P_{[AAB]} &&=&& \frac{(2+1)!}{2!1!} = 3 && [AAB], [ABA], [BAA]\\ &P_{[AAA]} &&=&& \frac{3!}{3!} = 1 && [AAA]\\ \end{align}\]

После 66% остался $S_2U$ $⇒$ остался $[SSU]$, $[USS]$ или $[SUS]$.

для типового состава (соответствует разложению бинома):
$[S_2U] = [SSU] + [USS] + [SUS] = 3 * [S]^2 * [U]$
$[SU_2] = [SUU] + [UUS] + [USU] = 3 * [S] * [U]^2$
остальные значения не отличаются от значений стерео-типового и позиционно-типового составов:
$[S_3] = [S]^3$
$[U_3] = [U]^3$

Calculation

$3[A] = 2[A]_{13} + [A]_2${0248e842}

Триглицерины (Triglycerides)

\[\begin{equation} \mathbb{A} = \{ a_1, a_2, \dots, a_n \} \end{equation}\]

Где

$\mathbb{A}$ — множество, представляющее виды $FA$;
$n$ — количество элементов множества $\mathbb{A}$;
$a_i$ — i-й элемент множества $\mathbb{A}$.

\[\begin{equation} \mathbb{S} = \{ s_1, s_2, \dots, s_{n_\mathbb{S}} \} \end{equation}\]

Где

$\mathbb{S}$ — подмножество множества $\mathbb{A}$, представляющее только насыщенные $FA$;
$n_\mathbb{S}$ — количество элементов множества $\mathbb{S}$.

\[\begin{equation} \mathbb{U} = \{ u_1, u_2, \dots, u_{n_\mathbb{U}} \} \end{equation}\]

Где

$\mathbb{U}$ — подмножество множества $\mathbb{A}$, представляющее только ненасыщенные $FA$;
$n_\mathbb{U}$ — количество элементов множества $\mathbb{U}$.

\[\begin{equation} \mathbb{T} = \{ S, U \} \end{equation}\]

Где

$\mathbb{T}$ — множество из двух элементов, представляющее типы элементов множества $\mathbb{A}$.

Трехэлементное размещение $\{ a_{1}, a_{2}, a_{3} \}$