Go backward to 4.7.2 Arithmetic Quantifiers Go up to 4.7 Arithmetic Notions Go forward to 4.7.4 Matrix Operations

4.7.3 Binomials

In combinatorics (the branch of mathematics that solves questions of the kind "how many objects do exist such that ...?"), the following notions are of importance.

n! := (prod_{1 <= i <= n} i).

Please note that the definition of prod implies 0!=1.

(n k) := if 0 <= k <= n then n!/k!*(n-k)! else 0.

The name "n choose k" stems from the fact that (n k) is the number of ways to choose a k element set from an n-element set.

{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}.

By above definition we have for every n and k with 0 <= k <= n

(n k) = (prod_{n-k+1 <= i <= n} i)/(prod_{1 <= i <= n} i).

Furthermore, we have the following important identities.

(n+1 k+1) = (n k) + (n k+1),

(n k) = (n n-k),

(n 0) = (n n) = 1.

These three laws give rise to  Pascal's triangle:

1

1     1

1     2     1

1     3      3     1

........................

=

(0 0)
(1 0) (1 1)
(2 0) (2 1) (2 2)
(3 0) (3 1) (3 2) (3 3)

........................

(n k) (n k+1)
......(n+1 k+1) .......