重複組合せの母関数

重複組合せの母関数は次式で表されます。$$\left(\displaystyle\sum_{k=0}^{\infty}x^k\right)^n=\displaystyle\sum_{m=0}^{\infty} {}_n\mathrm{H}_m x^m$$シグマを用いない場合$$(1+x+x^2+x^3+ \cdots )^n={}_n\mathrm{H}_0+{}_n\mathrm{H}_1 x+{}_n\mathrm{H}_2 x^2+{}_n\mathrm{H}_3 x^3+{}_n\mathrm{H}_4 x^4+ \cdots$$「(何回か)微分して \(0\) を代入」すれば \({}_n\mathrm{H}_m\,(m=0,1,2,3, \cdots)\) が
得られることが確認できます。











<証明(考え方)>

\(n=3\) の場合を考えてみます。すなわち$$\left(\displaystyle\sum_{k=0}^{\infty}x^k\right)^3=(1+x+x^2+x^3+x^4+ \cdots )^3$$右辺を展開したときの各 \(x\) の次数における係数を調べます。

次のように \(x\) の次数に着目します。
\begin{alignat}{2}
&  (1+x+x^2+x^3+x^4+ \cdots )^3\\
&\\
&=(1+x+x^2+x^3+ \cdots )(1+x+x^2+x^3+ \cdots )^3(1+x+x^2+x^3+ \cdots )\\
&\\
&=(x^0+x^1+x^2+x^3+ \cdots )(x^0+x^1+x^2+x^3+ \cdots )(x^0+x^1+x^2+x^3+ \cdots )\\
\end{alignat}下図のように、それぞれの括弧内の多項式を \(A,B,C\) グループとします。


\((α)\) \(x\) の \(0\) 次の係数(定数項)は

\(A\) のグループから「\(x^0\)」、\(B\) のグループから「\(x^0\)」,\(C\) のグループから「\(x^0\)」を取ればよく、

これを \((A,B,C)=(0,0,0)\) とします。(右の数字は \(x\) の次数を表します。)

よって \(1\) 通りであるので \(x\) の \(0\) 乗の係数は \(1\) です。



\((β)\) \(x\) の \(1\) 次の係数は

\(A,B,C\) のいずれかのグループから「\(x^1\)」を取ればよく

その場合の数は \((A,B,C)=(1,0,0),(0,1,0),(0,0,1)\) の \(3\) 通りであるので

\(x\) の \(1\) 乗の係数は \(3\) です。



\((γ)\) \(x\) の \(2\) 次の係数は

\(A,B,C\) のいずれかのグループから「\(x^2\)」を取る。

または \(A,B,C\) のいずれかの \(2\) つのグループから「\(x^1\)」を取ればよく

その場合の数は

\((A,B,C)=(2,0,0),(0,2,0),(0,2,0),(1,1,0),(1,0,1),(0,1,1)\) の \(6\) 通りであるので

\(x\) の \(2\) 乗の係数は \(6\) です。




\((δ)\) \(x\) の \(3\) 次の係数は

上記同様に考えれば \((A,B,C)=(3,0,0),(2,1,0),(2,0,1),(1,2,0),(1,1,1),(1,0,2)\)

\((0,3,0),(0,2,1),(0,1,2),(0,0,3)\) の \(10\) 通りあるので

\(x\) の \(3\) 乗の係数は \(10\) です。




…と続けることが出来ますが、これら場合の数は「重複組合せ」であることが分かるので

もう一度 \((α)\) から \((δ)\) までを \({}_n\mathrm{H}_m\) の式を用いて書いてみます。

\((α)\) \(3\) 種類 (\(A,B,C\)) のうちから重複を許して \(0\) 個選ぶ。 \({}_3\mathrm{H}_0={}_2\mathrm{C}_0=1\) 通り

\((β)\) \(3\) 種類 (\(A,B,C\)) のうちから重複を許して \(1\) 個選ぶ。 \({}_3\mathrm{H}_1={}_3\mathrm{C}_1=3\) 通り

\((γ)\) \(3\) 種類 (\(A,B,C\)) のうちから重複を許して \(2\) 個選ぶ。 \({}_3\mathrm{H}_2={}_4\mathrm{C}_2=6\) 通り

\((δ)\) \(3\) 種類 (\(A,B,C\)) のうちから重複を許して \(3\) 個選ぶ。 \({}_3\mathrm{H}_3={}_5\mathrm{C}_3=10\) 通り

            \(\cdots\)





よって \((1+x+x^2+x^3+x^4+ \cdots)^3\) を展開した結果は$$(1+x+x^2+x^3+ \cdots )^3={}_3\mathrm{H}_0+{}_3\mathrm{H}_1x+{}_3\mathrm{H}_3x^2+{}_3\mathrm{H}_3 x^3+{}_3\mathrm{H}_4x^4+ \cdots $$

同様の考え方で左辺を \(n\) 乗にすることで、「重複組合せの母関数」を得ます。$$(1+x+x^2+x^3+ \cdots )^n={}_n\mathrm{H}_0+{}_n\mathrm{H}_1x+{}_n\mathrm{H}_3x^2+{}_n\mathrm{H}_3 x^3+{}_n\mathrm{H}_4x^4+ \cdots$$以上より$$\left(\displaystyle\sum_{k=0}^{\infty}x^k\right)^n=\displaystyle\sum_{m=0}^{\infty} {}_n\mathrm{H}_m x^m$$


















コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です