permutations of a multiset having symbols with fixed multiplicity

Let $N$ be a multiset of $n$ distinct objects having the same multiplicity $k$. For instance,

$N=\{a,\,a,\,b,\,b\}$

where $n=2$ and $k=2$.

I was looking for the problem of counting the number of all the permutations of all the non-empty subsets of $N$.

For the N in the above example, there are 18 permutations of the subsets of N

$$a,b,\;\; aa,ab,ba,bb,\;\; aab,aba,abb,baa,bab,bba,\;\; aabb,abab,abba,baab,baba,bbaa$$

Till now I've ended up just with an upper bound of that number, by using the following idea. Compute all of the permutations of $N$ of length $nk$ (ignore subsets) with the basic formula $$perm(N;nk)=\frac{(nk)!}{\underbrace{(k!)(k!)...(k!)}_{n \; times}}$$

Then, just take all the $nk$-prefixes of all the objects in $perm(N;nk)$. That gives $$nk\frac{(nk)!}{(k!)^{n}}$$

However since this method counts twice a prefix shared by two $nk$-permutations (e.g. $ab$), I end up with a coarse upper bound. For $N$ in the example, $24$ ($>18$).

I was wondering if I can find a closed formula that computes exactly the desired number ?

8
2022-07-25 20:44:10
Source Share