2
$\begingroup$

Suppose that $n+m$ balls of which $n$ are red and $m$ are blue, are arranged in a linear order, we know there are $(n+m)!$ possible orderings. If all red balls are alike and all blue ball are alike, we know there are $\frac{(n+m)!}{n!m!}$ possible orderings.

For example, 2 red and 3 blue balls:

R1 R2 B1 B2 B3

R2 R1 B2 B3 B1

The above two orderings are equivalent and can be denoted as:

R R B B B

Now here is the problem: what if we further concentrate on the color, and record consecutive balls of the same color with the just ONE color code?

For example the color code for the afore-mentioned example would be:

R B

How many possible color code orderings are there?

$\endgroup$
1
  • $\begingroup$ Should be tagged co.combinatorics instead of pr.probability? $\endgroup$
    – Emil
    Nov 6, 2010 at 12:27

2 Answers 2

1
$\begingroup$

Such a color-code ordering starts with either R or B and continues with strictly alternating R and B. The string can be of any length up to the smaller of $n$ or $m$, meaning it can be twice that smaller value, but that can be followed by one more character if there are enough of the other color. Moreover, every such string is a color-code ordering for some linear ordering of balls. There are a couple of special cases, namely that if either $n$ or $m$ is zero then there is exactly one color-code ordering and there aren't any if both are zero. Also, if neither is zero, we must have at least one instance of each letter.

So:

If $n = m = 0$, the answer is 0.

If exactly one of $n$ and $m$ is zero, the answer is 1.

If $n = m > 0$, the answer is $4n - 2$.

Otherwise, let $p$ be the minimum of $n$ and $m$. The answer is $4p-1$.

$\endgroup$
2
$\begingroup$

Without loss of generality, assume $n \leq m$. Such a colour code ordering is just a sequence of alternating $R$ and $B$ letters. There are four types of such sequences, depending which letter they start and end with. Say a sequence is of type $(X,Y)$ if it begins with $X$ and ends with $Y$.

So, there are

  1. $n$ sequences of type $(R,B)$
  2. $n$ sequences of type $(B,R)$
  3. $n-1$ sequences of type $(R,R)$
  4. $n$ sequences of type $(B,B)$ (and only $n-1$ of them if $n=m$).

Thus, the answer is $4n-1$ if $n < m$, and $4n-2$ if $n=m$.

Edit. As Larry Denenberg mentions, in the degenerate case of $n=0$, the answer is always 1 (I count the empty string if $n=m=0$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.