There are 2^(n−1) compositions of n
ProvedFamousTheorems.card_compositions_6bThere are compositions of . A composition of is an ordered sequence of positive integers with sum . For every there are exactly compositions of , and there is exactly one composition of , the empty one.
A composition of is the same as a choice of which of the gaps between dots to cut, which gives the count. The number of compositions into exactly parts is . Compositions are used to index terms in the multivariate Faà di Bruno formula and in the theory of quasisymmetric functions.
Formalization note. Mathlib's composition_card. Composition n is the type of lists of positive natural numbers with sum . With natural-number subtraction, , so the formula also gives the correct count for .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems theorem card_compositions_6b (n : ℕ) : Fintype.card (Composition n) = 2 ^ (n - 1) := by sorry end FamousTheorems
Source
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `composition_card`. Proof here reduces to that Mathlib result.