In a random permutation of the first \(n\) natural numbers, what is the probability that \(k\) appears before all the numbers greater than itself where \(1 \le k \le n\)?

Sunday, July 1, 2012

Please email your solutions to puzzles@cotpi.com.

This puzzle is taken from folklore.

## Tim Ophelders solved this puzzle:

Call a permutation in which \(k\) appears before all the numbers greater than itself correct and let \(p(X, k)\) denote the probability that a random permutation of \(X\) is correct. What is the probability, \(p(1..n, k)\), that a random permutation of the first \(n\) natural numbers is correct?

\(p(k..n,k) = \frac{1}{|k..n|} = \frac{1}{n - k + 1}\) because a permutation of \(k..n\) is correct if and only if it starts with \(k\). All other numbers are greater than \(k\); thus if \(k\) is not in the first position, a greater number must take its place, making the permutation incorrect.

Note that inserting any number of numbers less than \(k\) to an arrangement does not affect its correctness. Since every number in \(1..n \setminus k..n = 1..(k-1)\) is less than \(k\), \(p(1..n, k) = p(k..n, k) = \frac{1}{n - k + 1}\).

## Rino Raj solved this puzzle:

Let us consider \(k\) appearing at the \(x\)th place, where \(1 \le x \le k\). \(x \in \{1, 2, \dots, k\}\) because if \(x > k\), then at least one of the places before \(k\) must be occupied by a number larger than \(k\), which is not permissible. Since all the numbers that appear before \(k\) must be smaller than \(k\), there are \(P(k - 1, x - 1)\) ways of arranging numbers in the first \(x - 1\) places. The remaining numbers can be arranged in one of \((n - x)!\) ways after \(k\). Hence there are \(\frac{(k - 1)! \cdot (n - x)!}{(k - x)!}\) ways to arrange the numbers such that \(k\) is at the \(x\)th place and it appears before all the numbers greater than itself.

As there are \(k\) possible values of \(x\) from \(1\) to \(k\), the total number of ways to have the required arrangement is

\begin{align} \sum_{x=1}^k \frac{(k - 1)! \cdot (n - x)!}{(k - x)!} & = (k - 1)! \sum_{x=1}^k \frac{(n - x)!}{(k - x)!} \notag \\ & = (k - 1)! \sum_{x=1}^k \binom{n - x}{n - k} (n - k)! \notag \\ & = (k - 1)! \cdot (n - k)! \cdot \sum_{x=1}^k \binom{n - x}{n - k} \notag \\ & = (k - 1)! \cdot (n - k)! \cdot \sum_{i=n-k}^{n-1} \binom{i}{n - k}. \label{eq1} \\ \end{align}

From the hockey-stick identity, we get

\begin{equation} \label{eq2} \sum_{i=n-k}^{n-1} \binom{i}{n - k} = \binom{n}{n - k + 1}. \end{equation}

Using \eqref{eq1} and \eqref{eq2}, we get

\begin{align*} \sum_{x=1}^k \frac{(k - 1)! \cdot (n - x)!}{(k - x)!} & = (k - 1)! \cdot (n - k)! \cdot \sum_{i=n-k}^{n-1} \binom{i}{n - k} \\ & = (k - 1)! \cdot (n - k)! \cdot \binom{n}{n - k + 1} \\ & = (k - 1)! \cdot (n - k)! \cdot \frac{n!}{(n - k + 1)! (k - 1)!} \\ & = \frac{n!}{n - k + 1}. \end{align*}

Since the total number of possible permutations of \(n\) natural numbers is \(n!\), the required probability is \(\frac{1}{n - k + 1}\).

## Mike Terry solved this puzzle:

There are \((n - k + 1)\) numbers greater than or equal to \(k\). The probability that \(k\) appears first out of these numbers is \(\frac{1}{n - k + 1}\).

## Atul S Vasu solved this puzzle:

Consider the inversion vector \(iv\) of a permutation of the first \(n\) natural numbers. It is defined as \(iv[i] =\) the number of elements greater than \(i\) to the left of \(i\) in the permutation where \(i\) is an integer such that \(1 \leq i \leq n\).

There is a bijection between the set of permutations of the first \(n\) natural numbers and the set of all integer vectors \(iv\) that satisfy \(0 \leq iv[i] \leq n - i\). For every permutation of the first \(n\) natural numbers, there is a unique integer vector \(iv\) such that \(0 \leq iv[i] \leq n - i\) by the definition of \(iv\). Similarly for every integer vector \(iv\) where \(0 \leq iv[i] \leq n - i\), we can obtain a unique permutation \(p\) of the first \(n\) natural numbers using the following construction procedure.

Now, we need to find the number of possible inversion vectors \(iv\) such that \(iv[k] = 0\). Since each \(iv[i]\) is an integer that can vary from \(0\) to \(n - i\) when \(i \neq k\), the total number of such inversion vectors is \(\frac{n!}{n - k + 1}\). Therefore, the required probability is \(\frac{1}{n - k + 1}\).