↓ メインコンテンツへスキップ
組合せ論、楽しい！
Featured image for キューティーなカタラン数

キューティーなカタラン数

箱星
著者
箱星
のんびり暮らしたい。
目次

この記事は日曜数学 Advent Calendar 2025 の 7 日目の記事です。

日曜数学について、まずは個人的なことを中心に話そうと思います。私は今年の 6 月から働き始めました。その前は数学の修士課程に通っており、数学が本業でした。博士課程に進むかはかなり悩みましたが、結局行かないことにしました。今は働きながら数学の勉強をしたり記事を書いたりと、趣味の数学活動を続けています。今の私がやっていることは日曜数学と呼ぶにふさわしいのではないかと思いました。

これからも楽しく数学を続けていきたいと思います。できれば数学の世界で業績を残せたらいいなとも思います。

自分語りが長くなってしまいましたが、本題に移っていきます。私が魅力的に感じている数学のトピックを紹介します。

カタラン数
#

次のような数え上げ問題を考えてみましょう。

nn 個の ( と nn 個の ) を使って、括弧の対応がとれている文字列を作る方法は何通りありますか？

例えば (())() は OK ですが ())( はダメです。

この問題は次のようにして経路の問題に言い換えることができます。原点 (0,0)(0,0) から出発します。( があったら上に 1 つ進み、) があったら右に 1 つ進みます。(())() の場合次のような経路になります。

image

ゴールは (n,n)(n,n) になります。括弧の対応がとれているという条件は、経路が常に y≥xy\ge x の領域にあるという条件に言い換えられます。

経路の問題に言い換えられましたが、この問題は「鏡像法」というテクニックで解くことができます。簡単にいうと (0,0)(0,0) から (n,n)(n,n) へのすべての経路から y≥xy\ge x という条件をみたさない経路を除きますが、条件をみたさない経路が別の経路と一対一対応することを使います。これについて解説している記事はたくさんあるのでここでは省略しますが、答えは

Cn=(2nn)−(2nn−1)=1n+1(2nn) C_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}

となります。この数はカタラン数と呼ばれており、組合せ論では中心的な数です。ここでは括弧列の個数や y≥xy\ge x の領域上にある経路の個数に等しいことを見ましたが、実は

  • 二分木の個数
  • 正多角形の三角形分割の個数
  • 最長増加部分列の長さが 2 以下の順列の個数

など、様々なオブジェクトの個数に等しいことが知られており、そのようなオブジェクトは 100 種類を超えます。まさに「カタラン数は至る所にある！」ですね。

q 類似
#

qq 類似は、大雑把にいうと q→1q\to 1 の極限で元に戻るようなものです。

例えば非負整数 nn の qq 類似は [n]q=1+q+⋯+qn−1[n]_q=1+q+\cdots+q^{n-1} です。q→1q\to 1 のとき [n]q→n[n]_q\to n になります。こんなものはいくらでもあるじゃん、と思いますが、基本的にはこの [n]q[n]_q が非負整数 nn の唯一の qq 類似として扱われます。

階乗 n!n! の qq 類似は [n]q!=[1]q[2]q⋯[n]q[n]_q!=[1]_q[2]_q\cdots [n]_q として定義されます。さらに二項係数の qq 類似が

[nk]q=[n]q![k]q![n−k]q! \genfrac[]{0pt}0nk_q=\frac{[n]_q!}{[k]_q![n-k]_q!}

により定義されます。

カタラン数の q 類似
#

カタラン数の qq 類似を考えましょう。非負整数と二項係数の qq 類似を定義したので、それを用いて

1[n+1]q[2nn]q \frac{1}{[n+1]_q}\genfrac[]{0pt}0{2n}{n}_q

と定義するのが自然に見えます。

しかし、カタラン数には別の qq 類似も知られています。それは

∑πqarea(π) \sum_{\pi}q^{\mathrm{area}(\pi)}

