number of n sorted numbers such that there's exactly one number that $a_i = i$

Question

How many $(a_1,a_2,...,a_n)$ are there such that $$ 1 \le a_1 \le a_2 \le ... \le a_n \le \ (n, a_i \in \mathbb{N} ) $$ and there's exactly one $i$ such that $a_i = i$ ?

Answer 1

I’m assuming that that the displayed line should be understood as

$$1\le a_1\le a_2\le\ldots\le a_n\le n,\text{ where all }a_i\in\Bbb N\;.\tag{1}$$

I’ll call a sequence $\langle a_1,\ldots,a_n\rangle$ that satisfies $(1)$ and is such that $a_k=k$ for exactly one $i\in[n]$ a good sequence.

Let $\langle a_1,\ldots,a_n\rangle$ be a good sequence, and let $k$ be the unique index such that $a_k=k$; clearly $a_{k-1}=k$ if $k>1$, and $a_{k+1}=k$ if $k<n$. We can interpret the sequence $\langle a_{k+1},\ldots,a_n\rangle$ as a lattice path (using only unit steps to the right or up) from $\langle k+1,a_{k+1}\rangle=\langle k+1,k\rangle$ to $\langle n+1,n\rangle$: specifically, we let $a_{n+1}=n$, and for $i=k+1,\ldots,n$ we get from $\langle i,a_i\rangle$ to $\langle i+1,a_{i+1}\rangle$ by taking one step to the right and then $a_{i+1}-a_i$ steps up. It’s not hard to see that this path never rises above the line $y=x-1$. Conversely, any lattice path from $\langle k+1,k\rangle$ to $\langle n+1,n\rangle$ that never rises above the line $y=x-1$ can be described by such a sequence $\langle a_{k+1},\ldots,a_n\rangle$. There are $C_{n-k}$ such lattice paths, so there are $C_{n-k}$ possibilities for the sequence $\langle a_{k+1},\ldots,a_n\rangle$.

Similarly, the initial sequences can be interpreted as lattice paths from $\langle 0,1\rangle$ to $\langle k-1,k\rangle$ that never drops below the line $y=x+1$: we let $a_0=1$ and for $i=1,\ldots,k-1$ we take $a_i-a_{i-1}$ steps up followed by one step to the right. And every lattice path from $\langle 0,1\rangle$ to $\langle k-1,k\rangle$ that never drops below the line $y=x+1$ can be represented by such a sequence, so there are $C_{k-1}$ possibilities for the sequence $\langle a_1,\ldots,a_{k-1}\rangle$.

Putting the pieces together, we must have $C_{k-1}C_{n-k}$ good sequences such that $a_k=k$, and summing over $k$ yields a total of

$$\sum_{k=1}^nC_{k-1}C_{n-k}=\sum_{k=0}^{n-1}C_kC_{n-1-k}=C_n$$

good sequences of length $n$.

As a quick sanity check we can enumerate the good sequences for $n=1,2,3,4$ to see that there are indeed $1,2,5$, and $14$ of them, respectively:

$$\begin{align*} n=1:\;&1\\ n=2:\;&11,12\\ n=3:\;&111,112,222,233,333\\ n=4:\;&1111,1112,1113,1122,1123,2222,2223,\\ &2333,2344,2444,3333,3344,3444,4444 \end{align*}$$