KBB2 Problem 10

Let $P$ be a permutation of the number $(1,2,\cdots,n)$. We apply a process as follows:

Start with the leftmost number and move to the right. Everytime we encounter a number that's bigger than the leftmost number, we swap that number and the leftmost number. Continue until we arrive at the rightmost number.

Define the rank of $P$ as the number of swaps that happened. For example, the permutation$(2,3,1,4)$ has rank 2 because:

$\displaystyle (2,3,1,4) \to (3,2,1,4) \to (4,2,1,3)$

Let$S_n$ be the sum of the ranks of all possible permutations of $(1,2,\cdots,n)$. Is there an $n$ for which$S_n > 2009n!$?

Solution

First, note that the rank of a sequence does not depend on the actual numbers but only on relative ordering of the numbers. For example, $(2,3,1)$ and $(3,4,1)$ has the same rank.

Now we shall prove that

$\displaystyle S_n =n! \left(\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right)$

Proof by induction: It's easy to verify that $S_1 = 0, S_2 = 1$. Now suppose it holds for $n=k$, we shall compute $n=k+1$:

Consider the number 1. If it's not the leftmost number, it will simply be ignored and passed by. The sequence rank will be determined by the numbers $2,3,\cdots,k+1$. In other words, if we delete 1 from the sequence, we are left with a new sequence of $k$ numbers. The sum of rank of all possible permutations of this sequence is the same as $S_k$ because as we stated above, the rank of a sequence is only determined by its ordering.

There are $k$ possible places for the number 1 not to be leftmost, therefore the total number of rank from this possibility is $kS_k$. For example, (3,1,2,4) has the same rank as (3,2,4), but it has the same rank as (3,2,1,4) and (3,2,4,1) as well.

If 1 is the leftmost number, it will be swapped with the second number in the sequence, and afterwards, the operation continues as usual. The rank of that sequence is the same as the rank of the remaining "tail" of the sequence. Thus, for each sequence where 1 is the leftmost number, we add 1 to the rank for the initial swap. There are $k!$ sequences where this is the case, so the total number of rank from this possibility is $S_k + k!$

So now we have the recursive formula: $S_{k+1} = kS_k + (S_k + k!)$

It's easy to show that the formula above satisfies the recursion.

Since the harmonic sum is unbounded, we conclude that there is a number $N$ for which $S_N > 2009N!$