Go backward to 4.7.2 Arithmetic QuantifiersGo up to 4.7 Arithmetic NotionsGo 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.

Definition 58 (Factorial) The  factorial (Fakultät) of a natural number n is the product of all non-zero numbers less than or equal n:
n! := (prod1 <= i <= n i).

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

Definition 59 (Binomial Coefficient) The  binomial coefficient (Binomialkoeffizient) of two natural numbers is defined as follows:
(n k) := if 0 <= k <= n then n!/k!*(n-k)! else 0.
We read this as "n choose k" ("n über k").

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.

Example  The set {0, 1, 2, 3} has 6 = (4 2) subsets with 2 elements:
{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) = (prodn-k+1 <= i <= n i)/(prod1 <= i <= n i).

Furthermore, we have the following important identities.

Proposition 61 (Binomial Identities) For every n in N and k in N with 0 <= k <= n, the following holds:
(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)

........................
This triangle is bounded by sides of 1 and where every interior element is the sum of both parents:
(n k) (n k+1)
......(n+1 k+1) .......

Author: Wolfgang Schreiner
Last Modification: October 4, 1999