§C3.12分割数と母関数

最終更新

本記事は、正の整数を正の整数の和として表す方法の個数を、母関数の係数として求めます。そのうえで、相異なる数への分割の個数と、奇数だけへの分割の個数がつねに等しいことを、母関数を変形して示します。数え上げの問題を、係数の並びについての等式の問題へ置き換える点が、母関数を用いる利点です。

母関数を形式的なべき級数として扱う枠組みは、母関数入門で扱います。本記事は、これを導入し直さずに用い、分割数という対象に絞ります。とくに、xxは値を代入する変数ではなく、係数の並びを表す不定元です。本記事は形式的なべき級数として計算し、収束には立ち入りません。

1 分割と分割数を定める

定義 1.1 (分割と分割数). 正の整数nnに対し、

n=λ1+λ2+⋯+λr,λ1≥λ2≥⋯≥λr≥1n = \lambda_1 + \lambda_2 + \cdots + \lambda_r, \qquad \lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_r \ge 1

を満たす正の整数の組(λ1,…,λr)(\lambda_1, \dots, \lambda_r)をnnの分割といい、各λi\lambda_iをその項という。項を大きい順に並べることで、和の順序の違いを同じ分割とみなす。nnの分割の個数をp(n)p(n)と書き、分割数という。また、項が一つも無い和を00の分割とみなしてp(0)=1p(0) = 1と定める。

分割は、順序を区別しない和への分け方です。3+13 + 1と1+31 + 3は44の同じ分割であり、二通りとは数えません。

例 1.2 (88以下の分割数).55の分割をすべて書き出すと

5,4+1,3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+15,\quad 4+1,\quad 3+2,\quad 3+1+1,\quad 2+2+1,\quad 2+1+1+1,\quad 1+1+1+1+1

の77通りであるからp(5)=7p(5) = 7である。同じように数えると、次の値が得られる。

nn 00 11 22 33 44 55 66 77 88
p(n)p(n) 11 11 22 33 55 77 1111 1515 2222

分割を一つずつ書き出す数え方では、nnが大きくなるにつれて書き出す個数が急に増えます。そこで、p(n)p(n)を一つずつ求める代わりに、すべてのnnについての値を係数として一列に並べたものを、一つの対象として扱います。

2 分割数の母関数

分割を決めることは、各正の整数kkについて「kkを何個使うか」を決めることと同じです。kkをmm個使うと和にkmkmが加わるので、kkについての選択を1+xk+x2k+⋯1 + x^k + x^{2k} + \cdotsという級数で表し、それらをkkについて掛け合わせます。

定理 2.1 (分割数の母関数). 形式的なべき級数として

∑n≥0p(n)xn=∏k≥111−xk\sum_{n \ge 0} p(n) x^n = \prod_{k \ge 1} \frac{1}{1 - x^k}

が成り立つ。

注意 2.2 (無限個の積が形式的なべき級数として定まること). 右辺は無限個の因子の積であるが、xnx^nの係数は有限個の因子だけで決まる。実際、各因子1/(1−xk)=1+xk+x2k+⋯1/(1-x^k) = 1 + x^k + x^{2k} + \cdotsの定数項は11であり、k>nk > nの因子からx0x^0以外の項を取ると次数がnnを超えるので、xnx^nの係数にはk≤nk \le nの因子だけが寄与する。したがって、各係数は有限個の積の展開として確定した値に定まる。xxに値を代入することも、級数の収束を論じることもしない。

証明.nnを固定し、両辺のxnx^nの係数を比べます。注意 2.2により、右辺のxnx^nの係数は

∏k=1n(1+xk+x2k+⋯ )\prod_{k=1}^{n} \left( 1 + x^k + x^{2k} + \cdots \right)

のxnx^nの係数と一致します。この積を展開すると、各kk（1≤k≤n1 \le k \le n）についてxkmkx^{k m_k}という項を一つずつ選び、それらを掛け合わせた項

