An exact finite sum for the mean number of mapping components
ProvedAnalyticCombinatorics.Ch2.Mappings.MappingComponentsNS.expected_components_eqanalytic-combinatoricslean4mappingssymbolic-method
Let be all functions from to itself. A point is periodic if for some integer . Define in the real numbers. For , let be the number of cyclic restrictions of the permutation induced by on its periodic points: a restriction is a nonempty subset of periodic points with a permutation whose iterates have one orbit, agreeing with on that subset. Thus is the source functional-graph component count. For ,
Both the averaging denominator and the factor in each summand are part of the formula.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch2_Mappings_MappingComponents import Mathlib set_option autoImplicit true set_option relaxedAutoImplicit false set_option maxSynthPendingDepth 3 /-! # Components of random mappings The component count is defined as the number of nonempty single-cycle restrictions of the permutation induced by a mapping on its periodic core. A candidate cycle `C` of a map is counted exactly when the ambient map restricts to a cyclic permutation on `C`; this is equivalent to being one cycle of the periodic-core permutation. -/ open Filter Asymptotics open scoped BigOperators Topology open AnalyticCombinatorics AnalyticCombinatorics.Ch2 AnalyticCombinatorics.Ch2.Mappings AnalyticCombinatorics.Ch2.Mappings.MappingComponentsNS open AnalyticCombinatorics.Ch2.Mappings.ConnectedMappingsNS open AnalyticCombinatorics.Ch2.Mappings.RamanujanQNS
Formal statement
theorem AnalyticCombinatorics.Ch2.Mappings.MappingComponentsNS.expected_components_eq {n : ℕ} (hn : 0 < n) :
(∑ f : Fin n → Fin n, (componentCount f : ℝ)) / (n : ℝ)^n
= ∑ k ∈ Finset.Icc 1 n,
(n.descFactorial k : ℝ) / ((k : ℝ) * (n : ℝ)^k) := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).