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

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

(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}

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

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

Див. також

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

Посилання

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.