The Orbit/Stabiliser Theorem is a simple theorem in group theory. Thanks to Tim Gowers for the proof I outline here - I find it much more intuitive than the proof that was presented in lectures, and it involves equivalence relations (which I think are wonderful things).
Proof: We fix an element , and define two equivalence relations: iff , and if , where .
Now, these are the same relation (we will check that they are indeed equivalence relations - don’t worry!). This is because .
And is an equivalence relation, almost trivially: it is reflexive since is obviously true; it is symmetric, since ; it is transitive similarly.
Now, it is clear that the number of equivalence classes of is just the size of the orbit , because for each equivalence class there is one member of the orbit (with representing ), and for each member of the orbit there is one equivalence class (with being represented solely by ).
It is also clear that the size of the stabiliser is just the size of an equivalence class of , since for each member of the stabiliser, we have that so , while for each for each member of we have that by definition of - but all these are different (because otherwise we could cancel a ) so
And the equivalence classes of partition the set , so (size of equivalence class) times (number of equivalence classes) is just - but this is exactly what we required.