分割の統計量の母関数

部分の個数・相異なる値の個数などの統計量に変数 $t$ を付けた 2 変数母関数（例: $\prod_{k} (1 + \frac{t x ^{k}}{1 - x ^{k}})$ ）を作り、 $t$ で微分して $t = 1$ とおくなどして、 $\sum_{λ ⊢ n} d (λ)$ のような統計量の総和を求められる

前提

分割数と分割の母関数（大学数学離散数学・組合せ論）

この技能までの道筋（61 技能）

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
同じものを含む順列・重複組合せ（数学A 場合の数と確率）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
3 次式までの展開と因数分解（数学I 数と式）
微分係数と導関数の定義（数学II 微分法と積分法）
多項式の微分（数学II 微分法と積分法）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
1 次方程式の解き方（中学数学方程式）
比例・反比例の式とグラフ（中学数学関数）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
平方完成と 2 次関数のグラフ（数学I 2次関数）
2 次不等式（数学I 2次関数）
剰余の定理・因数定理と高次方程式（数学II 複素数と方程式）
増減表と極値（数学II 微分法と積分法）
等間隔にならんだ数の和（算数計算と数のきまり）
等差・等比数列の和と Σ （数学B 数列）
数列の極限（数学III 極限）
関数の極限（数学III 極限）
関数の連続性と中間値の定理（数学III 極限）
平均値の定理（数学III 微分法）
積と商の微分（数学III 微分法）
第 2 次導関数とグラフの凹凸（数学III 微分法）
合成関数の微分（数学III 微分法）
円の周の長さと面積（算数平面図形）
おうぎ形の弧の長さと面積（算数平面図形）
弧の長さからおうぎ形の中心角と面積を求める（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
三平方の定理（中学数学相似と三平方の定理）
特別な直角三角形の辺の比（中学数学相似と三平方の定理）
弧度法と単位円による三角関数（数学II 三角関数）
$sin x / x$ の極限（数学III 極限）
加法定理と 2 倍角・半角・積和の公式（数学II 三角関数）
三角関数の導関数（数学III 微分法）
根号の乗除と加減（中学数学数と式）
指数の拡張と指数関数（数学II 指数関数と対数関数）
対数の定義と性質（数学II 指数関数と対数関数）
自然対数の底 $e$ （数学III 極限）
指数関数・対数関数の導関数（数学III 微分法）
増減・凹凸・漸近線とグラフ（数学III 微分法）
テイラー展開（大学数学微分積分）
無限等比級数と無限級数（数学III 極限）
べき級数と収束半径（大学数学微分積分）
母関数と係数の取り出し（大学数学離散数学・組合せ論）
分割数と分割の母関数（大学数学離散数学・組合せ論）

説明

分割の母関数 $\prod_{k \geq 1} \frac{1}{1 - x ^{k}}$ に、もう 1 つの変数 $t$ を「数えたい量の個数だけ」掛けておくと、分割を大きさと統計量（部分の個数、相異なる値の個数など）の両方で数える 2 変数の母関数ができます。これを $t$ で微分してから $t = 1$ とおくと、 $n$ のすべての分割にわたる統計量の総和 $\sum_{λ ⊢ n} (統計量)$ の母関数が得られます。分割を 1 つずつ書き出さなくても、総和を $p (m)$ などの既知の数で表せるのが利点です。

なぜそうしてよいのか

