# Discrete Math distinct words. "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?"

kadejoset 2022-07-18 Answered
Discrete Math distinct words
"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?"
You can still ask an expert for help

## Want to know more about Discrete math?

Expert Community at Your Service

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Available 24/7
• Math expert for every subject
• Pay only if we can solve it

## Answers (2)

Jeroronryca
Answered 2022-07-19 Author has 13 answers
Step 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.
Step 2
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).
Step 2
In the same way you found the total number of words originally, there are:
$\frac{\left(n+m+r-2\right)!}{n!m!\left(r-2\right)!}$
ways of completing the word, having put a CC somewhere. So your answer should be:
$\frac{\left(n+m+r\right)!}{n!m!r!}-\frac{\left(n+m+r-1\right)!}{n!m!\left(r-2\right)!}$
(providing $r\ge 2$).
###### Not exactly what you’re looking for?
Joanna Mueller
Answered 2022-07-20 Author has 5 answers
Step 1
There are $\left(\genfrac{}{}{0}{}{m+n}{m}\right)$ 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.
Step 2
We can choose r of these gaps in $\left(\genfrac{}{}{0}{}{m+n+1}{r}\right)$ ways. The number of words is therefore
$\left(\genfrac{}{}{0}{}{m+n}{m}\right)\left(\genfrac{}{}{0}{}{m+n+1}{r}\right).$
(By convention, $\left(\genfrac{}{}{0}{}{a}{b}\right)=0$
###### Not exactly what you’re looking for?

Expert Community at Your Service

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Available 24/7
• Math expert for every subject
• Pay only if we can solve it