# mathlib3documentation

data.nat.choose.basic

# Binomial coefficients #

THIS FILE IS SYNCHRONIZED WITH MATHLIB4. Any changes to this file require a corresponding PR to mathlib4.

This file defines binomial coefficients and proves simple lemmas (i.e. those not requiring more imports).

## 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.desc_factorial_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.

Equations
@[simp]
theorem nat.choose_zero_right (n : ) :
n.choose 0 = 1
@[simp]
theorem nat.choose_zero_succ (k : ) :
0.choose k.succ = 0
theorem nat.choose_succ_succ (n 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 : ) :
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) :
theorem nat.add_choose (i j : ) :
(i + j).choose j = (i + j).factorial / (i.factorial * 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)

### 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 : ) :
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 (λ (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

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

Equations
@[simp]
theorem nat.multichoose_zero_right (n : ) :
@[simp]
theorem nat.multichoose_zero_succ (k : ) :
0.multichoose (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 : ) :
@[simp]
theorem nat.multichoose_two (k : ) :
2.multichoose k = k + 1
@[simp]
theorem nat.multichoose_one_right (n : ) :
theorem nat.multichoose_eq (n k : ) :
n.multichoose k = (n + k - 1).choose k