A contest question on probability Let A denote the set of those 6-digit positive integers in which each of the digits $1, 2, 3, 4, 5, 6$ appears exactly once. An integer in A, having standard decimal representation $d_1d_2 \cdots d_6$, is called nice if for each $k = 1, 2, 3, 4, 5$ the set {$d_1,.., d_k$} contains at least one digit strictly greater than $k$ (for example, 234561 is nice, whereas 321645 is not nice). From $A$, an integer $n$ is randomly picked. What is the probability that $n$ is nice? 
My try:
Run the last digit from 1 through 6 and find the combinations by scanning the digits greater than the last digit across the first five positions in each of these scenarios.  It is pretty cumbersome and I am wondering if there could be anything simpler by means of symmetry or something like that as it does not give us any pattern. :
$234561 - 5!=120$
$345612 - 4*4! =96$
$456123 - 3*4!+3*3! = 90$
$561234 - 2*4!+4*3!+6*2! = 84$
$612345 - 1*4!+3*3!+8*2!+13*1! = 71$
$123456 - =0$
Total number of ways = $6! = 720$
Required probability = $$\frac{120+96+90+84+71}{720} = \frac{461}{720}$$
A simpler solution would be very much appreciated after verifying the answer.
 A: To make the problem more general, let's say that we are interested in $M$ digit positive integers which contain numbers $1,2,3,...,M$.
A number is called nice if for each $k \in {1,2,3,...,(M-1)}$ , at least one digit out of $d_1,..,d_k$ is strictly greater than $k$.
We are interested in counting the numbers which are not nice.
Notice that if a number is not nice, it must have some index which is the first index that violates the nice property. i.e. there must be some minimum index $j+1$ such that $d_1,..,d_{j}$ has some $l \le j$, such that $d_l>j$, but $d_{j+1}$ has no such $l$.
Let's define $T(n)$ as the number of $n$ digit numbers for which the smallest digit that violates the nice property is $d_n$. It's easy to see that $T(M)$ gives the exact number of $M$ digit nice numbers.
Also, notice that since the smallest position, $i$ which violates the nice property has $d_i$ we see that $d_1,d_2,...,d_i$ must be permutations of $1,2,3,...,i$ for which $d_1,d_2,...,d_{i-1}$ obey the nice property but $d_{i}$ doesn't. This is because if we had some integer greater than $i$ among $d_1,d_2,...,d_{i}$, then $d_i$ must also obey the nice property.
Also note that we can count the number of nice numbers by considering the smallest position which violates the nice property over all $n$ digit numbers.
In particular once we know what this minimum violating index is, we can simply permute the remaining numbers. This leads us to the following recurrence relation
$$T(n) = n! - \sum_{i=1}^{n-1} T(i)(n-i)!$$$$T(1)=T(2)=1$$
Note that $\sum_{i=1}^{n-1} T(i)(n-i)!$ is the total number of numbers that are not nice.
Going back to the original question, the probability is simply 
$$\frac{T(M)}{M!}$$ where $M=6$.
We see that $T(6)=461$ and hence the answer is $\frac{461}{720}$
Xoff pointed out in a comment above that $T(n)$ has an OEIS entry
