代数的組合せ論の問題

ガウス二項係数（$q$ 二項係数）を
$${\left(\genfrac{}{}{0ex}{}{n}{k}\right)}_q=\frac{(q^n-1)(q^{n-1}-1)\cdots (q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1)\cdots (q-1)}$$
とおく。これは ${\mathbb{F}}_q^n$ の $k$ 次元部分空間の個数である。

ステップ 1（事象の設定） $3$ 次元部分空間全体を $\mathcal{G}$ とし、$i=1,\dots ,5$ に対して $A_i=\{W\in \mathcal{G}:e_i\in W\}$ とおく。求める個数は $|\mathcal{G}\setminus (A_1\cup \cdots \cup A_5)|$ である。

ステップ 2（共通部分の大きさ） $S\subseteq \{1,\dots ,5\}$, $|S|=j$ に対し、$U_S=⟨e_i:i\in S⟩$ は $j$ 次元である。$W$ が $e_i$ $(i\in S)$ をすべて含むことは $W\supseteq U_S$ と同値なので
$$\left|\bigcap _{i\in S}{A}_i\right|=\#\{W:U_S\subseteq W,\dim W=3\}.$$
$W\mapsto W/U_S$ は、$U_S$ を含む $3$ 次元部分空間と $V/U_S\cong {\mathbb{F}}_q^{5-j}$ の $(3-j)$ 次元部分空間との全単射を与えるから、この個数は ${\left(\genfrac{}{}{0ex}{}{5-j}{3-j}\right)}_q$（$j>3$ のときは $0$）である。

ステップ 3（包除原理）
$$N=\sum _{j=0}^3(-1{)}^j(\genfrac{}{}{0ex}{}{5}{j}){\left(\genfrac{}{}{0ex}{}{5-j}{3-j}\right)}_q={\left(\genfrac{}{}{0ex}{}{5}{3}\right)}_q-5{\left(\genfrac{}{}{0ex}{}{4}{2}\right)}_q+10{\left(\genfrac{}{}{0ex}{}{3}{1}\right)}_q-10{\left(\genfrac{}{}{0ex}{}{2}{0}\right)}_q.$$

ステップ 4（計算）
$${\left(\genfrac{}{}{0ex}{}{5}{3}\right)}_q={\left(\genfrac{}{}{0ex}{}{5}{2}\right)}_q=\frac{(q^5-1)(q^4-1)}{(q^2-1)(q-1)}=(1+q+q^2+q^3+q^4)(1+q^2)=1+q+2q^2+2q^3+2q^4+q^5+q^6,$$
$${\left(\genfrac{}{}{0ex}{}{4}{2}\right)}_q=\frac{(q^4-1)(q^3-1)}{(q^2-1)(q-1)}=(1+q^2)(1+q+q^2)=1+q+2q^2+q^3+q^4,$$
$${\left(\genfrac{}{}{0ex}{}{3}{1}\right)}_q=1+q+q^2,{\left(\genfrac{}{}{0ex}{}{2}{0}\right)}_q=1.$$
したがって
$$\begin{array}{rl}N& =(1+q+2q^2+2q^3+2q^4+q^5+q^6)-(5+5q+10q^2+5q^3+5q^4)+(10+10q+10q^2)-10\\ & =q^6+q^5-3q^4-3q^3+2q^2+6q-4.\end{array}$$

検算 $q=2$ のとき $N=64+32-48-24+8+12-4=40$。一方、直交補空間 $W^{\perp }$（標準内積）を考えると、$e_i\in W$ は $W^{\perp }$ のすべてのベクトルの第 $i$ 成分が $0$ であることと同値なので、$N$ は $2$ 次元部分空間 $U$ で全座標に台をもつものの個数に等しい。これを包除原理で数えると $155-5\cdot 35+10\cdot 7-10\cdot 1=40$ となり一致する。

よって答えは $q^6+q^5-3q^4-3q^3+2q^2+6q-4$ である。

「$e_i\in W$」という条件を $A_i$ とし、包除原理を使う。基底ベクトルのうち $k$ 個 $e_{i_1},\dots ,e_{i_k}$ を含む 3 次元部分空間 $W$ は、それらが張る $k$ 次元部分空間 $U$ を含む $W$ と同じである（$k\le 3$）。これは商空間 $V/U\cong {\mathbb{F}}_q^{5-k}$ の $(3-k)$ 次元部分空間と 1 対 1 に対応するので、個数は ${\left(\genfrac{}{}{0ex}{}{5-k}{3-k}\right)}_q$（ガウス二項係数）。$k\ge 4$ では $\dim W=3$ より 0 個。

求める個数は
$$N={\left(\genfrac{}{}{0ex}{}{5}{3}\right)}_q-5{\left(\genfrac{}{}{0ex}{}{4}{2}\right)}_q+10{\left(\genfrac{}{}{0ex}{}{3}{1}\right)}_q-10{\left(\genfrac{}{}{0ex}{}{2}{0}\right)}_q.$$

各項：
- ${\left(\genfrac{}{}{0ex}{}{5}{3}\right)}_q={\left(\genfrac{}{}{0ex}{}{5}{2}\right)}_q=\frac{(q^5-1)(q^4-1)}{(q-1)(q^2-1)}=(q^4+q^3+q^2+q+1)(q^2+1)=q^6+q^5+2q^4+2q^3+2q^2+q+1$
- ${\left(\genfrac{}{}{0ex}{}{4}{2}\right)}_q=(q^2+1)(q^2+q+1)=q^4+q^3+2q^2+q+1$
- ${\left(\genfrac{}{}{0ex}{}{3}{1}\right)}_q=q^2+q+1$
- ${\left(\genfrac{}{}{0ex}{}{2}{0}\right)}_q=1$

よって
$N=(q^6+q^5+2q^4+2q^3+2q^2+q+1)-5(q^4+q^3+2q^2+q+1)+10(q^2+q+1)-10=q^6+q^5-3q^4-3q^3+2q^2+6q-4$.

検算：$q\to 1$ の極限で各項は組合せ数 $\left(\genfrac{}{}{0ex}{}{5}{3}\right)-5\left(\genfrac{}{}{0ex}{}{4}{2}\right)+10\left(\genfrac{}{}{0ex}{}{3}{1}\right)-10=10-30+30-10=0$ となり、多項式の $q=1$ での値 $1+1-3-3+2+6-4=0$ と一致する。また $q=2$ では $64+32-48-24+8+12-4=40$（全体 155 個）で、非負の整数として妥当。