Factorial

Fac­to­rial is most sim­ply defined as a func­tion on pos­i­tive in­te­gers. 5 fac­to­rial (writ­ten as \(5!\)) means \(1*2*3*4*5\). In gen­eral then, for a pos­i­tive in­te­ger \(n\), \(n!=\prod_{i=1}^{n}i\). For ap­pli­ca­tions to com­bi­na­torics, it will also be use­ful to define \(0! = 1\).

Ap­pli­ca­tions to Combinatorics

\(n!\) is the num­ber of pos­si­ble or­ders for a set of \(n\) ob­jects. For ex­am­ple, if we ar­range the let­ters \(A\), \(B\), and \(C\), here are all the op­tions:

$$ABC$$
$$ACB$$
$$BAC$$
$$BCA$$
$$CAB$$
$$CBA$$
You can see that there are \(6\) pos­si­ble or­ders for \(3\) ob­jects, and \(6 = 3*2*1 = 3!\). Why does this work? We can prove this by in­duc­tion. First, we’ll see pretty eas­ily that it works for \(1\) ob­ject, and then we can show that if it works for \(n\) ob­jects, it will work for \(n+1\). Here’s the case for \(1\) ob­ject.
$$A$$
$$1 = \prod_{i=1}^{1}i = 1!$$
Now we have the ob­jects \(\{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 or­der­ing \(n\) re­main­ing ob­jects in \(n\) re­main­ing slots, and by our in­duc­tion hy­poth­e­sis, there are \(n!\) ways to do this. Now let’s sup­pose \(A_{n+1}\) is in the sec­ond slot. Any or­der­ings that re­sult from this will be com­pletely unique from the or­der­ings where \(A_{n+1}\) was in the first slot. Again, there are \(n\) re­main­ing slots, and \(n\) re­main­ing ob­jects to put in them, in an ar­bi­trary or­der. There are an­other \(n!\) pos­si­ble or­der­ings. We can put \(A_{n+1}\) in each slot, one by one, and gen­er­ate an­other \(n!\) or­der­ings, all of which are unique, and by the end, we will have ev­ery pos­si­ble or­der­ing. We know we haven’t missed any be­cause \(A_{n+1}\) has to be some­where. The to­tal num­ber of or­der­ings we get is \(n!*(n+1)\), which equals \((n+1)!\).

Ex­trap­o­lat­ing to Real Numbers

The fac­to­rial func­tion can be defined in a differ­ent way so that it is defined for all real num­bers (and in fact for com­plex num­bers too).

We define \(x!\) as fol­lows:
$$x! = \Gamma (x+1),$$
where \(\Gamma \) is the gamma func­tion:
$$\Gamma(x)=\int_{0}^{\infty}t^{x-1}e^{-t}\mathrm{d} t$$
Why does this cor­re­spond to the fac­to­rial func­tion as defined pre­vi­ously? We can prove by in­duc­tion that for all pos­i­tive in­te­gers \(x\):
$$\prod_{i=1}^{x}i = \int_{0}^{\infty}t^{x}e^{-t}\mathrm{d} t$$
First, we ver­ify for the case where \(x=1\). In­deed:
$$\prod_{i=1}^{1}i = \int_{0}^{\infty}t^{1}e^{-t}\mathrm{d} t$$
$$1=1$$
Now we sup­pose that the equal­ity 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 in­duc­tion hy­poth­e­sis, and ma­nipu­late un­til we get the equal­ity 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 in­te­gra­tion:
$$=\int_{0}^{\infty}t^{x+1}e^{-t}\mathrm{d} t$$
This com­pletes the proof by in­duc­tion, and that’s why we can define fac­to­ri­als in terms of the gamma func­tion.

Children:

Parents:

  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.