とある組合せ論の命題の母関数を用いた証明

これは鯵坂もっちょさん企画のアドベントカレンダーの記事です。

私がブログを更新するのはほぼ一年ぶりで、最後に書いたのは昨年の素数大富豪アドベントカレンダーの記事でした。素数大富豪の日である12月13日に札幌で素数大富豪に興じていたのが約一年前。そう考えると2018年はあっという間でした。
今回の話題は、昨年の今頃に私が修論で書いていた内容の一部です。

※体裁修正中につきPC推奨

都合によりちょっとガロアなので（＝時間がないので）*1、分割数と母関数の知識等を仮定して進めます。

まず、整数の分割を扱いやすくするため、非負整数 $n$ の分割全体と一対一に対応する集合
$\begin{equation} \\ \\ U(n):=\{ \{ u_i \} _{i=1}^\infty :非負整数列| \sum_{i=1}^\infty i \cdot u_i =n \} \end{equation} \\$
を用意しておきます。一対一の対応は、 $U(n)$ の各元(非負整数列) $\{ u_i \} _{i=1}^\infty$ を、正整数 $i$ をちょうど $u_i$ 個成分に持つような分割に対応させることで得られます。

たとえば $n=4$ のときは次のようになっています。...
$\begin{equation} \\ \\ U(4)=\{ \{4,0,0,0,0,...\} , \{2,1,0,0,0,...\} , \{1,0,1,0,0,...\} , \{0,2,0,0,0,...\} , \{0,0,0,1,0,...\} \} \end{equation}$

(いずれも第5項以降は0)

$1×4 + 2×0 + 3×0 + 4×0 + 5×0 + ... = 1 + 1 + 1 + 1 \\ 1×2 + 2×1 + 3×0 + 4×0 + 5×0 + ... = 1 + 1 + 2 \\ 1×1 + 2×0 + 3×1 + 4×0 + 5×0 + ... = 1 + 3 \\ 1×0 + 2×2 + 3×0 + 4×0 + 5×0 + ... = 2 + 2 \\ 1×0 + 2×0 + 3×0 + 4×1 + 5×0 + ... = 4 \\ \\$
いきなり分かりにくい内容かもしれません。「分割数を扱いやすい形で表した」という認識だけでもOKです。

本題に入りましょう。次の問題を考えます。

非負整数 $n\in \mathbb{Z}_{>0}$ に対して

$\begin{equation} T(n) := \sum_{\{ u_i\} \in U(n)} \prod_{i=1}^{\infty} \frac{1}{i^{u_i} \cdot u_i !} \end{equation}$

を計算せよ．

再びn=4を例に計算してみます。前述のとおり $U(4)$ の元は以下の5つです。
$\begin{equation} \\ \{4,0,0,0,0,0,...\} ：分割「 1 + 1 + 1 + 1 」に対応\\ \{2,1,0,0,0,0,...\} ：分割「 1 + 1 + 2 」に対応\\ \{1,0,1,0,0,0,...\} ：分割「 1 + 3 」に対応\\ \{0,2,0,0,0,0,...\} ：分割「 2 + 2 」に対応\\ \{0,0,0,1,0,0,...\} ：分割「 4 」に対応\\ \end{equation} \\$
これら5つの数列（分割）のそれぞれについて、無限積 $\prod_{i=1}^{\infty} \frac{1}{i^{u_i} \cdot u_i !}$ を計算します。ただし無限積といっても、数列の0の項は無限積において1を掛けることに対応するので考えなくてよく、実質いくつかの分数の掛け算をするだけになります。
$\begin{equation} \\ \{4,0,0,0,0,0,...\} → \frac{1}{1^4 \cdot 4!} = \frac{1}{24} \\ \{2,1,0,0,0,0,...\} → \frac{1}{1^2 \cdot 2!} × \frac{1}{2^1 \cdot 1!} = \frac{1}{4} \\ \{1,0,1,0,0,0,...\} → \frac{1}{1^1 \cdot 1!} × \frac{1}{3^1 \cdot 1!} = \frac{1}{3} \\ \{0,2,0,0,0,0,...\} → \frac{1}{2^2 \cdot 2!} = \frac{1}{8} \\ \{0,0,0,1,0,0,...\} → \frac{1}{4^1 \cdot 1!} = \frac{1}{4} \\ \end{equation} \\$
最後にこの総和を計算します。
$\begin{equation} \\ \frac{1}{24} + \frac{1}{4} + \frac{1}{3} + \frac{1}{8} + \frac{1}{4} = 1 \end{equation} \\$
よって、 $T(4)=1$ と計算できました。

5つの分数を足したらぴったり1になったわけですが、勘のいい方はお気づきのとおり、これは偶然ではありません。というわけで、次の命題を示します。

任意の $n\in \mathbb{Z}_{>0}$ に対して

\begin{equation}
T(n):=\sum_{\{ u_i\} \in U(n)} \prod_{i=1}^{\infty} \frac{1}{i^{u_i} \cdot u_i !} =1
\end{equation}

が成り立つ．

私は修論研究の過程で、この事実を今から紹介する証明とともに発見しました。とはいえ適当な本を漁れば書いてあるような初等的な事実のような気もします（実際、研究中に複数の方から群論の知識を用いて比較的簡単に証明できる旨の指摘を受けました）。以下の証明に簡潔さや明快さはあまりありませんが、これこそが「私の好きな証明」です。

f:id:K-Miura:20181219225908j:plain