Formal generating function of compositions into ones and twos
ProvedAnalyticCombinatorics.Ch1.CombClass.ogf_seq_parts12analytic-combinatoricsformal-power-serieslean4symbolic-method
Let have one object of size , one object of size , and no objects of any other size. Let be the ordinary generating function over of finite sequences of -objects, with total size given by the sum of component sizes. In the ring of formal power series,
The empty sequence contributes the constant coefficient one. This is the sequence-construction identity for the two-size class and requires no analytic convergence condition.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Sequence
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Fibonacci
import Mathlib.Data.Nat.Fib.Basic
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.3 — Fibonacci numbers as compositions into parts `1` and `2`
Flajolet & Sedgewick, Part A, Chapter I, §I.3. Let `D` be the class with one
object of size `1` and one of size `2`. Then `SEQ(D)` enumerates compositions of
`n` into parts of size `1` and `2`, and
* `counts_seq_parts12` — there are `F_{n+1}` of them (`Nat.fib (n+1)`), via the
convolution recursion `counts_seq_succ`, which here is the Fibonacci recurrence;
* `ogf_parts12` / `ogf_seq_parts12` — `D(z) = z + z²` and the OGF is
`1/(1 - z - z²)`, the Fibonacci generating function.
-/
open AnalyticCombinatorics AnalyticCombinatorics.Ch1
open PowerSeries
Formal statement
theorem AnalyticCombinatorics.Ch1.CombClass.ogf_seq_parts12 :
CombClass.parts12.seq.ogf * (1 - (X + X ^ 2)) = 1 := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).