有限体上の数え上げと包除原理

「どの列も零ベクトルでない階数 $r$ の行列」「指定した基底ベクトルをどれも含まない $k$ 次元部分空間」の個数を、零になる列の集合や含まれるベクトルの集合 $S$ について包除原理 $\sum_{S} (- 1)^{∣ S ∣} N_{S}$ （例: $N_{S} = (k - ∣ S ∣ n - ∣ S ∣)_{q}$ ）で $q$ の多項式として求められる

前提

有限体上の階数を指定した行列の個数（大学院数学代数的組合せ論）
一般の包除原理（大学数学離散数学・組合せ論）

この技能までの道筋（10 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

有限体上の階数を指定した行列の個数（大学院数学代数的組合せ論）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
包除原理（数学A 場合の数と確率）
同じものを含む順列・重複組合せ（数学A 場合の数と確率）
一般の包除原理（大学数学離散数学・組合せ論）

説明

有限体 $F_{q}$ 上の部分空間や行列のうち、「どの基底ベクトル $e_{i}$ も含まない」「どの列も零ベクトルでない」のように、 $n$ 個の『してはいけない条件』をすべて避けるものの個数を求める技能です。条件 $A_{i}$ を満たすものの集合について、 $S$ に含まれる条件をすべて満たすものの個数 $N_{S}$ は、たいてい次元の小さい同種の問題（ $q$ 二項係数 $(j m)_{q}$ や階数 $r$ の行列の個数）になります。それを包除原理 $\sum_{S} (- 1)^{∣ S ∣} N_{S}$ に入れれば、答えが $q$ の多項式として得られます。

なぜそうしてよいのか

包除原理は、どの条件 $A_{i}$ も満たさないものの個数を $\sum_{S \subseteq {1, \dots, n}} (- 1)^{∣ S ∣} ⋂_{i \in S} A_{i}$ で与えます（ $S = \emptyset$ のときの共通部分は全体とする）。有限体の場面で効くのは、 $⋂_{i \in S} A_{i}$ がまた「同じ種類で次元の小さいもの全体」と 1 対 1 に対応し、その個数が $∣ S ∣$ だけで決まることです。そのため和は $\sum_{s} (- 1)^{s} (s n) N_{s}$ にまとまります。

部分空間の場合: $F_{q}^{n}$ の $k$ 次元部分空間 $V$ で $e_{i} \in V$ となるものの集合を $A_{i}$ とします。 $V$ が $e_{i} (i \in S)$ をすべて含むことは、 $V \supseteq W_{S} = ⟨ e_{i} : i \in S ⟩$ （ $dim W_{S} = ∣ S ∣$ ）と同じです。 $U = ⟨ e_{j} : j \in / S ⟩$ とおくと、 $F_{q}^{n}$ の各元は座標を分けて $w + u$ （ $w \in W_{S}$ , $u \in U$ ）とただ 1 通りに書けます。 $V \supseteq W_{S}$ のとき、 $v \in V$ を $v = w + u$ と分けると $u = v - w \in V$ なので、 $V$ の各元は $W_{S}$ の元と $V \cap U$ の元の和にただ 1 通りに書けます（ $V = W_{S} \oplus (V \cap U)$ 、 $dim (V \cap U) = k - ∣ S ∣$ ）。よって $V \mapsto V \cap U$ は「 $W_{S}$ を含む $k$ 次元部分空間」から「 $U ≅ F_{q}^{n - ∣ S ∣}$ の $(k - ∣ S ∣)$ 次元部分空間」への全単射（逆写像は $V^{'} \mapsto W_{S} \oplus V^{'}$ ）で、 $N_{S} = (k - ∣ S ∣ n - ∣ S ∣)_{q}$ です（ $k - ∣ S ∣ < 0$ なら $0$ ）。

行列の場合も同じで、 $m \times n$ 行列の第 $i$ 列が零ベクトルであることを $A_{i}$ とすると、 $S$ の列がすべて零の階数 $r$ の行列は、残りの $n - ∣ S ∣$ 列からなる階数 $r$ の $m \times (n - ∣ S ∣)$ 行列と 1 対 1 に対応します（零列は列空間に何も加えないので階数は変わらない）。したがって $N_{S}$ は前提の技能の公式で $n$ を $n - ∣ S ∣$ に置き換えたものになります。

手順

避けたい条件 $A_{1}, \dots, A_{n}$ （「 $e_{i}$ を含む」「第 $i$ 列が零」など）をはっきり書く
条件の集合 $S$ （ $∣ S ∣ = s$ ）をすべて満たすものを、次元の小さい同種のものと 1 対 1 に対応させ、個数 $N_{s}$ を求める（例: $N_{s} = (k - s n - s)_{q}$ ）
$N_{s} = 0$ になる $s$ （ $s > k$ など）を確認し、和に残る項を決める
包除原理 $s = 0 \sum n (- 1)^{s} (s n) N_{s}$ を計算し、 $q$ の多項式として整理する
$q = 2$ などの小さな値で直接数えて検算する

