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.

Given an alphabet $A$ of length $m$ ($A = \{a_1, a_2, a_3, \dots, a_m\}$), what is the quantity of words with the length $n$ when $a_1$ and $a_2$ and $a_3$ have to be contained in the word at least $k$ times.

I'm freshening up on combinatorics and found this problem, what would be the "master" formula for those "at least $k$ times" problems?

Thank you!

share|improve this question
1  
Hi! Let $n_{a_i}$ be the number of times $a_i$ appears in the word. Are you asking for $$n_{a_1}, n_{a_2}, n_{a_3} \geqslant k$$or $$n_{a_1} + n_{a_2} + n_{a_3} \geqslant k$$? –  uncookedfalcon Apr 24 '12 at 10:53
    
the latter one. –  Dänu Apr 24 '12 at 20:22

1 Answer 1

up vote 2 down vote accepted

Suppose that $a_1,a_2$, and $a_3$ had altogether to be contained in the word exactly $r$ times. Then there would be $\binom{n}r$ ways to choose the $r$ positions for the letters $a_1,a_2$, and $a_3$, $3^r$ ways to fill the $r$ positions with these three letters, and $(m-3)^{n-r}$ ways to fill the remaining $n-r$ positions with the remaining $m-3$ letters, for a total of $$\binom{n}r3^r(m-3)^{n-r}$$ words. We want to allow $r$ to assume any value from $k$ through $n$, so the total number of words is actually $$\sum_{r=k}^n\binom{n}r3^r(m-3)^{n-r}\;,$$ which is part of the binomial expansion of $m^n$ when $m$ is written as $3+(m-3)$. Equivalently, it’s $$m^n-\sum_{r=0}^{k-1}\binom{n}r3^r(m-3)^{n-r}\;,$$ which is more convenient when $k$ is small compared with $n$.

I don’t see a nice closed form, unfortunately.

share|improve this answer
    
Thank you for this very nice answer, thank you! –  Dänu May 5 '12 at 16:28

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.