To me it seems like counting multiset permutations is the same as counting subsets with dependent events. For example, to count all the permutations of the word MISSISSIPPI, we simply count all the permutations and divide out all the redundancies: $\frac {11!}{(4! \cdot 4! \cdot 2!)}$. We can also do this: ${11 \choose 4} \cdot {7\choose 4} \cdot {3\choose 2}$. Is there such a relation between counting combinations with independent events(for example, special cases of Vandermonde's Identity) and some other list counting problems? The reason I ask this is because it's much more natural for me to count lists rather than subsets.

Also, suppose we are choosing $3$ flavors of ice-cream out of $5$ different ones. If we are only allowed to choose one of each kind, then the problem is about counting subsets. If we can choose $2$ or $3$ scoops of the same flavor, we are dealing with multiset counting problem. If this is correct, how come in the problem about the word MISSISSIPPI, we can choose $4$ identical letters out of $11$ letters and the problem still has nothing to do with counting multiset combinations?

  • $\begingroup$ The permutations of the letters of the word MISSISSIPPI is a permutation of a multiset. The problem involving the selection of three scoops of ice cream selected from five flavors in which flavors may be repeated is a combination with repetition. The number of solutions is the number of solutions of the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 3$ in the nonnegative integers, which is the number of ways of inserting four addition signs in a row of three ones, that is, $\binom{3 + 4}{4} = \binom{7}{4}$. $\endgroup$ – N. F. Taussig Jun 20 '15 at 10:09

Your Answer

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

Browse other questions tagged or ask your own question.