Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Ordered positive-size component sequences and integer compositions

Definition
AnalyticCombinatorics_Ch1_OGF_Sequence

by FormallyCorrect · Oct 24, 2026 · Mathlib 777aaa6 (Lean v4.29.0-rc3)

analytic-combinatoricsformal-power-seriessymbolic-method

Let CCC be a combinatorial class, with CnC_nCn​ its finite set of size-nnn objects. A sequence object of total size nnn is an ordered composition (n1,…,nk)(n_1,\ldots,n_k)(n1​,…,nk​) of nnn into positive integers, together with a selected object from each set CniC_{n_i}Cni​​. Equivalently, its object type is represented by

∐(n1,…,nk)⊨n∏i=1kCni.\coprod_{(n_1,\ldots,n_k)\vDash n}\prod_{i=1}^k C_{n_i}.(n1​,…,nk​)⊨n∐​i=1∏k​Cni​​.

The empty composition gives the empty sequence at size zero. This represents unrestricted finite sequences of CCC-objects when CCC has no size-zero objects. The foundation also provides the class with one object of every positive size and the class of integer compositions themselves. These definitions connect finite combinatorial objects with their counting and generating-function identities.

Definition code
import Definitions.Def_AnalyticCombinatorics_Ch1_OGF_Defs
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.2 / §I.3 — The sequence construction and integer compositions

Flajolet & Sedgewick, Part A, Chapter I. The sequence construction `SEQ(C)` forms
all finite sequences `(γ₁, …, γₘ)` of `C`-objects, with size the sum of the
component sizes. For this to give a (finite) combinatorial class one needs `C` to
have no object of size `0` (F&S's standing side-condition); the positive
component sizes of a size-`n` sequence then form a *composition* of `n`, so we
model `SEQ(C)` over Mathlib's `Composition n`.

This file proves, at the level of counting sequences, the genuine combinatorial
content:

* `counts_seq` — `(SEQ C)ₙ = ∑_{compositions c of n} ∏ᵢ C_{cᵢ}`.
* `counts_seq_posInt` — **integer compositions are sequences of positive
  integers** (F&S §I.3): `(SEQ ℙ)ₙ = #(Composition n) = 2^{n-1}`.

The closed-form generating function of compositions lives in `Compositions.lean`.
-/

namespace AnalyticCombinatorics.Ch1

open PowerSeries Finset

/-- The sequence construction `SEQ(C)` (F&S §I.2): a size-`n` object is a
composition `c` of `n` together with a choice of a `C`-object for each (positive)
part. Faithful to `SEQ(C)` exactly when `C` has no size-`0` object. -/
def CombClass.seq (C : CombClass) : CombClass where
  Obj n := Σ c : Composition n, ∀ i : Fin c.length, C.Obj (c.blocksFun i)
  finObj _ := inferInstance

/-- The class `ℙ` of positive integers: one object of each size `n ≥ 1`
(F&S §I.3, the parts of a composition). -/
def CombClass.posInt : CombClass where
  Obj n := Fin (if 0 < n then 1 else 0)
  finObj _ := inferInstance

/-- The class of integer compositions (F&S §I.3): a size-`n` object is a
composition of `n`. This is Mathlib's `Composition n`. -/
def CombClass.compositions : CombClass where
  Obj n := Composition n
  finObj _ := inferInstance

end AnalyticCombinatorics.Ch1
Source
https://github.com/xiangyazi24/AnalyticCombinatorics/blob/f6f3f1cebdae245a61d9d71e6b47c69fbd096fe3/AnalyticCombinatorics/Ch1/OGF/Sequence.lean. Definitions for the sequence-construction portion of Flajolet and Sedgewick, Analytic Combinatorics (Cambridge University Press, 2009), Chapter I. Source code license: Apache-2.0; immutable license text: https://github.com/xiangyazi24/AnalyticCombinatorics/blob/f6f3f1cebdae245a61d9d71e6b47c69fbd096fe3/LICENSE.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me