$n$ の分割 $λ$ は、各 $k = 1, 2, 3, \dots$ について「部分 $k$ を何個使うか」という個数 $m_{k} \geq 0$ を決めることと同じで、 $n = \sum_{k} k m_{k}$ です。分割の母関数 $\prod_{k} \frac{1}{1 - x ^{k}} = \prod_{k} (1 + x^{k} + x^{2 k} + \dots)$ は、因子 $k$ から $x^{k m_{k}}$ を 1 つ選んで掛け合わせることで、各分割に $x^{∣ λ ∣}$ （ $∣ λ ∣$ は部分の和）を 1 回ずつ対応させています。ここで、数えたい量が増えるたびに $t$ を 1 つ掛けておきます。たとえば $d (λ)$ を $λ$ に現れる相異なる値の個数とすると、値 $k$ が現れる（ $m_{k} \geq 1$ ）ときだけ $t$ を掛ければよいので、因子 $k$ は
$1 + t (x^{k} + x^{2 k} + \dots) = 1 + \frac{t x ^{k}}{1 - x ^{k}}$
となり、 $F (x, t) = \prod_{k \geq 1} (1 + \frac{t x ^{k}}{1 - x ^{k}}) = \sum_{λ} t^{d (λ)} x^{∣ λ ∣}$ が成り立ちます。同様に、部分の個数 $ℓ (λ) = \sum_{k} m_{k}$ を数えたいなら、部分を 1 つ使うごとに $t$ を掛けて $\prod_{k} \frac{1}{1 - t x ^{k}} = \sum_{λ} t^{ℓ (λ)} x^{∣ λ ∣}$ です。

