Binomial Euler product for the size-grouped subset class
ProvedAnalyticCombinatorics.Ch1.CombClass.ogf_psetanalytic-combinatoricslean4ogfsymbolic-method
For a graded class of finite sets, write and . For each partition of into positive parts, write for the multiplicity of . Define a size- object to be together with, for every , a subset of of cardinality . Denote this graded class by . Then
Partition parts are positive, so : this source model ignores zero-size decorations even if is nonempty. The theorem has no hypothesis ; its interpretation as unrestricted finite sets of arbitrary -objects requires that additional model condition. All infinite operations are coefficientwise formal ones with discrete rational coefficients.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Pset
import Mathlib.Combinatorics.Enumerative.Partition.GenFun
import Mathlib.Data.Fintype.Powerset
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 powerset construction PSET(C)
Flajolet & Sedgewick, Part A, Chapter I, §I.2. `PSET(C)` forms finite *sets* of
C-objects (each object used at most once, `C₀=∅`). Grouping a set by object size, a
size-`n` object is a partition `p` of `n` together with, for each size `m`, a
*subset* of card `(mult m)` of the `Cₘ` objects of that size. The number of size-`k`
subsets of a `c`-set is `choose(c,k)`, so
`PSET(C)ₙ = ∑_{p:Partition n} ∏_m choose(Cₘ, mult_m p)
= genFun (fun m j => choose(Cₘ, j)) |>.coeff n`,
and the OGF is `PSET(C)(z) = ∏_{m≥1} (1 + z^m)^{Cₘ}` (since `∑_k choose(c,k) x^k =
(1+x)^c`). The construction mirrors `MSET` with subsets/`choose` in place of
multisets/`multichoose`.
-/
open AnalyticCombinatorics AnalyticCombinatorics.Ch1
open PowerSeries
open scoped PowerSeries.WithPiTopology
open PowerSeries.WithPiTopology
attribute [local instance] _root_.AnalyticCombinatorics.Ch1.instTopRatPset
local instance _root_.AnalyticCombinatorics.Ch1.instDiscRatPset : DiscreteTopology ℚ := ⟨rfl⟩
Formal statement
theorem AnalyticCombinatorics.Ch1.CombClass.ogf_pset (C : CombClass) :
C.pset.ogf
= ∏' i, ∑' k, ((C.counts (i + 1)).choose k : ℚ) • (X : ℚ⟦X⟧) ^ ((i + 1) * k) := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).