XORベクトル空間の基底の数え上げ
体 上のベクトル空間 について。
線形独立な集合 とする。このとき、任意の に対して もまた線形独立になる。ただし、 である。また、線形独立な集合の部分集合もまた線形独立である。線形代数で基本的なことだけど、これらにより次がわかる。
- 線形独立で大きさ の集合の個数は、
- 特に、基底(順序を考えない)の個数は、
関連
A053601 - OEIS
ARC146 C - Even XOR (この問題をきっかけに記事を書いた)
感想
ちょっと前にも少し考えていたのだけど、そのときは思いつかなかった。サイズを ずつ大きくすることを考えたらすぐなのだけど。(そしてこのブログ、やけにこの手の話題が好きだな...)