# Permutation without a subword repeat

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?

-
There seem to be some factorials missing (at least one). – Lord_Farin Oct 19 '12 at 15:46

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.

-

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.

-