# Order of Even and Odd Digits

Problem: Find the number of ways to write digits $1$ through $9$ in a row (so each digit appears exactly once) and no two EVEN digits are next to each other.

So this is what I have conceived thus far, I would appreciate if someone could help me connect it to a solution.

Basic Structure: Even1, Odd1, Even2, Odd2, Even3, Odd3, Even4, Leftover: Odd4, Odd5

$1,3,5,7,9$ (Odds) $5! = 120$ combinations $2,4,6,8$ (Even) $4! = 24$ combinations

Do I multiply the two permuatations with $\binom{5}{2}$ to find the answer?

• Hint: place the even numbers with spaces between them, as $aE_1bE_2cE_3dE_4e$ where the $E_i$ are the even digits, $a+b+c+d+e=5$ , each of $a,b,c,d,e$ are non-negative integers, and $b,c,d>0$. Now figure out how many acceptable $5-$tuples $(a,b,c,d,e)$ there are. Once you have all the available patterns, it is easy to count the ways to populate them. – lulu Feb 21 '18 at 18:29
• Would that be 5! x 4! x C(5,2) = 28,800? – Lucky12456 Feb 21 '18 at 18:31
• For what? the number of patterns? No...there are very few patterns. – lulu Feb 21 '18 at 18:31
• I'm not following your logic. I know the possible outcomes for even and odd ordering respectively, but I struggle with factoring in the order of the sequence – Lucky12456 Feb 21 '18 at 18:33
• My logic: count the possible patterns, call the answer to this $n$. Of course, for any fixed pattern there are $5!\times 4!$ ways to populate it so the answer is $5!\times 4!\times n$. – lulu Feb 21 '18 at 18:34

Let odd numbers be $O_1, O_2, O_3, O_4, O_5$. Then let us put them as in the following where "_" are the empty places where we can put even digits:

$$\_O_1\_O_2\_O_3\_O_4\_O_5\_$$

Then since in each blank "$\_$" we can put only one even digit (because if we put two, they will be next to each other), we can choose the places for four even digits with $\binom{6}{4} = 15$ and change their orders with $4!$. Notice that we can also change the order of odd digits with $5!$ so the answer should be $$\binom{6}{4}\cdot4!\cdot5! = 15\cdot24\cdot120 = 43200$$

• I like this answer much better than mine. – John Feb 21 '18 at 18:47
• Thank you very much @John :) – ArsenBerk Feb 21 '18 at 18:48

You can have the following nine fifteen patterns:

$$EOEOEOEOO,\\ EOEOEOOEO,\\ EOEOOEOEO,\\ EOOEOEOEO, \\OEOEOEOEO, \\OOEOEOEOE, \\OEOOEOEOE, \\OEOEOOEOE, \\OEOEOEOOE, \\EOOOEOEOE, \\EOEOOOEOE, \\EOEOEOOOE, \\EOOEOOEOE, \\EOOEOEOOE, \\EOEOOEOOE.$$

There are $5!$ ways to arrange the odd digits for each, and $4!$ ways to arrange the even digits. So, $15 \cdot 5! \cdot 4! = 43200$ ways.

• How about $EOOOEOEOE$? Your count seems to assume that we must have an odd number at (at least) one of the ends. – lulu Feb 21 '18 at 18:39
• Uh ... yeah ... that one too ... O_o ... LOL – John Feb 21 '18 at 18:40
• So it should actually be 10 x 5! x 4!? – Lucky12456 Feb 21 '18 at 18:43
• @Lucky12456 I don't think there are $10$ ways, it should be $15$. – ArsenBerk Feb 21 '18 at 18:44
• There are others. I think I have them all this time! :) (@ArsenBerk, yes, I think so.) – John Feb 21 '18 at 18:44