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).

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.

Children:

Parents:

  • Mathematics

    Mathematics is the study of numbers and other ideal objects that can be described by axioms.