§E13.2整数分割と母関数

証明.$\lambda\vdash n$とする。$\lambda$の部分は有限個であるから$m_k(\lambda)\ne0$となる$k$は有限個である。部分を値ごとに分類すると、加法原理（§D2.2 定理 2.1）により$\sum_{k\ge1}km_k(\lambda)=\sum_{i=1}^{r}\lambda_i=n$である。また$m_k(\lambda)\ne0$ならば$k$は$\lambda$の部分の一つであり、$k\le\sum_i\lambda_i=n$である。

逆写像を作る。条件を満たす族$(m_k)_{k\ge1}$に対し、値$k$を$m_k$個ずつ、$k$の大きい順に並べた有限列を$\lambda(m)$と定める。この列は非増加な正の整数の列であり、成分の総和は$\sum_k km_k=n$であるから$n$の分割である。構成から$m_k(\lambda(m))=m_k$であり、逆に非増加列$\lambda$は各値の重複度によって一意に定まるので$\lambda(m(\lambda))=\lambda$である。ゆえに二つの写像は互いに逆であり、主張の写像は全単射である。▨

証明. 空の分割については四つの主張はいずれも定義から直ちに従うので、以下$r\ge1$とする。

(1)を示す。$1\le j<j'\le\lambda_1$のとき$\{i:\lambda_i\ge j'\}\subseteq\{i:\lambda_i\ge j\}$であるから$\lambda'_{j'}\le\lambda'_j$であり、$\lambda'$は非増加である。$j\le\lambda_1$のとき$\lambda_1\ge j$であるから$1\in\{i:\lambda_i\ge j\}$であり$\lambda'_j\ge1$である。総和については、$D(\lambda)$の元を第二成分$j$の値ごとに分類すると、$j$を固定したときの元の個数は$|\{i:\lambda_i\ge j\}|=\lambda'_j$であるから、加法原理（§D2.2 定理 2.1）により

である。最後の等号も、$D(\lambda)$を第一成分ごとに分類した加法原理による。ゆえに$\lambda'\vdash n$である。

(2)を示す。$\lambda$は非増加であるから、$1\le j\le\lambda_1$に対し

である。実際、$\lambda_i\ge j$かつ$i'<i$ならば$\lambda_{i'}\ge\lambda_i\ge j$であるから、この集合は$1$から始まる連続した区間であり、その要素数は$\lambda'_j$である。したがって

である。最後の同値では、$(i,j)\in D(\lambda)$が$1\le i\le r$かつ$1\le j\le\lambda_i$を意味することと、$\lambda_i\ge j\ge1$が$i\le r$と$j\le\lambda_1$を含意することを用いた。

