代数的組合せ論の問題

方針は、与えられた事実を $q$ 二項係数による反転公式（包除原理の $q$ 類似）で逆に解き、$n=5$ の場合を計算することです。

1. $q$ 二項定理からの補題

$q$ 二項定理
$$\prod _{i=0}^{m-1}(1+q^{i}x)=\sum _{j=0}^m{q}^{\left(\genfrac{}{}{0ex}{}{j}{2}\right)}{\left[\begin{array}{c}m\\ j\end{array}\right]}_q{x}^j$$
で $x=-1$ とおきます。$m\ge 1$ のとき左辺には因子 $1-q^0=0$ が含まれるので、
$$\sum _{j=0}^m(-1{)}^j{q}^{\left(\genfrac{}{}{0ex}{}{j}{2}\right)}{\left[\begin{array}{c}m\\ j\end{array}\right]}_q={\delta }_{m,0}$$
が成り立ちます。

2. $q$ 反転公式

$f(n)=[n{]}_q!$、$g(k)=D_k(q)$ とおくと、事実は $f(n)={\sum }_k{\left[\begin{array}{c}n\\ k\end{array}\right]}_{q}g(k)$ と書けます。このとき
$$g(n)=\sum _{k=0}^n(-1{)}^{n-k}{q}^{\left(\genfrac{}{}{0ex}{}{n-k}{2}\right)}{\left[\begin{array}{c}n\\ k\end{array}\right]}_{q}f(k)$$
が成り立つことを示します。

右辺に $f(k)$ の式を代入し、等式 ${\left[\begin{array}{c}n\\ k\end{array}\right]}_q{\left[\begin{array}{c}k\\ j\end{array}\right]}_q={\left[\begin{array}{c}n\\ j\end{array}\right]}_q{\left[\begin{array}{c}n-j\\ k-j\end{array}\right]}_q$ を使うと、右辺は
$$\sum _{j=0}^{n}g(j){\left[\begin{array}{c}n\\ j\end{array}\right]}_q\sum _{k=j}^n(-1{)}^{n-k}{q}^{\left(\genfrac{}{}{0ex}{}{n-k}{2}\right)}{\left[\begin{array}{c}n-j\\ n-k\end{array}\right]}_q$$
となります。$m=n-j$、$i=n-k$ とおくと、内側の和は ${\sum }_{i=0}^m(-1{)}^i{q}^{\left(\genfrac{}{}{0ex}{}{i}{2}\right)}{\left[\begin{array}{c}m\\ i\end{array}\right]}_q={\delta }_{m,0}$ です。したがって $j=n$ の項だけが残り、右辺は $g(n)$ に等しくなります。

ここで ${\left[\begin{array}{c}n\\ k\end{array}\right]}_q[k{]}_q!=\frac{[n{]}_q!}{[n-k{]}_q!}$ を使い、$j=n-k$ と書き直すと
$$D_n(q)=\sum _{j=0}^n(-1{)}^j{q}^{\left(\genfrac{}{}{0ex}{}{j}{2}\right)}\frac{[n{]}_q!}{[j{]}_q!}$$
を得ます。

3. $n=5$ の計算

$j=0$ の項 $[5{]}_q!$ と $j=1$ の項 $-[5{]}_q!$ は打ち消し合います。残りは
$$D_5(q)=q[3{]}_q[4{]}_q[5{]}_q-q^3[4{]}_q[5{]}_q+q^6[5{]}_q-q^{10}$$
です。各項を展開します。

• $[3{]}_q[4{]}_q=1+2q+3q^2+3q^3+2q^4+q^5$ です。これに $[5{]}_q$ を掛けると $1+3q+6q^2+9q^3+11q^4+11q^5+9q^6+6q^7+3q^8+q^9$ となります。したがって第 1 項は $q+3q^2+6q^3+9q^4+11q^5+11q^6+9q^7+6q^8+3q^9+q^{10}$ です。
• $[4{]}_q[5{]}_q=1+2q+3q^2+4q^3+4q^4+3q^5+2q^6+q^7$ です。したがって第 2 項は $-(q^3+2q^4+3q^5+4q^6+4q^7+3q^8+2q^9+q^{10})$ です。
• 第 3 項は $q^6+q^7+q^8+q^9+q^{10}$、第 4 項は $-q^{10}$ です。

次数ごとに係数を足し合わせます。

よって
$$D_5(q)=q+3q^2+5q^3+7q^4+8q^5+8q^6+6q^7+4q^8+2q^9$$
です。

4. 検算

• $q=1$ とおくと $1+3+5+7+8+8+6+4+2=44$ となり、完全順列の個数 $D_5=44$ と一致します。
• $\mathrm{maj}=9$ となるのは、降下集合が $\{2,3,4\}$、つまり $\sigma (2)=5$ で以降が減少する置換です。このうち完全順列は $25431$ と $35421$ の $2$ 個で、$q^9$ の係数と一致します。
• $\mathrm{maj}=1$ となる完全順列は $51234$ のみで、$q^1$ の係数と一致します。

事実から D_n(q) = [n]_q! − Σ_{k<n} [n k]_q D_k(q) と再帰的に求められる。

小さい n は次のとおり。
- D_0=1, D_1=0
- D_2=q（置換 21 のみ）
- D_3=q+q^2（231 は maj 2、312 は maj 1 で、事実からも確かめた）
- D_4=q+2q^2+2q^3+2q^4+q^5+q^6（係数の和は 9）

D_4 は [4]!=1+3q+5q^2+6q^3+5q^4+3q^5+q^6 から Σ_{k<4}[4 k]D_k=1+2q+3q^2+4q^3+3q^4+2q^5 を引いて得た。

n=5 のとき、[5]_q! = [4]_q!·[5]_q の係数は 1,4,9,15,20,22,20,15,9,4,1（次数 0〜10）。

次に Σ_{k<5}[5 k]D_k を計算する。ここで [5 2]=[5 3]=1+q+2q^2+2q^3+2q^4+q^5+q^6、[5 4]=[5]_q=1+q+q^2+q^3+q^4 である。
- D_0 の項は 1。
- k=2 の項は q[5 2] で、係数は次数 1〜7 に 1,1,2,2,2,1,1。
- k=3 の項は (q+q^2)[5 2] で、係数は次数 1〜8 に 1,2,3,4,4,3,2,1。
- k=4 の項は [5]D_4 で、係数は次数 1〜10 に 1,3,5,7,8,8,6,4,2,1。

これらの和の係数は次数 0〜10 に 1,3,6,10,13,14,12,9,5,2,1（総和 76=1+10+20+45）。

引き算をして D_5 = (4−3)q+(9−6)q^2+(15−10)q^3+(20−13)q^4+(22−14)q^5+(20−12)q^6+(15−9)q^7+(9−5)q^8+(4−2)q^9+(1−1)q^10。

よって D_5(q)=q+3q^2+5q^3+7q^4+8q^5+8q^6+6q^7+4q^8+2q^9。

検算として q=1 で 1+3+5+7+8+8+6+4+2=44 となり、5 次の完全順列の個数 44 に一致する。