Multichoose Euler product for the size-grouped multiset class
ProvedAnalyticCombinatorics.Ch1.CombClass.ogf_msetanalytic-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 multiset of of cardinality . Denote this graded class by . Then
Here counts size- multisets from a -element set, including the usual zero-cardinality cases. 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 multisets 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_Mset
import Mathlib.Combinatorics.Enumerative.Partition.GenFun
import Mathlib.Data.Sym.Card
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 multiset construction MSET(C): counts layer
Flajolet & Sedgewick, Part A, Chapter I, §I.2. `MSET(C)` forms finite multisets of
C-objects (`C₀=∅`). Grouping a multiset by object size, a size-`n` object is a
partition `p` of `n` (recording the multiplicities of each size) together with, for
each size `m`, a size-`(mult m)` multiset of the `Cₘ` objects of that size (a `Sym`).
This file builds the graded `Fintype` model and the counting identity, and connects
it to Mathlib's `Nat.Partition.genFun`:
`MSET(C)ₙ = ∑_{p:Partition n} ∏_m multichoose(Cₘ, mult_m p)
= genFun (fun m j => multichoose(Cₘ, j)) |>.coeff n`.
The Euler product OGF `∏_m (1 - z^m)^{-Cₘ}` is proved in the OGF layer. (For `C = ℙ`,
`multichoose 1 k = 1`, recovering the partition flagship.)
-/
open AnalyticCombinatorics AnalyticCombinatorics.Ch1
open PowerSeries
open scoped PowerSeries.WithPiTopology
open PowerSeries.WithPiTopology
attribute [local instance] _root_.AnalyticCombinatorics.Ch1.instTopRatMset
local instance _root_.AnalyticCombinatorics.Ch1.instDiscRatMset : DiscreteTopology ℚ := ⟨rfl⟩
Formal statement
theorem AnalyticCombinatorics.Ch1.CombClass.ogf_mset (C : CombClass) :
C.mset.ogf
= ∏' i, ∑' k, ((C.counts (i + 1)).multichoose k : ℚ) • (X : ℚ⟦X⟧) ^ ((i + 1) * k) := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).