Полиномиальная теорема - Multinomial theorem

В математика, то полиномиальная теорема описывает, как расширить мощность суммы с точки зрения полномочий членов этой суммы. Это обобщение биномиальная теорема от биномов к полиномам.

Теорема

Для любого положительного целого числа м и любое неотрицательное целое число п, полиномиальная формула говорит нам, как сумма с м термины расширяются при возведении в произвольную степень п:

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

куда

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

это полиномиальный коэффициент. Сумма берется по всем комбинациям неотрицательный целое число индексы k₁ через k_м так что сумма всех k_я является п. То есть для каждого члена в разложении показатели степени Икс_я должно составлять до п. Также, как и в случае с биномиальная теорема, количества вида Икс⁰ которые появляются, принимаются равными 1 (даже если Икс равно нулю).

В случае м = 2, это утверждение сводится к утверждению биномиальной теоремы.

Пример

Третья степень трехчлена а + б + c дан кем-то

${\displaystyle (a+b+c)^{3}=a^{3}+b^{3}+c^{3}+3a^{2}b+3a^{2}c+3b^{2}a+3b^{2}c+3c^{2}a+3c^{2}b+6abc.}$

Это можно вычислить вручную, используя распределительное свойство умножения над сложением, но это также можно сделать (возможно, более легко) с помощью полиномиальной теоремы, которая дает нам простую формулу для любого коэффициента, который нам может понадобиться. Можно "считать" полиномиальные коэффициенты из членов, используя формулу полиномиальных коэффициентов. Например:

${\displaystyle a^{2}b^{0}c^{1}}$ имеет коэффициент ${\displaystyle {3 \choose 2,0,1}={\frac {3!}{2!\cdot 0!\cdot 1!}}={\frac {6}{2\cdot 1\cdot 1}}=3.}$

${\displaystyle a^{1}b^{1}c^{1}}$ имеет коэффициент ${\displaystyle {3 \choose 1,1,1}={\frac {3!}{1!\cdot 1!\cdot 1!}}={\frac {6}{1\cdot 1\cdot 1}}=6.}$

Альтернативное выражение

Формулировку теоремы можно кратко записать, используя мультииндексы:

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

куда

${\displaystyle \alpha =(\alpha _{1},\alpha _{2},\dots ,\alpha _{m})}$

и

${\displaystyle x^{\alpha }=x_{1}^{\alpha _{1}}x_{2}^{\alpha _{2}}\cdots x_{m}^{\alpha _{m}}}$

Доказательство

Это доказательство полиномиальной теоремы использует биномиальная теорема и индукция на м.

Во-первых, для м = 1, обе стороны равны Икс₁^п так как есть только один термин k₁ = п в сумме. Для шага индукции предположим, что полиномиальная теорема верна для м. потом

${\displaystyle {\begin{aligned}&(x_{1}+x_{2}+\cdots +x_{m}+x_{m+1})^{n}=(x_{1}+x_{2}+\cdots +(x_{m}+x_{m+1}))^{n}\\[6pt]={}&\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}\end{aligned}}}$

по предположению индукции. Применяя биномиальную теорему к последнему множителю,

${\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 {n \choose k_{1},k_{2},\ldots ,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}}}$

Сумма всех полиномиальных коэффициентов

Замена Икс_я = 1 для всех я в полиномиальную теорему

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

сразу дает, что

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

Количество полиномиальных коэффициентов

Количество членов в полиномиальной сумме, #_п,м, равно количеству одночленов степени п по переменным Икс₁, …, Икс_м:

${\displaystyle \#_{n,m}={n+m-1 \choose m-1}.}$

Подсчет можно легко произвести с помощью метода звезды и решетки.

Оценка полиномиальных коэффициентов

Наибольшая степень простого числа ${\displaystyle p}$ который делит полиномиальный коэффициент, может быть вычислен с использованием обобщения Теорема Куммера.

Интерпретации

Способы складывать предметы в мусорные ведра

Полиномиальные коэффициенты имеют прямую комбинаторную интерпретацию, поскольку количество способов внесения п отдельные объекты в м отдельные бункеры, с k₁ объекты в первой корзине, k₂ объекты во второй корзине и так далее.^[1]

Количество способов выбора в зависимости от распределения

В статистическая механика и комбинаторика если имеется несколько распределений меток, то полиномиальные коэффициенты естественным образом возникают из биномиальных коэффициентов. Учитывая числовое распределение {п_я} на наборе N всего предметов, п_я представляет количество элементов, которым будет присвоена метка я. (В статистической механике я это метка состояния энергии.)

Количество аранжировок определяется по

• Выбор п₁ от общего N быть помеченным 1. Это можно сделать ${\displaystyle N \choose n_{1}}$ способами.
• Из оставшихся N − п₁ предметы выбрать п₂ на метку 2. Это можно сделать ${\displaystyle N-n_{1} \choose n_{2}}$ способами.
• Из оставшихся N − п₁ − п₂ предметы выбрать п₃ на метку 3. Опять же, это можно сделать ${\displaystyle N-n_{1}-n_{2} \choose n_{3}}$ способами.

Умножение количества вариантов на каждом шаге дает:

${\displaystyle {N \choose n_{1}}{N-n_{1} \choose n_{2}}{N-n_{1}-n_{2} \choose n_{3}}\cdots ={\frac {N!}{(N-n_{1})!n_{1}!}}\cdot {\frac {(N-n_{1})!}{(N-n_{1}-n_{2})!n_{2}!}}\cdot {\frac {(N-n_{1}-n_{2})!}{(N-n_{1}-n_{2}-n_{3})!n_{3}!}}\cdots .}$

После отмены мы приходим к формуле, приведенной во введении.

Количество уникальных перестановок слов

Мультиномиальный коэффициент - это также количество различных способов переставлять а мультимножество из п элементы и k_я являются множественность каждого из отдельных элементов. Например, количество различных перестановок букв слова MISSISSIPPI, которое имеет 1 M, 4 Is, 4 Ss и 2 Ps, равно

${\displaystyle {11 \choose 1,4,4,2}={\frac {11!}{1!\,4!\,4!\,2!}}=34650.}$

(Это все равно что сказать, что существует 11! Способов переставлять буквы - обычное толкование факториал как количество уникальных перестановок. Однако мы создали повторяющиеся перестановки, потому что некоторые буквы совпадают и должны разделиться, чтобы исправить наш ответ.)

Обобщенный треугольник Паскаля

Можно использовать полиномиальную теорему для обобщения Треугольник Паскаля или же Пирамида паскаля к Симплекс Паскаля. Это обеспечивает быстрый способ создания таблицы поиска для полиномиальных коэффициентов.

Смотрите также

• Мультиномиальное распределение
• Звезды и стержни (комбинаторика)

Рекомендации

1. Национальный институт стандартов и технологий (11 мая 2010 г.). «Электронная библиотека математических функций NIST». Раздел 26.4. Получено 30 августа, 2010.