0
$\begingroup$

This question has been asked here: find the number of rearrangements of 11223344 that contain no two consecutive equal digits

My question is slightly different. In the linked thread they use multinomial coefficients, I am trying to do the same thing using the binomials.

Suppose we have eight boxes labeled $A$ through $H.$ Also assume we have eight balls labeled $1, 1, 2, 2, 3, 3, 4, 4.$

There are seven ways to place two balls labeled $1, 1$ into the adjacent boxes. These possibilities are $AB, BC, CD, DE, EF, FG, GH.$ For each of these possibilities there are $\binom62\binom42$ ways to place the rest of the balls. We must repeat this process for the pairs $2, 2; 3, 3; 4, 4$. In total there are $7 \cdot \binom62\binom42 \cdot 4$ ways to count $\sum_{i = 1}^4|S_i|$ where $S_i$ is a set of words where integers $ii$ are consequtive.

Now suppose we want to place the pairs $1, 1$ and $2, 2$ into the seven adjacent box pairs. My first guess was to choose a box pair from those listed above. There are seven possibilities. Then choose another box pair from the remaining six. Altogether there are $7 \cdot 6 \cdot \binom42 \cdot 6$ ways. But this is wrong. The correct answer is $6 \cdot 5 \cdot \binom42 \cdot 6.$ Looks like we are choosing the first box pair out of six possible pairs, not seven. Why is that? One problem seems to be that if we choose the boxes $CD,$ then we can't choose $BC$ and $DE$ leaving only four possible pairs whereas if we choose $AB$, we have five possible pairs left. This probably complicates things. Can someone, please, explain how to think correctly to obtain $6 \cdot 5 \cdot \binom42 \cdot 6$ rather than $7 \cdot 6 \cdot \binom42 \cdot 6.$

$\endgroup$
  • $\begingroup$ There may well be other approaches to solving the same problem (asked here and in the earlier Question), but you seem to be asking "what is wrong with my approach?". You seem to realize that you are getting an overcount in your approach, but have not winnowed out which counts are "extras". Generally one can get a clearer understanding by working out the details for themselves in such cases. $\endgroup$ – hardmath May 30 '17 at 20:48
2
$\begingroup$

The number of ways to place the $2$'s depends upon where you placed the $1$'s. If the $1$'s are placed in A and B or G and H, then there are 5 ways to place the $2$'s. For every other combination there are only $4$ ways to place the $2$'s so they are next to each other.

Then after you have placed the $1$'s and $2$'s, there are ${4}\choose{2}$ $=6$ ways to arrange the $3$'s and $4$'s. So the number of ways are $(2\cdot 5 + 5\cdot4)\cdot 6 = 180$

$\endgroup$

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.