Disjoint unions add ordinary generating functions
ProvedAnalyticCombinatorics.Ch1.CombClass.ogf_sumanalytic-combinatoricslean4ogfsymbolic-method
For a graded class of finite sets, write and . For arbitrary classes , let . Then
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Sum 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 combinatorial sum (disjoint union) construction Flajolet & Sedgewick, Part A, Chapter I, §I.2, first admissible construction. If `A = B + C` is the disjoint union of two combinatorial classes (an object of size `n` is a `B`-object of size `n` *or* a `C`-object of size `n`), then the counting sequences add, `Aₙ = Bₙ + Cₙ`, and hence the OGFs add: **`(B + C)(z) = B(z) + C(z)`** (part of F&S Theorem I.1). The combinatorial content is the `Fintype.card` identity `counts_sum`; the generating-function identity `ogf_sum` is its image under `ogfSeq`. -/ open AnalyticCombinatorics AnalyticCombinatorics.Ch1 open PowerSeries
Formal statement
theorem AnalyticCombinatorics.Ch1.CombClass.ogf_sum (C D : CombClass) :
(C.sum D).ogf = C.ogf + D.ogf := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).