Burnside's lemma

バーンサイドの補題なるものがある。wikiはこちら。

数え上げの問題において、非常に有用である。

• Gを有限群で、集合Xに作用している。
  • 作用には右から、左からと言う二つのパターンがある。
  • 作用するとは、演算をしても閉じていて、（つまり、Gの要素をXの要素に噛ませても、Xの要素になる）
  • かつ、結合則と単位元の存在を満たすもの
• 
  • 左辺は軌道の数
  • 右辺は、
    • 分母の部分は集合Gの要素の数
      • 集合の大きさみたいなこと
    • 分子は、要素gを噛ませても変化しない（固定点と言われる）集合Xの要素の数
• 簡単な例題を考える。 
  • 例えば、立体４目並べがあった時に、そこに32個の白玉と32個の黒玉を入れることを考えるとする。
  • そしたら、全部で何通りの敷き詰め方があるでしょうか。ただし、鉛直軸周りの回転によってパターンの重なるものは同一視する。と言う問題を考えよう。
  • まず、作用している群は巡回群0, 90, 180, 270度回す操作に対応する。
  • 次に、バーンサイドの補題の式に代入していく。
    • 0の場合、それはそのまま、なので、64!/(32!32!)
    • 90、270の場合、結局4分の1ごとに同じ敷き詰め方になってほしいので、合わせて、2＊16!/(8!8!)
    • 180の場合、半分ごとに同じ構造が現れるので、32!/(16!16!)
  • よって求める総和は、となる。