です。ここで π\pi は (0,0)(0,0) から (n,n)(n,n) への経路であって領域 y≥xy\ge x 上にあるもの全体を動くとし、area(π)\mathrm{area}(\pi) は経路 π\pi と直線 y=xy=x で挟まれた領域内にあるマスの個数とします。（ただし、直線 y=xy=x により二等分されるマスは数えないものとします。）

さきほどの図の場合 area(π)=1\mathrm{area}(\pi)=1 です。

例を挙げましょう。便宜上、前者を Cnbinom(q)C_n^{\mathrm{binom}}(q)、後者を Cnarea(q)C_n^{\mathrm{area}}(q) と書きます。

  • C1binom(q)=1C_1^{\mathrm{binom}}(q)=1
  • C2binom(q)=q2+1C_2^{\mathrm{binom}}(q)=q^2+1
  • C3binom(q)=q6+q4+q3+q2+1C_3^{\mathrm{binom}}(q)=q^6 + q^4 + q^3 + q^2 + 1
  • C4binom(q)=q12+q10+q9+2q8+q7+2q6+q5+2q4+q3+q2+1C_4^{\mathrm{binom}}(q)=q^{12} + q^{10} + q^9 + 2q^8 + q^7 + 2q^6 + q^5 + 2q^4 + q^3 + q^2 + 1
  • C1area(q)=1C_1^{\mathrm{area}}(q)=1
  • C2area(q)=q+1C_2^{\mathrm{area}}(q)=q+1
  • C3area(q)=q3+q2+2q+1C_3^{\mathrm{area}}(q)=q^3 + q^2 + 2q + 1
  • C4area(q)=q6+q5+2q4+3q3+3q2+3q+1C_4^{\mathrm{area}}(q)=q^6 + q^5 + 2q^4 + 3q^3 + 3q^2 + 3q + 1

両者は異なっていますが、どちらもカタラン数の qq 類似です。

マクドナルド多項式
#

話は変わりますが、マクドナルド多項式も組合せ論では非常に重要です。

対称多項式は基本対称多項式を使って表せるという事実を聞いたことがある人も多いと思います。他にも重要な対称多項式があります。代表的なものは 5 つあり

  • モノミアル対称多項式
  • 基本対称多項式
  • 完全対称多項式
  • 冪和対称多項式
  • シューア多項式

です。この中でもシューア多項式は特に重要で、組合せ論の他にも

  • 表現論
  • 幾何学
  • 数理物理

など、様々な分野に現れます。

シューア多項式を一般化したものとして、ホール・リトルウッド多項式があります。これは tt というパラメータをもつ多項式で、t=0t=0 のときシューア多項式になります。他にもジャック多項式など、様々なシューア多項式の一般化が誕生しました。

そのような流れの中で、マクドナルドはホール・リトルウッド多項式やジャック多項式の共通の一般化である多項式を発見します。現在マクドナルド多項式と呼ばれているこの多項式は q,tq,t という 2 つのパラメータをもつ多項式で、q=0q=0 のときホール・リトルウッド多項式、q=tq=t のときシューア多項式になります。q,tq,t をうまく選ぶことでジャック多項式も得ることができます。

そんなマクドナルド多項式を定義するには、内積と直交性を用いるものや、固有関数を用いるものなどがあります。少し難しいのと、私があまり勉強できてない部分なので解説を割愛します。すみません。

このマクドナルド多項式はよく PλP_{\lambda} と書かれます。λ\lambda は λ1≥λ2≥⋯≥λl≥0\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_l\ge 0 をみたす整数列で、しばしばヤング図形と同一視されます。この PλP_{\lambda} を変形したものとして H~λ\tilde{H}_{\lambda} があり、これもマクドナルド多項式と呼ばれることがあります。

抽象的な話が多くなってしまったので、具体的に計算をします。SageMath という数式処理システムを用いてマクドナルド多項式を計算します。

sage: Sym = SymmetricFunctions(FractionField(QQ['q','t']))
sage: Ht = Sym.macdonald().Ht()
sage: Ht[3,1].expand(2)
x0^4 + (q^2 + q + t + 1)*x0^3*x1 + (2*q^2 + q*t + q + t + 1)*x0^2*x1^2 + (q^2 + q + t + 1)*x0*x1^3 + x1^4

