Factorial

Factorial is most simply defined as a function on positive integers. 5 factorial (written as $5!$) means $1*2*3*4*5$. In general then, for a positive integer $n$, $n!=\prod_{i=1}^{n}i$. For applications to combinatorics, it will also be useful to define $0! = 1$.

Applications to Combinatorics

$n!$ is the number of possible orders for a set of $n$ objects. For example, if we arrange the letters $A$, $B$, and $C$, here are all the options:

$$ABC$$

$$ACB$$

$$BAC$$

$$BCA$$

$$CAB$$

$$CBA$$

You can see that there are $6$ possible orders for $3$ objects, and $6 = 3*2*1 = 3!$. Why does this work? We can prove this by induction. First, we’ll see pretty easily that it works for $1$ object, and then we can show that if it works for $n$ objects, it will work for $n+1$. Here’s the case for $1$ object.

$$A$$

$$1 = \prod_{i=1}^{1}i = 1!$$

Now we have the objects $\{A_{1},A_{2},...,A_{n},A_{n+1}\}$, and $n+1$ slots to put them in. If $A_{n+1}$ is in the first slot, now we’re ordering $n$ remaining objects in $n$ remaining slots, and by our induction hypothesis, there are $n!$ ways to do this. Now let’s suppose $A_{n+1}$ is in the second slot. Any orderings that result from this will be completely unique from the orderings where $A_{n+1}$ was in the first slot. Again, there are $n$ remaining slots, and $n$ remaining objects to put in them, in an arbitrary order. There are another $n!$ possible orderings. We can put $A_{n+1}$ in each slot, one by one, and generate another $n!$ orderings, all of which are unique, and by the end, we will have every possible ordering. We know we haven’t missed any because $A_{n+1}$ has to be somewhere. The total number of orderings we get is $n!*(n+1)$, which equals $(n+1)!$.

Extrapolating to Real Numbers

The factorial function can be defined in a different way so that it is defined for all real numbers (and in fact for complex numbers too).

Definition

We define $x!$ as follows:

$$x! = \Gamma (x+1),$$

where $\Gamma $ is the gamma function:

$$\Gamma(x)=\int_{0}^{\infty}t^{x-1}e^{-t}\mathrm{d} t$$

Why does this correspond to the factorial function as defined previously? We can prove by induction that for all positive integers $x$:

$$\prod_{i=1}^{x}i = \int_{0}^{\infty}t^{x}e^{-t}\mathrm{d} t$$

First, we verify for the case where $x=1$. Indeed:

$$\prod_{i=1}^{1}i = \int_{0}^{\infty}t^{1}e^{-t}\mathrm{d} t$$

$$1=1$$

Now we suppose that the equality holds for a given $x$:

$$\prod_{i=1}^{x}i = \int_{0}^{\infty}t^{x}e^{-t}\mathrm{d} t$$

and try to prove that it holds for $x + 1$:

$$\prod_{i=1}^{x+1}i = \int_{0}^{\infty}t^{x+1}e^{-t}\mathrm{d} t$$

We’ll start with the induction hypothesis, and manipulate until we get the equality for $x+1$.

$$\prod_{i=1}^{x}i = \int_{0}^{\infty}t^{x}e^{-t}\mathrm{d} t$$

$$(x+1)\prod_{i=1}^{x}i = (x+1)\int_{0}^{\infty}t^{x}e^{-t}\mathrm{d} t$$

$$\prod_{i=1}^{x+1}i = (x+1)\int_{0}^{\infty}t^{x}e^{-t}\mathrm{d} t$$

$$= 0+\int_{0}^{\infty}(x+1)t^{x}e^{-t}\mathrm{d} t$$

$$= \left[ (-t^{x+1}e^{-t}) \right]_{0}^{\infty}+\int_{0}^{\infty}(x+1)t^{x}e^{-t}\mathrm{d} t$$

$$= \left[ (-t^{x+1}e^{-t}) \right]_{0}^{\infty}-\int_{0}^{\infty}(x+1)t^{x}(-e^{-t})\mathrm{d} t$$

By the product rule of integration:

$$=\int_{0}^{\infty}t^{x+1}e^{-t}\mathrm{d} t$$

This completes the proof by induction, and that’s why we can define factorials in terms of the gamma function.