0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – N. Shales Feb 16 '17 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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