### 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`! := (**prod**_{1 <= 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`) = (**prod**_{n-k+1 <= i
<= n} `i`)/(**prod**_{1 <= 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