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