AOCP/Permutations

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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_{n,k} = n(n-1)(\dots)(n-k+1) }

The total number of permutations is

$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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \{1, 2, 3\}} ,

Here are permutations of order 3:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2), (3 2 1) }

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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (4 2 3 1), (2 4 3 1), (2 3 4 1), (2 3 1 4) }

Method 2:

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} 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{align} }

Aaaaaand... yeah. No idea.

Factorial Identities

Factorial definition:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n! = 1 \cdot 2 \dots n = \prod_{1 \leq k \leq n} k }

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 0! = 1 }

and with this convention,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n! = (n-1)! n }

for all positive integers n.

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n! \approx \sqrt{2 \pi n} \left(\frac{n}{e} \right)^n }

Thus, for 8! = 40320:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 8! \approx 4 \sqrt{\pi} \left( \frac{8}{e} \right)^8 \approx 39902 }

Relative error of Stirling's formula is approximately Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align} }

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mu = 333 + 111 + 37 + 12 + 4 + 1 = 498 }

Therefore, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 1000!} is divisible by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3^{498}} , but not by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 3^{499}} .

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mbox{floor}\left(\frac{n}{p^{k+1}} \right) = \mbox{floor}\left( \frac{\mbox{floor}( \frac{n}{p^k} )}{p} \right) }

Binomial Coefficients

See AOCP/Binomial Coefficients

Multinomial Coefficients

See AOCP/Multinomial Coefficients

Generating Functions

See AOCP/Generating Functions