What is the number of permutations of subsets of the multiset $S$ with cardinality $n$? A sample problem would be to find the number of ways you can construct "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 on MSE and on MO, but no formula was posted. Such formula exists for sets with distinct elements, $P(n,r)$. 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. Suresh Venkat suggested to sum multinomial coefficients, but I don't understand his reasoning.
I originally posted this on MathOverflow, now deleted.