Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am asked the following:

Let m, n, and r be non-negative integers.

How many distinct "words" are there consisting of m occurrences of the letter A, n occurrences of the letter B, r occurrences of the letter C, such that no subword of the form CC appears, and no other letters are used?

I have tried various methods but none of which I can get to just account for the total amount of double c's without overlapping.

I came up with this: $$ \frac{(n+m+r-2)!}{n!m!(r-2)!} - (n+m+r)$$ which works in some cases however the more c's there are the more overlapping occurs and the more inaccurate the answer becomes.

At somepoint $ \frac{(n+m+r)!}{n!m!(r-2)!} = f(n,m,r)$ when r is certain size or larger r would saturate

Can anyone provide me with a hint on how I should proceed?

share|improve this question
    
There seem to be some factorials missing (at least one). –  Lord_Farin Oct 19 '12 at 15:46
add comment

2 Answers

up vote 3 down vote accepted

There are $\dbinom{m+n}{m}$ ways to make a word with $m$ A's and $n$ B's.

For each of these ways, there are $m+n+1$ "gaps" (including the end gaps), into which to place the C's. We need to choose $r$ of these gaps. This can be done in $\dbinom{m+n+1}{r}$ ways.

share|improve this answer
add comment

Think of the $r$ C’s as ‘barriers’ breaking up the string of $m+n$ A’s and B’s into $r+1$ blocks: a block before the first C, $r-1$ blocks between C’s, and a block after the last C. The first and last blocks may be empty; the other $r-1$ may not, since you have to keep adjacent C’s apart.

Let $x_0,x_1,\dots,x_r$ be the numbers of A’s and B’s in the $r+1$ blocks, reading from left to right; we require that $x_0+x_1+\ldots+x_r=m+n$, that $x_0,x_r\ge 0$, and that $x_1,\dots,x_{r-1}\ge 1$, and of course all of the $x_k$ must be integers. If we let $y_0=x_0$, $y_r=x_r$, and $y_k=x_k-1$ for $k=1,\dots,r-1$, we’re looking for solutions to $y_0+y_1+\ldots+y_r=m+n-(r-1)$ in non-negative integers. Counting those solutions is a standard problem; if you’ve not seen it before, you might want to read this article. That will give you the number of ways of arranging $m+n$ letters amongst the $r$ C’s in such a way that no two C’s are adjacent.

Then there are $\binom{m+n}m$ ways to decide which of the $m+n$ positions for A’s and B’s will contain A’s, so the final count will be ... ?

Added: This approach starts with the C’s and inserts the other letters to break up adjacent C’s. Alternatively, you can turn the problem around and think of inserting C’s into a string of A’s and B’s; this is André Nicolas’s solution, which is a bit shorter.

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.