Formal generating function of integer compositions
ProvedAnalyticCombinatorics.Ch1.CombClass.ogf_compositionsanalytic-combinatoricsformal-power-serieslean4symbolic-method
Let be the ordinary generating function over of ordered compositions of natural numbers into positive integer parts, including the unique empty composition of zero. As formal power series,
This expresses the rational generating-function relation for unrestricted integer compositions. The statement is a multiplicative identity in the formal power-series ring.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Sequence
import Mathlib.Combinatorics.Enumerative.Composition
import Mathlib.RingTheory.PowerSeries.Basic
import Mathlib.Data.Fintype.Card
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Ch1 §I.3 — The generating function of integer compositions
Flajolet & Sedgewick, Part A, Chapter I, §I.3. There are `2^{n-1}` compositions
of `n ≥ 1` (Mathlib's `composition_card`), so their ordinary generating function
is
`C(z) = ∑ₙ 2^{n-1} zⁿ = (1 - z)/(1 - 2z)`,
which we state in polynomial form as `C(z)·(1 - 2z) = 1 - z`. Mathlib has the
counting result but not this generating function, so the identity is new content;
it is the closed form predicted by the symbolic method via `compositions = SEQ(ℙ)`
(see `counts_seq_posInt` in `Sequence.lean`).
-/
open AnalyticCombinatorics AnalyticCombinatorics.Ch1
open PowerSeries
Formal statement
theorem AnalyticCombinatorics.Ch1.CombClass.ogf_compositions :
CombClass.compositions.ogf * (1 - 2 * X) = 1 - X := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).