Burnside's lemma
E586575
Burnside's lemma is a result in group theory and combinatorics that counts distinct configurations under symmetries by averaging the number of fixed points of group actions.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
lemma in group theory
ⓘ
result in combinatorics ⓘ |
| alsoKnownAs |
Cauchy–Frobenius lemma
NERFINISHED
ⓘ
Cauchy–Frobenius–Burnside lemma NERFINISHED ⓘ |
| appearsIn | Burnside's book "Theory of Groups of Finite Order" NERFINISHED ⓘ |
| appliesTo |
finite groups
ⓘ
group actions on finite sets ⓘ |
| assumption |
group action is well-defined
ⓘ
group is finite ⓘ |
| category |
enumerative combinatorics
ⓘ
group actions in algebra ⓘ |
| coreIdea | counts orbits by averaging fixed points of group elements ⓘ |
| field |
combinatorics
ⓘ
group theory ⓘ |
| formula | |X/G| = (1/|G|) * Σ_{g∈G} |Fix(g)| ⓘ |
| generalizedBy | Polya enumeration theorem NERFINISHED ⓘ |
| historicalAttribution |
ideas developed by Frobenius
ⓘ
ideas trace back to Cauchy ⓘ often misattributed solely to Burnside ⓘ |
| implies | number of orbits equals average of fixed point counts ⓘ |
| mathematicalDomain |
abstract algebra
ⓘ
discrete mathematics ⓘ |
| namedAfter | William Burnside NERFINISHED ⓘ |
| relatesConcept |
Polya enumeration theorem
NERFINISHED
ⓘ
class equation ⓘ orbit-stabilizer principle ⓘ |
| requires |
knowledge of basic group theory
ⓘ
understanding of permutations ⓘ |
| statementInformal | the number of distinct configurations up to symmetry equals the average number of configurations fixed by each group element ⓘ |
| symbolDefinition |
Fix(g) is the subset of X fixed by group element g
ⓘ
G is a finite group acting on X ⓘ X is a finite set with a group action of G ⓘ X/G denotes the set of orbits of X under G ⓘ |
| typeOfCounting | orbit counting ⓘ |
| typicalExample |
counting distinct bead necklaces under rotation
ⓘ
counting distinct colorings of faces of a cube ⓘ counting symmetrically distinct vertex colorings of polygons ⓘ |
| usedFor |
counting colorings up to symmetry
ⓘ
counting combinatorial objects modulo group actions ⓘ counting unlabeled graphs ⓘ enumeration under dihedral symmetry ⓘ enumeration under rotational symmetry ⓘ |
| usesConcept |
fixed point
ⓘ
group ⓘ group action ⓘ orbit ⓘ set ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.