Мультиномиальная формула Ньютона

[math]\displaystyle{ (x_1 + x_2 + ... + x_k)^m = \sum_{\substack{(\alpha_1, ..., \alpha_k), alpha_1+\alpha_2 + ... + \alpha_k=m, \alpha_i\in\mathbb{N}_0, i=\overline{1,k} }} \frac{m!}{\alpha_1!\alpha_2!...\alpha_k!} x_1^{\alpha_1} x_2^{\alpha_2} ... x_k^{\alpha_k}. }[/math]

Докажем по индукции. Для $k=2$ утверждение верно в силу формулы бинома Ньютона. Действительно, $\sum_{\substack{(\alpha_1,\alpha_2), \alpha_1+\alpha_2 =n, \alpha_1, \alpha_2\in\mathbb{N}_0 }} \frac{n!}{\alpha_1!\alpha_2!} a^{\alpha_1} b^{\alpha_2} = \sum_{\substack{k\in \{0,...,n\}, \alpha_1=k, \alpha_2 = n-k }} \binom{n}{\alpha_1} a^{\alpha_1} b^{\alpha_2} = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k} = (a+b)^n. $

Пусть утверждение верно для всех $k\leq K$ для любых $m$.

Пусть теперь $k=K+1$. $(x_1 + x_2 + ... + x_K + x_{K+1})^m = ((x_1 + ... + x_K) + x_{K+1})^m =$

по индукционному предположению

$\sum_{\substack{\alpha+\beta = m,\\ \alpha, \beta\in\mathbb{N}_0}} \frac{m!}{\alpha!\beta!} (x_1 + ... + x_K)^\alpha x_{K+1}^{\beta} = $

$\sum_{\substack{\alpha+\beta = m,\\ \alpha, \beta\in\mathbb{N}_0}} \frac{m!}{\alpha!\beta!} x_{K+1}^{\beta} \sum_{\substack{(\alpha_1, ..., \alpha_K), \alpha_1+\alpha_2 + ... + \alpha_K=\alpha, \alpha_i\in\mathbb{N}_0, i=\overline{1,K} }} \frac{\alpha!}{\alpha_1!\alpha_2!...\alpha_K!} x_1^{\alpha_1} x_2^{\alpha_2} ... x_K^{\alpha_K}=$

$= \sum_{\substack{(\alpha_1, ..., \alpha_K, \beta), \alpha_1+\alpha_2 + ... + \alpha_K+\beta=m, \alpha_i\in\mathbb{N}_0, i=\overline{1,K}, \beta\in\mathbb{N}_0 }} \frac{m!}{\alpha_1!\alpha_2!...\alpha_K!\beta!} x_1^{\alpha_1} x_2^{\alpha_2} ... x_K^{\alpha_K} x_{K+1}^{\beta}$.

Что и требовалось доказать.

Рис. 1. Коэффициент при [math]\displaystyle{ x^2y }[/math] равен [math]\displaystyle{ 3!/(2!1!)=3 }[/math]: слово из двух [math]\displaystyle{ x }[/math] и одного [math]\displaystyle{ y }[/math] имеет три порядка. Коэффициент при [math]\displaystyle{ xyz }[/math] равен [math]\displaystyle{ 3!/(1!1!1!)=6 }[/math] — все перестановки трёх разных букв.

Легко доказать следующее свойство мультиномиальных коэффициентов:

Следствие:

Пусть $m\in\mathbb{N}_0$. [math]\displaystyle{ \sum_{\substack{(\alpha_1, ..., \alpha_k),\\ \alpha_1+\alpha_2 + ... + \alpha_k=m,\\ \alpha_i\in\mathbb{N}_0, i=\overline{1,k} }} \binom{m}{\alpha_1, \alpha_2, ..., \alpha_k} = k^m }[/math]

Следует из утверждения для мультиномиальной формулы Ньютона при подстановке $x_i = 1$, $i=\overline{1,k}$.

Конспект: Дискретная математика