Wikipedia:Reference desk/Archives/Mathematics/2009 October 9

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 9

Double check logic on this permutation question

I have a problem that basically equates to the following: I have 14 numbered boxes. I have 13 red balls, 13 blue balls, 13 green balls, and 13 yellow balls. I select balls at random without replacement from the combined total of 52 to place in the boxes. A valid combination must have at least one of each colour in the selected group of 14, and the order matters. As far as I can work out, this is a permutation problem, which looks like

(Number of permutations of 14 selected from 52) - (3 times the number of permutations of 14 selected from 39)

The subtraction term is designed to removes all permutations that ignore one colour. Is this accurate? Fritzpoll (talk) 09:07, 9 October 2009 (UTC)

First, it is 4 times rather than 3 times, as you have 4 different colours. Second, it still does not work, since there are also permutations which avoid two colours, and you have erroneously subtracted these twice. The correct answer is provided by the inclusion-exclusion principle: you need to further add ${\binom {4}{2}}=6$ times the number of permutations of 14 selected from 26. (In principle, you also need to subtract 4 times the number of permutations of 14 selected from 13, and add once the number of permutations of 14 selected from 0, but these are all zero.) — Emil J. 11:19, 9 October 2009 (UTC)

Or you can do it by the rather simpler method by first picking one ball from each colour and then randomly picking from the rest. I'll leave it to you to work out that logic. Hint : Think of a permutation as arranging the ones selected. Rkr1991 ^{(Wanna chat?)} 04:27, 10 October 2009 (UTC)

Hmm....that method definitely comes up with too many, so it would appear that I have translated my problem incorrectly. I actually have a 28 bit bitstring, made up from 14 selections of two-bit states (00,01,10,11) with the condition that each state must appear at least once in the string - all I want to work out is how many states that leaves - it's part of a proposal for some cluster time at work. Fritzpoll (talk) 11:48, 12 October 2009 (UTC)

I think the way to proceed is as follows. First of all, the fact that there are 13 balls of each colour, rather than infinitely many, doesn't actually make a difference to the problem, since if you have an assignment of balls to boxes with at least one of each of red, green, and blue, you can only fit in at most 11 yellows (for example). So a valid configuration will never use more than 11 of one colour, so you can forget about the number 13.

Now, the next step is to forget, briefly, that you want to be sure to get at least one of each colour. If you didn't have that condition, then you would have $4^{14}$ possibilities, since for each of the 14 slots, you would have four choices.

Now you have overcounted, and the way to deal with that is, as was suggested, inclusion-exclusion. You need to remove the $4(3)^{14}$ ways which use at most three colours. But now you have undercounted, because you removed those using at most two colours twice, so add those back in (there are $6(2)^{14}$; the 6 comes from the number of ways to choose which two colours), but you have now overcounted those using at most one colour; there are $4(1)^{14}$ of those.

Thus, the answer is $4^{14}-4(3)^{14}+6(2)^{14}-4(1)^{14}$Ctourneur (talk) 02:46, 15 October 2009 (UTC)

Thank you! Exactly what I was after Fritzpoll (talk) 13:02, 15 October 2009 (UTC)