# 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.

• It's late here, and I'm note sure what you did, but I just found $461$ instead of $446$, but perhaps I made a mistake ? – Xoff Dec 14 '13 at 23:30
• Could you show your working? Did you take the cue from me to work or is it something simpler than what I did? Let me know tomorrrow when you have a chance. It could be possible that I made a mistake too!! – Satish Ramanathan Dec 14 '13 at 23:34
• I made some recurrence relations and found the sequence oeis.org/A003319 which is indeed what you want. If needed, I'll give an explanation tomorrow. – Xoff Dec 14 '13 at 23:44
• The definition of nice integers reads like the following and nothing else: $d_5$ has to be 6-- since it's the only digit greater than 5. When $d_5=6$, $d_4=5$, .., $d_1=2$. And the only nice integer is 234561. something missing here. – ashley Dec 15 '13 at 0:14
• @satishramanathan I agree with the answer of obinna. – Xoff Dec 15 '13 at 8:27

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

• Nice solution, This is exaxtly what I was looking for. Thanks to Xoff too!!. – Satish Ramanathan Dec 15 '13 at 15:09
• @Xoff,obinna: I found the extra 5 counts missing and you guys are right on the answer. – Satish Ramanathan Dec 15 '13 at 19:31