例題

$q$ を素数べきとし、 $F_{q}^{3}$ の標準基底を $e_{1}, e_{2}, e_{3}$ とする。 $F_{q}^{3}$ の $2$ 次元部分空間のうち、 $e_{1}, e_{2}, e_{3}$ のどれも含まないものの個数を $q$ の式で求めよ。

例題の解答

【手順 1】 $2$ 次元部分空間 $V$ で $e_{i} \in V$ となるものの集合を $A_{i}$ （ $i = 1, 2, 3$ ）とする。求めるのは $A_{1}, A_{2}, A_{3}$ のどれにも属さない $V$ の個数。

【手順 2】 $∣ S ∣ = s$ のとき、 $S$ の基底ベクトルをすべて含む $2$ 次元部分空間の個数は $N_{s} = (2 - s 3 - s)_{q}$ 。
- $s = 0$ : $(2 3)_{q} = q^{2} + q + 1$
- $s = 1$ : $(1 2)_{q} = q + 1$
- $s = 2$ : $(0 1)_{q} = 1$

【手順 3】 $s = 3$ では $3$ つの基底ベクトルを含む $2$ 次元部分空間はないので $N_{3} = 0$ 。

【手順 4】包除原理より
$(0 3) (q^{2} + q + 1) - (1 3) (q + 1) + (2 3) \cdot 1 - 0 = q^{2} + q + 1 - 3 q - 3 + 3 = q^{2} - 2 q + 1 = (q - 1)^{2} .$

【手順 5】 $q = 2$ のとき、 $F_{2}^{3}$ の $2$ 次元部分空間は $a_{1} x_{1} + a_{2} x_{2} + a_{3} x_{3} = 0$ （ $(a_{1}, a_{2}, a_{3}) \neq = 0$ ）の $7$ 個で、 $e_{i}$ を含まないのは $a_{i} \neq = 0$ のとき。すべての $a_{i} \neq = 0$ となるのは $(1, 1, 1)$ の $1$ 個で、 $(2 - 1)^{2} = 1$ と一致する。

答え: $(q - 1)^{2}$

よくある誤り

$N_{s}$ を $(k - s n)_{q}$ のように全体の次元 $n$ のままで計算してしまう誤り。 $W_{S}$ を含む部分空間は残りの $n - s$ 次元の空間の部分空間に対応するので、正しくは $N_{s} = (k - s n - s)_{q}$ （例: $n = 3, k = 2, s = 1$ で $(1 2)_{q} = q + 1$ であり、 $(1 3)_{q} = q^{2} + q + 1$ ではない）
条件の集合 $S$ の選び方 $(s n)$ を掛け忘れる誤り。対称な条件では $\sum_{s} (- 1)^{s} (s n) N_{s}$ （例: 上の例の $s = 1$ の項は $- (q + 1)$ ではなく $- 3 (q + 1)$ ）
「 $e_{i}$ を含まない」を「 $e_{i}$ を使って作ったベクトル（ $e_{1} + e_{2}$ など）も含まない」と強く読んでしまう誤り。条件は $e_{i} \in V$ かどうかだけで（部分空間なので、これは $0$ でない $c e_{i}$ を含まないことと同じ）、 $e_{1} + e_{2} \in V$ でも $e_{1}, e_{2} \in / V$ ならよい。例: $q = 2$ で数える唯一の部分空間は ${0, e_{1} + e_{2}, e_{2} + e_{3}, e_{1} + e_{3}}$ で、 $e_{i} + e_{j}$ まで禁止と読むと個数を $0$ と誤る
零列を避ける行列の問題で、 $N_{S}$ を「 $S$ の列を除いた $m \times (n - ∣ S ∣)$ の行列全部」として階数の条件を落とす誤り。正しくは残りの列からなる階数 $r$ の行列の個数 $(r n - ∣ S ∣)_{q} \prod_{i = 0}^{r - 1} (q^{m} - q^{i})$ で、 $n - ∣ S ∣ < r$ なら $0$

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
$q$ を素数の累乗とし、 $F_{q}$ を位数 $q$ の有限体、 $V = F_{q}^{4}$ とする。 $e_{1}, e_{2}, e_{3}, e_{4}$ を $V$ の標準基底とする。 $V$ の $2$ 次元部分空間 $W$ のうち、 $e_{1} \in / W$ かつ $e_{2} \in / W$ をみたすものの個数を $q$ の多項式として求めよ。

有限体上の数え上げと包除原理

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題