2
$\begingroup$

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?

2 Answers 2

3

There are $\dbinom{m+n}{m}$ words of length $m+n$ that use $m$ A's and $n$ B's.

Any such word determines $m+n+1$ "gaps" (including the $2$ endgaps) into which we can slip a C.

We can choose $r$ of these gaps in $\dbinom{m+n+1}{r}$ ways. The number of words is therefore $\binom{m+n}{m}\binom{m+n+1}{r}.$ (By convention, $\dbinom{a}{b}=0$ if $a\lt b$.)

  • 0
    Thanks for mentioning the typo. Yes, for this problem there is a pleasant direct count.2012-12-12
1

Not the best possible answer, because it doesn't explain where your solution breaks down, but a different derivation...

Following the same basic principle, you want to know the number of words of the right form that have a CC in them. This has to start somewhere, and there are $n+m+r-1$ places it could start - i.e. the first C in the pair can occur as all but the last letter.

Then you just need to fill up the remaining letters with $n$ As, $m$ Bs and $r-2$ Cs (so we should make some allowances for the cases $r=0$ and $r=1$, when we won't deduct anything at this stage anyway as there are no words with a CC subword).

In the same way you found the total number of words originally, there are:

$\frac{(n+m+r-2)!}{n!m!(r-2)!}$

ways of completing the word, having put a CC somewhere. So your answer should be:

$\frac{(n+m+r)!}{n!m!r!}-\frac{(n+m+r-1)!}{n!m!(r-2)!}$

(providing $r\geq 2$).

  • 0
    This *is* a proof (assuming I didn't mess up somewhere). It's probably a good idea to try some small examples to check that you (or in this case I) didn't make a mistake.2012-12-12