Permutation Cycles
DefinitionAnalyticCombinatorics_Ch9_LimitLaws_PermutationCyclesanalytic-combinatoricslean4limit-laws
The mathematical objects and operations are specified by the following source definitions.
def cycleH (n : ℕ) : ℝ :=
(harmonic n : ℝ)
def cycleP (n : ℕ) : Measure (CycleΩ n) :=
Measure.pi (fun i : Fin n => cycleBernoulliLaw i.1)
def cycleCount (n : ℕ) (ω : CycleΩ n) : ℝ :=
∑ i, ω i
def cycleBernoulliLaw (k : ℕ) : Measure ℝ :=
ENNReal.ofReal (1 - ((k : ℝ) + 1)⁻¹) • Measure.dirac (0 : ℝ) +
ENNReal.ofReal (((k : ℝ) + 1)⁻¹) • Measure.dirac (1 : ℝ)
abbrev CycleΩ (n : ℕ) := Fin n → ℝ
Definition code
import Mathlib
import Mathlib.MeasureTheory.Function.ConvergenceInDistribution
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Cycles in a random permutation
This file instantiates the local quasi-powers interface for the Feller coupling
model of the number of cycles in a uniform random permutation:
`C_n = sum_{k=1}^n B_k`, with independent Bernoulli variables
`P(B_k = 1) = 1 / k`.
-/
noncomputable section
open Complex Filter MeasureTheory ProbabilityTheory
open scoped Topology
namespace AnalyticCombinatorics
namespace Ch9
namespace LimitLaws
/-- The harmonic scale `H_n = sum_{k=1}^n 1/k`, as a real number. -/
def cycleH (n : ℕ) : ℝ :=
(harmonic n : ℝ)
end LimitLaws
end Ch9
end AnalyticCombinatorics
Source