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

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

Теорема

Для любого положительного целого числа $m$ и любого неотрицательного целого числа $n$ полиномиальная теорема описывает, как сумма с $m$ членами расширяется при возведении в $n$ -ю степень: $(x_{1}+x_{2}+\cdots +x_{m})^{n}=\sum _{\begin{array}{c}k_{1}+k_{2}+\cdots +k_{m}=n\\k_{1},k_{2},\cdots ,k_{m}\geq 0\end{array}}{n \choose k_{1},k_{2},\ldots ,k_{m}}x_{1}^{k_{1}}\cdot x_{2}^{k_{2}}\cdots x_{m}^{k_{m}}$ где ${n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}$ является полиномиальным коэффициентом . Сумма берется по всем комбинациям неотрицательных целочисленных индексов $от k 1$ до $km,$ таких, что сумма всех $k i$ равна $n$ . То есть для каждого члена разложения показатели степени $x i$ должны в сумме составлять $n$ . ^[1]^[а]

В случае $m = 2$ это утверждение сводится к утверждению биномиальной теоремы . ^[1]

Пример

Третья степень трехчлена $a + b + c$ определяется выражением $(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.$ Это можно вычислить вручную, используя распределительное свойство умножения на сложение и объединение подобных членов, но это также можно сделать (возможно, более легко) с помощью полиномиальной теоремы. Можно «считать» полиномиальные коэффициенты из термов, используя формулу полиномиальных коэффициентов. Например, $a^{2}b^{0}c^{1}$ имеет коэффициент ${3 \choose 2,0,1}={\frac {3!}{2!\cdot 0!\cdot 1!}}={\frac {6}{2\cdot 1\cdot 1}}=3$ , $a^{1}b^{1}c^{1}$ имеет коэффициент ${3 \choose 1,1,1}={\frac {3!}{1!\cdot 1!\cdot 1!}}={\frac {6}{1\cdot 1\cdot 1}}=6$ , и так далее.

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

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

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

где

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

и

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

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

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

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

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

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

=\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}!}}.

Полиномиальные коэффициенты

Числа

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

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

Подстановка $x i = 1$ для всех $i$ в полиномиальную теорему

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

дает сразу это

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

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

Количество членов в полиномиальной сумме $# n, m$ равно количеству мономов степени $n$ от переменных $x 1, \dots, x m$ :

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

Подсчет можно легко выполнить, используя метод звезд и полос .

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

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

Асимптотика

В соответствии с приближением Стирлинга или, что эквивалентно, лог-гамма-функции , асимптотическим разложением $\log {\binom {kn}{n,n,\cdots ,n}}=kn\log(k)+{\frac {1}{2}}\left(\log(k)-(k-1)\log(2\pi n)\right)-{\frac {k^{2}-1}{12kn}}+{\frac {k^{4}-1}{360k^{3}n^{3}}}-{\frac {k^{6}-1}{1260k^{5}n^{5}}}+O\left({\frac {1}{n^{6}}}\right)$ так, например, ${\binom {2n}{n}}\sim {\frac {2^{2n}}{\sqrt {n\pi }}}$

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

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

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

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

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

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

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

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

{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 .

Отмена приводит к формуле, приведенной выше.

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

Полиномиальный коэффициент

{\binom {n}{k_{1},\ldots ,k_{m}}}

— это также количество различных способов перестановки мультимножества из элементов $n$ , где $k i$ — кратность каждого $i-$ го элемента. Например, количество различных перестановок букв слова MISSISSIPPI, в котором 1 M, 4 Is, 4 Ss и 2 Ps, равно

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

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

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

См. также

Ссылки

^ Как и в случае с биномиальной теоремой , величины вида $x 0$ которые появляются, принимаются равными 1, даже когда $x$ равен нулю .

^ Перейти обратно: ^а ^б Стэнли, Ричард (2012), Перечислительная комбинаторика , том. 1 (2-е изд.), Издательство Кембриджского университета, §1.2
^ Национальный институт стандартов и технологий (11 мая 2010 г.). «Цифровая библиотека математических функций NIST» . Раздел 26.4 . Проверено 30 августа 2010 г.

[2] Как и в случае с биномиальной теоремой , величины вида $x 0$ которые появляются, принимаются равными 1, даже когда $x$ равен нулю .

[EC1-1] Перейти обратно: ^а ^б Стэнли, Ричард (2012), Перечислительная комбинаторика , том. 1 (2-е изд.), Издательство Кембриджского университета, §1.2

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

[1]

[а]

[2]