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:

$ 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 $ \{1, 2, 3\} $,

Here are permutations of order 3:

$ (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:

$ (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:

$ \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} $