多項式定理

数学において、多項式定理は、和のべき乗をその和を構成する項のべき乗で展開する方法を記述する。これは、二項式定理を二項式から多項式へと一般化したものである。

定理

任意の正の整数 $m$ と任意の非負整数 $n$ について、多項式定理は、 $m項の和を$ $n$ 乗するとどのように展開するかを記述する。ここで、は多項式係数である。^{[1]この和は、すべての} $k$ $i$ の和が $n$ となるような、非負整数の添え字 $k$ $1$ から $k$ $m$ までのすべての組み合わせについてとられる。つまり、展開の各項について、 $x$ $i$ の指数は必ず $n$ となる。^[2]^[a] $(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}!}}$

$m = 2$ の場合、この記述は二項定理の記述に帰着する。^[2]

例

$三項式a + b + c$ の3乗は次のように表されます。これは、加法に対する乗法の分配法則と同類項の結合を用いて手計算で計算できますが、多項式定理を用いて（おそらくより簡単に）行うこともできます。多項式係数の公式を用いることで、項から多項式係数を「読み取る」ことが可能です。例えば、項の係数は、項の係数は、といった具合です。 $(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$ の場合、和には $k$ $1$ $=$ $n$ となる項が1つだけあるため、両辺は $x 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}},

次のように 3 つの係数を階乗で表すと簡単にわかります。

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

すべての多項式係数の合計

多項式定理にすべての $iについて$ $x i = 1$ を代入すると、

\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$ は、変数 $x$ $1$ $, \dots,$ $x$ $m$ $のn$ 次単項式の数に等しい。

\#_{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個の$ 異なるビンに配置する方法の数として、直接的な組み合わせ論的解釈が可能です。最初のビンには $k1 個のオブジェクト、$ $2番目のビンには$ $k2$ 個のオブジェクト、というように配置します。^[3]

分布に従って選択する方法の数

統計力学と組合せ論において、ラベルの数分布が与えられれば、多項式係数は二項式係数から自然に導かれます。N個のアイテムの集合における数分布{n i }が与えられた場合 $、$ n i $はラベル i が$ $付与$ $さ$ れるアイテムの数を表します $。$ （統計力学において、 $i$ はエネルギー状態のラベルです。）

配置の数は次のように求められる。

合計 $N 個のうち$ $n 1 個$ を選択して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という単語には、Mが1個、Iが4個、Sが4個、Pが2個あるが、その文字の異なる並べ替えの数は、

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

一般化されたパスカルの三角形

多項式定理を用いると、パスカルの三角形またはパスカルのピラミッドをパスカルの単体に一般化することができます。これにより、多項式係数のルックアップテーブルを迅速に生成できます。

関連する構造として、多項式三角形、あるいはm次の一般化パスカル三角形があり、これは漸化式: を用いて構築することができる。この関係からパスカルの法則がのときに得られる。これらの多項式係数は、有界整数合成を持つ閉形式式として表すことができる。 ${\binom {n}{k}}_{m-1}=\sum _{i=0}^{m-1}{\binom {n-1}{k-i}}_{m-1}$ $m=2$

${\binom {n}{k}}_{m-1}=\sum _{\begin{array}{c}k_{0}+k_{1}+\cdots +k_{m-1}=n\\k_{1}+2k_{2}+\cdots +(m-1)k_{m-1}=k\end{array}}{n \choose k_{0},k_{1},\ldots ,k_{m-1}}$ なし：^[4]（OEISの配列A008287）

${\binom {n}{k}}_{m-1}=\sum _{i=0}^{\lfloor k/m\rfloor }(-1)^{i}{\binom {n}{i}}{\binom {n-1+k-im}{n-1}}$

参照

参考文献

^ 二項定理と同様に $、 x$ $0$ の形式の量は $、 x が$ 0 の場合でも1 とみなされます。

^ Aigner, Martin (1997)、組合せ理論、Springer、p. 77
^ ab スタンレー、リチャード（2012）、列挙的組合せ論、第1巻（第2版）、ケンブリッジ大学出版局、§1.2
^ 米国国立標準技術研究所(2010年5月11日). 「NISTデジタル数学関数ライブラリ」. 第26.4節. 2010年8月30日閲覧。
^ Belbachir, H.; Bouroubi, S.; Khelladi, A. (2008)「通常の多項式、フィボナッチ数、ベル多項式、離散一様分布の関係」、Annales Mathematicae et Informaticae、35 :24 https://arxiv.org/abs/0708.2195