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

I am looking for a way to compute the number of $K$ permutations of a multiset with $N*D$ elements where each group has exactly $D$ equal elements (and typically $D < N$ ).

I've got an application that actually generates these unique permutations and works on them, but I'd like to understand how I can compute the number of sets I'll have across various inputs without computing the entire result.

Example (in R):

N <- 19
K <- 4
# Implied D = 3 by just duplicating it in-place three times.

a <- append(1:N, append(1:N, 1:N))
b <- unique(gtools::permutations(length(a), K, a, set=FALSE))

nrow(b) in this case will be 130,302.

This is slow and inelegant. Can someone help me do this with actual math?

Expanding a bit

If N is 9 and D is 3, my input might look like this:

1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9

A standard permutation would look like this:

1    1    1    2
1    1    1    2
1    1    1    2
1    1    1    3
1    1    1    3
1    1    1    3

But at this point, I want to treat the things that look the same as the same, so I deduplicate to get the following:

1    1    1    2
1    1    1    3
1    1    1    4
1    1    1    5
1    1    1    6
1    1    1    7

The first (full permutation) provides 421,200 rows: $(9*3)! \over (9 * 3 - 4)!$

My final, deduplicated answer is 6,552 rows. I'd like to know how I can get that without generating them all.

New Discovery

For my initial case where $D = K - 1$, I get the correct answer with $N^K - N$.

share|improve this question
    
what's a "unique set of k "? could you make an example? –  Pietro Majer Sep 14 '11 at 21:18
    
does this help? –  dustin Sep 14 '11 at 21:31
    
It looks like you want to count ordered $k$-tuples from a set of size $n$ with at most $d$ repetitions of each element. –  Douglas Zare Sep 15 '11 at 0:30
    
The ordering part doesn't matter much to me (depending on what you meant by it). I want AAAB and ZZZY and every permutation between except where that permutation is identical to another. –  dustin Sep 15 '11 at 3:49
    
Do you want AAAB to be different from AABA or not? –  Douglas Zare Sep 15 '11 at 4:22
show 1 more comment

3 Answers 3

You could try to use exponential generating functions.

For each of the N letters you could use the exponential generating function

$$ \sum_{i=0}^D \frac{x^i}{i!} $$

Cause each letter can be used at most D times this is the same for each letter.

Then for using all different letters the egf's have to be multipled (you have N different letters so N times):

$$ \left(\sum_{i=0}^D \frac{x^i}{i!}\right)^N $$

Then you are looking for the amount of different words of length K which is if you expand the expression above (which is possible if you put into it values for $D, N$. Then the coefficient of $x^K$ multiplied by $k!$ is your solution.

What I wasn't able to do right now is trying to expand the generating function into a series without using concrete values for $D$ and $N$.

share|improve this answer
add comment

I'm thinking the result should be:
n ^ k for d >= k
n ^ k - n ^ (k - d) for d < k

share|improve this answer
    
It's not deduplicated in the sense that the same item doesn't show up, but that the same sequence doesn't show up in the result. i.e. AAAB, AAAC, but not another AAAB where the As were rearranged. –  dustin Sep 14 '11 at 23:10
    
I don't know why I was making this far too hard. D will not matter, because no matter what it is, it will get deduplicated. Since what you're doing is (n*d)Pk with deduplication, your result is just n^k. –  nullghost Sep 15 '11 at 0:00
    
Okay, I missed the bit where you can only choose a number a maximum of D times. If D is greater than or equal to K, number of rows = N^K If D is less than K, number of rows should = N^K - N^(K-D) Test that for me, see if the results make sense. –  nullghost Sep 15 '11 at 0:08
    
That's off in just a couple of cases: pastebin.com/LUd8BMSR –  dustin Sep 15 '11 at 1:03
add comment

The number of $K$-permutations of the numtiset $\{ 1^D, 2^D, \ldots, N^D \}$ is $$\sum_{j_1+j+2+\dots+j_N=K\atop 0 \leq j_i \leq D} \binom{K}{j_1,j_2,\dots,j_N}.$$ (summands here are multinomial coefficients)

Alternatively, denoting by $m_i$ the number of $j$'s equal $i$, we get a formula as the sum over restricted partitions: $$\sum_{0m_0+1m_1 + \dots + Dm_D = K\atop m_0 + m_1 + \dots + m_D = N,\quad m_i\geq 0} \binom{N}{m_0,\dots,m_D} \frac{K!}{1!^{m_1} 2!^{m_2} \cdots D!^{m_D}}$$

For the example with $N=9$, $D=3$, $K=4$, the latter formula consists of four summands and gives: $$\binom{9}{5,4} \frac{4!}{1!^4} + \binom{9}{6,2,1}\frac{4!}{1!^2 2!^1} + \binom{9}{7,1,1}\frac{4!}{1!^1 3!^1} + \binom{9}{7,2}\frac{4!}{2!^2}$$ $$ = 3024 + 3024 + 288 + 216 = 6552$$ as expected.

share|improve this answer
add comment

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.