x1⋅m1+2⋅m2+⋯+n⋅mnx^{1 \cdot m_1 + 2 \cdot m_2 + \cdots + n \cdot m_n}

が、00以上の整数の組(m1,…,mn)(m_1, \dots, m_n)ごとにちょうど一つ現れます。したがってxnx^nの係数は、

1⋅m1+2⋅m2+⋯+n⋅mn=n1 \cdot m_1 + 2 \cdot m_2 + \cdots + n \cdot m_n = n

を満たす00以上の整数の組(m1,…,mn)(m_1, \dots, m_n)の個数です。

一方、nnの分割は、各kkについて「項kkが何個現れるか」をmkm_kとすることで、そのような組と一対一に対応します。項の個数を与えれば分割が定まり、分割からは各項の個数が定まるからです。よってxnx^nの係数はp(n)p(n)に等しくなります。▨

例 2.3 (係数を実際に読み取る).x5x^5までの係数を求めるには、k≤5k \le 5の因子をx5x^5までで打ち切れば足りる。

(1+x+x2+x3+x4+x5)(1+x2+x4)(1+x3)(1+x4)(1+x5)(1 + x + x^2 + x^3 + x^4 + x^5)(1 + x^2 + x^4)(1 + x^3)(1 + x^4)(1 + x^5)

を順に展開し、そのつどx6x^6以上の項を落とすと

1+x+2x2+2x3+3x4+3x5→ 1+x+2x2+3x3+4x4+5x5→ 1+x+2x2+3x3+5x4+6x5→ 1+x+2x2+3x3+5x4+7x5\begin{aligned} &1 + x + 2x^2 + 2x^3 + 3x^4 + 3x^5 \\ \to\ &1 + x + 2x^2 + 3x^3 + 4x^4 + 5x^5 \\ \to\ &1 + x + 2x^2 + 3x^3 + 5x^4 + 6x^5 \\ \to\ &1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 \end{aligned}

となる。係数の並び1,1,2,3,5,71, 1, 2, 3, 5, 7は例 1.2のp(0),…,p(5)p(0), \dots, p(5)と一致する。

3 項を制限した分割の母関数

分割の項に条件を付けても、同じ考え方で母関数を作ることができます。

定義 3.1 (相異なる数への分割と奇数への分割). 正の整数nnの分割のうち、項がすべて相異なるものの個数をpd(n)p_{\mathrm{d}}(n)と書く。また、項がすべて奇数であるものの個数をpo(n)p_{\mathrm{o}}(n)と書く。後者では、同じ奇数が何度現れてもよい。pd(0)=po(0)=1p_{\mathrm{d}}(0) = p_{\mathrm{o}}(0) = 1と定める。

定理 3.2 (制限した分割の母関数). 形式的なべき級数として

∑n≥0pd(n)xn=∏k≥1(1+xk),∑n≥0po(n)xn=∏k は奇数11−xk\sum_{n \ge 0} p_{\mathrm{d}}(n) x^n = \prod_{k \ge 1} (1 + x^k), \qquad \sum_{n \ge 0} p_{\mathrm{o}}(n) x^n = \prod_{k\ \text{は奇数}} \frac{1}{1 - x^k}

が成り立つ。

証明. 第一の等式では、各kkについて「kkを使わない」か「kkを一度だけ使う」かの二択なので、kkに対応する因子は1+xk1 + x^kです。定理 2.1の証明と同じ数え方によって、xnx^nの係数は、相異なる項からなるnnの分割の個数に等しくなります。

第二の等式では、奇数kkについて「kkを何個使うか」を決め、偶数は使いません。よって奇数kkに対応する因子だけを掛け合わせ、xnx^nの係数は、奇数だけを項とするnnの分割の個数に等しくなります。▨

4 相異なる数への分割と奇数への分割は同じ個数である

二つの母関数は、見た目には無関係です。しかし、一方を変形すると他方に一致します。

