# linear ordering of color balls

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?

-
Should be tagged co.combinatorics instead of pr.probability? –  Emil Nov 6 '10 at 12:27

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

-

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

-