Stars and bars
ProvedFamousTheorems.stars_and_bars_theoremStars and bars. Let be a finite set with elements and let . The number of multisets of size with elements from is
Equivalently, this is the number of ways to put identical balls into distinguishable boxes, or the number of solutions of in non-negative integers. It is one of the basic counting principles of enumerative combinatorics (the twelvefold way). It also gives the dimension of the space of degree- homogeneous polynomials in variables.
Formalization note. Mathlib's Sym.card_sym_eq_multichoose. Sym α k is the type of multisets of size over , and Nat.multichoose n k is the multiset coefficient, equal to (Mathlib's Nat.multichoose_eq).
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem stars_and_bars_theorem (α : Type*) (k : ℕ) [Fintype α] [DecidableEq α] :
Fintype.card (Sym α k) = (Fintype.card α).multichoose k := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Sym.card_sym_eq_multichoose`. Proof here reduces to that Mathlib result.