定理 4.1 (相異なる数への分割と奇数への分割). すべての00以上の整数nnについてpd(n)=po(n)p_{\mathrm{d}}(n) = p_{\mathrm{o}}(n)が成り立つ。

証明.定理 3.2の二つの母関数が、形式的なべき級数として等しいことを示します。

nnを固定し、xn+1x^{n+1}以上の項を無視して比べます。注意 2.2と同じ理由で、どちらの母関数についても、xnx^nまでの係数はk≤nk \le nの因子だけで決まります。そこで

∏k=1n(1+xk)\prod_{k=1}^{n} (1 + x^k)

を考えます。各kkについて(1+xk)(1−xk)=1−x2k(1 + x^k)(1 - x^k) = 1 - x^{2k}であり、1−xk1 - x^kは定数項が11であるから形式的なべき級数として逆元を持ちます。よって

∏k=1n(1+xk)=∏k=1n(1−x2k)∏k=1n(1−xk)\prod_{k=1}^{n} (1 + x^k) = \frac{\prod_{k=1}^{n} (1 - x^{2k})}{\prod_{k=1}^{n} (1 - x^{k})}

です。右辺の分子に現れる因子の指数は2,4,…,2n2, 4, \dots, 2n、分母に現れる因子の指数は1,2,…,n1, 2, \dots, nです。共通する因子は指数がnn以下の偶数であるものなので、それらを約分すると、分子には指数がnnより大きい偶数の因子だけが、分母には指数がnn以下の奇数の因子だけが残ります。

分子に残る因子1−x2k1 - x^{2k}は2k>n2k > nを満たすので、xn+1x^{n+1}以上の項を無視すれば11です。したがって

∏k=1n(1+xk)≡∏k≤nk は奇数11−xk(modxn+1)\prod_{k=1}^{n} (1 + x^k) \equiv \prod_{\substack{k \le n \\ k\ \text{は奇数}}} \frac{1}{1 - x^k} \pmod{x^{n+1}}

が成り立ちます。両辺のxnx^nの係数は、定理 3.2によりそれぞれpd(n)p_{\mathrm{d}}(n)とpo(n)p_{\mathrm{o}}(n)です。nnは任意であったから、すべてのnnについてpd(n)=po(n)p_{\mathrm{d}}(n) = p_{\mathrm{o}}(n)です。▨

例 4.2 (n=6n = 6とn=7n = 7で確かめる).n=6n = 6のとき、項が相異なる分割は

6,5+1,4+2,3+2+16,\quad 5+1,\quad 4+2,\quad 3+2+1

の44通り、項がすべて奇数である分割は

5+1,3+3,3+1+1+1,1+1+1+1+1+15+1,\quad 3+3,\quad 3+1+1+1,\quad 1+1+1+1+1+1

の44通りである。n=7n = 7のとき、項が相異なる分割は

7,6+1,5+2,4+3,4+2+17,\quad 6+1,\quad 5+2,\quad 4+3,\quad 4+2+1

の55通り、項がすべて奇数である分割は

7,5+1+1,3+3+1,3+1+1+1+1,1+1+1+1+1+1+17,\quad 5+1+1,\quad 3+3+1,\quad 3+1+1+1+1,\quad 1+1+1+1+1+1+1

の55通りである。どちらのnnでも個数が一致する。

注意 4.3 (個数の一致と、対応の構成とは別の主張である).定理 4.1は二つの個数が等しいことを述べるものであり、相異なる項からなる分割と奇数だけからなる分割との間に具体的な対応を与えるものではない。母関数による証明は、係数の並びが等しいことを示すことによって個数の一致を導いており、どの分割がどの分割へ移るかを指定しない。

5 分割数の増え方

注意 5.1 (分割数の増え方).例 1.2の値からも分かるとおり、p(n)p(n)はnnとともに速く増える。nnが大きいときにp(n)p(n)がどれくらいの速さで増えるかという評価は、本記事では扱わない。母関数を漸近的な評価と組み合わせる扱いは組合せ論・グラフ理論で行う。

前提記事