Suppose we have $n$ days, and a job consisting of a number of sequential stages, so that each stage takes a day. Consider following stochastic process: the day $t$ for each stage is picked randomly from natural domain, but keeping the ordering of stages. As a result we get a random sequence of naturals $\{t_1, t_2,...\}$ with conditions: $0<t_i\leq n$, $i<j$ implies $t_i<t_j$. The sequence rapidly becomes dence as $t_i$ approaches to $n$, and at some point it is impossible to add new term, so the sequence terminates. I wish to find a probability $P_n(k)$ to get a sequence of $k$ terms for fixed $n$ by described process.
I have obtained empirical PMF for the distribution, using a simple program, and it looks good. But I want to get the analytic result.
The PMF for n = 10 obtained by imitational modelling
Also I have found solution for few special cases and a recurrent expressions for the PMF: $$P_n(1)=0,\\ P_n(2)=\frac{1}{n},\\ P_n(3)=\frac{1}{n}H_{n-1},\\ P_n(k)=\frac{1}{n}[P_{n-1}(k-1)+P_{n-2}(k-1)+...+P_{k-2}(k-1)],\\ P_n(n-1)=\frac{n(n-1)}{2n!}=\frac{1}{(n-2)!},\\ P_n(n)=\frac{1}{n!},$$ here $H_n$ is a harmonic number.
Moreover I could find exact expression for the expected value of $k$ for given $n$: $$\mathbf{E}(k) = H_{n}.$$ This distribution should be named harmonic distribution :) I would be happy to find a complete closed form solution. Combinatorial approach didn't help, unfortunately.
It appears that I have found (almost guessed) the answer. The PMF for the length of sequences build by described process could be computed exactly in closed form using Stirling numbers of the first kind: $$ P_n(k) = \genfrac{[}{]}{0pt}{}{n}{k}\frac{1}{n!}\\ E(k) = H_n\\ Var(k) = H_n - H_n^{(2)} $$ Even though I'm interested in a proof, especially combinatorial. It is obvious that factorial in denominator counts all possible sequences, however, what is a connection between ordered sequences and cycles, which are counted by Stirling numbers?
Does anyone know the name of this distribution?