Applying the Pólya-Burnside Enumeration Theorem
Applying the Pólya-Burnside Enumeration Theorem
The Pólya–Burnside enumeration theorem is an extension of the Pólya–Burnside lemma, Burnside's lemma, the Cauchy–Frobenius lemma, or the orbit-counting theorem.
Given a finite group acting on a set of elements, the Pólya–Burnside enumeration theorem counts the number of elements of a given type as a function of their order.
In this Demonstration, a set of binary strings of a given length is acted upon by the group ×. The first component acts by word-reversing, while the second acts by bit-wise negation. Rewriting rules and corresponding orbits are explicitly worked out for these reflections.
n
2
2
The number of × orbits is +1+ for even and + for odd .
2
2
1
4
n
2
2
n
2
n
1
4
n
2
n+1
2
2
n