Shorter Version. Pick a list $\mathbf{a}$ of length $n$, taking in values in $\{1,2,\ldots,n+1\}$ at random. Then sort $\mathbf{a}$ in increasing order to obtain $\mathbf{a}' = (a_{(1)}, \ldots, a_{(n)})$, and count the number of times $a_{(k)} \leq k$ holds.
Conjecture: The resulting count takes in values $0, 1, \ldots, n$ equally likely.
How do we prove or disprove this conjecture?
Longer Version. The setting is as follows:
$\mathcal{A}_n = \{1, 2, \ldots, n+1\}^n$ is the collection of all lists of length $n$ taking integer values between $1$ and $n+1$.
For each list $\mathbf{a} \in \mathcal{A}_n $, we sort $a$ in increasing order to obtain $\mathtt{sort}(\mathbf{a}) = (a_{(k)})_{k=1}^{n}$. Equivalently, $a_{(k)}$ denotes the $k$th smallest element in $\mathbf{a}$. For example, $$ \mathtt{sort}(5, 1, 2, 7, 5, 2) = (1, 2, 2, 5, 5, 7). $$
Then, define the function $\mathtt{below}(\mathbf{a})$ as the number of $k$'s for which $a_{(k)} \leq k$ holds, that is, $\mathtt{below}(\mathbf{a}) = \sum_{k=1}^{n} \mathbf{1}[a_{(k)} \leq k]$. For example, $$ \mathtt{below}(5, 1, 2, 7, 5, 2) = \mathtt{below}(\underline{1}, \underline{2}, \underline{2}, 5, \underline{5}, 7) = 4. $$
While playing with this setting with computer software, I noticed some patterns that eventually led me to formulate the following conjecture:
Conjecture. Sample $A$ from $\mathcal{A}_n$ uniformly at random. Then $\mathtt{below}(A)$ is uniformly distributed over the set $\{0, 1, \ldots, n\}$.
How do we prove or disprove this?
Discussion. For example, if $n = 2$, then
$$ \begin{array}{c} \mathbf{a} \\ (1, 1) \\ (1, 2) \\ (1, 3) \\ (2, 1) \\ (2, 2) \\ (2, 3) \\ (3, 1) \\ (3, 2) \\ (3, 3) \end{array} \quad \longrightarrow \quad \begin{array}{c} \mathtt{sort}(\mathbf{a}) \\ (1, 1) \\ (1, 2) \\ (1, 3) \\ (1, 2) \\ (2, 2) \\ (2, 3) \\ (1, 3) \\ (2, 3) \\ (3, 3) \end{array} \quad \longrightarrow \quad \begin{array}{c} \mathtt{below}(\mathbf{a}) \\ 2\vphantom{,)} \\ 2\vphantom{,)} \\ 1\vphantom{,)} \\ 2\vphantom{,)} \\ 1\vphantom{,)} \\ 0\vphantom{,)} \\ 1\vphantom{,)} \\ 0\vphantom{,)}\\ 0\vphantom{,)} \end{array} $$
and hence $\mathtt{below}(A)$ takes values $0, 1, 2$ with equal probabilities. Also, using computer software, I tested this conjecture for $n \leq 7$. However, brute-force search goes quickly out of hand as $n$ gets larger. And I was unable to come up with a nice explanation of this observation, letting alone a proof.
Context. This can be thought of as a discrete analog of the fact that, for the Brownian bridge $(B_t)_{t\in[0,1]}$ joining $(0, 0)$ to $(1, 0)$, the occupation time $\int_{0}^{1} \mathbf{1}[B_t \geq 0] \, \mathrm{d}t$ is uniformly distributed over $[0, 1]$. Indeed, a version of invariance principle tells that
$$t \mapsto n^{-1/2}(\lfloor nt\rfloor - a_{(\lfloor nt\rfloor)})$$
tends to the Brownian bridge as $n \to \infty$ in an appropriate sense. So, it is reasonable to expect that $\mathtt{below}(A)$ is approximately uniformly distributed. What is quite surprising is that $\mathtt{below}(A)$ seems exactly uniformly distributed.
We begin with sorted lists. There are $\binom{n+1+n-1}n=\binom {2n}n$ such lists by identifying each sorted lists to the number of solutions to $x_1+\cdots + x_{n+1}=n$ in nonnegative integers. Here, $x_i$ is the number of $i$'s in a given list.
Then we identify a given sorted list $\bf a$ to a lattice path $L(\bf a)$ in $[0,n]\times[0,n]$, (paths consisting of $\rightarrow$, $\uparrow$) by putting $x_i$ $\uparrow$'s on the $i$-th vertical line from the left. Then for a given sorted list $\bf a$,
below($\bf a$) is the number of $\uparrow$'s of $L(\bf a)$ in the region $y\geq x$ (this is called the "exceedance" in the third proof here: https://en.wikipedia.org/wiki/Catalan_number).
Following the procedure there:
$\bullet$ Starting from the bottom left, follow the path until it first travels above the diagonal.
$\bullet$ Continue to follow the path until it touches the diagonal again. Denote by X the first such edge that is reached.
$\bullet$ Swap the portion of the path occurring before X with the portion occurring after X.
It is proved that exceedance within $\binom {2n}n$ lattice paths is uniformly distributed on $\{0,\ldots, n\}$. Thus, each number is attained exactly $C_n = \frac1{n+1}\binom {2n}n$ times. Indeed, the procedure gives a bijection between all paths with exceedance $k+1$ and all paths with exceedance $k$. Moreover, this exceedance dropping bijection does not change the multiset $\{x_1,\ldots, x_{n+1}\}$.
Therefore, in the following $$ {\bf a} \mapsto {\rm sort}({\bf a}) \mapsto L({\rm sort}({\bf a}))\mapsto {\rm exceedance}(L({\rm sort}({\bf a}))), $$ each number in $\{0,\ldots, n\}$ is attained equally many times.