How can I calculate the combinations of words having exactly k distinct letters and of length n?

For example, we have a set of letters {A, B, C}, the words of length 3 having exactly 2 letters are:




I tried to solve the problem by first stating at position 1 to k it must fulfill k exact letters, while the remaining can be any character. This results in m * (m - 1) *... (m - k + 1) combinations. The first k positions can actually be any place in the word, so I multiply the previous combinations by nCk. However, this approach is incorrect and the results contain some duplicated entries.


marked as duplicate by ccorn, Namaste, user99914, Parcly Taxel, user061703 Jul 18 '18 at 2:40

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ In your example, there are $\binom{3}{2}$ ways to select two of the three letters, $2^3$ ways to fill each of the three positions with one of the two selected letters and $2$ ways to fill all the positions with the same letter, so there are $\binom{3}{2}(2^3 - 2)$ permissible words. $\endgroup$ – N. F. Taussig Nov 4 '17 at 9:28
  • $\begingroup$ How many letters do we have available? $\endgroup$ – N. F. Taussig Nov 4 '17 at 9:29
  • $\begingroup$ In fact I want a general solution for any m >= k, if my problem involves m letters available. For my practical problem, m < 50. $\endgroup$ – Ho Tsz Yan Nov 4 '17 at 9:34
  • $\begingroup$ @ccorn: As both this Question and the proposed duplicate currently appear in the Close Review Queue, I'd like to point out a subtle difference between them that affects their solutions. This Question asks for exactly $k$ letters to appear, while the other problem doesn't appear to have that requirement (and is correspondingly easier). $\endgroup$ – hardmath Jul 18 '18 at 2:06
  • 1
    $\begingroup$ @hardmath: Both require exactly $k$ distinct letters/symbols (first sentence each). $\endgroup$ – ccorn Jul 19 '18 at 17:47

In the sequel $0\in\mathbb N$.

There are $\binom{n}{k}$ choices for the $k$ distinct letters.

By a fixed choice of letters - let's call them $L_1,\dots,L_k$ - we must find how many sums $l_1+\cdots+l_k=n$ exist where the $l_i$ are positive integers. Here $l_i$ stands for the number of times that letter $L_i$ is used in the word. This can be solved by stars and bars and gives the factor $\binom{n-1}{k-1}$.

Finally by this fixed choice there are $\binom{n}{l_1,\dots,l_k}$ possible arrangements for the letters.

That leads to:$$\binom{n}{k}\binom{n-1}{k-1}\sum_{\langle l_1,\dots,l_k\rangle\in S}\binom{n}{l_1,\dots,l_k}$$where $S=\{\langle x_1,\dots,x_k\rangle\in\mathbb N_+^k\mid x_1+\cdots+x_k=n\}$.

I am not familiar with a closed form for the the summation.

More directly it can be stated that we are dealing with:$$\sum_{\langle l_1,\dots,l_n\rangle\in T}\binom{n}{l_1,\dots,l_n}$$where $T=\{\langle x_1,\dots,x_n\rangle\in\mathbb N^n\mid x_1+\cdots+x_n=n\text{ and exactly }k\text{ of the components are positive}\}$.


If we have $m$ letters available, we can select $k$ of them in $\binom{m}{k}$ ways. If there were no restrictions, we would have $k$ choices for each of the $n$ positions, so there would be $$\binom{m}{k}k^n$$ possible words. From these, we must exclude those in which fewer than $k$ of the letters appear. There are $\binom{k}{j}$ ways to exclude $j$ of the $k$ letters and $(k - j)^n$ ways to form words of length $n$ with the remaining $k - j$ letters. By the Inclusion-Exclusion Principle, the number of words of length $n$ that can be formed with exactly $k$ of the $m$ distinct letters is $$\binom{m}{k}\sum_{j = 0}^{k} (-1)^j\binom{k}{j}(k - j)^n$$


Not the answer you're looking for? Browse other questions tagged or ask your own question.