The questions was this

The number 916238457 is an example of a nine digit number which contains each of the digit 1 to 9 exactly once .It also has the property that digits 1 to 5 occur in their natural order while digits 1 to 6 do not .Find number of such numbers.

So I did it like this I first chose 5 places from 9 available places.This can be done in 9C5 ways.Then I arranged the remaining letters in 4! Ways .Now for the third condition if 6 would appear before 5 then it will be automatically satisfied.Now For 6 there are only two possibilities, it can either appear before 5 or after 5 so I divided my answer by 2!. But my book says that the answer is 2520. I don't know what I am missing . Any help will be appreciated

  • 2
    $\begingroup$ Just because there are two possibilities, it doesn't follow that they are equally likely. If the first $5$ digits are $12345$ then there is no way to place the $6$. Consider how many ways there are to arrange the digits$1$ through $6$. $\endgroup$ – saulspatz Dec 3 at 16:06

Consider the string $12345$, the number $6$ can be inserted in $5$ places ( in order to fullfil the requirement of avoiding $123456$.) Now $7$ can be inserted in $7$ places, $8$ can be inserted in $8$ places and $9$ can be inserted in $9$ places. So that makes \begin{eqnarray*} 5 \times 7 \times 8 \times 9 = \color{red}{2520} \text{ ways.} \end{eqnarray*}

  • $\begingroup$ @saulspatz, No! There are 23 ways for 6-9 to not be in natural order, for each of the ways to choose the 5 places 1-5 are in which in PARI GP gives back 2898. This is the most free way, to interpret what is asked for. okay partially screwed up. still my point is valid. $\endgroup$ – Roddy MacPhee Dec 3 at 16:22
  • $\begingroup$ @RoddyMacPhee I was mistakenly thinking it was $10$ digits. I don't understand what $6-9$ not being in natural order has to do with is. $612345789$ is a valid sequence, with $6-9$ in natural order. $\endgroup$ – saulspatz Dec 3 at 17:04
  • $\begingroup$ I misread the question as well. But even with all orders of 6-9 valid, not caring for the 1-6 not natural order part you get 3024, my point is, it's not an order of magnitude ( only 1.2 times it) off. $\endgroup$ – Roddy MacPhee Dec 3 at 18:23

Its equal probability to see 1,2, 3, 4,5,6 in any of their all 720 ways to see them.

Now we want to see 612345 , 162345,126345,123645, or 123465.Which is 5 cases of 720 cases.

There are total of 9 factorial ways but we will multiply it by 5/720



Reword this till it is viable.

Lay out the $1$ to $5$ in order. Before the $1$, between any two numbers, and after the $5$ are potential "pockets" where we can put more numbers. There are six such pockets.

The $6$ is not in order so it can't go in the pocket after the $5$ and must go in one of the five pockets before the five but can go in any one of those $5$ pockets.

There are $5$ choices of where to put the six.

Placing the $6$ in a pocket, splits the existing one pocket into two and we have a new pocket immediately before and a new pocket immediately after the $6$. There as $7$ pockets now.

And we may place the seven in any of those $7$ pockets.

The seven will split a pocket to make $8$ pockets to place the $8$. And placing the eight in one of them will create $9$ pockets to place the $9$.

So there will be $5\cdot 7\cdot 8 \cdot 9=2520$ such numbers.


Alternatively there are $9$ spaces to put that $9$ digits. There are ${9\choose 5}$ spots to reserve for the $1$ to $5$ (which must be put in order). There are $4$ remaining spots for the remaining $4$ and $4! ways to arrange them. Thus ${9\choose 5}4!= 6*7*8*9$.

But we cant have the six in order. By same logic there are ${9\choose 6}3!$ to have the $1$ to $6$ in order so there are ${9\choose 5}4!-${9\choose 6}3!= 6*7*8*9- 7*8*9 =5*7*8*9$.


Or there are $9!$ ways to place them. There are $5!$ ways to to arrange the $1$ to $5$ in order. There are $6!$ ways to arrange the $1$ to $6$ in order so $\frac {9!}{6!}$ ways to place the $1$ to $6$ in order, and $\frac {9!}{5!} -\frac {9!}{5!} = 6*7*8*9 - 7*8*9$ to place the $1$ to $5$ in order and the $6$ not.


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.