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

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

СОДЕРЖАНИЕ

• 1 Теорема
  • 1.1 Пример
  • 1.2 Альтернативное выражение
  • 1.3 Доказательство
• 2 Полиномиальные коэффициенты
  • 2.1 Сумма всех полиномиальных коэффициентов
  • 2.2 Количество полиномиальных коэффициентов
  • 2.3 Оценка полиномиальных коэффициентов
• 3 Толкования
  • 3.1 Способы складывать предметы в мусорные ведра
  • 3.2 Количество способов выбора в соответствии с распределением
  • 3.3 Количество уникальных перестановок слов
  • 3.4 Обобщенный треугольник Паскаля
• 4 См. Также
• 5 ссылки

Теорема

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

${\ displaystyle (x_ {1} + x_ {2} + \ cdots + x_ {m}) ^ {n} = \ sum _ {k_ {1} + k_ {2} + \ cdots + k_ {m} = n } {n \ выберите k_ {1}, k_ {2}, \ ldots, k_ {m}} \ prod _ {t = 1} ^ {m} x_ {t} ^ {k_ {t}} \,,}$

куда

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

- полиномиальный коэффициент. Сумма берется по всем комбинациям неотрицательных целочисленных индексов с k 1 по k m, таким образом, что сумма всех k i равна n. То есть для каждого члена в разложении показатели степени x i должны составлять в сумме n. Кроме того, как и в случае с биномиальной теоремой, появляющиеся количества вида x ⁰ принимаются равными 1 (даже если x равен нулю).

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

Пример

Третья степень трехчлена a + b + 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 а ^ {1} Ь ^ {1} с ^ {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 \ альфа = (\ альфа _ {1}, \ альфа _ {2}, \ точки, \ альфа _ {м})}$

а также

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

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

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

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

${\ displaystyle {\ begin {align} amp; (x_ {1} + x_ {2} + \ cdots + x_ {m} + x_ {m + 1}) ^ {n} = (x_ {1} + x_ {2 } + \ cdots + (x_ {m} + x_ {m + 1})) ^ {n} \\ [6pt] = {} amp; \ sum _ {k_ {1} + k_ {2} + \ cdots + k_ {m-1} + K = n} {n \ выбрать 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 {выровнено}}}$

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

${\ displaystyle = \ sum _ {k_ {1} + k_ {2} + \ cdots + k_ {m-1} + K = n} {n \ select 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 \ выберите k_ {m}, k_ {m + 1}} x_ {m} ^ {k_ {m}} x_ {m + 1} ^ { к_ {м + 1}}}$

${\ displaystyle = \ sum _ {k_ {1} + k_ {2} + \ cdots + k_ {m-1} + k_ {m} + k_ {m + 1} = n} {n \ select 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 {п \ выбрать k_ {1}, k_ {2}, \ ldots, k_ {m-1}, K} {K \ выбрать k_ {m}, k_ {m + 1}} = {n \ выбрать 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 \ select k_ {1}, k_ {2}, \ ldots, k_ {m}}}$

в теореме фигурируют полиномиальные коэффициенты. Они могут быть выражены множеством способов, в том числе как произведение биномиальных коэффициентов или факториалов :

${\ displaystyle {n \ select 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} \ выбрать k_ {m}}}$

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

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

${\ displaystyle \ sum _ {k_ {1} + k_ {2} + \ cdots + k_ {m} = n} {n \ select 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 \ select k_ {1}, k_ {2}, \ ldots, k_ {m}} = м ^ {п}.}$

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

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

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

Подсчет легко производится методом звездочек и столбиков.

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

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

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

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

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

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

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

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

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

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

${\ displaystyle {N \ choose n_ {1}} {N-n_ {1} \ choose n_ {2}} {N-n_ {1} -n_ {2} \ choose n_ {3}} \ cdots = {\ гидроразрыв {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.}$

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

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

Полиномиальный коэффициент как произведение биномиальных коэффициентов, считая перестановки букв MISSISSIPPI.

Мультиномиальный коэффициент также число различных способов переставить с мультимножеством из п элементов, где K я это кратность каждых из I - го элемента. Например, количество различных перестановок букв слова MISSISSIPPI, которое имеет 1 M, 4 Is, 4 Ss и 2 Ps, равно ${\ displaystyle {\ binom {n} {k_ {1}, \ ldots, k_ {m}}}}$

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

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

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

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

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

использованная литература