Documentation

Mathlib.Data.Nat.Choose.Basic

Binomial coefficients #

This file defines binomial coefficients and proves simple lemmas (i.e. those not requiring more imports). For the lemma that n.choose k counts the k-element-subsets of an n-element set, see Fintype.card_powersetCard in Mathlib.Data.Finset.Powerset.

Main definition and results #

Nat.choose: binomial coefficients, defined inductively
Nat.choose_eq_factorial_div_factorial: a proof that choose n k = n! / (k! * (n - k)!)
Nat.choose_symm: symmetry of binomial coefficients
Nat.choose_le_succ_of_lt_half_left: choose n k is increasing for small values of k
Nat.choose_le_middle: choose n r is maximised when r is n/2
Nat.descFactorial_eq_factorial_mul_choose: Relates binomial coefficients to the descending factorial. This is used to prove Nat.choose_le_pow and variants. We provide similar statements for the ascending factorial.
Nat.multichoose: whereas choose counts combinations, multichoose counts multicombinations. The fact that this is indeed the correct counting function for multisets is proved in Sym.card_sym_eq_multichoose in Data.Sym.Card.
Nat.multichoose_eq : a proof that multichoose n k = (n + k - 1).choose k. This is central to the "stars and bars" technique in informal mathematics, where we switch between counting multisets of size k over an alphabet of size n to counting strings of k elements ("stars") separated by n-1 dividers ("bars"). See Data.Sym.Card for more detail.

Tags #

binomial coefficient, combination, multicombination, stars and bars

def Nat.choose :

ℕ → ℕ → ℕ

choose n k is the number of k-element subsets in an n-element set. Also known as binomial coefficients. For the fact that this is the number of k-element-subsets of an n-element set, see Fintype.card_powersetCard.

Equations

x✝.choose 0 = 1
Nat.choose 0 n.succ = 0
n.succ.choose k.succ = n.choose k + n.choose (k + 1)

@[simp]

theorem Nat.choose_zero_right (n : ℕ) :

n.choose 0 = 1

@[simp]

theorem Nat.choose_zero_succ (k : ℕ) :

choose 0 k.succ = 0

theorem Nat.choose_succ_succ (n k : ℕ) :

n.succ.choose k.succ = n.choose k + n.choose k.succ

theorem Nat.choose_succ_succ' (n k : ℕ) :

(n + 1).choose (k + 1) = n.choose k + n.choose (k + 1)

theorem Nat.choose_succ_left (n k : ℕ) (hk : 0 < k) :

(n + 1).choose k = n.choose (k - 1) + n.choose k

theorem Nat.choose_succ_right (n k : ℕ) (hn : 0 < n) :

n.choose (k + 1) = (n - 1).choose k + (n - 1).choose (k + 1)

theorem Nat.choose_eq_choose_pred_add {n k : ℕ} (hn : 0 < n) (hk : 0 < k) :

n.choose k = (n - 1).choose (k - 1) + (n - 1).choose k

theorem Nat.choose_eq_zero_of_lt {n k : ℕ} :

n < k → n.choose k = 0

@[simp]

theorem Nat.choose_self (n : ℕ) :

n.choose n = 1

@[simp]

theorem Nat.choose_succ_self (n : ℕ) :

n.choose n.succ = 0

@[simp]

theorem Nat.choose_one_right (n : ℕ) :

n.choose 1 = n

theorem Nat.triangle_succ (n : ℕ) :

(n + 1) * (n + 1 - 1) / 2 = n * (n - 1) / 2 + n

theorem Nat.choose_two_right (n : ℕ) :

n.choose 2 = n * (n - 1) / 2

choose n 2 is the n-th triangle number.

theorem Nat.choose_pos {n k : ℕ} :

k ≤ n → 0 < n.choose k

theorem Nat.choose_eq_zero_iff {n k : ℕ} :

n.choose k = 0 ↔ n < k

theorem Nat.succ_mul_choose_eq (n k : ℕ) :

n.succ * n.choose k = n.succ.choose k.succ * k.succ

theorem Nat.choose_mul_factorial_mul_factorial {n k : ℕ} :

k ≤ n → n.choose k * k.factorial * (n - k).factorial = n.factorial

theorem Nat.choose_mul {n k s : ℕ} (hkn : k ≤ n) (hsk : s ≤ k) :

n.choose k * k.choose s = n.choose s * (n - s).choose (k - s)

theorem Nat.choose_eq_factorial_div_factorial {n k : ℕ} (hk : k ≤ n) :

n.choose k = n.factorial / (k.factorial * (n - k).factorial)

theorem Nat.add_choose (i j : ℕ) :

(i + j).choose j = (i + j).factorial / (i.factorial * j.factorial)

theorem Nat.add_choose_mul_factorial_mul_factorial (i j : ℕ) :

(i + j).choose j * i.factorial * j.factorial = (i + j).factorial

theorem Nat.factorial_mul_factorial_dvd_factorial {n k : ℕ} (hk : k ≤ n) :

k.factorial * (n - k).factorial ∣ n.factorial

theorem Nat.factorial_mul_factorial_dvd_factorial_add (i j : ℕ) :

i.factorial * j.factorial ∣ (i + j).factorial

@[simp]

