↓ メインコンテンツへスキップ
組合せ論、楽しい！

【月刊組合せ論 Natori】ヤコビの三重積公式とオイラーの五角数定理【2023 年 2 月号】

·
代数的組合せ論
箱星
著者
箱星
のんびり暮らしたい。
目次

月刊組合せ論 Natori は面白そうな組合せ論のトピックを紹介していく企画です。今回はヤコビの三重積公式とオイラーの五角数定理について説明します。個人的にかなり美しい等式だと思っています。

ヤコビの三重積公式
#

次の等式をヤコビの三重積公式といいます。

∏i=1∞(1+xqi)(1+x−1qi−1)(1−qi)=∑n∈Zqn(n+1)/2xn \prod_{i=1}^{\infty}(1+xq^i)(1+x^{-1}q^{i-1})(1-q^i)=\sum_{n\in\mathbb{Z}}q^{n(n+1)/2}x^n

左辺は無限積、右辺は無限和です。この 2 つが等号で結ばれているのは面白いですね。

証明
#

証明方法は色々ありますが、組合せ論的なものを紹介します。

f(x)=∏i=1∞(1+xqi)(1+x−1qi−1) f(x)=\prod_{i=1}^{\infty}(1+xq^i)(1+x^{-1}q^{i-1})

とおきます。f(x)f(x) を展開したときの xnx^n の係数を cn=cn(q)c_n=c_n(q) とします。つまり

f(x)=∑n∈Zcnxn f(x)=\sum_{n\in\mathbb{Z}}c_nx^n

です。このとき、f(xq)=1+x−1q−11+xqf(x)=x−1q−1f(x)f(xq)=\frac{1+x^{-1}q^{-1}}{1+xq}f(x)=x^{-1}q^{-1}f(x) なので

∑n∈Zcnxnqn=∑n∈Zcnxn−1q−1 \sum_{n\in\mathbb{Z}}c_nx^nq^n=\sum_{n\in\mathbb{Z}}c_nx^{n-1}q^{-1}

となります。xnx^n の係数を比較して、cn+1=qn+1cnc_{n+1}=q^{n+1}c_n を得ます。1+2+⋯+n=n(n+1)21+2+\cdots+n=\frac{n(n+1)}{2} なので、cn=qn(n+1)/2c0c_n=q^{n(n+1)/2}c_0 となります。あとは c0c_0 を求めればよいです。c0c_0 は f(x)f(x) の定数項なので、展開することで

c0=∑qa1+⋯+an+b1+⋯+bn c_0=\sum q^{a_1+\cdots+a_n+b_1+\cdots+b_n}

（ここで和は n≥0,1≤a1<⋯<an,0≤b1<⋯<bnn\ge 0, 1\le a_1<\cdots<a_n, 0\le b_1<\cdots<b_n となるもの全体を動く）となります。数列 a,ba,b の組は次のようにヤング図形と一対一に対応します。

よって c0c_0 は

c0=∑λ:ヤング図形q∣λ∣=∑n=0∞p(n)qn c_0=\sum_{\lambda:\text{ヤング図形}}q^{|\lambda|}=\sum_{n=0}^{\infty}p(n)q^n

となることがわかりました。ここで p(n)p(n) はサイズ nn のヤング図形の個数、すなわち分割数です。よく知られているように分割数の母関数は

c0=∏i=1∞11−qi c_0=\prod_{i=1}^{\infty}\frac{1}{1-q^i}

となります。以上により、ヤコビの三重積公式が得られました。

オイラーの五角数定理
#

次の等式をオイラーの五角数定理といいます。

∏i=1∞(1−qi)=∑n∈Z(−1)nqn(3n+1)/2 \prod_{i=1}^{\infty}(1-q^i)=\sum_{n\in\mathbb{Z}}(-1)^nq^{n(3n+1)/2}

左辺は分割数の母関数の逆数です。右辺には五角数が現れます。

この定理は競技プログラミングにおいても有用です。この問題で用いられます。

この定理はヤコビの三重積公式から証明することができます。新しい変数 zz を用意し、ヤコビの三重積公式に q=z3,x=−z−1q=z^3, x=-z^{-1} を代入することで、左辺は

∏i=1∞(1−z3i−1)(1−z3i−2)(1−z3i)=∏i=1∞(1−zi) \prod_{i=1}^{\infty}(1-z^{3i-1})(1-z^{3i-2})(1-z^{3i})=\prod_{i=1}^{\infty}(1-z^i)

右辺は

∑n∈Zz3n(n+1)/2(−z−1)n=∑n∈Z(−1)nzn(3n+1)/2 \sum_{n\in\mathbb{Z}}z^{3n(n+1)/2}(-z^{-1})^n=\sum_{n\in\mathbb{Z}}(-1)^nz^{n(3n+1)/2}

となり、オイラーの五角数定理が得られました。

なお、組合せ論を用いて直接オイラーの五角数定理を証明することも可能です。英語版 Wikipedia をご覧ください。

分割数
#

分割数 p(n)p(n) の母関数はオイラーの五角数定理の左辺の逆数であることから

∑n=0∞p(n)xn=1∏i(1−xi)=1∑m∈Z(−1)mxm(3m+1)/2 \sum_{n=0}^{\infty}p(n)x^n=\frac{1}{\prod_{i}(1-x^i)}=\frac{1}{\sum_{m\in\mathbb{Z}}(-1)^mx^{m(3m+1)/2}}

が得られます。この式から分割数の漸化式が得られるので、p(1),p(2),…,p(N)p(1),p(2),\ldots,p(N) を時間計算量 O(NN)O(N\sqrt{N}) で計算できます。

さらに形式的冪級数のテクニックを用いると O(Nlog⁡N)O(N\log N) に高速化することもできます。

おわりに
#

ヤコビの三重積公式はまだまだ面白いことがたくさんありますが、今回は割愛させていただきます。またいつか書くかもしれません。

今後も月刊組合せ論 Natori では様々なトピックを紹介していきたいと思います。応援のほどよろしくお願いします！

参考文献
#

  1. Flajolet, Philippe; Sedgewick, Robert. Analytic combinatorics. Cambridge: Cambridge University Press (2009).

ヤコビの三重積公式の証明を参考にした文献は忘れてしまいました……。