## Position in a random permutation

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$$?

[SOLVED]

#### 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.

1. Let $$p = ()$$.
2. For each $$i$$ in $$(n, n - 1, \dots, 1)$$, insert $$i$$ into $$p$$ after the $$\bigl(iv[i]\bigr)$$th element of $$p$$.

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

### Credit

This puzzle is taken from folklore.