Pascal's Triangle, Combinatorial Coefficients (C)

Factorial Notation

If n is a non-negative integer, we define the symbol n!, read ``n factorial'', recursively.

$$\begin{array} {rcll} 0! & := & 1\ (n+1)! &:=& (n+1)n!& n\geq 0\end{array}$$

Thus, for example,

$$\begin{array} {rclcl} 0! & := & 1\ 1! & = & 1\times 0! & = ... ...= & 2\times 1! & = & 2\ 3! & = & 3\times 2! & = & 6\end{array}$$

If $n \geq 2$ we have

$$n! = n\times(n-1)\times\cdots\times 2\times 1.$$

Counting ordered samples

The number of ways to choose, in order, k objects from a set of n distinct objects, called the number of permutations of k out of n objects, and denoted by (n)_k, is 1 if k = 0 (there is one way to do nothing) and is

$$(n)_k = n\times(n-1)\times\cdots\times(n-(k-1))$$

if $k\in\{1,\dots,n\}$, since there are n choices for the first object, n-1 choices for the second object, and so on. The two case can be combined as

$$(n)_k = \frac{n!}{(n-k)!}.$$

Thus the number of ways to choose, in order, 5 pool balls from 15 is $15\times 14\times 13\times 12\times 11$.

Combinatorial Coefficients

If order does not matter, what we want to count is the number of combinations of k objects from n objects, which we denote by _nCk, read ``n choose k''. Observe that

$$_nC_k\times (k)_k = (n)_k$$

since to make a permutation of k objects out of n, we first select one of the _nC_k unordered samples and then order it in one of (k)_k ways. Therefore,

$$_nC_k = \frac{(n)_k}{(k)_k} = \frac{n!}{(n-k)!k!}.$$

Thus there are 10 combinations of 2 objects from a set of 5 objects. In other words, a set of 5 objects has 10 subsets of size 2.

Another common notation for _nC_k is

$$_nC_k = \mbox{$\left(\begin{array} {c}n\ k\end{array}\right)$}.$$

Also, _nC_k is sometimes called a bf binomial coefficient. See below.

Pascal's Triangle

There are many relations among the combinatorial coefficients. Pascal's Triangle is the most famous.

If we want to count the number of subsets of size k+1 of a set of n+1 distinct objects, proceed as follows. Paint one object white. Then there are _nC_k+1 subsets which do not contain the white object and $1\times _nC_k$ subsets which do contain it. Therefore

_n+1C_k+1 = _nC_k+1 + _nC_k.

The name derives from the following picture, where the row number indicates the size of the set from which the subsets are to be drawn. The top row is row 0. A set of size 0 has 1 subset, the empty set.

$$\begin{array} {ccccccccccc} &&&&& 1 \ &&&& 1 && 1\ &&& 1 &... ...1 && 4 && 6 && 4 && 1\ 1 && 5 && 10 && 10 && 5 && 1\end{array}$$

Remark: The binomial coefficients

$$\mbox{$\left(\begin{array} {c}p\ k\end{array}\right)$}$$

can be given a meaning even if p is not a positive integer, so long as k is positive integer.

We put

$$\mbox{$\left(\begin{array} {c}p\ 0\end{array}\right)$} = 1$$

and

$$\mbox{$\left(\begin{array} {c}p\ 1\end{array}\right)$} = p$$

For $${k \geq 2}$$

$$\mbox{$\left(\begin{array} {c}p\ k\end{array}\right)$} = \frac{p(p-1)\cdots(p-(k-1))}{k!}.$$

This conforms to the case where p is a positive integer since

$$p! = p(p-1)\cdots(p-(k-1))(p-k)!$$

For example

$$\mbox{$\left(\begin{array} {c}\frac{1}{3}\ 2\end{array}\rig... ...= \frac{\left(\frac{1}{3}\right)\left(\frac{-2}{3}\right)}{2!}$$

and

$$\mbox{$\left(\begin{array} {c}\frac{-1}{5}\ 3\end{array}\ri... ...ight)\left(\frac{-6}{5}\right) \left(\frac{-11}{5}\right)}{3!}$$