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

%%hidden(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. %%