# Permutations with identical objects

Note: I tried asking this on math.stackexchange (here), but didn't really receive an answer - so I figured this might be the right place.

How can I find the number of k-permutations of n objects, where there are x types of objects, and r1, r2, r3 ... rx give the number of each type of object?

Example:

I have 20 letters from the alphabet. There are some duplicates - 4 of them are a, 5 of them are b, 8 of them are c, and 3 are d. How many unique 15-letter permutations can I make?

In the example:

n = 20
k = 15
x = 4
r1 = 4, r2 = 5, r3 = 8, r4 = 3

Furthermore, if there isn't a straightforward solution: how efficiently can this problem be solved?

-
Next time you re-ask a question, please include the URL of the question on the other site so that people do not have to search around. math.stackexchange.com/questions/2372/… –  Tsuyoshi Ito Aug 31 '10 at 3:11
@Tsuyoshi Ito: Sure, edited. –  Cam Aug 31 '10 at 3:18

Here's a sketch of an idea. Consider first the problem of computing the number of permutations of $k$ elements given the number of elements $n_i$ in each class. This is easy: it works out to $$\frac{k!}{\Pi_i n_i !}$$ because in any fixed string, you can permute the elements in a class without changing the string.
Now consider the problem of writing down the different partitions of $k$ into the sum of $x$ labelled numbers. Merely finding the sum itself can be done by determining the coefficient of $y^k$ in the polynomial $$\Pi_i \frac{y^{r_i+1}-1}{y-1}$$
But this is not enough, since you need to weight each such partition by a different number. However, we know that the contribution of $y^i$ must be $1/i!$, so the overall number we are looking for is $k!$ times the coefficient of $y^k$ in the polynomial $$\Pi_i \sum_{j=0}^{r_i} \frac{y^j}{j!}$$