AlgoWikiAlgoWiki

  • Home
  • All pages
  • Categories
  • Help

This page


  • Edit
  • See history
  • See raw source
  • View on GitHub

Burnside's lemma

  • Combinatorics

Let $G$ be a finite group that acts on a set $X$. For each $g$ in $G$ let $X^g$ denote the set of elements in $X$ that are fixed by $g$. Then the number of orbits $$|X/G| = \frac{1}{|G|} \sum_{g\in G} |X^g|.$$

Problems

  • Necklace of Beads
  • TheBeautifulBoard
  • Magic Bracelet
  • Lucy and the Flowers
  • Sorting Machine
  • Pizza Toppings
  • Alphabet soup2
  • Drum Decorator1
  • Count the Necklaces
  • Cube Coloring

See also

  • Pólya enumeration theorem

External links

  • Burnsides Lemma
  • Burnside's lemma: orbit-counting theorem (cube and necklace colorings)
  • Burnside's lemma
  • Burnside's Lemma

  1. https://archive.algo.is/icpc/swerc/2011/SWERC-sols.pdf↩
  2. http://codeforces.com/blog/entry/18204?#comment-231223↩
AlgoWikiCC-BY-SA 4.0| fork us on GitHub