組み合わせ論と母関数１：べき乗和、基本対称式、完全斉次式
べき乗和、基本対称式、完全斉次式
文字の集合$S={a,b,c,d,e,~..}$に対し、べき乗和、基本対称式、完全斉次式を以下のように定義します。これから述べることは$S$の要素数が有限のときも無限のときも成り立ちます。
文字の$k$乗の和を$k$次のべき乗和といい$p_k$と表す。
$$
p_k = \sum_j a_j^k
$$
例
\begin{eqnarray} p_1 &=& a & ~+~ & b & ~+~ & c & ~+~ & d & ~+~ & .. \\ p_2 &=& a^2 & ~+~ & b^2 & ~+~ & c^2 & ~+~ & d^2 & ~+~ & .. \\ p_3 &=& a^3 & ~+~ & b^3 & ~+~ & c^3 & ~+~ & d^3 & ~+~ & .. \\ ..\end{eqnarray}
異なるk個の文字からなる項の和を$k$次の基本対称式と呼び$s_k$と表す。
$$
s_k = \sum_{j_1< j_2<..< j_k}a_{j_1}a_{j_2}~..a_{j_k}
$$
例
\begin{eqnarray} s_1 = a & ~+~ & b & ~+~ & c & ~+~ & d & ~+~ & .. \\ \end{eqnarray}\begin{eqnarray} s_2 =a b & ~+~ & a c & ~+~ & a d & ~+~ & a e & ~+~ & a f & ~+~ & .. \\ & ~+~ & b c & ~+~ & b d & ~+~ & b e & ~+~ & b f & ~+~ & .. \\ & & & ~+~ & c d & ~+~ & c e & ~+~ & c f & ~+~ & .. \\ & & & & & ~+~ & d e & ~+~ & d f & ~+~ & .. \\ & & & & & & & ~+~ & e f & ~+~ & .. \\ \end{eqnarray}\begin{eqnarray} s_3 = a b c & ~+~ & a b d & ~+~ & a b e & ~+~ & a b f & ~+~ & a b g & ~+~ & .. \\ & & a c d & ~+~ & a c e & ~+~ & a c f & ~+~ & a c g & ~+~ & .. \\ & & & ~+~ & a d e & ~+~ & a d f & ~+~ & a d g & ~+~ & .. \\ & & & & & ~+~ & a e f & ~+~ & a e g & ~+~ & .. \\ & & & & & & & ~+~ & a f g & ~+~ & .. \\ & & & & & & & & & & \\ & ~+~ & b c d & ~+~ & b c e & ~+~ & b c f & ~+~ & b c g & ~+~ & .. \\ & & & & b d e & ~+~ & b d f & ~+~ & b d g & ~+~ & .. \\ & & & & & ~+~ & b e f & ~+~ & b e g & ~+~ & .. \\ & & & & & & & ~+~ & b f g & ~+~ & .. \\ & & & & & & & & & & \\ & & & ~+~ & c d e & ~+~ & c d f & ~+~ & c d g & ~+~ & .. \\ & & & & & & c e f & ~+~ & c e g & ~+~ & .. \\ & & & & & & & ~+~ & c f g & ~+~ & .. \\\\ & & & & & & & & & &..\end{eqnarray}
$s_k$の項数
文字の数が$n$個の場合、
$s_1$の項数は$n$
$s_2$の項数は
$$
(n-1)+(n-2)+~..~+1 = \frac{n(n-1)}{2} = \dbinom{n}{2}
$$
$s_3$の項数は
$$
\dbinom{n-1}{2}+ \dbinom{n-2}{2} + ~..~ + 1 = \dbinom{n}{3}
$$
$s_k$の項数は$\binom{n}{k} $個です。これは定義からも分かります。
重複を許したk個の文字からなる項の和を$k$次の完全斉次式と呼び$h_k$と表す。
$$
h_k = \sum_{j_1\le j_2 \le.. \le j_k}a_{j_1}a_{j_2}~..a_{j_k}
$$
例
\begin{eqnarray} h_1 = a & ~+~ & b & ~+~ & c & ~+~ & d & ~+~ & .. \\ \end{eqnarray}\begin{eqnarray} h_2 = a^2 & ~+~ & a b & ~+~ & a c & ~+~ & a d & ~+~ & a e & ~+~ .. \\ & ~+~ & b^2 & ~+~ & b c & ~+~ & b d & ~+~ & b e & ~+~ ..\\ & & & ~+~ & c^2 & ~+~ & c d & ~+~ & c e & ~+~ .. \\ & & & & & ~+~ & d^2 & ~+~ & d e & ~+~ ..\\ & & & & & & & ~+~ & e^2 & ~+~ ..\\ \end{eqnarray}\begin{eqnarray} h_3 = a^3 & ~+~ & a^2 b & ~+~ & a^2 c & ~+~ & a^2 d & ~+~ & .. \\ & ~+~ & a b^2 & ~+~ & a b c & ~+~ & a b d & ~+~ & .. \\ & & & ~+~ & a c^2 & ~+~ & a c d & ~+~ & .. \\ & & & & & ~+~ & a d^2 & ~+~ & .. \\ & & & & & & & & \\ & ~+~ & b^3 & ~+~ & b^2 c & ~+~ & b^2 d & ~+~ & .. \\ & & & ~+~ & b c^2 & ~+~ & b c d & ~+~ & .. \\ & & & & & ~+~ & b d^2 & ~+~ & .. \\ & & & & & & & & \\ & & & & c^3 & ~+~ & c^2 d & ~+~ & .. \\ & & & & & ~+~ & c d^2 & ~+~ & .. \\ & & & & & & & & \\ & & & & & ~+~ & d^3 & ~+~ & .. \\\end{eqnarray}
$h_k$の項数
$h_1$の項数は$n$
$h_2$の項数は
$$
n+(n-1)+~..~+1 = \frac{n(n+1)}{2} = \dbinom{n+1}{2}
$$
$h_3$の項数は
$$
\dbinom{n+1}{2}+ \dbinom{n}{2} + ~..~ + 1 = \dbinom{n+2}{3}
$$
$h_k$の項数は$\binom{n+k-1}{k} $個です。これは重複組合せの係数で
$$
\left(\!\!{n\choose k}\!\!\right) = \dbinom{n+k-1}{k}
$$
とも書きます。これは以下のような考察で分かります。$n$個の文字に$k-1$個の数字を混ぜ、そこから$k$個取り出します。文字はアルファベット順に並べ、しきいの有無により重複を表します。数字が取り出されたら、その番号のしきいを抜きます。
例えば、(a,b,c,d,e)が取り出された場合、(a|b|c|d|e)というイメージになります。(1,a,b,c,d)の場合、1番のしきいが抜かれ、(aa|b|c|d)となり$a^2bcd$を表します。この方法で$h_k$の項を過不足なく作れるので、$h_k$の項数は$\binom{n+k-1}{k}$となります。
母関数
\begin{eqnarray} P&:=&\frac{az}{1-az}+\frac{bz}{1-bz}+\frac{cz}{1-cz} + ~..\\ &=&p_1 z + p_2 z^2 + p_3 z^3 + ~..\\ Q&:=&\frac{az}{1+az}+\frac{bz}{1+bz}+\frac{cz}{1+cz} + ~..\\ &=&p_1 z - p_2 z^2 + p_3 z^3 - ~.. \end{eqnarray}
\begin{eqnarray} R&:=&(1+az)(1+bz)(1+cz) ~..\\ &=&1+s_1 z + s_2 z^2 + s_3 z^3 + ~..\\ S&:=&(1-az)(1-bz)(1-cz) ~..\\ &=&1+s_1 z - s_2 z^2 + s_3 z^3 - ~.. \end{eqnarray}
$s_k$の項数は$a,b,c,~..$を全て$1$にしたときの$z^k$の係数なので、$(1+z)^k$の$z^k$の係数、すなわち$\binom{n}{k}$ になります。
\begin{eqnarray}
V&:=&\frac{1}{S}=\frac{1}{(1-az)(1-bz)(1-cz)~..}\\
&=&(1+az+a^2z^2+~..)(1+bz+b^2z^2+~..)(1+cz+c^2z^2+~..)~..\\
&=&1+h_1z+h_2z^2+h_3z^3+~..
\end{eqnarray}
\begin{eqnarray}
T&:=&\frac{1}{R}=\frac{1}{(1+az)(1+bz)(1+cz)~..}\\
&=&1-h_1z+h_2z^2-h_3z^3+~..
\end{eqnarray}
$h_k$の項数は$(1-z)^{-n}$の$z^k$の係数なので、一般二項定理より$\binom{n+k-1}{k}$となります。
\begin{eqnarray}
(1-z)^{-n} &=& 1 - (-n) z + \frac{(-n)(-n-1)}{2} z^2 - \frac{(-n)(-n-1)(-n-2)}{6} + ~..\\
&=& 1 + nz + \frac{n(n+1)}{2}z^2 + \frac{n(n+1)(n+2)}{6}z^3+~..
\end{eqnarray}
ニュートンの恒等式
\begin{eqnarray}
R=(1+az)(1+bz)(1+cz) ~..
\end{eqnarray}
の対数微分より
\begin{eqnarray}
\frac{zdR}{Rdz} = \frac{az}{1+az}+\frac{bz}{1+bz}+\frac{cz}{1+cz} + ~.. = Q
\end{eqnarray}
また
\begin{eqnarray}
\frac{zdS}{Sdz} = \frac{az}{1-az}+\frac{bz}{1-bz}+\frac{cz}{1-cz} + ~.. = -P
\end{eqnarray}
よって
\begin{eqnarray}
P=p_1z+p_2z^2+p_3z^3+~.. = \frac{s_1 z-2s_2z^2+3s_3z^3-~..}{1-s_1z+s_2z^2-s_3z^3+~..}\\
Q=p_1z-p_2z^2+p_3z^3-~.. = \frac{s_1 z+2s_2z^2+3s_3z^3+~..}{1+s_1z+s_2z^2+s_3z^3+~..}
\end{eqnarray}
$Q$の式について係数比較します。どちらの式を使っても同じ結果になります。
\begin{eqnarray}
~~&z& & z^2 & & z^3 & & z^4 & & z^5 & &..\\
~~&s_1 & ~ & 2s_2 & ~ & 3s_3 & ~ & 4s_4 & ~ & 5s_5 & ~ & .. \\
=~&p_1 & & -p_2 & & p_3 & & -p_4 & & p_5 & & .. \\ & & & s_1p_1 & &-s_1p_2 & & s_1p_3 & & -s_1p_4 && .. \\ & & & & & s_2p_1 & & -s_2p_2 & & s_2p_3 & & .. \\ & & & & & & & s_3p_1 & &-s_3p_2 && .. \\
& & & & & & & & &s_4p_1 && .. \\
\end{eqnarray}
これより以下のニュートンの恒等式を得ます。
\begin{eqnarray} s_1&=&p_1\\ 2s_2&=&s_1p_1-p_2\\ 3s_3&=&s_2p_1-s_1p_2+p_3\\ 4s_4&=&s_3p_1-s_2p_2+s_1p_3-p_4\\ .. \end{eqnarray}
指数表現
$\frac{zdR}{Rdz} = Q$より$\ln R = \int \frac{Q dz}{z}$
$$
\int \frac{Q dz}{z} = p_1 z - p_2 z^2/2+p_3z^3/3-~..
$$
より
$$
\ln (1+s_1z+s_2z^2+~..) = e^{p_1z-p_2z^2/2+p_3z^3/3-~..}
$$
$$
\ln (1-s_1z+s_2z^2-~..) = e^{-p_1z-p_2z^2/2-p_3z^3/3-~..}
$$
完全斉次式と基本対象式の関係
$V=1/S,T=1/R$より
\begin{eqnarray}
1=(1+s_1z+s_2z^2+~..)(1-h_1z+h_2z^2-~..)\\
1=(1-s_1z+s_2z^2-~..)(1+h_1z+h_2z^2+~..)
\end{eqnarray}
係数比較より以下の関係式が得られます。
\begin{eqnarray} h_1&=&s_1\\ h_2&=&s_1 h_1 - s_2\\ h_3&=&s_1 h_2 - s_2 h_1 + s_3\\ h_3&=&s_1 h_3 - s_2 h_2 + s_3 h_1 - s_4\\ .. \end{eqnarray}
完全斉次式とべき乗和の関係
$V=1/S,T=1/R$を微分し
\begin{eqnarray}
dS/S=-dV/V\\
dR/R=-dT/T
\end{eqnarray}
$P=-\frac{zdS}{Sdz},Q=\frac{zdR}{Rdz}$より
\begin{eqnarray}
P=\frac{zdV}{Vdz}\\
Q=-\frac{zdT}{Tdz}\\
\end{eqnarray}
これより
\begin{eqnarray}
P=p_1z+p_2z^2+p_3z^3+~..=\frac{h_1z+2h_2z^2+3h_3z^3+~..}{1+h_1z+h_2z^2+h_3z^3+~..}\\
Q=p_1z-p_2z^2+p_3z^3-~..=\frac{h_1z-2h_2z^2+3h_3z^3-~..}{1-h_1z+h_2z^2-h_3z^3+~..}
\end{eqnarray}
係数比較より以下の式を得ます。
\begin{eqnarray} h_1&=&p_1\\ 2h_2&=&h_1 p_1 + p_2\\ 3h_3&=&h_2 p_1 + h_1 p_2 + p_3\\ 4h_4&=&h_3 p_1 + h_2 p_2 + h_1 p_3 + p_4\\ .. \end{eqnarray}
指数表現
$TR=1,SV=1$より
\begin{eqnarray}
\ln(1+s_1z+s_2z^2+~..)=-\ln(1-h_1z+h_2z^2-~..)\\
\ln(1-s_1z+s_2z^2-~..)=-\ln(1+h_1z+h_2z^2+~..)
\end{eqnarray}
また
\begin{eqnarray}
1-h_1z+h_2z^2+~..&=&e^{-p_1z+p_2z^2/2-p_3/z^3/3+~..}\\
1+h_1z+h_2z^2+~..&=&e^{p_1z+p_2z^2/2+p_3z^3/3+~..}
\end{eqnarray}
その他の関係式
\begin{eqnarray}
1+s_1z+s_2z^2+~.. &=& R\\
1-s_1z+s_2z^2-~.. &=& S\\
1-h_1z+h_2z^2-~..&=&1/R\\
1+h_1z+h_2z^2+~..&=&1/S
\end{eqnarray}
より
\begin{eqnarray}
R&=&\frac{R-1}{1-1/R}=\frac{s_1z+s_2z^2+s_3z^3+~..}{h_1z-h_2z^2+h_3z^3-~..}\\
S&=&\frac{S-1}{1-1/S}=\frac{s_1z-s_2z^2+s_3z^3-~..}{h_1z+h_2z^2+h_3z^3+~..}
\end{eqnarray}
また
\begin{eqnarray}
\frac{R+S}{2} &=& 1+s_2z^2+s_4z^4+s_6z^6+~..\\
\frac{R-S}{2} &=& s_1z+s_3z^3+s_5z^5+~..\\
\frac{R+S}{2RS} &=& 1+h_2z^2+h_4z^4+h_6z^6+~..\\
\frac{R-S}{2RS} &=& h_1z+h_3z^3+h_5z^5+~..\\
\end{eqnarray}
また$P=-\frac{zdS}{Sdz},Q=\frac{zdR}{Rdz},P=\frac{zdV}{Vdz},Q=-\frac{zdT}{Tdz},V=1/S,T=1/R$より
\begin{eqnarray}
PS&=&s_1z-2s_2z^2+3s_3z^3-~..\\
QR&=&s_1z+2s_2z^2+3s_3z^3+~..\\
P/S&=&h_1z+2h_2z^2+3h_3z^3+~..\\
Q/R&=&h_1z-2h_2z^2+3h_3z^3-~..\\
\end{eqnarray}
よって
\begin{eqnarray}
S&=&\frac{h_1z-2h_2z^2+3h_3z^3-~..}{p_1z+p_2z^2+p_3z^3+~..}\\
&=&\frac{p_1z+p_2z^2+p_3z^3+~..}{h_1z+2h_2z^2+3h_3z^3+~..}\\
R&=&\frac{h_1z+2h_2z^2+3h_3z^3+~..}{p_1z-p_2z^2+p_3z^3-~..}\\
&=&\frac{p_1z-p_2z^2+p_3z^3-~..}{h_1z-2h_2z^2+3h_3z^3-~..}\\
\end{eqnarray}
これから$R$を何通りもの方法で表すことができます。$z$を$-z$で置き換えると$S$についての式になります。
\begin{eqnarray} R&=&(1+az)(1+bz)(1+cz)~..\\ &=&1+s_1z+s_2z^2+s_3z^3+~..\\ &=&\frac{1}{1-h_1z+h_2z^2-h_3z^3+~..}\\ &=&\frac{s_1z+s_2z^2+s_3z^3+~..}{h_1z-h_2z^2+h_3z^3-~..}\\ &=&\frac{s_1z+2s_2z^2+3s_3z^3+~..}{p_1z-p_2z^2+p_3z^3-~..}\\ &=&\frac{p_1z-2p_2z^2+3p_3z^3+~..}{h_1z-2h_2z^2+3h_3z^3-~..}\\ \end{eqnarray}
応用
$a,b,c,..$として$q,q^2,q^3~..$を使うと、自然数の分割関数の母関数が得られます。また素数の$-n$乗を使い、$z=1$とするとオイラー積
$$
V=\prod_p \frac{1}{1-p^{-n}}= \sum_{k=1}^{\infty}k^{-n}
$$
が得られます。
