Generating function of distinct positive parts
ProvedAnalyticCombinatorics.Ch1.CombClass.ogf_pset_posIntanalytic-combinatoricslean4ogfsymbolic-method
Let be the source powerset construction on the class with one object of each positive size: equivalently, a partition of decorated by a subset of the singleton object set at each positive size, of cardinality equal to that size multiplicity. Every multiplicity is therefore zero or one. Then
The equality is coefficientwise over with discrete coefficient topology.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Sequence
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Pset
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_DistinctPartitions
import Mathlib.Combinatorics.Enumerative.Partition.GenFun
import Mathlib.Data.Fintype.Powerset
import Mathlib.Combinatorics.Enumerative.Composition
import Mathlib.RingTheory.PowerSeries.Basic
import Mathlib.Data.Fintype.Card
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Ch1 §I.3 — Partitions into distinct parts (PSET flagship)
Flajolet & Sedgewick, Part A, Chapter I, §I.3. A partition of `n` into *distinct*
parts is a set of distinct positive integers summing to `n` — an object of
`PSET(ℙ)` of size `n`. Specializing the general powerset transfer `ogf_pset` to the
positive-integer class `ℙ` (`Cₘ=1`, `choose 1 k` supported on `{0,1}`) gives the
classical generating function
`D(z) = ∏_{m≥1} (1 + z^m)`.
-/
open AnalyticCombinatorics AnalyticCombinatorics.Ch1
open PowerSeries
open scoped PowerSeries.WithPiTopology
open PowerSeries.WithPiTopology
attribute [local instance] _root_.AnalyticCombinatorics.Ch1.instTopRatDistinct
local instance _root_.AnalyticCombinatorics.Ch1.instDiscRatDistinct : DiscreteTopology ℚ := ⟨rfl⟩
Formal statement
theorem AnalyticCombinatorics.Ch1.CombClass.ogf_pset_posInt :
CombClass.posInt.pset.ogf = ∏' i, (1 + (X : ℚ⟦X⟧) ^ (i + 1)) := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).