文献あり

major indexによるq-Narayana数とq-Catalan数

309

概要

Catalan数に関係する数として Narayana数
$\begin{array}{r} N_{n, k} ≜ \frac{1}{n} (\binom{n}{k}) (\binom{n}{k - 1}) \end{array}$
がある．Narayana数はピークを $k$ 個持つ，サイズ $n$ のDyck路の数に等しい．
またここから，Narayana数の $k$ にわたる和は，Catalan数であることがわかる．

本稿ではNarayana数の $q$ 類似を解説する．
Dyck路にmajor indexという統計量を入れて数え上げると，母関数として $q$ -Narayana数
$\begin{array}{r} N_{n, k} (q) = \frac{q^{n + k (k - 1)}}{[n]_{q}} {(\binom{n}{k})}_{q} {(\binom{n}{k - 1})}_{q} \end{array}$
が出てきて，さらにその和は $q$ -Catalan数
$\begin{array}{r} C_{n} (q) ≜ \frac{q^{n}}{[n + 1]_{q}} {(\binom{2 n}{n})}_{q} \end{array}$
になることが知られている [1]．

準備

二種のステップ $A ≜ (1, 0), B ≜ (0, 1)$ を使って $(0, 0)$ から $(n, n)$ まで行くパスのうち，直線 $y = x$ より上に行かないものをDyck路という．
Dyck路は，以前の記事 [5]で紹介した正方格子路の一種である． $(0, 0)$ から $(n, n)$ へ行くDyck路の集合を $Dyck (n)$ と書く．
例えば下図は $Dyck (5)$ の元の例．
Dyck路の例と，そのmajの値

major indexについて復習

集合 $Dyck (n)$ から自然数への写像
$\begin{array}{r} maj : Dyck (n) \to N \end{array}$
を，以前の記事 [5]で定めたように定義する．復習すると，Dyck路
$\begin{array}{r} ω = ω_{1} \dots ω_{2 n}, ω_{i} \in {A, B} \end{array}$
に対して，descentと呼ばれる集合 $D (ω)$ を
$\begin{array}{r} D (ω) ≜ {i ∣ ω_{i} = A, ω_{i + 1} = B} \end{array}$
と定め，その和
$\begin{array}{r} maj (ω) ≜ \sum_{i \in D (ω)} i \end{array}$
をmajor indexと呼ぶのであった．

上の図の例でいうと，パスの中で"┘"みたいになってる場所がdescentである．

descentの数ごとのDyck路の数え上げ

