1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Xoff Dec 14 '13 at 23:30
  • $\begingroup$ 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!! $\endgroup$ – Satish Ramanathan Dec 14 '13 at 23:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Xoff Dec 14 '13 at 23:44
  • $\begingroup$ 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. $\endgroup$ – ashley Dec 15 '13 at 0:14
  • 1
    $\begingroup$ @satishramanathan I agree with the answer of obinna. $\endgroup$ – Xoff Dec 15 '13 at 8:27
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.