Ternary binomial sequence and Stirling scale
DefinitionAnalyticCombinatorics_Ch7_SingularityApp_TernaryTreesanalytic-combinatoricscoefficient-asymptoticslean4
The natural sequence is Nat.choose(3n,n)/(2n+1), using natural division, and the real Stirling comparison scale is sqrt(2n*pi)(n/exp(1))^n. A tree datatype or cardinality equivalence is not introduced by these definitions.
Definition code
import Mathlib import Mathlib.Combinatorics.Enumerative.Catalan import Mathlib.Data.Nat.Choose.Cast import Mathlib.Analysis.SpecialFunctions.Gaussian.GaussianIntegral import Mathlib.NumberTheory.Real.GoldenRatio import Mathlib.Analysis.SpecialFunctions.Gamma.Beta import Mathlib.Analysis.Analytic.Binomial import Mathlib.Analysis.Asymptotics.AsymptoticEquivalent import Mathlib.Analysis.SpecificLimits.Basic import Mathlib.Analysis.SpecialFunctions.Choose import Mathlib.Data.Nat.Fib.Basic import Mathlib.RingTheory.PowerSeries.WellKnown import Mathlib.RingTheory.PowerSeries.Inverse import Mathlib.Analysis.SpecificLimits.Normed import Mathlib.Analysis.Meromorphic.Order import Mathlib.Analysis.Complex.Basic import Mathlib.Algebra.BigOperators.NatAntidiagonal import Mathlib.RingTheory.PowerSeries.NoZeroDivisors import Mathlib.Combinatorics.Enumerative.Composition import Mathlib.Analysis.Analytic.Basic import Mathlib.Analysis.Analytic.OfScalars import Mathlib.Analysis.Analytic.RadiusLiminf import Mathlib.RingTheory.PowerSeries.Basic import Mathlib.Algebra.Algebra.Rat import Mathlib.Data.Complex.Basic import Mathlib.Data.Fintype.Card set_option autoImplicit true set_option relaxedAutoImplicit false set_option maxSynthPendingDepth 3 /-! # Ternary trees and the Fuss-Catalan asymptotic The number of full ternary trees with `n` internal nodes is `1 / (2n + 1) * binom(3n,n)`. This file proves the corresponding Fuss-Catalan asymptotic directly from Stirling's formula. -/ open Filter Asymptotics open scoped Topology /-- The number of full ternary trees with `n` internal nodes. -/ def ternaryTreeCount (n : ℕ) : ℕ := Nat.choose (3 * n) n / (2 * n + 1) noncomputable def stirlingScale (n : ℕ) : ℝ := Real.sqrt (2 * (n : ℝ) * Real.pi) * (((n : ℝ) / Real.exp 1) ^ n)
Source