代数的組合せ論の問題

難易度 3大学院入試の専門科目の標準レベル証明問題大学院数学代数的組合せ論

正の整数 $n$ の分割とは、和が $n$ になる正の整数の非増加列のことであり、各項を部分という。分割の中に正の整数 $k$ が部分として現れる回数を $k$ の重複度という（現れなければ重複度は $0$ ）。また $0$ の分割は空列ただ 1 つとする。正の整数 $n$ に対し

$A (n)$ : $n$ の分割のうち、どの正の整数 $k$ についても $k$ の重複度が $3$ を法として $1$ に合同でないもの（すなわち各重複度が $0, 2, 3, 5, 6, 8, 9, \dots$ のいずれかであるもの）の個数
$B (n)$ : 非負整数 $a, b$ と、 $a$ の分割 $μ$ 、 $b$ の分割 $ν$ の組 $(μ, ν)$ であって、 $a + b = n$ 、 $μ$ のどの部分も $4$ を法として $2$ に合同、 $ν$ のどの部分も $3$ の倍数であるものの個数

とする。すべての正の整数 $n$ に対して $A (n) = B (n)$ が成り立つことを、母関数を用いて証明せよ。

ただし、母関数は有理数係数の形式的冪級数環 $Q [[x]]$ で考え、次の事実は用いてよい: 形式的冪級数の列 $a_{1}, a_{2}, \dots$ で $a_{k}$ の位数（ $0$ でない最低次の次数）が $k \to \infty$ で $\infty$ に発散するものについて、無限積 $\prod_{k \geq 1} (1 + a_{k})$ は収束し、その $x^{N}$ までの係数は有限個の因子の積で決まること、また収束する無限積どうしの積・商（定数項が $1$ のもの）は因子ごとにとってよく、因子の並べ替えや分け方を変えても値は変わらないこと。

この問題で使うもの

分割数と分割の母関数（説明と入口の問題）
母関数と係数の取り出し（説明と入口の問題）
等差・等比数列の和と Σ（説明と入口の問題）

この問題を解けるようになるまで（61 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$A (n)$ と $B (n)$ の母関数をそれぞれ無限積で表し、その 2 つが形式的冪級数として等しいことを示す。 $B$ の母関数は 2 つの無限積の積になる。

ヒント 2

重複度が $3$ を法として $1$ に合同でないことに対応する因子は $\sum_{m \neq \equiv 1 (3)} y^{m} = \frac{1}{1 - y} - \frac{y}{1 - y ^{3}}$ （ $y = x^{k}$ ）であり、これは $\frac{1 + y ^{2}}{1 - y ^{3}}$ にまとまる。

ヒント 3

$1 + y^{2} = \frac{1 - y ^{4}}{1 - y ^{2}}$ を使うと、 $A$ の母関数は $\frac{\prod ( 1 - x ^{4 k} )}{\prod ( 1 - x ^{2 k} ) \prod ( 1 - x ^{3 k} )}$ になる。 $\prod (1 - x^{2 k})$ を $k$ の偶奇で分けて約分する。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$A (n)$ の母関数を、重複度が $3$ を法として $1$ に合同でないことに対応する因子 $\sum_{m \neq \equiv 1 (3)} x^{k m}$ の無限積として、係数の意味づけとともに導いている（2 点）
$B (n)$ の母関数を、 $4$ を法として $2$ に合同な部分の分割の母関数と $3$ の倍数の部分の分割の母関数の積として表している（2 点）
各因子を $\frac{1 + x ^{2 k}}{1 - x ^{3 k}}$ 、さらに $\frac{1 - x ^{4 k}}{( 1 - x ^{2 k} ) ( 1 - x ^{3 k} )}$ と正しく変形している（3 点）
$\prod (1 - x^{2 k})$ を $k$ の偶奇で分けて $\prod (1 - x^{4 k})$ を約分し、残る $\prod_{j 奇数} (1 - x^{2 j})^{- 1}$ が $4$ を法として $2$ に合同な部分に対応することを確かめている（2 点）
2 つの母関数が等しいことから係数比較で $A (n) = B (n)$ を結論している（1 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

$A (0) = B (0) = 1$ と約束し（ $A$ は空の分割、 $B$ は空の分割どうしの組）、 $F (x) = \sum_{n \geq 0} A (n) x^{n}$ , $G (x) = \sum_{n \geq 0} B (n) x^{n}$ とおく。 $F = G$ を示せば、 $x^{n}$ の係数を比べて $A (n) = B (n)$ が得られる。

