Consider an urn containing $n$ balls numbered $1,2,3\dots n$. $k$ balls are picked from this urn,one by one, with replacement, what is the probability of obtaining a non decreasing sequence?
I figured out that after picking the first ball, all the balls before the ball that was picked first will be ‘removed’ because we can’t pick any of those balls if we want a non decreasing sequence, but this is as far as i got, can someone help me out.
If you are working without replacement, it is simple and the answer will then be $1/k!$ since one of the sequences if you reorder them afterwards is a valid sequence.
Your problem is, I think, a bit more difficult. If you condition on the first ball you could work it out: $$p_k(|0)=\sum_{i=1}^{n} \left(p_{k-1}(|i)\cdot\frac1n\right) = \frac{1}{n}\sum_{i=1}^{n}p_{k-1}(|i)$$ where I used the notation $p_m(|j)$ to denote the probability of an increasing sequence if you draw $m$ balls given that in the last turn we drew ball $j$. Now I would guess that $$p_{k-1}(|i)=\left(1-\frac{i-1}n\right)^{k-1}\cdot p_{k-1}(|0)$$ And from this relation we find $$p_k(|0)=\frac{p_{k-1}(|0)}{n}\cdot \sum_{i=1}^{n} (1-(i-1)/n)^{k-1}.$$ We can simplify this a bit $$p_k(|0)=\frac{p_{k-1}(|0)}{n^k}\cdot \sum_{i=1}^{n} i^{k-1}.$$ There are formulas for the latter formula, but in general you should expect a polynomial in $n$ of degree $k$. Let's say this sum is given by $s_{k-1}$, then $$p_k(|0) = \left(\frac{1}{n^k}\right)^{k-1} \cdot\left(\prod_{i=1}^{k-1} s_{i}\right)\cdot p_1(|0) = \frac{1}{n^{k(k-1)}} \cdot\left(\prod_{i=1}^{k-1} s_{i}\right)$$ since $p_1(|0) = 1$.
EDIT: this might not be the smartest method but, give or take maybe a few calculation errors in the above, it does work.