8
$\begingroup$

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 ?

  • 0
    Thanks for the point, I forgot to say non-empty subset.2012-05-13

2 Answers 2

2

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.

  • 0
    Any hope of relating this to some well-known combinatorial objects, maybe Stirling numbers?2012-05-13
2

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.