descentの要素数が $k$ 個であるようなDyck路の集合を
$\begin{array}{r} Dyck (n, k) ≜ {ω \in Dyck (n) ∣ # D (ω) = k} \end{array}$
とかく．
この集合をmajor indexに関して数え上げる母関数を
$\begin{array}{r} N_{n, k} (q) ≜ \sum_{ω \in Dyck (n, k)} q^{maj (ω)} \end{array}$
とかき， $q$ -Narayana数という．

$q$ -Narayana数の積表示

まず， $q$ -Narayana数は以下のようにSchur関数の特殊値である．

q-Narayana数のSchur関数による表示

$\begin{array}{r} N_{n, k} (q) = q^{n} s_{⟨ 2^{k - 1} ⟩} (q, q^{2}, \dots, q^{n - 1}) \end{array}$
が成り立つ．但し， $s$ はSchur関数を表し， $⟨ 2^{k - 1} ⟩$ は縦が $k - 1$ で横が $2$ の長方形のヤング図形を表す．

Dyck路からparallelogram polyomino (staircase polygonとも呼ばれる)への全単射を考える [4]．
サイズ $n$ で $k$ 列のparallelogram polyomino (略してポリオミノ)とは， $(0, 0)$ から $(k, n + 1 - k)$ へ，ステップ $A, B$ を使って行く二本のパスの組で， $(0, 0)$ と $(k, n + 1 - k)$ 以外では交差しないものである．

サイズ $n$ で $k$ 列のポリオミノの集合と，集合 $Dyck (n, k)$ の間に一対一対応が存在する (下図)．
Dyck路ポリオミノの一対一対応
この全単射の正確な定義は文献 [4,Exercises 57]に任せるとして，めっちゃ雑に説明すると，Dyck路のステップ $A$ (下図でいうと➘)の情報がポリオミノの「上の線（図の赤い線）」で表され， $B$ (図でいうと➚)の情報が「下の線（図の青い線）」で表されるのである．（下図参照）
全単射のめっちゃ雑な説明

この全単射を曇りなき眼で見ると，重みを入れることができる．
つまり，ポリオミノが置かれているグリッドの横線 (ステップ $B$ )に下図下側のように重みを入れると，ポリオミノが通る横線の重みの積が，Dyck路のmajor indexに一致する．
major indexと，横線の重みの積が一致する様子

つまり， $q$ -Narayana数 $N_{n, k} (q)$ は，サイズ $n$ で $k$ 列のポリオミノを，上図の重みのもとで数え上げる母関数に一致する．
ここで， Lindström–Gessel–Viennotの補題を使うと，その母関数は基本対称式の行列式として
$\begin{array}{r} N_{n, k} (q) = q^{n} \det [\begin{array}{ll} e_{k - 1} (q, \dots, q^{n - 1}) & e_{k} (q, \dots, q^{n - 1}) \\ e_{k - 2} (q, \dots, q^{n - 1}) & e_{k - 1} (q, \dots, q^{n - 1}) \end{array}] \end{array}$
と表せて，Jacobi-Trudi公式 ( Nägelsbach–Kostka恒等式ともいうらしい)を使うとそれはSchur関数を使って
$\begin{array}{r} N_{n, k} (q) = q^{n} s_{⟨ 2^{k - 1} ⟩} (q, q^{2}, \dots, q^{n - 1}) \end{array}$
と書ける．

q

-Narayana数の積表示

上の定理で求めた式は以下の通り計算できて積型になる．
$\begin{aligned} N_{n, k} (q) & = q^{n} s_{⟨ 2^{k - 1} ⟩} (q, q^{2}, \dots, q^{n - 1}) \\ = \frac{q^{n + k (k - 1)}}{[n]_{q}} {(\binom{n}{k})}_{q} {(\binom{n}{k - 1})}_{q} \end{aligned}$

やることはWeylの指標公式
$\begin{array}{r} s_{λ} (x_{1}, \dots, x_{n}) = \frac{\det {(x_{i}^{λ_{j} + n - j})}_{i, j = 1}^{n}}{\det {(x_{i}^{n - j})}_{i, j}^{n}} \end{array}$
に突っ込んで，右辺のVandermonde行列式を計算するだけなのだが，特にヤング図形が長方形のときは計算した結果がすでに平面分割のMacMahon公式
$\begin{array}{r} s_{⟨ t^{r} ⟩} (q, q^{2}, \dots, q^{r + s}) = q^{r (r - 1) t / 2} \prod_{i = 1}^{r} \prod_{j = 1}^{s} \prod_{k = 1}^{t} \frac{1 - q^{i + j + k - 1}}{1 - q^{i + j + k - 2}} \end{array}$
として知られているから，ここでは簡単のためそちらを使う．
突っ込んで計算するだけなのであとは省略する．
Weylの指標公式とかMacMahon公式とかに関しては，文献 [3] が詳しいので，そちらを見ると良い．

$q$ -Catalan数の積表示

$q$ -Narayana数の $k$ にわたる和
$\begin{array}{r} C_{n} (q) ≜ \sum_{k = 1}^{n - 1} N_{n, k} (q) \end{array}$
を $q$ -Catalan数という．

q

-Catalan数の積表示

$\begin{array}{r} C_{n} (q) = \frac{q^{n}}{[n + 1]_{q}} {(\binom{2 n}{n})}_{q} \end{array}$

Heineの和公式 [2]
$\begin{array}{r} _{2} ϕ_{1} (q^{- n}, b; c; q, c q^{n} / b) = \frac{(c / b; q)_{n}}{(c; q)_{n}} \end{array}$
を使う．
$\begin{aligned} \sum_{k = 1}^{n} N_{n, k} (q) & = \sum_{k = 1}^{n} \frac{q^{n + k (k - 1)}}{[n]} {(\binom{n}{k})}_{q} {(\binom{n}{k - 1})}_{q} \\ = q^{n} \cdot_{2} ϕ_{1} (q^{- n + 1}, q^{- n}; q^{2}; q, q^{2 n + 1}) \\ = q^{n} \frac{(q^{n + 2}; q)_{n - 1}}{(q^{2}; q)_{n - 1}} \\ = \frac{q^{n}}{[n + 1]_{q}} {(\binom{2 n}{n})}_{q} \end{aligned}$

参考文献

[1]

T. K. Petersen, Eulerian Numbers, Birkhäuser Advanced Texts, Birkhäuser Verlag, 2015

[2]

G. Gasper, M. Rahman, Basic Hypergeometric Series, Secon Edition, Encyclopedia of Mathematics and its Applications 96, Cambridge univ. press, 2004

[3]

高崎金久, 線形代数と数え上げ, 増補版, 日本評論社, 2021

[4]

R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015

[5]

major indexによるq-二項係数, 閲覧日 2023年9月5日, https://mathlog.info/articles/JfEhzAfpKzCutuv06tim

投稿日：2023年9月5日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

little q-Laguerre

1679

Do everything bijectively.

他の人のコメント

コメントはありません。

読み込み中

little q-Laguerre

major indexによるq-Narayana数とq-Catalan数

概要
準備
$q$-Narayana数の積表示
$q$-Catalan数の積表示
参考文献

major indexによるq-Narayana数とq-Catalan数

概要

準備

major indexについて復習

descentの数ごとのDyck路の数え上げ

q-Narayana数の積表示

q-Catalan数の積表示

参考文献

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

$q$ -Narayana数の積表示

$q$ -Catalan数の積表示