1
$\begingroup$

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!

  • 0
    the latter one.2012-04-24

1 Answers 1

2

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.