これは

H~(3,1)(x0,x1)=x04+(q2+q+t+1)x03x1+(2q2+qt+q+t+1)x02x12+(q2+q+t+1)x0x13+x14 \begin{align*} \tilde{H}_{(3,1)}(x_0,x_1) &= x_0^4 + (q^2 + q + t + 1)x_0^3x_1 \\ &+ (2q^2 + qt + q + t + 1)x_0^2x_1^2 \\ &+ (q^2 + q + t + 1)x_0x_1^3 + x_1^4 \end{align*}

を計算しています。確かに対称多項式ですね。

組合せ論のナブラ
#

ヤング図形 λ\lambda の転置、すなわち行と列の入れ替えを λ′\lambda' とします。さらに n(λ)=∑i(i−1)λin(\lambda)=\sum_i(i-1)\lambda_i とします。

∇H~λ=qn(λ′)tn(λ)H~λ\nabla\tilde{H}_{\lambda}=q^{n(\lambda')}t^{n(\lambda)}\tilde{H}_{\lambda} をみたす作用素 ∇\nabla があります。ナブラ演算子ゲームでお馴染みのナブラとはおそらく別物です。

これも SageMath で計算してみましょう。

sage: Ht[3,2].nabla()
q^4*t^2*McdHt[3, 2]

(3,2)(3,2) の転置は (2,2,1)(2,2,1) であり、n((3,2))=2,n((2,2,1))=4n((3,2))=2, n((2,2,1))=4 なので確かに合っています。

このナブラを他の対称多項式に適用するということが興味深いです。ここでは基本対称多項式 ene_n にナブラを施してみましょう。

sage: for i in range(1,5):
....:     print(e[i].nabla())
....:
e[1]
e[1, 1] + (q+t-1)*e[2]
e[1, 1, 1] + (q^2+q*t+t^2+q+t-2)*e[2, 1] + (q^3+q^2*t+q*t^2+t^3-q^2-t^2-q-t+1)*e[3]
e[1, 1, 1, 1] + (q^3+q^2*t+q*t^2+t^3+q^2+q*t+t^2+q+t-3)*e[2, 1, 1] + (q^4+q^3*t+q^2*t^2+q*t^3+t^4-q^3-t^3-q-t+1)*e[2, 2] + (q^5+q^4*t+q^3*t^2+q^2*t^3+q*t^4+t^5+q^3*t+q^2*t^2+q*t^3-2*q^2-q*t-2*t^2-q-t+2)*e[3, 1] + (q^6+q^5*t+q^4*t^2+q^3*t^3+q^2*t^4+q*t^5+t^6-q^5-t^5-q^4-q^3*t-q^2*t^2-q*t^3-t^4-q^2*t-q*t^2+q^2+t^2+q+t-1)*e[4]

ここで係数の和をとってみましょう。

S1=1S2=q+tS3=q3+q2t+qt2+t3+qtS4=q6+q5t+q4t2+q3t3+q2t4+qt5+t6+q4t+q3t2+q2t3+qt4+q3t+q2t2+qt3 \begin{align*} S_1 &= 1 \\ S_2 &= q+t \\ S_3 &= q^3 + q^2t + qt^2 + t^3 + qt \\ S_4 &= q^6 + q^5t + q^4t^2 + q^3t^3 + q^2t^4 + qt^5 + t^6 \\ &+ q^4t + q^3t^2 + q^2t^3 + qt^4 + q^3t + q^2t^2 + qt^3 \end{align*}

勘のいい読者は、お気づきでしょうか。

なぜ、前半でカタラン数の話をしたあと、突然マクドナルド多項式の話を始めたのか。その答えが明らかになります！

実は、この係数の和 SnS_n に q=t=1q=t=1 を代入すると、カタラン数になります！

一見無関係な 2 つの話題がつながるのは面白いですね！

さらにそれだけではありません！t=1t=1 を代入すると

  • S1∣t=1=1S_1|_{t=1}=1
  • S2∣t=1=q+1S_2|_{t=1}=q+1
  • S3∣t=1=q3+q2+2q+1S_3|_{t=1}=q^3+q^2+2q+1
  • S4∣t=1=q6+q5+2q4+3q3+3q2+3q+1S_4|_{t=1}=q^6+q^5+2q^4+3q^3+3q^2+3q+1

となります。これはカタラン数の qq 類似 Cnarea(q)C_n^{\mathrm{area}}(q) に等しいです！

カタラン数にはもう 1 つの qq 類似がありましたが

Cnbinom(q)=q(n2)Sn∣t=q−1 C_n^{\mathrm{binom}}(q)=q^{\binom{n}{2}}S_n|_{t=q^{-1}}

が成り立っています。2 つの qq 類似には共通の親玉がいたのですね！

この SnS_n は q,tq,t カタラン数と呼ばれており、Cn(q,t)C_n(q,t) と表します。

q,t カタラン数を深掘り
#

Cnarea(q)C_n^{\mathrm{area}}(q) は area という関数を用いて定義されました。q,tq,t カタラン数は新たな関数 ff を用いて

Cn(q,t)=∑πqarea(π)tf(π) C_n(q,t)=\sum_{\pi}q^{\mathrm{area}(\pi)}t^{f(\pi)}

と定義できないでしょうか？

できます。dinv と呼ばれる関数と bounce と呼ばれる関数が上の式をみたすことが知られています。q,tq,t カタラン数を組合せ論的に記述できました。

ところで、上記の q,tq,t カタラン数の例を見て、他にも気づいたことはないでしょうか？

実は q,tq,t を入れ替えても等しくなります。つまり Cn(q,t)=Cn(t,q)C_n(q,t)=C_n(t,q) です。

これを組合せ論的な記述に代入すると、例えば

∑πqarea(π)tdinv(π)=∑πqdinv(π)tarea(π) \sum_{\pi}q^{\mathrm{area}(\pi)}t^{\mathrm{dinv}(\pi)}=\sum_{\pi}q^{\mathrm{dinv}(\pi)}t^{\mathrm{area}(\pi)}

となります。これを組合せ論的に証明するには、経路 π\pi を別の経路にうつす全単射 φ\varphi であって

  • area(φ(π))=dinv(π)\mathrm{area}(\varphi(\pi))=\mathrm{dinv}(\pi)
  • dinv(φ(π))=area(π)\mathrm{dinv}(\varphi(\pi))=\mathrm{area}(\pi)

をみたすものを構成すればよいことになります。

しかし、私の知る限りではこの問題は未解決のようです。なお、q,tq,t カタラン数は同値な定義方法がいくつか知られていますが、定義によっては q,tq,t 対称性は自明です。組合せ論だからといって簡単になるとは限りません。そこが組合せ論の奥深いところですね。

上は (area, dinv) と (dinv, area) の間の対応と見ることができますが、他にも (area, bounce), (bounce, area) との間の対応という問題も考えられます。

その他の話題
#

q,tq,t カタラン数やマクドナルド多項式は他にも魅力的な話題がたくさんあります。現在でも様々な研究が行われています。いくつかキーワードを挙げると

  • n!n! 予想
  • シャッフル予想
  • マクドナルド多項式の組合せ論的公式
  • 結び目理論との関係

他にもいろいろあります。2026 年はこういった話題を勉強していきたいです。

おわりに
#

カタラン数は歴史があり有名ですが、その qq 類似、さらにはその tt 類似が発見され、魅力は計り知れません。そんな q,tq,t カタラン数、とってもキューティーですね！

参考文献
#

  • Haglund, James. The q,tq,t-Catalan numbers and the space of diagonal harmonics. With an appendix on the combinatorics of Macdonald polynomials. University Lecture Series 41. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4411-3/pbk). viii, 167 p. (2008).