Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
Should be tagged co.combinatorics instead of pr.probability? –  Emil Nov 6 '10 at 12:27
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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