## Random Crayons

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

Solutions were received from Dan Dima, Joseph DeVincentis, and Kirk Bresniker.  For 2 and 3 pairs, the probability is exactly 1/3.  For four pairs, the probability increases (slightly) to 12/35.  The following are Kirk's summary of multiple pairs and Joseph's analysis of the first three.

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?
```

From Jospeh DeVincentis:
```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.
```

Mail to Ken