Factorials

One of the most basic concepts of permutations and combinations is the use of factorial notation. Using the concept of factorials, many complicated things are made simpler. The use of \(!\) was started by Christian Kramp in 1808. Though they may seem very simple, the use of factorial notation for non-negative integers and fractions is a bit complicated. The applications range from simple algebra to calculus, and it is used to find probabilities too.

Let's first get familiar with the definition of factorial and then we will discuss some properties associated with factorial.

For all positive integers, \(n!\) (read as \(n\) factorial) is defined as

\[ n! = n(n-1)(n-2) \cdots (2)(1). \]

In words, \(n!\) is the product of all positive integers less than or equal to \(n\).

Here are some examples based on the above definition:

Evaluate \(5!\).

---

We have

\[\begin{align} 5!&=5×4×3×2×1\\\\ &=120.\ _\square \end{align}\]

Evaluate \(\dfrac{10!}{6!}.\)

---

We can write \(10!\) as\(10\times 9\times 8\times 7\times 6!\). Substituting this value in the question, we get

\[\begin{eqnarray} \dfrac{10\times 9\times 8\times 7\times 6!}{6!} & =&10\times 9\times 8\times 7 \\ &=& 5040.\ _\square \end{eqnarray}\]

Evaluate \(4!×3!\).

---

We have

\[\begin{align} 4!×3! &=(4×3×2×1)\times (3×2×1)\\ &=24×6\\ &=144.\ _\square \end{align}\]

If \( x!= 1,\) how many different values can \(x\) have?

---

We have

\[0!=1,\quad 1!=1.\]

So, \(2\) values of \(x\) satisfy the given equation. \(_\square\)

Evaluate \(\dfrac{3!}{5!} \).

---

The expression is equal to

\[ \begin{align}
\dfrac{3 \times 2 \times 1}{5 \times 4 \times 3 \times 2 \times 1} = & \dfrac{1}{5 \times 4}\\\\ = & \dfrac{1}{20}.\ _\square \end{align} \]

Now you can easily solve the following problems:

Let's try a special case of \(0!\). There had been many controversies about the case \(0!\), but finally it was accepted that \(0!=1.\) Before proving this, let's understand a basic theorem.

For any positive integer \(n\), \(\frac{n!}{n}=(n-1)!.\)

We can write \(\frac{n!}{n}\) as

\[\begin{eqnarray} \dfrac{n\times(n-1)\times(n-2)\times\cdots\times3\times2\times1}{n} &=&(n-1)\times(n-2)\times\cdots\times3\times2\times1 \\ &=& (n-1)!.\ _\square \end{eqnarray} \]

Now, let's prove that \(0! = 1.\)

We can express \((n-1)!=\frac{n!}{n}\). Then we can put the value of \(n=1\) to obtain

\[\begin{eqnarray} (1-1)!&=&\dfrac{1!}{1} \\\\0!&=&1!\\&=&1.\ _\square \end{eqnarray} \]

Evaluate \(\frac{8!}{8}.\)

---

We have

\[\begin{align} \dfrac {8!}{8} &=7!\\ &=7×6×5×4×3×2×1\\ &=5040.\ _\square \end{align}\]

Evaluate \(\frac{8!×7!}{6!×5!}.\)

---

We have

\[\begin{align} \require{cancel} \dfrac {8!×7!}{6!×5!} &=\dfrac {8×7×6×5×4×3×2×1×7×\cancel{6×5×4×3×2×1}}{\cancel{6×5×4×3×2×1}×5×4×3×2×1}\\\\ &=2352.\ _\square \end{align}\]

Now, let's talk about what double factorials are. This type of factorial is denoted by \(n!!\). It is a type of multifactorial which will be discussed in this wiki. As far as double factorial is concerned, it ends with \(2\) for an even number, and ends with \(1\) for an odd number. In other words,

• for an even number and \(n>0,\) \(n!!=n×(n-2)×\cdots×4×2;\)
• for an odd number and \(n>0,\) \(n!!=n×(n-2)×\cdots×3×1;\)
• if \(n=0,\) \(0!!=1.\)

For any non-negative integer \(n,\) we find that

\[\begin{array} &\dfrac{n!}{n!!}=(n-1)!! &\text{ or } &n!=(n-1)!!×n!!. \end{array}\]

There are the following 2 cases:

• Case 1: \(n\) is odd. Then we have \[\dfrac{n!}{n!!}=\dfrac{n\times(n-1)\times(n-2)\times \cdots \times3\times2\times1}{n\times(n-2)\times(n-4)\times \cdots \times 5\times3\times1}.\] Since all the odd numbers \(n, n-2, n-4, \ldots, 5, 3, 1\) get canceled, this equation is equivalent to \[\dfrac{n!}{n!!}=(n-1)!!.\]

• Case 2: \(n\) is even. Then we have \[\dfrac{n!}{n!!}=\dfrac{n\times(n-1)\times(n-2)\times \cdots \times3\times2\times1}{n\times(n-2)\times(n-4)\times \cdots \times 4\times2}.\] Since all the even numbers \(n, n-2, n-4, \ldots, 4, 2\) get canceled, this equation is equivalent to \[\dfrac{n!}{n!!}=(n-1)!!.\]

Now, if we combine both the cases, we find that for any non-negative integer \(n,\)

\[\dfrac{n!}{n!!}=(n-1)!!.\ _\square\]

Evaluate \(\frac {9!}{9!!}.\)

---

We know that \(\frac {n!}{n!!}=(n-1)!!\). Substituting in the values, we get

\[\begin{align} \dfrac{9!}{9!!} &=(9-1)!!\\ &=8!!\\ &=8×6×4×2\\ &=384.\ _\square \end{align}\]

If \(\frac{100 \times 99 \times 98 \times 97 \times \cdots \times 3 \times 2 \times 1}{100 \times 99}\) can be written as \(x!,\) what is the value of \(x?\)

---

We have

\[\begin{align} \dfrac{100 \times 99 \times 98 \times 97 \times \cdots \times 3 \times 2 \times 1}{100 \times 99} &=98 \times 97 \times 96 \times 95 \times \cdots \times 3 \times 2 \times 1\\ &=98!. \end{align}\]

So, the value of \(x\) is \(98.\) \(_\square\)

For any non-negative integer \(n,\) we find that

\[\dfrac{(2n+1)!}{(2n)!!}=(2n+1)!!.\]

Here, there is no need to consider two separate cases because, whether \(n\) is either odd or even, it makes no difference.

We can expand the expression as

\[\dfrac{(2n+1)×(2n)×(2n-1)\times \cdots ×3×2×1}{(2n)×(2n-2)×(2n-4)\times \cdots \times 4×2}.\]

We find that \(2n, 2n-2, 2n-4,\ldots , 4, 2\) get canceled (i.e. all the even numbers get canceled), leading us to this result:

\[\dfrac{(2n+1)!}{(2n)!!}=(2n+1)!!.\ _\square\]

For any non-negative integer \(n,\) we find that

\[\dfrac{(2n-1)!}{(2n-2)!!}=(2n-1)!!.\]

Again here, there is no need to consider two separate cases.

We can expand the expression in the LHS as

\[\dfrac{(2n-1)\times(2n-2)\times×(2n-3)\times \cdots \times3\times2\times1}{(2n-2)\times(2n-4)\times \cdots \times 4\times2}.\]

Since all the even numbers \(2n-2, 2n-4, \ldots, 4, 2\) get canceled, this equation is equivalent to

\[\dfrac{(2n-1)!}{(2n-2)!!}=(2n-1)!!.\ _\square\]

Note: Do not interpret \(n!!\) to be \((n!)!\). They are completely different.

Evaluate \(\dfrac{9!}{8!!}\).

---

We have

\[ \begin{align}
\dfrac { 9! } { 8!!} = & \dfrac{ (2 \times 5 - 1 ) ! } { (2 \times 5 - 2 ) !! } \\ = & (2 \times 5 - 1 )!! \\ = & 9 !! \\ = & 9 \times 7 \times 5 \times 3 \times 1 \\ = &945.\ _\square \end{align} \]

Evaluate \(\dfrac {(3!)!}{3!!}\).

---

We have

\[\begin{align} \dfrac {(3!)!}{3!!} &=\dfrac {(3×2×1)!}{3×1}\\ &=\dfrac {6!}{3}\\ &=\dfrac {6×5×4×3×2×1}{3}\\ &=\dfrac {720}{3}\\ &=240.\ _\square \end{align}\]

Stirling's approximation for \(n!\) says that

\[ n! \approx \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n.\]

Furthermore, we know of a good lower bound for \(n!:\)

\[n! \ge \frac{{ n }^{ n } \sqrt { 2\pi n }}{{e}^{n}}.\]

An interesting fact about factorials is that for any polynomial \(f(x)\), we can say for an integer \(n\) that \(n!>f(n)\) and for \(m>n\) that \(m!>f(m)\). We'll call this "overcoming" \(f(x)\).

A simple approach to show this is to use the lower bound already provided, and assume that \(n>1\). This tells us that

\[n! \ge \frac{{ n }^{ n } \sqrt { 2\pi n }}{{e}^{n}} \ge \left(\frac{n}{e}\right)^n.\]

For \(f(x)=a{x}^{k}\) it is clear that any exponential function with a base greater than 1 will "overcome" it by taking logs. Because \(\left(\frac{n}{e}\right)^n\) will grow faster than an exponential function for \(n>1\), it follows that it must also overcome \(f(x)\). As this was a lower bound for \(n!,\) we have shown \(x!\) overcomes \(a{x}^{k}\) for an arbitrary \(k\) and \(a\).

As polynomials are composed of such functions, the result follows.

While factorials are usually used with integers, they can be generalized for complex values (except negative integers) and expressed by an integral:

\[ n!=\Gamma (n+1)=\int _{ 0 }^{ \infty }{ \frac { { x }^{ n } }{ { e }^{ x } } } dx, \]

where \(\Gamma(n)\) is defined as \((n-1)!\). This is also written as \(\displaystyle z!=\Gamma (z+1)=\int _{ 0 }^{ \infty }{ { t }^{ z }{ e }^{ -t } } dt\).

A very nice derivation of this formula begins with the integral

\[\int { \frac { 1 }{ { e }^{ kx } } } dx=-\frac { { e }^{ -kx } }{ k } +C,\]

and hence

\[\int_{0}^{\infty} { \frac { 1 }{ { e }^{ kx } } } dx=\frac{1}{k}. \]

Then differentiate \(n\) times with respect to \(k\) to obtain

\[ \int_{0}^{\infty} { \frac { {(-x)}^{n} }{ { e }^{ kx } } } dx=\frac{{(-1)}^{n}n!}{{k}^{n+1}}. \]

Observe that \({(-1)}^{n}\) can be factored out from both sides, and then taking \(k=1,\) we arrive at

\[ n!=\int _{ 0 }^{ \infty }{ \frac { { x }^{ n } }{ { e }^{ x } } } dx.\ _\square\]

From this integral definition, some nice properties of \(\Gamma\left(\frac{n}{2}\right)\) can be derived. First, we need to compute \(\left(-\frac{1}{2}\right)!\) or \(\Gamma\left(\frac{1}{2}\right)\). This is found through the integral

\[\int _{ 0 }^{ \infty }{ \frac {1 }{ \sqrt { x } { e }^{ x } } } dx = \sqrt{\pi}.\]

Using this combined with \(\Gamma(n+1)=n\Gamma(n),\) you can arrive at

\[\left(n-\frac{1}{2}\right)!=\sqrt{\pi}\left(\frac{1}{2}\right)\left(\frac{3}{2}\right)...\left(n-\frac{1}{2}\right)=\sqrt{\pi}\prod _{ j=1 }^{ n }{ j-\frac { 1 }{ 2 } }. \]

All that is left is to simplify \(\prod _{ j=1 }^{ n }{ j-\frac { 1 }{ 2 } } \). This is easier once you express each term as a fraction:

\[\prod _{ j=1 }^{ n }{ j-\frac { 1 }{ 2 } } = \prod _{ j=1 }^{ n }{ \frac { 2j-1 }{ 2 } } = \frac{(2n)!}{{2}^{n}\prod _{ j=1 }^{ n }{ 2j } } = \frac{(2n)!}{{4}^{n}n!}. \]

Hence, the final result for \(\left(n-\dfrac{1}{2}\right)!\) is \(\sqrt{\pi}\dfrac{(2n)!}{{4}^{n}n!} \).

The idea of factorials is not confined to only double factorials, but there exist multi-factorials as well!

• Permutations

• Combinations