総和を取り出すには、 $t^{s}$ を $t$ で微分すると $s t^{s - 1}$ になり、 $t = 1$ とおくと $s$ が残ることを使います。したがって
$\frac{\partial F}{\partial t}_{t = 1} = λ \sum d (λ) x^{∣ λ ∣},$
つまり $x^{n}$ の係数が $\sum_{λ ⊢ n} d (λ)$ です。積の微分は、積の法則を因子の個数だけ繰り返して $\frac{\partial}{\partial t} \prod_{k} f_{k} = \sum_{k} f_{k}^{'} \prod_{j \neq = k} f_{j}$ となります。 $t = 1$ ではすべての因子がもとの $\frac{1}{1 - x ^{k}}$ に戻るので、 $\prod_{j \neq = k} f_{j}$ は $P (x) = \prod_{j} \frac{1}{1 - x ^{j}}$ を $f_{k} (x, 1)$ で割ったものです。

無限積を微分してよいか気になるかもしれませんが、 $x^{n}$ の係数に効くのは $k \leq n$ の因子だけです（ $k > n$ の因子は $x^{n}$ 以下の次数では $1$ と同じ）。そこで $k \leq n$ の有限個の因子の積で考えれば、ふつうの多項式（べき級数）の微分だけで同じ結論が得られます。

手順

数えたい統計量が分割のどの選択で 1 増えるかを確かめ、因子 $k$ （部分 $k$ の個数の選び方）に $t$ を付ける。相異なる値の個数なら $1 + \frac{t x ^{k}}{1 - x ^{k}}$ 、部分の個数なら $\frac{1}{1 - t x ^{k}}$
2 変数母関数 $F (x, t) = \prod_{k \geq 1} (因子_{k})$ を書き、 $F = \sum_{λ} t^{(統計量)} x^{∣ λ ∣}$ となっていることを確認する
積の微分 $\frac{\partial}{\partial t} \prod_{k} f_{k} = \sum_{k} f_{k}^{'} \prod_{j \neq = k} f_{j}$ で $t$ について微分する
$t = 1$ を代入し、 $P (x) = \prod_{k} \frac{1}{1 - x ^{k}}$ を使って $(簡単な級数) \times P (x)$ の形に整理する
$x^{n}$ の係数を取り出し、 $p (m)$ などの既知の値を代入して総和を計算する

例題

分割 $λ$ に現れる相異なる値の個数を $d (λ)$ とする（例: $d (3 + 1 + 1) = 2$ ）。6 のすべての分割についての和 $\sum_{λ ⊢ 6} d (λ)$ を求めよ。

例題の解答

手順 1: 値 $k$ を少なくとも 1 回使うときだけ $t$ を 1 つ掛けるので、因子 $k$ は $1 + t (x^{k} + x^{2 k} + \dots) = 1 + \frac{t x ^{k}}{1 - x ^{k}}$ 。

手順 2: $F (x, t) = \prod_{k \geq 1} (1 + \frac{t x ^{k}}{1 - x ^{k}}) = \sum_{λ} t^{d (λ)} x^{∣ λ ∣}$ 。

手順 3: $f_{k} = 1 + \frac{t x ^{k}}{1 - x ^{k}}$ とおくと $\frac{\partial f _{k}}{\partial t} = \frac{x ^{k}}{1 - x ^{k}}$ なので
$\frac{\partial F}{\partial t} = k \geq 1 \sum \frac{x ^{k}}{1 - x ^{k}} j \neq = k \prod f_{j} .$

手順 4: $t = 1$ では $f_{j} = 1 + \frac{x ^{j}}{1 - x ^{j}} = \frac{1}{1 - x ^{j}}$ だから $\prod_{j \neq = k} f_{j} = (1 - x^{k}) P (x)$ 。よって
$\frac{\partial F}{\partial t}_{t = 1} = k \geq 1 \sum \frac{x ^{k}}{1 - x ^{k}} (1 - x^{k}) P (x) = (k \geq 1 \sum x^{k}) P (x) = \frac{x}{1 - x} P (x) .$

手順 5: $\frac{x}{1 - x} = x + x^{2} + x^{3} + \dots$ と $P (x) = \sum_{m} p (m) x^{m}$ の積の $x^{6}$ の係数は $p (0) + p (1) + \dots + p (5)$ 。 $p (0) = 1, p (1) = 1, p (2) = 2, p (3) = 3, p (4) = 5, p (5) = 7$ より
$λ ⊢ 6 \sum d (λ) = 1 + 1 + 2 + 3 + 5 + 7 = 19.$
（確認: 6 の 11 個の分割 $6, 51, 42, 411, 33, 321, 3111, 222, 2211, 21111, 111111$ の $d$ は順に $1, 2, 2, 2, 1, 3, 2, 1, 2, 2, 1$ で、和は $19$ 。）

答え: $19$

よくある誤り

微分する前に $t = 1$ を代入してしまう誤り。 $F (x, 1) = P (x)$ の $x^{6}$ の係数は分割の個数 $p (6) = 11$ にすぎない。正しくは $\frac{\partial F}{\partial t}_{t = 1}$ の係数を見る
係数の取り出しで和の範囲をずらしてしまう誤り。 $\frac{x}{1 - x} P (x)$ の $x^{n}$ の係数を $p (0) + \dots + p (n)$ とすると $n = 6$ で $30$ になってしまう。 $\frac{x}{1 - x}$ は $x^{1}$ から始まるので、正しくは $\sum_{m = 0}^{n - 1} p (m)$
統計量と因子の対応を取り違える誤り。相異なる値の個数に $\prod_{k} \frac{1}{1 - t x ^{k}}$ を使うと、部分の個数 $ℓ (λ)$ の総和（ $n = 6$ では $35$ ）を求めてしまう。値 $k$ が現れるかどうかだけで $t$ を 1 つ付けるので、正しくは $\prod_{k} (1 + \frac{t x ^{k}}{1 - x ^{k}})$
2 乗の和 $\sum d (λ)^{2}$ を $\frac{\partial ^{2} F}{\partial t ^{2}}_{t = 1}$ の係数としてしまう誤り。2 回微分で出るのは $\sum d (λ) (d (λ) - 1)$ なので、正しくは $(\frac{\partial ^{2} F}{\partial t ^{2}} + \frac{\partial F}{\partial t})_{t = 1}$ の係数

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
正の整数 $n$ の分割とは、正の整数の非増加列 $λ = (λ_{1} \geq λ_{2} \geq \dots \geq λ_{ℓ} > 0)$ で $λ_{1} + \dots + λ_{ℓ} = n$ を満たすものをいい、このとき $λ ⊢ n$ と書く。分割 $λ$ の部分のうち $2$ に等しいものの個数を $m_{2} (λ)$ とする（たとえば $m_{2} ((3, 2, 2)) = 2$ , $m_{2} ((4, 1, 1, 1)) = 0$ ）。
$λ$ を $0$ 以上の整数すべての分割（ $0$ の分割は空の分割 $1$ 個とする）にわたらせた 2 変数母関数
$F (x, t) = n \geq 0 \sum λ ⊢ n \sum t^{m_{2} (λ)} x^{n}$
を用いて、
$λ ⊢ 7 \sum m_{2} (λ)$
を求めよ。

分割の統計量の母関数

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題