2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – lulu Feb 21 '18 at 18:29
  • $\begingroup$ Would that be 5! x 4! x C(5,2) = 28,800? $\endgroup$ – Lucky12456 Feb 21 '18 at 18:31
  • $\begingroup$ For what? the number of patterns? No...there are very few patterns. $\endgroup$ – lulu Feb 21 '18 at 18:31
  • $\begingroup$ 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 $\endgroup$ – Lucky12456 Feb 21 '18 at 18:33
  • $\begingroup$ 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$. $\endgroup$ – lulu Feb 21 '18 at 18:34
3
$\begingroup$

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$$

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

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.

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

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.