3
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – alex.jordan Feb 29 '12 at 1:56
  • $\begingroup$ Would there be no concise closed-form solution even if the multiset is given? $\endgroup$ – Neo Feb 29 '12 at 1:58
  • $\begingroup$ 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. $\endgroup$ – alex.jordan Feb 29 '12 at 2:07
0
$\begingroup$

Lets say $S$ is the multiset and $m_k$ is the multiplicity of the element $k$ of the multiset $$ S=(m_1,m_2,...,m_n) $$ and we want all the unique permutations of length $l$ of the multiset. For the formula we have to find all the combinations $C=(x_1,x_2,...,x_n)$ where $0 \leq x_k \leq m_k$ such that $$ \sum_{k=1}^n x_k=l $$

What we need is actually the productory of the factorials of the elements of that combination: $$ P(C)=\prod_{k=1}^n x_k! $$ Now lets say that the number of combinations is J, so to answer your question the number of permutation is $$ \sum_{j=1}^J \frac{l!}{P(Cj)} $$ Lets try this formula with this example: the multiset is $S=(3,2,1)$ and $l=4$. All the combinations are $$ C=((1,2,1),(2,1,1),(2,2,0),(3,0,1),(3,1,0)) $$ so the number of permutation is $$ \frac{4!}{1!2!1!}+\frac{4!}{2!1!1!}+\frac{4!}{2!2!0!}+\frac{4!}{3!0!1!}+\frac{4!}{3!1!0!}=\frac{24}{2}+\frac{24}{2}+\frac{24}{4}+\frac{24}{6}+\frac{24}{6}=38 $$ I'm going to explain the formula using again my example. We want a permutation of length $l$ so it's like having 4 slots to fill up with what we have. In this case we have our multiset $S=(3,2,1)$. We start with the first element $m_1=3$. How many of $m_1$ we can use, remembering that we have $l$ free slots and that after $m_1$ we have $m_2+m_3=3$ to use? The answer is $$ MAX(0,l-m_2-m_3) \leq x_1 \leq MIN(l,m_1) $$ We can't use less or more or we won't reach $l$ at the end, so $x_1=(1,2,3)$. Lets start with $x_1=1$. What is the number of combination with $4$ free slots and $1$ to use? This is the binomial coefficient $$ \binom{l}{x_1}=\binom{4}{1} $$ What I'm going to do is to repeat what I did until I completely fill all the slots. Now we have $l-x_1=3$ free slots and $m_2$ to use. Of $m_2$ I can use no less than $MAX(0,l-x_1-m_3)$ and no more than $MIN(l-x_1,m_2)$, so $x_2=(2)$ as it's the only choice. What is the number of combination with 3 free slots and 2 to use? Like before, it's $$ \binom{l-x_1}{x_2}=\binom{3}{2} $$ Combined with $x_1=1$ it becomes $$ \binom{l}{x_1}\binom{l-x_1}{x_2}=\binom{4}{1}\binom{3}{2} $$ Now we have $l-x_1-x_2=1$ free slots and $m_3$ to use. One slot can be filled in one way only, so $x_3=1$ and the combinations are $$ \binom{l-x_1-x_2}{x_3}=\binom{1}{1} $$ Combined with $x_1=1$ and $x_2=2$ it becomes $$ \binom{l}{x_1}\binom{l-x_1}{x_2}\binom{l-x_1-x_2}{x_3}=\binom{4}{1}\binom{3}{2}\binom{1}{1} $$ We can clearly see a pattern here so we can try to get a nicer formula from that $$ \binom{l}{x_1}\binom{l-x_1}{x_2}\binom{l-x_1-x_2}{x_3}=\frac{l!}{x_1!(l-x_1)!}\frac{(l-x_1)!}{x_2!(l-x_1-x_2)!}\frac{(l-x_1-x_2)!}{x_3!(l-x_1-x_2-x_3)!} $$ We can simplify that and get $$ \frac{l!}{x_1!x_2!x_3!(l-x_1-x_2-x_3)!} $$ Since we know that $x_1+x_2+x_3=l$ we can simplify again and get $$ \frac{l!}{x_1!x_2!x_3!(l-x_1-x_2-x_3)!}=\frac{l!}{x_1!x_2!x_3!0!}=\frac{l!}{x_1!x_2!x_3!} $$ $$ \frac{l!}{x_1!x_2!x_3!}=\frac{4!}{1!2!1!} $$ Now lets get back where we were. Since we filled up all the slot we have to go back and since $x_1=(1)$ and $x_2=(2)$ we have to get back to $x_1=(1,2,3)$ and pick the second, so $x_1=2$. With $x_1=2$ follows up that $x_2=(1,2)$. Since there are more than 1 way to choose $x_2$, we can write it this way $$ \binom{4}{2}(\binom{2}{1}+\binom{2}{2}) $$ If we continue with $x_2=1$ we get $x_3=1$, and if we continue with $x_2=2$ we get $x_3=0$ and get $$ \binom{4}{2}(\binom{2}{1}\binom{1}{1}+\binom{2}{2}\binom{0}{0})=\binom{4}{2}\binom{2}{1}\binom{1}{1}+\binom{4}{2}\binom{2}{2}\binom{0}{0}=\frac{4!}{2!1!1!}+\frac{4!}{2!2!0!} $$ Lets get back the last time to $x_1$ and pick up the last, so $x_1=3$. With $x_1=3$ it follow that $x_2=(0,1)$, so $$ \binom{4}{3}(\binom{1}{0}+\binom{1}{1}) $$ If we continue with $x_2=0$ we get $x_3=1$, and if we continue with $x_2=1$ we get $x_3=0$ and get $$ \binom{4}{3}(\binom{1}{0}\binom{1}{1}+\binom{1}{1}\binom{0}{0})=\binom{4}{3}\binom{1}{0}\binom{1}{1}+\binom{4}{3}\binom{1}{1}\binom{0}{0}=\frac{4!}{3!0!1!}+\frac{4!}{3!1!0!} $$ If we sum up all the results we get the same formula as before.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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