Теорема мультинома

Формула мультинома — твердження, що узагальнює біном Ньютона на випадок довільної кількості доданків:

(x_{1} + x_{2} + \dots + x_{m})^{n} = \sum_{k_{1} + k_{2} + \dots + k_{m} = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m}^{k_{m}} .

Числа $(\binom{n}{k_{1}, k_{2}, \dots, k_{m}})$ називаються поліноміальними (мультиноміальними) коефіцієнтами.

Їх визначено для всіх цілих невід’ємних чисел $n$ і $k_{1}, k_{2}, \dots, k_{m}$ таких, що $k_{1} + k_{2} + \dots + k_{m} = n$ :

(\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) = \frac{n!}{k_{1}! k_{2}! \dots k_{m}!} = (\binom{k_{1}}{k_{1}}) (\binom{k_{1} + k_{2}}{k_{2}}) \dots (\binom{k_{1} + k_{2} + \dots + k_{m}}{k_{m}})

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

(\binom{n}{k}) = (\binom{n}{k, n - k})

.

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

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

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

(x_{1} + \dots + x_{m})^{n} = \sum_{| α | = n} (\binom{n}{α}) x^{α}

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

Доведення

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

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

Потім

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

= \sum_{k_{1} + k_{2} + \dots + k_{m - 1} + K = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m - 1}, K}) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m - 1}^{k_{m - 1}} (x_{m} + x_{m + 1})^{K}

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

= \sum_{k_{1} + k_{2} + \dots + k_{m - 1} + K = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m - 1}, K}) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m - 1}^{k_{m - 1}} \sum_{k_{m} + k_{m + 1} = K} (\binom{K}{k_{m}, k_{m + 1}}) x_{m}^{k_{m}} x_{m + 1}^{k_{m + 1}}

= \sum_{k_{1} + k_{2} + \dots + k_{m - 1} + k_{m} + k_{m + 1} = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m - 1}, k_{m}, k_{m + 1}}) x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{m - 1}^{k_{m - 1}} x_{m}^{k_{m}} x_{m + 1}^{k_{m + 1}}

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

(\binom{n}{k_{1}, k_{2}, \dots, k_{m - 1}, K}) (\binom{K}{k_{m}, k_{m + 1}}) = (\binom{n}{k_{1}, k_{2}, \dots, k_{m - 1}, k_{m}, k_{m + 1}}),

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

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

Властивості

\sum_{k_{1} + k_{2} + \dots + k_{m} = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{m}}) = m^{n}

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

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

Див. також

Джерела

Карнаух Т.О. Комбінаторика Шаблон:Недоступне посилання

Теорема мультинома

Зміст

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

Доведення

Властивості

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

Див. також

Джерела

Навігаційне меню

Теорема мультинома

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

Доведення

Властивості

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

Див. також

Джерела

Навігаційне меню

Пошук