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 ?
Best Answer
Suppose you have $n$ elements with multiplicity $k$ each. Then the total number of the desired permutations will be $$\left(\sum_{0\leq t_1,...,t_n\leq k} \frac{(t_1+...+t_n)!}{t_1!\cdot...\cdot t_n!}\right)-1$$ Not counting the empty set.