Counting connected functional graphs on a labelled finite set
ProvedAnalyticCombinatorics.Ch2.Mappings.ConnectedMappingsNS.card_connectedMappingsanalytic-combinatoricslean4mappingssymbolic-method
Let be all functions from to itself. A point is periodic if for some integer . Define in the real numbers. Call connected when, for all , there exist with . For ,
Here is the descending factorial.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch2_Mappings_ConnectedMappings import Mathlib namespace AnalyticCombinatorics.Ch2.Mappings.RamanujanQNS end AnalyticCombinatorics.Ch2.Mappings.RamanujanQNS set_option autoImplicit true set_option relaxedAutoImplicit false set_option maxSynthPendingDepth 3 /-! # Connected random mappings This file banks the iteration-level periodic-core facts used in the standard cyclic-core decomposition of connected mappings. The exact enumeration is not completed here. -/ open Filter Asymptotics open scoped BigOperators Topology open AnalyticCombinatorics AnalyticCombinatorics.Ch2 AnalyticCombinatorics.Ch2.Mappings AnalyticCombinatorics.Ch2.Mappings.ConnectedMappingsNS open AnalyticCombinatorics.Ch2.Mappings.ForestCountNS open AnalyticCombinatorics.Ch2.Mappings.RamanujanQNS
Formal statement
theorem AnalyticCombinatorics.Ch2.Mappings.ConnectedMappingsNS.card_connectedMappings {n : ℕ} (hn : 0 < n) :
Fintype.card {f : Fin n → Fin n // MappingConnected f}
= ∑ k ∈ Finset.Icc 1 n, (n - 1).descFactorial (k - 1) * n ^ (n - k) := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).