Products on disjoint labelled subsets
DefinitionAnalyticCombinatorics_Ch2_EGF_LabelledProductanalytic-combinatoricsexponential-generating-functionslean4set-partitions
A size-n labelled product object chooses a subset of k labels, an object of size k from the first component class, and an object of size n−k from the second. The complement supplies the remaining labels, and all choices form finite types.
Definition code
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Defs
import Mathlib.Algebra.BigOperators.NatAntidiagonal
import Mathlib.Data.Fintype.Powerset
import Mathlib.RingTheory.PowerSeries.WellKnown
import Mathlib.RingTheory.PowerSeries.Exp
import Mathlib.GroupTheory.Perm.Basic
import Mathlib.Data.Fintype.Perm
import Mathlib.RingTheory.PowerSeries.Basic
import Mathlib.Data.Fintype.Card
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Ch2 §II.1 — The labelled product
Flajolet & Sedgewick, Part A, Chapter II, the labelled (partitional) product, the
defining construction of the EGF framework. To form `A ⋆ B` on `n` labels, one
chooses which `k` of the labels go to the `A`-component (a `k`-subset) and puts an
`A`-structure on them and a `B`-structure on the remaining `n-k`. Hence
`(A ⋆ B)ₙ = ∑_{k} C(n,k) · Aₖ · B_{n-k}` (binomial convolution),
and therefore the EGFs multiply:
**`(A ⋆ B)(z) = A(z) · B(z)`** (F&S Theorem II.1).
-/
namespace AnalyticCombinatorics.Ch1
open PowerSeries Finset
/-- The labelled product `A ⋆ B` (F&S §II.1): a size-`n` object chooses a `k`-subset
`S` of the `n` labels, an `A`-structure on `S`, and a `B`-structure on the rest. -/
def CombClass.lprod (A B : CombClass) : CombClass where
Obj n := Σ k : Fin (n + 1),
{ S : Finset (Fin n) // S.card = k } × A.Obj k × B.Obj (n - k)
finObj _ := inferInstance
end AnalyticCombinatorics.Ch1
Source