Factorial is most simply defined as a function on positive integers. 5 factorial (written as ) 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: $A B C$ $A C B$ $B A C$ $B C A$ $C A B$ $C B A$ 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 = 1 \prod i = 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! = Γ (x + 1),$ where $Γ$ is the gamma function: $Γ (x) = \int_{0}^{\infty} t^{x - 1} e^{- t} d t$ Why does this correspond to the factorial function as defined previously? We can prove by induction that for all positive integers $x$ : $x \prod i = 1 i = \int_{0}^{\infty} t^{x} e^{- t} d t$ First, we verify for the case where $x = 1$ . Indeed: $1 \prod i = 1 i = \int_{0}^{\infty} t^{1} e^{- t} d t$ $1 = 1$ Now we suppose that the equality holds for a given $x$ : $x \prod i = 1 i = \int_{0}^{\infty} t^{x} e^{- t} d t$ and try to prove that it holds for $x + 1$ : $x + 1 \prod i = 1 i = \int_{0}^{\infty} t^{x + 1} e^{- t} d t$ We'll start with the induction hypothesis, and manipulate until we get the equality for $x + 1$ . $x \prod i = 1 i = \int_{0}^{\infty} t^{x} e^{- t} d t$ $(x + 1) x \prod i = 1 i = (x + 1) \int_{0}^{\infty} t^{x} e^{- t} d t$ $x + 1 \prod i = 1 i = (x + 1) \int_{0}^{\infty} t^{x} e^{- t} d t$ $= 0 + \int_{0}^{\infty} (x + 1) t^{x} e^{- t} d t$ $= {(- t^{x + 1} e^{- t})]}_{0}^{x + 1} + \int_{0}^{\infty} (x + 1) t^{x} e^{- t} d t$ $= {(- t^{x + 1} e^{- t})]}_{0}^{x + 1} - \int_{0}^{\infty} (x + 1) t^{x} (- e^{- t}) d t$ By the product rule of integration: $= \int_{0}^{\infty} t^{x + 1} e^{- t} d t$ This completes the proof by induction, and that's why we can define factorials in terms of the gamma function.

Posts

Wikitag Contributions

Comments