# Computing Permutations with Partial Duplicates

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$.

-
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

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$.

-

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

-
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

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.

-