Algorithms/Combinatorics

Notes

Knuth AOCP Volume 3 Sorting and Searching

5.1 Combinatorics

Knuth begins talking about sorting by talking about combinatorics and permutations of items.

Start with definition of an inversion:

Let $ a_1 a_2 a_3 \dots a_n $ be a permutation of the integers $ {1 \dots n} $.

If $ i < j $ and $ a_i > a_j $, then $ (a_i, a_j) $ is an inversion.

Inversions are out-of-sorts pairs.

Cramer (1750) introduced inversions - utilized to find determinant.

Can also construct an inversion table:

Let $ b_1 b_2 \dots b_n $ denote the inversion table of $ a_1 a_2 \dots a_n $. Then $ b_j $ is the number of elements to the left of j that are greater than j.

Example of sequence and its inversion table:

5 9 1 8 2 6 4 7 3
2 3 6 4 0 2 2 1 0

$ 0 \leq b_1 \leq n-1, 0 \leq b_2 \leq n-2, \dots, 0 \leq b_{n-1} \leq 1 $

Hall (1956) showed that inversion tables uniquely determine permutations - these make inversion tables alternative representations for different permutations.

Transformation technique: turn counting problems into inversion table problems

Now, suppose we want to count number of elements larger than their successor. (This is the number of j such that $ b_j = n-j $).

Note that this idea is related to nested for loops:

for(int i = 0; i < N; i++ ) {
    for(int j = i; j < N; j++) { 

We have $ b_j = n - j $

Since we know the probability that b1 equals n-1 is $ P(b_1 = n-1) = \frac{1}{n} $,

and independently the probability that b2 equals n-2 is $ P(b_2 = n-2) = \frac{1}{n-1} $,

and so on, then we can say:

$ \dfrac{1}{n} + \dfrac{1}{n-1} + \dots + 1 = H_{n} $

These are the harmonic numbers.