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 ?

-
I would say the answer is 19, as you've left out the empty set. – Gerry Myerson May 13 '12 at 12:24
Thanks for the point, I forgot to say non-empty subset. – fede May 13 '12 at 12:29

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.

-
Thanks for the help Dennis. I found this form as well, but I wanted something simpler for the sake of description in my dissertation. Could it exist another formula for counting how many time a prefix (i.e. the permutation of a subset of N, e.g. ab) is shared by some other permutations of N? – fede May 13 '12 at 13:02
Any hope of relating this to some well-known combinatorial objects, maybe Stirling numbers? – Gerry Myerson May 13 '12 at 13:10

I calculated the following table of values with GAP:

$$\tiny \begin{array}{r|rrrrrr} & n=1 & 2 & 3 & 4 & 5 & 6 \\ \hline k=1 & 1 & 4 & 15 & 64 & 325 & 1956 \\ 2 & 2 & 18 & 270 & 7364 & 326010 & 21295782 \\ 3 & 3 & 68 & 5247 & 1107696 & 492911195 & 396643610628 \\ 4 & 4 & 250 & 110250 & 191448940 & 904434761800 & 9459612561834054 \\ 5 & 5 & 922 & 2435199 & 35899051100 & 1856296498826905 & 260080189398141873510 \\ 6 & 6 & 3430 & 55621566 & 7101534312684 & 4098746255797339510 & 7843008902239185171370146 \\ 7 & 7 & 12868 & 1301226495 & 1458965717496880 & 9527671240728144876535 & 252375551579644513763596356612 \\ 8 & 8 & 48618 & 30992872482 & 308290573348183628 & 23008745547185924987336820 & 8521137082687484698075500756496758 \\ 9 & 9 & 184754 & 748574130015 & 66577182435768923244 & 57224682697609859297931802325 & 298568465318687485121812233253672384734 \\ 10 & 10 & 705430 & 18283414868862 & 14629025943480502591444 & 145692364455943850433130828021810 & 10773961436670577098657278942204092992628650 \\ \end{array}$$

Some of these numbers don't appear in Sloane's OEIS (or even Google [yet]), and many of those that appear belong to sequences without references (such as A144660 or A144661). So it's unlikely there's a known formula, but we might be able to tackle some simple cases.

• When $n=2$ the number is $\binom{2k+2}{k+1}-2$, which is a special case of Dennis Gulko's answer, simplified using the binomial identity $$\sum_{s=0}^k \sum_{t=0}^k \binom{s+t}{s} = \binom{2k+2}{k+1}-1$$ (see Sloane's A030662).

• Sloane's A003011 gives formulae for the $k=2$ case, e.g. a recurrence relation.

-