I've got a problem where I have N
items with up to D
duplicates for each item. I want to know how many unique sets of K
of the input items I will have given my inputs.
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.