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.

How can I find the number of $k$-permutations of $n$ objects, where there are $x$ types of objects, and $r_1, r_2, r_3, \cdots , r_x$ give the number of each type of object?

Example:

I have 20 letters from the alphabet. There are some duplicates - 4 of them are a, 5 of them are b, 8 of them are c, and 3 are d. How many unique 15-letter permutations can I make?

In the example:

$n = 20$

$k = 15$

$x = 4$

$r_1 = 4 \quad r_2 = 5 \quad r_3 = 8 \quad r_4 = 3$

Some background...

I was originally going to solve this problem in order to solve a simpler problem, but I managed to find a simpler solution to that problem instead. Now I'm still looking for the solution to this more general problem out of interest.


Edit:

I've done some more work on this problem but haven't really come up with anything useful. Intuition tells me that as Douglas suggests below there will probably not be an easy solution. However, I haven't been able to prove that for sure - does anyone else have any ideas?

Edit:

I've now re-asked this question (here) on MO.

share|improve this question
1  
possible duplicate of Permutations with duplicates –  Grigory M Aug 13 '10 at 17:09
    
@Grigory: I read that question and had already reached a similar conclusion myself (brute-force is a possible solution). I'm looking for a more elegant solution if one exists. –  Cam Aug 13 '10 at 17:12
2  
@Grigory: Nobody provided a general solution for that problem (or even says the word multinomial). Cam here asks for one. I think it makes more sense to answer this question, then say that question is a duplicate of this. –  Larry Wang Aug 13 '10 at 17:13
    
@Kaestur You're right, sorry –  Grigory M Aug 13 '10 at 17:51
    
It seems I haven't yet received a definitive answer - should I try MO? Or are there perhaps some other resources I should look into (books you guys know of, etc)? –  Cam Aug 24 '10 at 1:15

2 Answers 2

up vote 3 down vote accepted

There's probably not going to be an easy way to do this... Consider two different examples of 15-letter "permutations". Then the number of permutations with that multiset of digits depends on the proportions of the chosen digits.

If you really want to do this, you can sum $k!/(s(1)! s(2)! \cdots s(x)!)$ (called the mulitnomial coefficient) over all partitions of $s(1)+s(2)+ \cdots +s(x)=k$ [in this partition s(i) is allowed to be zero and order is important] such that $s(i) \leq r(i)$ for all i. The part s(i) says you have s(i) copies of the i-th letter. The number of permutations with s(i) i-th letters is given as above, by the Orbit Stabiliser Theorem.

Although, this is only one step better than the caveman's counting formula: sum_P 1 where P is the set of permutations you want to count. I.e. just count them one-by-one.

EDIT: While I'm making a few touch-ups, here's GAP code that implements the above formula.

NrPermIdent:=function(k,T)
  local PSet,x;
  x:=Size(T);
  PSet:=Filtered(OrderedPartitions(k+x,x)-1,p->ForAll([1..x],i->p[i]<=T[i]));
  return Sum(PSet,p->Factorial(k)/Product(p,i->Factorial(i)));
end;;

where T is a list of bounds and k is the number of terms in the partition.

For example:

gap> NrPermIdent(15,[4,5,8,3]);
187957770

As another indication that finding a simple formula for these numbers is not going to be easy, observe that NrPermIdent(n,[n,k]) is equal to $\sum_{0 \leq i \leq k} {n \choose k}$ (which is considered a difficult sum to find -- see: http://mathoverflow.net/questions/17202/). I remember reading somewhere (most likely in A=B) that you can prove there is no "closed-form" solution for this.

share|improve this answer

There are 20!/4!5!8!3! arrangements of the 20 alphabets. Consider the action of $S_5$ on the arrangements by permuting the last 5 digits. You want to compute the number of orbits. You can then try to do it by Burnside's formula. It is not difficult to do it at least for this case, since if a permutation of $S_5$ fixes an arrangement, it means that each cycle of the permutation corresponds to a color.

For the general case, I suspect that Polya's enumeration theorem can do it, though I'm not certain.

share|improve this answer
    
This seems to be a just a change of variables: you can instead sum over t(1)+t(2)+...+t(x)=n-k where t(i)=r(i)-s(i). [in this partition t(i) is allowed to be zero] Actually, as it stands, it's even more complicated than that, since you're summing over partitions of {16..20} corresponding to the cycles of permutations, then assigning letters a..d to the parts in such a way as to not create too many copies of a single letter. –  Douglas S. Stones Aug 31 '10 at 5:49

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.