Signless Stirling Numbers of 1st Kind and Probabilistic Descent

Question

I'm trying to see more clearly the reason behind the connection of the two following situations:

Situation 1: The signless Stirling numbers of the first kind, where $s(n,k)$ counts the number of permutations of $n$ elements that are comprised of a $k$ number of cycles.

Situation 2: Starting at $n$, choose a random integer in $0$ to $n-1$ (with equal likelihood). If you pick $0$, stop and say the process took 1 step. Otherwise repeat, counting the number of steps until $0$. Let $P(n,k)$ be the probability of starting at $n$ and taking $k$ steps to reach $0$. (You can think of this process as doing the Euclidean Algorithm where the remainders are always taken between $0$ and one less than the previous remainder.)

Working through a recursive computation for $P(n,k)$ leads to the fact that $$P(n,k) = \frac{s(n,k)}{n!}$$ (since $n!P(n,k)$ satisfies the same recursive formula as the signless Stirling numbers of the first kind. I can show the details if you think it'd help.)

My question: What is the relationship/reason behind the above equality? How does $s(n,k)$ count descents of length $k$ and/or vice versa?

For example: Take $n=4$, and $k=2$. Then $s(4,2) = 11$ coming from the 11 permutations: $(12)(34)$, $(13)(24)$, $(14)(23)$, $(123)(4)$, $(132)(4)$, $(124)(3)$, $(142)(3)$, $(134)(2)$, $(143)(2)$, $(1)(234)$, $(1)(243)$.

On the other side, $P(4,2)$ can be computed as follows: The 2-step decent $4-3-0$ happens with probability $\frac{1}{4}\cdot\frac{1}{3} = \frac{2}{24}$. The decent $4-2-0$ happens with probability $\frac{1}{4}\cdot\frac{1}{2} = \frac{3}{24}$. and $4-1-0$ has probability $\frac{1}{4} = \frac{6}{24}$. So $P(4,2) = \frac{11}{24}$.

So what's the explicit matching/counting going on between the $k$-cycle permutations and the $k$-step descents?

Answer 1

Start with an arbitrary permutation in $S_n$ written in cycle form:

\begin{align*} \psi := (\pi(n-1),\ldots,\pi(n_1))(\pi(n_1-1),\ldots,\pi(n_2))&\ldots(\pi(n_{k-1}-1),\ldots,\pi(n_k)) \end{align*}

Next, for $\ell = 1\ldots k$, define the sets $N_\ell$ as the collections of elements in each cycle of this permutation: \[ N_\ell := {\pi(n_{\ell-1}-1),\ldots,\pi(n_\ell)} \]

Now impose the following condition on the $N_\ell$:

\[ \max\left(\nu|\nu\notin\bigcup_{i<\ell}N_i\right)\in N_\ell \]

Clearly for a given permutation in cycle notation, this inclusion condition defines a unique order on the cycles (the leftmost cycle is the cycle containing the maximal element and from there one chooses the cycle with the largest remaining element to be the next cycle, and so forth). Then, given the ordered cycles one obtains a unique descent associated to $\psi$ by taking the lengths of each cycle to be the step sizes starting at $n$, so if $\psi$ satisfies the max element condition on its ordered cycles, we associate it to the descent $[n=n_0,n_1,\ldots,n_k=0]$.

Finally, one notes that the count of permutations whose cycle structure leads to a given descent is exactly the numerator of the probability for the original descent; since every permutation leads to some descent by this process, one gets the bijection you sought.

Another way to view the above bijection is that when you choose your first number, make a cycle of length represented by the difference of the number you chose from the start number, place the number $n$ at the start of your cycle and fill the remaining slots of the cycle however you like. Then choose your next descent step at random, form another cycle whose length is the difference between this step and the previous one, place the largest number not yet used at the start of the cycle, and fill the remainder any way you like with the unused numbers. Repeat until you exhaust your descent; at this point every number will have been put into some cycle and you will have a permutation corresponding to your particular descent.