The ordinary generating function of ordered sequences
ProvedAnalyticCombinatorics.Ch1.CombClass.ogf_seq_mulanalytic-combinatoricsformal-power-serieslean4symbolic-method
Let be a combinatorial class with finitely many objects of each natural-number size, and assume that it has no objects of size zero. Write for its ordinary generating function over and for the ordinary generating function of finite ordered sequences of its objects, with total size given by the sum of component sizes. Then
The sequence class includes the unique empty sequence of total size zero. This general construction rule provides the formal inverse identity used by concrete sequence-counting examples.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Sequence
import Mathlib.Algebra.BigOperators.NatAntidiagonal
import Mathlib.RingTheory.PowerSeries.Inverse
import Mathlib.RingTheory.PowerSeries.NoZeroDivisors
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.2 — The sequence construction: `SEQ(C)(z) = 1/(1 - C(z))`
Flajolet & Sedgewick, Part A, Chapter I, §I.2, the sequence construction, for a
general class `C` with no object of size `0` (`C.counts 0 = 0`). A sequence
decomposes as `SEQ(C) = ε + C × SEQ(C)` (empty, or first component × rest), so the
counting sequence satisfies a convolution recursion and the OGF satisfies the
functional equation `S(z) = 1 + C(z)·S(z)`, hence
**`(seq C).ogf · (1 - C.ogf) = 1`**, i.e. `SEQ(C)(z) = 1/(1 - C(z))`.
The combinatorial core is the first-part decomposition of compositions, built from
Mathlib's `Composition.append`/`single`.
-/
open AnalyticCombinatorics AnalyticCombinatorics.Ch1
open PowerSeries Finset
variable {C : CombClass}
Formal statement
theorem AnalyticCombinatorics.Ch1.CombClass.ogf_seq_mul (hC0 : C.counts 0 = 0) :
C.seq.ogf * (1 - C.ogf) = 1 := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).