§ Counting necklackes with unique elements
Count number of ways to form a necklace with {1,2,…,n}
- Method 1: This is equivalent to counting ∣S5∣ modulo the subgroup generated by(12…). That subgroup has size 5. So the size is S5/5.
- Method 2: A cycle is an equivalence class of elements (a,b,c,d,e) along withall of its cyclic shifts ((b,c,d,e,a), (c,d,e,a,b), (d,e,a,b,c), (e,a,b,c,d)).We are to count the number of equivalence classes. First pick a canonical elementof each equivalence class of the form (1,p,q,r,s).