ステップ 1（ $F$ の積表示）. 分割は、各正の整数 $k$ の重複度 $m_{k} \geq 0$ （有限個を除き $0$ ）の列で一意に定まり、その大きさは $\sum_{k} k m_{k}$ である。 $A (n)$ が数える分割は、各 $k$ について $m_{k} \in M = {m \geq 0 : m \neq \equiv 1 (mod 3)}$ かつ $\sum_{k} k m_{k} = n$ をみたす列 $(m_{k})$ と 1 対 1 に対応する。 $k$ ごとに因子
$Φ_{k} = m \in M \sum x^{k m}$
をとる。 $M$ の $0$ の次に小さい元は $2$ なので $Φ_{k} - 1$ の位数は $2 k$ であり、積 $\prod_{k \geq 1} Φ_{k}$ は収束する。 $x^{n}$ の係数を求めるには $k \leq n$ の因子だけ見ればよく（ $k > n$ の因子は $x^{n}$ 以下の次数では $1$ ）、有限積 $\prod_{k \leq n} Φ_{k}$ を展開した $x^{n}$ の係数は、各因子から項 $x^{k m_{k}}$ （ $m_{k} \in M$ ）を 1 つずつ選んで $\sum_{k} k m_{k} = n$ となる選び方の個数、すなわち $A (n)$ である。よって $F = \prod_{k \geq 1} Φ_{k}$ 。

ステップ 2（ $G$ の積表示）. $P (x) = \sum_{a \geq 0} p_{1} (a) x^{a}$ , $Q (x) = \sum_{b \geq 0} p_{2} (b) x^{b}$ とおく。ただし $p_{1} (a)$ は部分がすべて $4$ を法として $2$ に合同な $a$ の分割の個数、 $p_{2} (b)$ は部分がすべて $3$ の倍数である $b$ の分割の個数である。ステップ 1 と同じ議論（使える部分 $k$ ごとに重複度が任意で、因子は $\sum_{j \geq 0} x^{j k} = \frac{1}{1 - x ^{k}}$ ）により
$P = k \geq 1 k \equiv 2 (4) \prod \frac{1}{1 - x ^{k}} = j odd \prod \frac{1}{1 - x ^{2 j}}, Q = k \geq 1 \prod \frac{1}{1 - x ^{3 k}}$
である（ $k \equiv 2 (mod 4) ⟺ k = 2 j$ で $j$ が正の奇数）。 $B (n)$ は $a + b = n$ をみたす $(a, b)$ ごとの $p_{1} (a) p_{2} (b)$ の和なので、冪級数の積の定義から $B (n)$ は $P Q$ の $x^{n}$ の係数であり、 $G = P Q$ 。

ステップ 3（因子の変形）. $y$ を不定元として $Q [[y]]$ で計算する。 $(1 - y) (1 + y + y^{2}) = 1 - y^{3}$ より $\frac{1}{1 - y} = \frac{1 + y + y ^{2}}{1 - y ^{3}}$ であり、また $\sum_{j \geq 0} y^{3 j + 1} = \frac{y}{1 - y ^{3}}$ である（定数項が $1$ の冪級数は可逆なので割り算は正当）。 $M$ は非負整数全体から $3 j + 1$ $(j \geq 0)$ の形の数を除いたものだから
$m \in M \sum y^{m} = \frac{1}{1 - y} - \frac{y}{1 - y ^{3}} = \frac{1 + y + y ^{2} - y}{1 - y ^{3}} = \frac{1 + y ^{2}}{1 - y ^{3}} .$
さらに $(1 + y^{2}) (1 - y^{2}) = 1 - y^{4}$ より $1 + y^{2} = \frac{1 - y ^{4}}{1 - y ^{2}}$ なので
$m \in M \sum y^{m} = \frac{1 - y ^{4}}{( 1 - y ^{2} ) ( 1 - y ^{3} )} .$
$k \geq 1$ に対し $y = x^{k}$ を代入する（定数項 $0$ の冪級数の代入は環準同型 $Q [[y]] \to Q [[x]]$ を与えるので等式は保たれる）と
$Φ_{k} = \frac{1 - x ^{4 k}}{( 1 - x ^{2 k} ) ( 1 - x ^{3 k} )} .$

ステップ 4（無限積の整理）. 与えられた事実により因子ごとに積をとって
$F = \frac{\prod _{k \geq 1} ( 1 - x ^{4 k} )}{\prod _{k \geq 1} ( 1 - x ^{2 k} ) \prod _{k \geq 1} ( 1 - x ^{3 k} )}$
である（各無限積は、因子から $1$ を引いたものの位数が $\infty$ に発散するので収束する）。分母の $\prod_{k \geq 1} (1 - x^{2 k})$ を $k$ の偶奇で分けると、 $k = 2 i$ の因子は $1 - x^{4 i}$ なので
$k \geq 1 \prod (1 - x^{2 k}) = i \geq 1 \prod (1 - x^{4 i}) j odd \prod (1 - x^{2 j}) .$
これを代入し、定数項が $1$ で可逆な $\prod_{i \geq 1} (1 - x^{4 i})$ を約分すると
$F = \frac{1}{\prod _{j odd} ( 1 - x ^{2 j} ) \prod _{k \geq 1} ( 1 - x ^{3 k} )} = P Q .$

結論. ステップ 2 と 4 より $F = P Q = G$ 。両辺の $x^{n}$ の係数を比べて、すべての正の整数 $n$ について $A (n) = B (n)$ が成り立つ。 $■$

（確認: $n = 6$ のとき、 $A$ は $3 + 3, 2 + 2 + 2, 2 + 2 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1$ の $4$ 個。 $B$ は $(μ, ν) = ((6), \emptyset), ((2, 2, 2), \emptyset), (\emptyset, (6)), (\emptyset, (3, 3))$ の $4$ 個。）

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる