# Volume 1

## Chapter 1: Basic Concepts

### Permutations and Factorials

If we have n distinct objects to arrange in a row, and order of placement matters, we can arrange these things in n! different ways.

For the first object, we have n choices of places to put it. For the second object, we have n-1 choices of places to put it. And so on.

In general, if we have to choose k objects out of n total, and arrange them in a row, we have the number of possibilities as:

${\displaystyle p_{n,k}=n(n-1)(\dots )(n-k+1)}$

The total number of permutations is

${\displaystyle p_{n,n}=n(n-1)\dots (2)(1)}$

The process of constructing a permutation of n objects, given all permutations of n-1 objects, is important. If we consider the case of three objects ${\displaystyle \{1,2,3\}}$,

Here are permutations of order 3:

${\displaystyle (123),(132),(213),(231),(312),(321)}$

Now, how to get to permutations of 4 objects?

Method 1:

For each permutation of n-1 elements, form n additional permutations by inserting the nth element in every possible open slot

Adding 4 to our set of objects and using method 1 gives:

${\displaystyle (4231),(2431),(2341),(2314)}$

Method 2:

For each permutation of the n-1 elements, form n new permutations by first constructing the array:

{\displaystyle {\begin{aligned}a_{1}a_{2}\dots a_{n-1}&\quad &{\frac {1}{2}}\\a_{1}a_{2}\dots a_{n-1}&\quad &{\frac {3}{2}}\\&\dots &\\a_{1}a_{2}\dots a_{n-1}&\quad &(n-{\frac {1}{2}})\end{aligned}}}

Aaaaaand... yeah. No idea.

### Factorial Identities

Factorial definition:

${\displaystyle n!=1\cdot 2\dots n=\prod _{1\leq k\leq n}k}$

${\displaystyle 0!=1}$

and with this convention,

${\displaystyle n!=(n-1)!n}$

for all positive integers n.

10! is a useful benchmark - it is around 3.5 million.

${\displaystyle 10!=3,628,800}$

10! represents an upper ceiling on computable tasks.

To tell how large a very big factorial is going to be, use Stirling's formula:

${\displaystyle n!\approx {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}}$

Thus, for 8! = 40320:

${\displaystyle 8!\approx 4{\sqrt {\pi }}\left({\frac {8}{e}}\right)^{8}\approx 39902}$

Relative error of Stirling's formula is approximately ${\displaystyle {\dfrac {1}{12n}}}$

To obtain the exact value of n! factored into primes, we can use some useful identities. First, the prime p is a divisor of n! with multiplicity:

{\displaystyle {\begin{aligned}\mu &=&{\mbox{floor}}({\frac {n}{p}})+{\mbox{floor}}({\frac {n}{p^{2}}})+{\mbox{floor}}({\frac {n}{p^{3}}})+\dots \\&=&\sum _{k>0}{\mbox{floor}}({\frac {n}{p^{k}}})\end{aligned}}}

As an example, for n = 1000, p = 3,

${\displaystyle \mu ={\mbox{floor}}({\frac {1000}{3}})+{\mbox{floor}}({\frac {1000}{9}})+{\mbox{floor}}({\frac {1000}{27}})+{\mbox{floor}}({\frac {1000}{81}})+{\mbox{floor}}({\frac {1000}{243}})}$

which gives

${\displaystyle \mu =333+111+37+12+4+1=498}$

Therefore, ${\displaystyle 1000!}$ is divisible by ${\displaystyle 3^{498}}$, but not by ${\displaystyle 3^{499}}$.

Furthermore, to speed up the calculation of the above, we can use the identity

${\displaystyle {\mbox{floor}}\left({\frac {n}{p^{k+1}}}\right)={\mbox{floor}}\left({\frac {{\mbox{floor}}({\frac {n}{p^{k}}})}{p}}\right)}$