REFERENCE SHEET

Group actions & counting

Study a group by what it moves and what it fixes.

Before this Groups & subgroups

|Orb(x)| = [G:Stab(x)]

Definitions

Action

A map G×X→X with e·x=x and (gh)·x=g·(h·x). Equivalently, a homomorphism G→Sym(X).

Orbit

Orb(x)={g·x:g∈G}, the points reachable from x.

Stabilizer

Stab(x)={g:g·x=x}, a subgroup of G.

Key theorems

Orbit–stabilizer

The map g Stab(x)↦g·x is a bijection. For finite G, |Orb(x)|=|G|/|Stab(x)|.

Burnside counting lemma

For a finite group acting on a finite set, the number of orbits equals (1/|G|)Σg |Fix(g)|.

Notable applications

Counting up to symmetry

Count colorings, arrangements, or configurations while identifying rotations or other allowed symmetries.

Permutation representations

An action on a finite set yields a linear action on the vector space with that set as a basis.

Work it out

Try before revealing

01 / Count

How many binary colorings of three labeled vertices are distinct up to cyclic rotation?

Hint

Apply Burnside to the three rotations.

Solution

The identity fixes all 8 colorings. Each nonidentity rotation fixes the 2 monochromatic colorings. Thus the count is (8+2+2)/3=4.

02 / Compute

S₃ acts on {1,2,3}. Find the stabilizer of 1 and its orbit.