Cauchy's formula for the number of permutations of a given cycle type
ProvedFamousTheorems.cauchy_cycle_type_count_7bCauchy's formula for the number of permutations of a given cycle type. Let be a finite set with elements and let be a multiset of integers with sum . The number of permutations of whose nontrivial cycles have lengths given by is
where is the number of times occurs in . If or contains an entry less than , there are no such permutations.
The formula gives the sizes of the conjugacy classes of and, dividing into , the orders of their centralizers. It underlies the cycle index of the symmetric group and Pólya enumeration. It follows from the orbit–stabilizer theorem, since the centralizer of a permutation of type is generated by rotations of the cycles, permutations of equal-length cycles, and permutations of the fixed points.
Formalization note. Mathlib's Equiv.Perm.card_of_cycleType. The cycle type omits fixed points, so is the number of fixed points. The division is natural number division, and it is exact in the first case.
import Mathlib
namespace FamousTheorems
theorem cauchy_cycle_type_count_7b (α : Type*) [DecidableEq α] [Fintype α] (m : Multiset ℕ) :
({g : Equiv.Perm α | g.cycleType = m} : Finset (Equiv.Perm α)).card =
if m.sum ≤ Fintype.card α ∧ ∀ a ∈ m, 2 ≤ a then
(Fintype.card α).factorial /
((Fintype.card α - m.sum).factorial * m.prod * ∏ n ∈ m.toFinset, (Multiset.count n m).factorial)
else 0 := by sorry
end FamousTheorems