Skip to content →

q類似

\(\mathbb{F}_q\) 上の \(n\) 次元ベクトル空間 \(V_n\) の部分空間がなす束の極大鎖
\(0 = V_0 \subset V_1 \subset \cdots \subset V_n\)
を取る方法は
\((q^n-1)(q^{n-1}-1)\cdots(q-1) = \boldsymbol {n }!\) 通りある。\(V_n\) の \(k\) 次元部分空間の個数を \(\boldsymbol{ n \choose k}\) と置く。極大鎖に \(k\) 次元部分空間は必ず含まれる。各 \(k\) 次元部分空間 \(V_k\) に対して、\(V_k\) を終点とする極大鎖は \(\boldsymbol {k}!\) 個、\(W\) を始点とする極大鎖は \(V_n / V_k \cong V_{n – k}\) より \(\boldsymbol {(n-k)!}\) 個ある。従って、$$\boldsymbol{ n \choose k} = \frac{\boldsymbol{n}!}{\boldsymbol{k}!\boldsymbol{(n-k)}!}$$である。
\(m \) \((\leq n)\) 個の独立なベクトルを選ぶ方法は \((q^{n}-1)(q^n – q) \cdots (q^n-q^{m-1}) = q^{{m-1 \choose 2}} \frac{\boldsymbol{n}!}{\boldsymbol{(n-m)}!}\) 通りある。\(m \) \((\geq n)\) 個のベクトルが \(V_n\) を張るような選び方は \((q^{m}-1)(q^{m} – q) \cdots (q^m-q^{n-1})\) 通りある。これは、ランク \(n\) の \(n \times m\) 行列の個数を数えている(ARC139F)。

\((\mathbb{Z}/p^k\mathbb{Z})^n\) の自由 \(\mathbb{Z} / p^k \mathbb{Z}\) 加群

\((\mathbb{Z}/p^k\mathbb{Z})^n\) の自由 \(\mathbb{Z} / p^k \mathbb{Z}\) 加群の部分自由加群が包含関係に関してなす束の極大鎖は \begin{align}
& \prod_{i=1}^n (p^{ik}-p^{i(k-1)}) \\
& \prod_{i=1}^n p^{i(k-1)}(p^i-1) \\
=& p^{(k-1){n + 1 \choose 2}} \boldsymbol{n}_p!\\
\end{align}
個ある(2桁目以降は自由に決められるとも解釈できる)。従って、階数 \(k\) の部分自由加群は\begin{align}
\frac{p^{(k-1){n + 1 \choose 2}} \boldsymbol{n}_p!}{p^{(k-1){k + 1 \choose 2}} \boldsymbol{n}_p!p^{(k-1){n – k + 1 \choose 2}} \boldsymbol{n}_p!}=
{\boldsymbol{n} \choose \boldsymbol{k}}_p p^{k(k-1)(n-k)}
\end{align} 個ある。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA