Counting words over a finite alphabet
ProvedAnalyticCombinatorics.Ch1.counts_seq_alphabetanalytic-combinatoricslean4ogfsymbolic-method
Let . The alphabet class has objects of size one and no objects of any other size; its finite sequence construction consists of ordered lists whose sizes sum to . Then
Both zero values are included, with the empty word counted once.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Sequence import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_ProductPower 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 — Applications of the sequence construction Flajolet & Sedgewick, Part A, Chapter I, §I.3, applying the general transfer `SEQ(C)(z) = 1/(1 - C(z))` (`ogf_seq_mul`): * `counts_seq_alphabet` / `ogf_seq_alphabet` — **words over a finite alphabet**: `SEQ` of an `a`-letter alphabet enumerates all words; there are `a^n` of length `n`, with OGF `1/(1 - a z)`. * `ogf_seq_posInt` — **compositions revisited**: the special case `C = ℙ` recovers `(seq ℙ)(z)·(1 - ℙ(z)) = 1` as an instance of the general theorem (cf. the bespoke proof in `SeqFormula.lean`). -/ open AnalyticCombinatorics AnalyticCombinatorics.Ch1 open PowerSeries
Formal statement
theorem AnalyticCombinatorics.Ch1.counts_seq_alphabet (a n : ℕ) :
(CombClass.alphabet a).seq.counts n = a ^ n := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).