Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
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
add comment

2 Answers 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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.