I am asked this:
"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?"
This was my method to solve the problem which was incorrect:
We can find all possible words with length n+m+r where we have n-A's, m-B's, and r-C's : $\frac{(n+m+r)!}{n!m!r!}$
We are asked to find how many distinct words there are such that "no subword of the form CC appears." You can look at this problem in two ways to look at this problem 1. We could use C's and insert letters that would effectively break up adjacent C's 2. We could use a string and A's and B's and try to put C's into the string in order to break up the string. Both views will result in the number of subwords with the form CC.
So we know that we are looking for: $\frac{(n+m+r)!}{n!m!r!}$ −number of words with doubles C′s
So we must now formulate how to find the number of double C forms.
Using the second approach aforementioned we can construct a word with n-A's and m2-B's $n+m\choose m$ ways. In order to appropriately account for overlaps and gaps we can expand on the previous form resulting in : $n+m+1\choose{r}$⇒ $\frac{(n+m+1)!}{((r!((n+m+1)−r)!))}$
This effectively chooses the number of gaps we can insert C into.
So we can calculate the number of words created without the subword CC being repeated by: f(n,m,r)=$\frac{(n+m+r)!}{n!m!r!}$ − $\frac{(n+m+1)!}{((r!((n+m+1)−r)!))}$
So for n=2, m=1, r=2 f(2,1,2)=30 −6⇒24
This was wrong. Can anyone help me with where I went wrong?