Take the 2-minute tour ×

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?



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?

share|improve this question
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

1 Answer 1

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

share|improve this answer

Your Answer


