# Factorial

https://arbital.com/p/factorial

by Michael Cohen Jul 13 2016 updated Jul 17 2016

The number of ways you can order things. (Alternately subtitled: Is that exclamation point a factorial, or are you just excited to see me?)

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

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