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?


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?

  • $\begingroup$ 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/… $\endgroup$ Aug 31 '10 at 3:11
  • $\begingroup$ @Tsuyoshi Ito: Sure, edited. $\endgroup$
    – 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!}$$


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.