XORベクトル空間の基底の数え上げ

 \mathbb{F}_2 = \{0,1\} 上のベクトル空間  \mathbb{F}_2^n について。
線形独立な集合  S\subset\mathbb{F}_2^n とする。このとき、任意の  x\not\in\mathrm{span}\;S に対して  S\cup\{x\} もまた線形独立になる。ただし、 \mathrm{span}\;\emptyset = \{0\} である。また、線形独立な集合の部分集合もまた線形独立である。線形代数で基本的なことだけど、これらにより次がわかる。

  • 線形独立で大きさ  k\in\mathbb{N} の集合の個数は、 \prod_{i=0}^{k-1}{(2^n-2^i)}\;/k!
  • 特に、基底(順序を考えない)の個数は、 \prod_{i=0}^{n-1}{(2^n-2^i)}\;/n!

関連

A053601 - OEIS
ARC146 C - Even XOR (この問題をきっかけに記事を書いた)

感想

ちょっと前にも少し考えていたのだけど、そのときは思いつかなかった。サイズを  1 ずつ大きくすることを考えたらすぐなのだけど。(そしてこのブログ、やけにこの手の話題が好きだな...)