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.

What is the number of permutations of subsets of the multiset $S$ with cardinality $n$? A sample problem would be, say, to find the number of ways can you make "words" with three of the letters in the set $[G,R,E,E,N]$.

I've looked everywhere and found two identical posts by the same person (here and here), but no formula was posted. Such formula exists for sets with distinct elements, $P(n,r)$ or $nPr$. The number of permutations of a multiset also exists as the multinomial coefficient. But there seems to be no way to compute the number of permutations of subsets of a multiset given the cardinality other than going case by case and using logic. I've heard that generating functions can be used to solve such problems (as was written in Maple's help files) but I'm looking for a general solution using combinatorics, although a generating functions solution would be cool too (I have yet to learn generating functions).

I played around with this last week and found a formula when the multiset only contains one element that is duplicated. Let's suppose the number of duplicates is $E$, the cardinality of the multiset $S$ is $n$, and that the cardinality of the subsets desired is $P$. Then, the number of permutations is $$\sum_{k=0}^{E}\binom{P}{k}P(n-E,P-k)$$ This formula only works when $n\geq E+P$ and even then it might not work, and I didn't know how to proceed from here. One person at MO suggested to sum multinomial coefficients but I don't understand the reasoning behind that. If anyone would like to help it'd be greatly appreciated.

(This was reposted from MO here)

share|improve this question
    
Knowing the cardinality $n$ would not be enough. Surely the answer also depends on the multiplicities of the letters involved, which will make it impossible to have a concise closed-form answer to this question. There might be ways to answer this as a sum. –  alex.jordan Feb 29 '12 at 1:56
    
Would there be no concise closed-form solution even if the multiset is given? –  Neo Feb 29 '12 at 1:58
    
If the multiset is given then you don't need a formula. You just need the number that describes all the permutations for that particular multiset. Computing that number would likely involve a sum that makes use of the various multiplicities. –  alex.jordan Feb 29 '12 at 2:07
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.