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

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

${\displaystyle (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}}.}$

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

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

${\displaystyle {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}}}$

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

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

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

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

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

${\displaystyle (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 в сумі.  Для кроку індукції, припустимо що поліноміальна теорема вірна для т. 

Потім

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

${\displaystyle =\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}}$

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

${\displaystyle =\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}}}$

${\displaystyle =\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}}}$

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

${\displaystyle {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}},}$

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

${\displaystyle {\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}!}}.}$

Властивості

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

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

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

Див. також

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

Посилання

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