At a restaurant, two children each receive a packet of four crayons, each a different color. They combine their crayons (to make four pairs) and line them up randomly on the table. What is the probability that all pairs of adjacent crayons are different colors? Repeat for two and three pairs of crayons.
Source: It just, uh, came to me...
From Kirk Bresniker:
Here's the probabilities for two to seven pairs: 2 = 2/6 = 0.333 3 = 30/90 = 0.333 4 = 864/2520 = 0.343 5 = 39480/113400 = 0.348 6 = 2631600/7484400 = 0.352 7 = 241133760/681080400 = 0.354 The denominator is (2*n)!/2^n. The numerator is the tricky part. I calculated these via a program that generates all the combinations and also counts those that are valid. It *looks* like the sequence is converging, but you can't tell from inspection. I imagine if you were to draw out all the decision trees for each number of pairs you might be able to see the pattern. I wonder if it could be defined recursively?
Starting with the two pairs: There are 4!/(2!*2!) = 6 distinct arrangements of the four crayons. There are two ways that the first pair can be the same (the last pair will also be the same in exactly these cases). There are two ways that the middle pair can be the same. Thus, there are exactly 6-2-2 = 2 ways that no adjacent pair will be the same, and the probability is 1/3. (ABAB and BABA) Three pairs: There are 6!/(2!*2!*2!) = 90 distinct arrangements of the six crayons. How many of them have adjacent like pairs? There are 3 ways to choose a like pair for the first two crayons, and then 6 ways to arrange the remaining crayons, for 18 arrangements. There are 3 ways to choose a like pair for the 2nd and 3rd crayons, and then 6 ways to arrange the other 4, and none of these are already counted because the first couldn't also be the same as these two, for another 18. When the middle two are the same (3 choices for color), the case where the first two are alike has already been counted, so only count the 2!*2! = 4 arrangements of the other two where the first two are different, for 12 more. When the 4th and 5th crayons are the same (3 choices for color), but no earlier pairs are the same, there must be a like pair among the first three, and if it is non-adjacent it must be 1st and 3rd. So there are two ways to arrange the others, giving 6 more cases. When the last two are the same, but no adjacent pairs before them are the same, the first four crayons form the same puzzle as above, where there are two ways of arranging them, times 3 color choices, for 6 more cases. So in all there are 90 - 18 - 18 - 12 - 6 - 6 = 30 ways to arrange the crayons, and the probability is again 1/3. Four pairs: There are 8!/(2!*2!*2!*2!) = 2520 distinct ways to arrange 8 crayons. When the first two are the same, there are (as in all these cases) four choices for the like color, and there are 90 ways to arrange the remaining crayons. When the 2nd & 3rd are the same, there are 90 ways to arrange the remaining crayons, none of which have been counted yet. When the 3rd & 4th are the same, there are 90 ways to arrange the remaining crayons, but 18 of these (from above) have the first two alike, so there are 72 new ways. When the middle two are the same, there are 90 ways to arrange the remaining crayons, but from above, 36 of them have the first two or the 2nd & 3rd alike, so there are 54 new ways. When the 5th & 6th are the same, there are 90-48 = 42 ways to arrange the others which are not already counted. 6th & 7th alike, 90 - 54 = 36 new ways. last two alike, 30 new ways. In all, there are 2520 - 4*(90 + 90 + 72 + 54 + 42 + 36 + 30) = 864 ways to arrange the crayons with no adjacent pairs alike, for a probability of 12/35.