5 fixed for always getting the right answer

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

4 updated with better description from someone who knows math better than I

I've got a problem where

I have N items with up to D duplicates am looking for each item. I want a way to know how many unique sets compute the number of K$K$ permutations of the input items I will have given my inputsa 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. 
 
 
 
3 expanded a bit

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.

2 minor bug in the R code
1