# Finding total number of possible numbers using below condition

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

• 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$. – 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*}$$

• @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. – Roddy MacPhee Dec 3 at 16:22
• @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. – saulspatz Dec 3 at 17:04
• 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. – 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

9!*(5/720)=2520

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.