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

Основые формулы и обозначения

$K$-сочетания без повторений

$ C^k_n = \frac{A^k_n}{k!} = \frac{n!}{k!(n-k)!} $

Произносится как "$C$ из $ n $ по $k$", иностранное обозначение как $\begin{pmatrix} n \\ k \end{pmatrix}$ "n choose k"

$K$-размещения без повторений

$ A^k_n=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!} $

"$A$ из $ n $ по $k$"

$K$-сочетания с повторениями

$ \overline{C^k_n} = C^k_{n+k-1} $

"$C$ из $ n $ по $k$ с чертой"

$K$-размещения с повторениями

$ \overline{A^k_n}=n^k $

"$A$ из $ n $ по $k$ с чертой"

Бином Ньютона

$(x+y)^n = C^0_n x^n y^0 + C^1_{n-1} x^{n-1} y^1 + \dots + C^n_n x^0 y^n $

Тождества с участием биномиальных коэффициентов

  1. $ C^k_n = C^{n-k}_n $
  2. $ C^k_n = C^k_{n-1} + C^{k+1}_{n-1} $
  3. $ C^0_n + C^1_n + \dots + C^n_n = 2^n $
  4. $ (C^0_n)^2 + (C^1_n)^2 + \dots + (C^n_n)^2 = C^n_{2n} $
  5. $ C^{n-1}_{n+m-1} + C^{n-1}_{n+m-2} + \dots + C^{n-1}_{n-1} = C^{n-1}_{n+m} $
  6. $ C^0_n - C^1_n + C^2_n + \dots + (-1)^n(C^n_n) = \begin{cases} 1, & если & n=0 \
    0, & если & n \ge 0 \end{cases} $

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

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

Например, может применятся для подсчета перестановок букв в слове.

Полиномиальная формула в общем виде

$$ (x_1 + x_2 + ... + x_k)^n = \sum_{(n_1,...,n_k): n_i \ge 0, n_1+...n_k=n} P(n_1, ... , n_k) x_1^{n_1} , ... , x_k^{n_k} $$

Формула включений и исключений

$$ N(\alpha_{1}^{'},...,\alpha_{n}^{'}) = N - N(\alpha_{1}) - ... - N(\alpha_{n}) + N(\alpha_{1},\alpha_{2}) + ... + N(\alpha_{n-1},\alpha_{n}) + ... + (-1)^n N(\alpha_{1},...,\alpha_{n}) $$

$ \alpha $ свойство $ \alpha^{'} $ исключающее свойство $ N(\alpha_{n-1},\alpha_{n}) = C_n^2 $

$$ \sum_{k=0}^{n} (-1)^k C_n^k (n-k)^m = 0 $$

Читать...