Подсчёт и комбинаторные тождества

$\binom {n}{k} = \binom {n}{n-k}$.

Найдите сумму $\binom {n}{0} + \ldots + \binom {n}{n}$.

Правило Паскаля. $\binom {n+1}{k+1} = \binom {n}{k+1} + \binom {n}{k}$, если $0 \leqslant k \leqslant n-1$.

\begin{Bmatrix} \end{Bmatrix} n+1 \\ k+1 \end{Bmatrix} = (k+1)\begin{Bmatrix} \end{Bmatrix} n \\ k+1 \end{Bmatrix} + \begin{Bmatrix} \end{Bmatrix} n \\ k \end{Bmatrix}. Здесь \begin{Bmatrix} \end{Bmatrix} n \\ k \end{Bmatrix} — количество разбиений $n$-элементного множества на $k$ частей (т.е. непустых подмножеств); разбиения считаются неупорядоченными, т.е. разбиение множества $\{ 1,2,3\}$ на части $\{ 1,2\}$ и $\{ 3\}$ и разбиение того же множества на части $\{ 3\}$ и $\{ 1,2\}$ считаются одинаковыми. Ср. с задачей 1.4.7(5).

Числа \begin{Bmatrix} \end{Bmatrix} n \\ k \end{Bmatrix} называются числами Стирлинга второго рода.

Во скольких подмножествах множества $\mathscr {R}_{11}$ не найдётся двух подряд идущих чисел?

То же для трёх подряд идущих чисел.

$\binom {n}{k} = \dfrac {n!}{k!(n-k)!} = \dfrac {n(n-1)\ldots (n-k+1)}{k!}$.

Бином Ньютона. $(a+b)^n = \displaystyle \sum_{j=0}^{n}\binom {n}{j}a^jb^{n-j}$.

$\binom {n}{0} - \binom {n}{1} + \ldots + (-1)^n\binom {n}{n}$;

$\binom {n}{0} + \dfrac {1}{2}\binom {n}{1} + \dfrac {1}{3}\binom {n}{2} + \ldots + \dfrac {1}{n+1}\binom {n}{n}$;

$\binom {n}{1} + 2\binom {n}{2} + 3\binom {n}{3} + \ldots + n\binom {n}{n}$;

$\binom {n}{k} + \binom {n+1}{k+1} + \ldots + \binom {n+m}{k+m}$;

$\binom {n}{0}^2 + \ldots + \binom {n}{n}^2$;

$\binom {n}{0}\binom {m}{k} + \binom {n}{1}\binom {m}{k-1} + \ldots + \binom {n}{k}\binom {m}{0}$;

$\binom {2n}{0} - \binom {2n-1}{1} + \binom {2n-2}{2} - \ldots + (-1)^n\binom {n}{n}$;

$\binom {2n}{n} + 2\binom {2n-1}{n} + 4\binom {2n-2}{n} + \ldots + 2^n\binom {n}{n}$.

Найдите $\displaystyle \sum_{k \geqslant 0}\binom {n}{2k}$.

Найдите $\displaystyle \sum_{k \geqslant 0}\binom {n}{4k}$.

Найдите $\displaystyle \sum_{k \geqslant 0}\binom {n}{3k}$.