(3)を示す。(2)を$\lambda'$へ適用すると$D((\lambda')')$は$D(\lambda')$の第一成分と第二成分を入れ替えた集合であり、ふたたび(2)により$D(\lambda)$に等しい。分割はその Ferrers 図形の第$i$行の点の個数として復元されるので$(\lambda')'=\lambda$である。共役は$n$の分割の全体からそれ自身への写像であり、自分自身が逆写像であるから全単射である。

(4)を示す。$\lambda'$の最大の部分は$\lambda'_1=|\{i:\lambda_i\ge1\}|=r$であり、これは$\lambda$の部分の個数である。$\lambda'$の部分の個数は定義から$\lambda_1$であり、これは$\lambda$の最大の部分である。▨

証明.命題 1.4 (3)により、共役は$n$の分割の全体上の全単射である。命題 1.4 (4)により、$\lambda$の部分の個数が$m$以下であることと$\lambda'$の最大の部分が$m$以下であること、すなわち$\lambda'$の各部分が$m$以下であることは同値である。したがって共役は、部分の個数が$m$以下である分割の全体から、各部分が$m$以下である分割の全体への全単射を与える。全単射原理（§D2.2 命題 1.5）により両者の個数は等しい。▨

証明.$F=0$または$G=0$のときは$FG=0$であり、両辺とも$\infty$である。以下$F\ne0$かつ$G\ne0$とし、$p=\operatorname{ord}(F)$、$q=\operatorname{ord}(G)$と置く。Cauchy 積の定義（§D2.4 定義 4.1）により

である。

$n<p+q$とする。各項について、$j<p$ならば$[x^{j}]F=0$であり、$j\ge p$ならば$n-j\le n-p<q$であるから$[x^{n-j}]G=0$である。ゆえに$[x^{n}](FG)=0$である。

$n=p+q$とする。$j<p$の項と$j>p$の項（このとき$n-j<q$）はいずれも$0$であるから、$[x^{n}](FG)=([x^{p}]F)([x^{q}]G)$である。$\mathbb Q$は体であり零因子をもたないので、この値は$0$でない。ゆえに$\operatorname{ord}(FG)=p+q$である。▨

証明.§E13.1 命題 1.2 (4)の分配法則を有限個の因子へ繰り返し適用し、§E13.1 命題 1.2 (3)の結合性と§E13.1 命題 1.2 (2)の可換性によって因子を集めると、

である（右辺は$J'$の部分集合にわたる有限和であり、$S=\emptyset$の項は$1$と読む）。

$S\subseteq J'$が$S\subseteq J$を満たさないとする。このとき$i_0\in S\setminus J$が存在する。$I_n\subseteq J$であるから$i_0\notin I_n$であり、$\operatorname{ord}(G_{i_0})>n$である。補題 2.2を繰り返し用いると

であるから$[x^{n}]\prod_{i\in S}G_i=0$である。ゆえに

となる。▨

証明.$r$個の因子の積は§E13.1 命題 1.2 (3)により括弧の付け方によらず定まる。$r$についての帰納法で示す。$r=1$のときは両辺とも$[x^{n}]F_1$である。$r\ge2$とし、$r-1$について主張が成り立つとする。Cauchy 積の定義（§D2.4 定義 4.1）と帰納法の仮定により

となる。右辺の二重和は、$n_1+\dots+n_r=n$を満たす非負整数の組の全体にわたる和にほかならない。組の個数は有限であるから和は有限和である。▨

証明. 係数の値は定義 2.3の定義から直ちに従う。$n=jk$を満たす非負整数$j$は$k\mid n$のときちょうど一つ存在し、そのとき$[x^{n}]x^{jk}=1$、他の項は$0$である。

$(1-x^{k})Q_k$の係数を計算する。Cauchy 積により$[x^{n}]\bigl((1-x^{k})Q_k\bigr)=[x^{n}]Q_k-[x^{n-k}]Q_k$である（$n<k$のとき第二項は$0$と読む）。$n=0$のとき値は$1-0=1$である。$n\ge1$で$k\mid n$のとき$n\ge k$であり、$k\mid(n-k)$であるから値は$1-1=0$である。$k\nmid n$のとき$k\nmid(n-k)$でもあるから値は$0-0=0$である。ゆえに$(1-x^{k})Q_k=1$である。▨

証明.$G_k=Q_k-1=\sum_{j\ge1}x^{jk}$と置く。補題 2.7により$[x^{m}]G_k$は$k\mid m$かつ$m\ge1$のとき$1$、それ以外のとき$0$である。ゆえに$\operatorname{ord}(G_k)=k$であり、各$n$に対して$\{k\ge1:\operatorname{ord}(G_k)\le n\}=\{1,2,\dots,n\}$は有限集合である。したがって族$(G_k)_{k\ge1}$は総和可能であり、無限積$\prod_{k\ge1}(1+G_k)=\prod_{k\ge1}Q_k$が定まる。

$n=0$のとき、$\{k:\operatorname{ord}(G_k)\le0\}=\emptyset$であるから定義により$[x^{0}]\prod_{k\ge1}Q_k=[x^{0}]1=1=p(0)$である。

$n\ge1$とする。定義 2.5により

である。補題 2.6を$F_k=Q_k$（$k=1,\dots,n$）へ適用すると

となる。補題 2.7により、積$\prod_{k=1}^{n}[x^{n_k}]Q_k$は、すべての$k$について$k\mid n_k$が成り立つとき$1$、そうでないとき$0$である。したがって右辺は

に等しい。$k\mid n_k$を満たす非負整数$n_k$は$n_k=km_k$（$m_k\in\mathbb Z_{\ge0}$）と一意に書くことができるので、この集合は

と全単射に対応する。命題 1.2により、$\sum_{k\ge1}km_k=n$を満たす非負整数の族で$m_k\ne0$となる$k$が有限個であるものは$n$の分割と一対一に対応し、しかも同命題の最後の主張により$m_k\ne0$ならば$k\le n$である。ゆえに上の集合は$n$の分割の全体と全単射に対応し、その要素数は$p(n)$である。全単射原理（§D2.2 命題 1.5）により

が成り立つ。$n$は任意であったから主張を得る。▨

証明.$\operatorname{ord}(x^{k})=k$であるから$\{k\ge1:\operatorname{ord}(x^{k})\le n\}=\{1,\dots,n\}$は有限集合であり、族は総和可能である。$n=0$のとき、この集合は空であるから$[x^{0}]\prod_{k\ge1}(1+x^{k})=1$であり、$q(0)=1$（空の分割）と一致する。

$n\ge1$とする。定義 2.5により第一の等号が成り立ち、§E13.1 命題 1.2の分配法則と結合性を有限個の因子へ繰り返し適用すると第二の等号が成り立つ。

である。$\prod_{k\in S}x^{k}=x^{\sum_{k\in S}k}$であるから、右辺は$\sum_{k\in S}k=n$を満たす部分集合$S\subseteq\{1,\dots,n\}$の個数に等しい。

このような$S$と、$n$の分割で部分がすべて相異なるものとの対応を作る。$S$に対し、$S$の元を大きい順に並べた列は、部分が相異なる$n$の分割である。逆に、部分が相異なる$n$の分割$\lambda$に対し、その部分の集合$S(\lambda)$は$\sum_{k\in S(\lambda)}k=n$を満たし、各部分は$n$以下であるから$S(\lambda)\subseteq\{1,\dots,n\}$である。二つの対応は互いに逆であるから全単射であり、全単射原理（§D2.2 命題 1.5）により右辺は$q(n)$に等しい。▨

証明.$G_k=Q_{2k-1}-1=\sum_{j\ge1}x^{j(2k-1)}$と置く。補題 2.7により$\operatorname{ord}(G_k)=2k-1$であるから、各$n$に対し$\{k\ge1:\operatorname{ord}(G_k)\le n\}=\{k\ge1:2k-1\le n\}$は有限集合であり、族は総和可能である。$n=0$のときこの集合は空であるから$[x^{0}]\prod_{k\ge1}Q_{2k-1}=1=p_{\mathrm{odd}}(0)$である。

$n\ge1$とし、$O_n=\{k\ge1:2k-1\le n\}$と置く。定義 2.5により

である。補題 2.6を因子$Q_{2k-1}$（$k\in O_n$）へ適用すると

となる。補題 2.7により、積$\prod_{k}[x^{n_k}]Q_{2k-1}$は、すべての$k\in O_n$について$(2k-1)\mid n_k$が成り立つとき$1$、そうでないとき$0$である。$(2k-1)\mid n_k$を満たす非負整数$n_k$は$n_k=(2k-1)m_k$（$m_k\in\mathbb Z_{\ge0}$）と一意に書くことができるので、右辺は

に等しい。

最後に、この集合と、部分がすべて奇数である$n$の分割の全体との対応を作る。命題 1.2の全単射$\lambda\mapsto(m_k(\lambda))_{k\ge1}$は、$\lambda$の部分がすべて奇数であることと、偶数$k$に対して$m_k(\lambda)=0$であることを同値にする。さらに同命題の最後の主張により$m_k(\lambda)\ne0$ならば$k\le n$であるから、非零の重複度の添字は$O_n$の元$k$に対応する奇数$2k-1$に限られる。したがって、部分が奇数である$n$の分割と上の集合とは一対一に対応し、全単射原理（§D2.2 命題 1.5）により$[x^{n}]\prod_{k\ge1}Q_{2k-1}=p_{\mathrm{odd}}(n)$である。▨

証明. 非負整数$n$を固定し、$N$を$N\ge\max(n,1)$を満たす整数とする。$M=\lfloor N/2\rfloor$と置く。

段階 1。各$k\ge1$に対し、Cauchy 積により$(1+x^{k})(1-x^{k})=1-x^{2k}$である。補題 2.7により$1-x^{k}$は可逆であるから、両辺に$Q_k=(1-x^{k})^{-1}$を掛けて

を得る。

段階 2。段階 1 の式を$k=1,\dots,N$について掛け合わせると、§E13.1 命題 1.2により$\mathbb Q[[x]]$が可換環であることから

となる。

段階 3。右側の積を偶奇で分ける。因子の並べ替えには§E13.1 命題 1.2 (2)と§E13.1 命題 1.2 (3)を用いる。$\{1,\dots,N\}$のうち偶数であるものは$2,4,\dots,2M$であるから

である。

段階 4。補題 2.7により$(1-x^{2j})Q_{2j}=1$である。§E13.1 命題 1.2 (2)と§E13.1 命題 1.2 (3)によって因子を組み替えると

である。$N\ge1$のとき$M=\lfloor N/2\rfloor<N$であるから、右端の積は空でない。段階 2 と段階 3 と合わせて

を得る。

段階 5。$R_N=1+E_N$と置く。§E13.1 命題 1.2の分配法則により$E_N$は、$M+1\le k\le N$を満たす$k$の空でない部分集合$S$にわたる$\pm\prod_{k\in S}x^{2k}$の和である。各項の位数は$\sum_{k\in S}2k\ge2(M+1)$である。$M=\lfloor N/2\rfloor\ge(N-1)/2$であるから$2(M+1)\ge N+1>n$である。ゆえに$\operatorname{ord}(E_N)>n$である。

段階 6。段階 4 の等式の両辺の第$n$係数を取る。補題 2.2により

であるから、この積の第$n$係数は$0$である。ゆえに

である。

段階 7。$N\ge n$であるから、$\{k\ge1:\operatorname{ord}(x^{k})\le n\}=\{1,\dots,n\}\subseteq\{1,\dots,N\}$であり、命題 2.4により左辺は$[x^{n}]\prod_{k\ge1}(1+x^{k})$に等しい。同様に、$\operatorname{ord}(Q_{2k-1}-1)=2k-1$であるから、位数が$n$以下の奇数番号の因子はすべて$\{1\le k\le N,\ k\ \text{奇数}\}$に含まれ、右辺は$[x^{n}]\prod_{k\ge1}Q_{2k-1}$に等しい。