1
$\begingroup$

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:

AAB,ABA,BAA,BBA,BAB,ABB,

AAC,ACA,CAA,CCA,CAC,ACC,

BBC,BCB,CBB,CCB,CBC,BCC

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.

$\endgroup$

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
1
$\begingroup$

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}\}$.

$\endgroup$
2
$\begingroup$

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$$

$\endgroup$

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