Finite Cartesian powers and alphabets
DefinitionAnalyticCombinatorics_Ch1_OGF_ProductPoweranalytic-combinatoricslean4ogf
The zeroth Cartesian power is the neutral class with one size-zero object, and each successor multiplies by C using additive sizes. The alphabet class has a prescribed finite number a of objects in size one and none elsewhere.
Definition code
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Product 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. -/ namespace AnalyticCombinatorics.Ch1 open PowerSeries /-- The `k`-fold Cartesian power `C^k = C × (C × (⋯))` (F&S §I.2). -/ def CombClass.prodPow (C : CombClass) : ℕ → CombClass | 0 => CombClass.neutral | (k + 1) => C.prod (C.prodPow k) /-- The alphabet class on `a` letters: `a` distinct objects of size `1` (F&S §I.3). Its OGF is `a·z`. -/ def CombClass.alphabet (a : ℕ) : CombClass where Obj n := Fin (if n = 1 then a else 0) finObj _ := inferInstance end AnalyticCombinatorics.Ch1
Source