161225

Carlitz-Riordan q-Catalan number(1)

Handbook of Enumerative Combinatorics のDefinition 14.10.19 によれば、

Carlitz-Riordan q-Catalan number C_n(q) は次のように定義される。

C_{n + 1}(q) = Sum_{k = 0..n} q^k * C_k(q) * C_{n - k}(q)

with C_0(q) = 1.

C_n(q) を順番に求めると次のようになる。

C_1(q) = 1 * C_0(q) * C_0(q) = 1,

C_2(q) = 1 * C_0(q) * C_1(q) + q * C_1(q) * C_0(q) = q + 1,

C_3(q) = 1 * C_0(q) * C_2(q) + q * C_1(q) * C_1(q) + q^2 * C_2(q) * C_0(q) = q^3 + q^2 + 2q + 1,

…

なお、C_1(q), C_2(q), … , C_10(q) までが、

http://www.math.uiuc.edu/~llpku/qtCatalan/qCatalan.html

に載っている。