Поліноміальна теорема

Поліноміальна теорема - це узагальнення бінома Ньютона:

$(x_{1}+x_{2}+\dots +x_{m})^{n}=\sum _{k_{1}+k_{2}+\dots +k_{m}=n}{n \choose k_{1},\ k_{2},\ \dots ,\ k_{m}}x_{1}^{k_{1}}x_{2}^{k_{2}}\dots x_{m}^{k_{m}}.$

Числа ${n \choose k_{1},\ k_{2},\ \dots ,\ k_{m}}$ називаються поліноміальними (мультиноміальними) коефіцієнтами. Їх визначено для всіх цілих невід’ємних чисел $n$ і $k_{1},k_{2},\dots ,k_{m}$ таких, що $k_{1}+k_{2}+\dots +k_{m}=n$:

${n \choose k_{1},\ k_{2},\ \dots ,\ k_{m}}={\frac {n!}{k_{1}!k_{2}!\dots k_{m}!}}$.

${n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}={k_{1} \choose k_{1}}{k_{1}+k_{2} \choose k_{2}}\cdots {k_{1}+k_{2}+\cdots +k_{m} \choose k_{m}}$

Біноміальний коефіцієнт ${n \choose k}$ для невід’ємних $n,k$ є частковим випадком мультиноміального коефіцієнта (для $m=2$), а саме

${n \choose k}={n \choose k,\ n-k}$.

В комбінаторному сенсі мультиноміальний коефіцієнт ${n \choose k_{1},\ k_{2},\ \dots ,\ k_{m}}$ дорівнює числу впорядкованих розбиттів $n$-елементарної множини на $m$ підмножини потужностей $k_{1},k_{2},\dots ,k_{m}$.

Альтернативне формулювання

Формулювання теореми можна записати в стислій формі використовуючи мультиіндекси:

$(x_{1}+\cdots +x_{m})^{n}=\sum _{|\alpha |=n}{n \choose \alpha }x^{\alpha }$

де α = (α₁,α₂,…,α_m) and x^α = x₁^α₁x₂^α₂⋯x_m^α_m.

Доведення

Це доведення теореми з використанням біному Ньютона і математичної індукції по m.

Спочатку для m = 1, дві сторони рівності рівні x₁ⁿ так як існує тільки один член k₁ = n в сумі.  Для кроку індукції, припустимо що поліноміальна теорема вірна для т. 

Потім

$(x_{1}+x_{2}+\cdots +x_{m}+x_{m+1})^{n}=(x_{1}+x_{2}+\cdots +(x_{m}+x_{m+1}))^{n}$

$=\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+K=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},K}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}(x_{m}+x_{m+1})^{K}$

ідучи за припущенням індукції. Застосовуючи біном до останнього фактору,

$=\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+K=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},K}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}\sum _{k_{m}+k_{m+1}=K}{K \choose k_{m},k_{m+1}}x_{m}^{k_{m}}x_{m+1}^{k_{m+1}}$

$=\sum _{k_{1}+k_{2}+\cdots +k_{m-1}+k_{m}+k_{m+1}=n}{n \choose k_{1},k_{2},\ldots ,k_{m-1},k_{m},k_{m+1}}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m-1}^{k_{m-1}}x_{m}^{k_{m}}x_{m+1}^{k_{m+1}}$

який завершує індукцію. Останній крок випливає з цього:

${n \choose k_{1},k_{2},\ldots ,k_{m-1},K}{K \choose k_{m},k_{m+1}}={n \choose k_{1},k_{2},\ldots ,k_{m-1},k_{m},k_{m+1}},$

в цьому легко переконатися записавши три коефіцієнти з використанням факторіалів наступним чином:

${\frac {n!}{k_{1}!k_{2}!\cdots k_{m-1}!K!}}{\frac {K!}{k_{m}!k_{m+1}!}}={\frac {n!}{k_{1}!k_{2}!\cdots k_{m+1}!}}.$

Властивості

$\sum _{k_{1}+k_{2}+\dots +k_{m}=n}{n \choose k_{1},\ k_{2},\ \dots ,\ k_{m}}=m^{n}$

Узагальнений трикутник Паскаля

Можна використовувати поліноміальну теорему для узагальнення трикутника Паскаля або піраміди Паскаля до симплекса Паскаля. Це забезпечує швидкий спосіб створення таблиці підстановки для поліноміальних коефіцієнтів.

Див. також

• Мультиноміальний розподіл

Посилання

1. Карнаух Т.О. Комбінаторика^{[недоступне посилання з липня 2019]}