# How many n-letter distinct words can be formed using at most m repeated letter?

Using letters $(a,b,c,d,e)$ how many distinct $n$ length words can be formed ? Note that every word can contain same letter $m$ times at most.

For: $n=3, m=2$ $$Answer=5∗5∗5−5=120$$ (all combinations except $aaa,bbb,ccc,ddd,eee$).

## 1 Answer

This is equivalent to asking about the number of partitions of $\{1,\dots,n\}$ to at most $5$ parts (assuming your alphabet is of size $5$), where each size is of size at most $m$. See here:

https://en.wikipedia.org/wiki/Partition_(number_theory)#Partitions_in_a_rectangle_and_Gaussian_binomial_coefficients

• The Gaussian binomial coefficients enumerate integer partitions. I don't see how that helps here because this question is closer to counting set partitions with restricted size. For this we can use egfs $\sum\limits_{k=a}^{b}\frac{x^k}{k!}$. Here $a$ is the minimum number of times a letter is used and $b$ is the maximum. We have an egf for each letter then multiply them and evaluate the coefficient of $\frac{x^n}{n!}$, this is then the count required. – N. Shales Feb 16 '17 at 16:20