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!

  • 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$$?2012-04-24
  • 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.