Комбинаторика: формулы

Комбинаторика считает, сколькими способами можно выбрать или расставить элементы. Сначала решают, важен ли порядок и можно ли повторять элементы.

Подходит для: ЕГЭ профиль, ОГЭ. Раздел: вероятность.

• $$N=n_1\cdot n_2\cdot\ldots\cdot n_k$$правило произведения: первый выбор можно сделать $n_1$ способами, второй — $n_2$ и т. д.
• $$N=n_1+n_2$$правило суммы: объект выбирают из одного из двух непересекающихся наборов
• $$n!=1\cdot2\cdot3\cdot\ldots\cdot n,\quad 0!=1,\quad 1!=1$$факториал
• $$n!=n\cdot(n-1)!$$рекуррентное свойство факториала
• $$P_n=n!$$перестановки: число способов расставить $n$ различных элементов в ряд
• $$A_n^k=\dfrac{n!}{(n-k)!}=n(n-1)\ldots(n-k+1)$$размещения: выбор $k$ из $n$, порядок важен
• $$C_n^k=\dfrac{n!}{k!\,(n-k)!}$$сочетания: выбор $k$ из $n$, порядок не важен
• $$C_n^k=\dfrac{A_n^k}{P_k}$$связь сочетаний и размещений
• $$C_n^k=C_n^{n-k}$$симметрия сочетаний
• $$C_n^0=C_n^n=1,\quad C_n^1=n$$частные случаи
• $$C_n^k=C_{n-1}^{k-1}+C_{n-1}^{k}$$правило Паскаля: каждое число треугольника Паскаля равно сумме двух над ним
• $$C_n^0+C_n^1+\ldots+C_n^n=2^n$$сумма строки треугольника Паскаля равна числу всех подмножеств $n$-элементного множества
• $$n^k$$размещения с повторениями: $k$ мест, на каждое — один из $n$ вариантов
• $$\dfrac{n!}{n_1!\,n_2!\ldots n_m!}$$перестановки с повторениями: слово из $n$ букв, буква $i$ встречается $n_i$ раз
• $$(a+b)^n=\sum\limits_{k=0}^{n}C_n^k\,a^{n-k}b^k$$бином Ньютона ЕГЭ профиль
• $$T_{k+1}=C_n^k\,a^{n-k}b^k$$общий член разложения бинома ЕГЭ профиль
• $$(n-1)!$$число способов рассадить $n$ человек за круглым столом (повороты не различаются) ЕГЭ профиль
• $$C_n^2=\dfrac{n(n-1)}{2}$$число рукопожатий (пар, отрезков, матчей «каждый с каждым») в группе из $n$ человек