theorem Nat.choose_symm {n k : ℕ} (hk : k ≤ n) :

n.choose (n - k) = n.choose k

theorem Nat.choose_symm_of_eq_add {n a b : ℕ} (h : n = a + b) :

n.choose a = n.choose b

theorem Nat.choose_symm_add {a b : ℕ} :

(a + b).choose a = (a + b).choose b

theorem Nat.choose_symm_half (m : ℕ) :

(2 * m + 1).choose (m + 1) = (2 * m + 1).choose m

theorem Nat.choose_succ_right_eq (n k : ℕ) :

n.choose (k + 1) * (k + 1) = n.choose k * (n - k)

@[simp]

theorem Nat.choose_succ_self_right (n : ℕ) :

(n + 1).choose n = n + 1

theorem Nat.choose_mul_succ_eq (n k : ℕ) :

n.choose k * (n + 1) = (n + 1).choose k * (n + 1 - k)

theorem Nat.ascFactorial_eq_factorial_mul_choose (n k : ℕ) :

(n + 1).ascFactorial k = k.factorial * (n + k).choose k

theorem Nat.ascFactorial_eq_factorial_mul_choose' (n k : ℕ) :

n.ascFactorial k = k.factorial * (n + k - 1).choose k

theorem Nat.factorial_dvd_ascFactorial (n k : ℕ) :

k.factorial ∣ n.ascFactorial k

theorem Nat.choose_eq_asc_factorial_div_factorial (n k : ℕ) :

(n + k).choose k = (n + 1).ascFactorial k / k.factorial

theorem Nat.choose_eq_asc_factorial_div_factorial' (n k : ℕ) :

(n + k - 1).choose k = n.ascFactorial k / k.factorial

theorem Nat.descFactorial_eq_factorial_mul_choose (n k : ℕ) :

n.descFactorial k = k.factorial * n.choose k

theorem Nat.factorial_dvd_descFactorial (n k : ℕ) :

k.factorial ∣ n.descFactorial k

theorem Nat.choose_eq_descFactorial_div_factorial (n k : ℕ) :

n.choose k = n.descFactorial k / k.factorial

def Nat.fast_choose (n k : ℕ) :

A faster implementation of choose, to be used during bytecode evaluation and in compiled code.

Equations

n.fast_choose k = n.descFactorial k / k.factorial

@[csimp]

theorem Nat.choose_eq_fast_choose :

choose = fast_choose

Inequalities #

theorem Nat.choose_le_succ_of_lt_half_left {r n : ℕ} (h : r < n / 2) :

n.choose r ≤ n.choose (r + 1)

Show that Nat.choose is increasing for small values of the right argument.

theorem Nat.choose_le_middle (r n : ℕ) :

n.choose r ≤ n.choose (n / 2)

choose n r is maximised when r is n/2.

Inequalities about increasing the first argument #

theorem Nat.choose_le_succ (a c : ℕ) :

a.choose c ≤ a.succ.choose c

theorem Nat.choose_le_add (a b c : ℕ) :

a.choose c ≤ (a + b).choose c

theorem Nat.choose_le_choose {a b : ℕ} (c : ℕ) (h : a ≤ b) :

a.choose c ≤ b.choose c

theorem Nat.choose_mono (b : ℕ) :

Monotone fun (a : ℕ) => a.choose b

Multichoose #

Whereas choose n k is the number of subsets of cardinality k from a type of cardinality n, multichoose n k is the number of multisets of cardinality k from a type of cardinality n.

Alternatively, whereas choose n k counts the number of combinations, i.e. ways to select k items (up to permutation) from n items without replacement, multichoose n k counts the number of multicombinations, i.e. ways to select k items (up to permutation) from n items with replacement.

Note that multichoose is not the multinomial coefficient, although it can be computed in terms of multinomial coefficients. For details see https://mathworld.wolfram.com/Multichoose.html

TODO: Prove that choose (-n) k = (-1)^k * multichoose n k, where choose is the generalized binomial coefficient. https://github.com/leanprover-community/mathlib/pull/15072#issuecomment-1171415738

@[irreducible]

def Nat.multichoose :

ℕ → ℕ → ℕ

multichoose n k is the number of multisets of cardinality k from a type of cardinality n.

Equations

x✝.multichoose 0 = 1
Nat.multichoose 0 n.succ = 0
n.succ.multichoose k.succ = n.multichoose (k + 1) + (n + 1).multichoose k

@[simp]

theorem Nat.multichoose_zero_right (n : ℕ) :

n.multichoose 0 = 1

@[simp]

theorem Nat.multichoose_zero_succ (k : ℕ) :

multichoose 0 (k + 1) = 0

theorem Nat.multichoose_succ_succ (n k : ℕ) :

(n + 1).multichoose (k + 1) = n.multichoose (k + 1) + (n + 1).multichoose k

@[simp]

theorem Nat.multichoose_one (k : ℕ) :

multichoose 1 k = 1

@[simp]

theorem Nat.multichoose_two (k : ℕ) :

multichoose 2 k = k + 1

@[simp]

theorem Nat.multichoose_one_right (n : ℕ) :

n.multichoose 1 = n

@[irreducible]

theorem Nat.multichoose_eq (n k : ℕ) :

n.multichoose k = (n + k - 1).choose k