Полиномиальные коэффициенты

Материал из Algocode wiki
Перейти к: навигация, поиск

Посчитаем теперь количество разбиений множества на $m$ множеств размеров $k_1,k_2\ldots,k_m$. Это называется полиномиальные коэффициенты и обозначается $C(k_1,k_2,\ldots,k_m)$ Будем набирать эти множества по очереди. Количество способов выбрать первое подмножесто равно $C_n^{k_1}$, второе $C_{n-k_1}^{k_2}$ и так далее. Итоговая формула $C(k_1,k_2,\ldots,k_m)=C_n^{k_1}\cdot C_{n-k_1}^{k_2}\cdots C_{k_m}^{k_m}=\frac{n!}{k_1!k_2!\cdots k_m!}$.

Аналогично биному Ньютона, такие числа являются коэффициентами при членах $x_1^{k_1}x_2^{k_2}\cdots x_m^{k_m}$ выражения $(x_1+\ldots+x_m)^n$. Доказательство тоже аналогично доказательству из предыдущего раздела и оставляется в качестве упражнения.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin