Cartesian powers raise the ordinary generating function to a power
ProvedAnalyticCombinatorics.Ch1.CombClass.ogf_prodPowanalytic-combinatoricslean4ogfsymbolic-method
For a graded class of finite sets, write and . Let have one size-zero object and let , with component sizes adding in the product. For every ,
The case is included.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_ProductPower import Mathlib.Algebra.BigOperators.NatAntidiagonal 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–I.3 — Cartesian powers and words over a finite alphabet Flajolet & Sedgewick, Part A, Chapter I. Iterating the product construction gives the `k`-fold Cartesian power `C^k = C × C × ⋯ × C`, with OGF `C(z)^k` (an immediate induction from the binary product rule `ogf_prod`). As the standard application, words of length `k` over an alphabet of `a` letters form `(a·Z)^k`, with OGF `(a z)^k` (so there are `a^k` of them), recovering F&S §I.3. -/ open AnalyticCombinatorics AnalyticCombinatorics.Ch1 open PowerSeries
Formal statement
theorem AnalyticCombinatorics.Ch1.CombClass.ogf_prodPow (C : CombClass) (k : ℕ) :
(C.prodPow k).ogf = C.ogf ^ k := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).