2
$\begingroup$

Here is the question: If one has 4 Blue cards and 6 Red cards, we wish to to know how many of these can be put in a row so that Blue cards will not be beside one another. I guess another way we can put it is that 2 or more blue cards cannot be consecutive. All blue cards are identical and all red cards are identical.

I tried to do this 2 ways and i got different results: Method-1) Do the permutation of all possible arrangements, removing duplicates. Then subtract a few cases of permutations, where all 4Blue together, then 3Blue together, then when 2Blue together. I get answer of 119.

Method-2) I found this other way online, where you put spaces between, so to illustrate : _R_R_R_R_R_R_

So those spaces are where the blue can go possibly. So there are a total of 7 spaces and 4Blue, therefore can use C(7,4). Total = Blue-Combination * Reds But because the Reds are all the same, they have only one way.

SO Total = C(7,4) * 1 which gives total = 35.

SO, I can't figure out which way would be correct here.

SO can this be done via both a permutations way and a combinations way?

Hope someone can help!

$\endgroup$
  • 2
    $\begingroup$ The second method is the correct one. If you were to do method 1, you will need to be especially careful but it is possible to arrive at the correct answer through a careful application of inclusion-exclusion principle. The danger in doing so however is that you can simultaneously have different groups of blues together at the same time and that it can be especially difficult to define the events correctly. $\endgroup$ – JMoravitz Nov 7 '17 at 23:00
  • $\begingroup$ The 35 is correct ... the first method should work as well, but is more work. ... if you provide more details about how you went about the first method we can try and find the mistake you made there. $\endgroup$ – Bram28 Nov 7 '17 at 23:15
1
$\begingroup$

As stated in the comments, the answer you obtained using the second method is correct. We can use the Inclusion-Exclusion Principle to correct your first method.

There are $$\binom{10}{6}$$ distinguishable ways to arrange four blue and six red cards in a row since choosing the positions of the red cards completely determines the arrangement of the cards. From these, we must exclude those arrangements in which there are one or more pairs of adjacent blue cards.

A pair of adjacent blue cards: We have nine objects to arrange: BB, B, B, R, R, R, R, R, R. We choose six of the nine positions for the red cards and one of the three remaining positions for the pair of adjacent blue cards. The other blue cards must fill the remaining two positions. Hence, there are $$\binom{9}{6}\binom{3}{1}$$ such arrangements.

Two pairs of adjacent blue cards: This can occur in two ways. Either we have an overlapping pair (three consecutive blue cards) or two separate pairs of blue cards.

  1. Two overlapping pairs: We have eight objects to arrange: BBB, B, R, R, R, R, R, R. We choose six of the eight positions for the red cards and one of the remaining two positions for the three adjacent blue cards. The remaining blue card must be placed in the remaining position. Hence, there are $$\binom{8}{6}\binom{2}{1}$$ such cases.
  2. Two separate pairs: We have eight objects to arrange: BB, BB, R, R, R, R, R, R. We choose six of the eight positions for the red cards. The remaining two positions must be filled with the two pairs of adjacent blue cards. Hence, there are $$\binom{8}{6}$$ such cases.

Three pairs of adjacent blue cards: This can only occur if there are four consecutive blue cards. We have seven objects to arrange: BBBB, R, R, R, R, R, R. We choose six of the seven positions for the six red cards. The four adjacent blue cards must be replaced in the remaining position. Hence, there are $$\binom{7}{6}$$ such cases.

By the Inclusion-Exclusion Principle, the number of arrangements of four blue and six red cards in which no two of the blue cards are consecutive is $$\binom{10}{6} - \binom{9}{6}\binom{3}{1} + \binom{8}{6}\binom{2}{1} + \binom{8}{6} - \binom{7}{6}$$

Note: When we subtract those arrangements in which there is a pair of adjacent blue cards, we subtract those arrangements in which there are two pairs of adjacent blue cards twice, once for each way we could designate one of those pairs as the excluded pair. We only want to subtract such cases once, so we must add them back.

When we subtract those arrangements in which there are a pair of adjacent blue cards, we subtract those arrangements in which there are three pairs of adjacent blue cards thrice, once for each way we could designate one of those pairs as the excluded pair. When we then add those cases in which there are two excluded pairs, we add those arrangements in which there are three pairs of adjacent blue cards thrice, once for each of the $\binom{3}{2}$ ways we could designate two of those three pairs as the excluded pairs. Since we have both added and subtracted these arrangements three times, we have not excluded them at all. Therefore, we must subtract the number of arrangements in which there are three excluded pairs.

$\endgroup$
  • 1
    $\begingroup$ Thanks Taussig, I see which cases I did not take into account. Thanks so much! $\endgroup$ – Palu Nov 8 '17 at 20:45
  • $\begingroup$ Hi there, I see you have put in Addition Signs, when I think that these should all be minus. Are we not subtracting all these consecutive cases from the grand total of everything. Please let me know Taussig. $\endgroup$ – Palu Nov 12 '17 at 19:29
  • $\begingroup$ I have added an explanation and a link to the Inclusion-Exclusion Principle to my answer. $\endgroup$ – N. F. Taussig Nov 12 '17 at 19:44
  • 1
    $\begingroup$ OK, I see the addition you made, labeling it as Notes. Thanks for the explanation. I see that this is much more complicated that i thought. I would not have thought that the Inclusion-Exclusion principle types would also add to the expression. Thanks I will mark your solution as THE solutions. Thanks so much Taussig for your further explanation. $\endgroup$ – Palu Nov 12 '17 at 23:13
0
$\begingroup$

By far the easiest is the way described with the gaps to get (7 choose 4) =35, which is the right answer.

There are (10 choose 6) = (10 choose 4) = 210 possible arrangements without the constraint but to get to 35 by removing those with 2 or more Bs together would be a lot more work.

$\endgroup$
  • $\begingroup$ Hi JMoravitz and Bram28, yes i do wish to know how to do it the other way as well. $\endgroup$ – Palu Nov 8 '17 at 0:25
  • $\begingroup$ Hi JMoravitz and Bran28, I wish to do this with Method #1 as well. Here is how i did my method #1: Get total permutation for everything, taking repetitive symbols into account you get Total = 10!/(6!4!). Then cases for Blue cards. Case1 = all 4 Blue together , = 7!/6!. Case2 = 3Blue together, 8!/6!. Case3 = 2Blue together = 8!/6!2!. SO Final Result = Total - Case1 - Case2 - Case3. But I get 119. SO I maybe missing another possibility then. But can't think of that possibility. $\endgroup$ – Palu Nov 8 '17 at 0:34

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.