Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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