# Count unique combinations of items from multiple multisets

Sorry for any bad terminology, that's probably why I can't find info on it.
Let's say I have following multisets (all of the same cardinality):

[red, green, green, yellow]
[square, circle, circle, circle]
[small, medium, large, large]


I produce a multiset of combinations, according to those rules:

1. Each combination consists of items from all those multisets
2. From each set, each item is only used once
3. The multisets must be fully exhausted (so the cardinality of result multiset = cardinality of original multisets)

So a result multiset of combinations is something like

[red-circle-medium, green-circle-large, green-square-small, yellow-circle-large]


Given that, how do I count the number of distinct result multisets?

• oh,oops, didn't see you repeated values, was that on purpose? because for example: sets {1,1} and {1} are the same, if you care about how many times the element appears you should use multisets. – Jorge Fernández Hidalgo Nov 21 '13 at 1:28
• Yes, sorry for confusion -- I used the wrong terminology. Updated the question accordingly. – Andrey Shchekin Nov 21 '13 at 2:58
• Before other people attempt to answer, this you need to further clarify with you mean about the repeated items. For example there are three 'circles' in the second set. Should they be considered different eg effectively ['square', 'circle1', 'circle'2', 'circle3'] or are they indistinguishable, in which case the second set should just be ['square', 'circle'] – Martin Roberts Jul 17 '18 at 4:58

Divide it into two cases:

Case 1, one of the green ones is the square, then all figures and different and the ways to do it is $\frac{4!}{2}=12$ since there are 2 large ones.

case 2, either blue or yellow is square(2 ways for this to happen), then we just have to chose sizes,but this is easier since the two greens are the same up to now, we divide in 3 cases:

case2.1 the two green figures are small and medium (1 way)

case2.2 one of the greens and one of the yellow or blue are small and medium (4 ways)

case 2.3 the yellow and blue are small and medium (2 cases)

total for case 2: $7*2$ (because we need to multiply by making either the blue or yellow the square)

Therefore the final answer is $12+14=26$.

• Yes, the problem is, if you just consider determining shape for each color, I do not see how it takes into account that there are some repetitions. For example, if we have 3 circles and 1 square, the number of total unique sets of combinations would be less than if every figure is unique. – Andrey Shchekin Nov 21 '13 at 1:30
• I think this is what you are looking for, please tell me if this answer please you. – Jorge Fernández Hidalgo Nov 21 '13 at 2:02
• Thanks, but that solves a specific case -- is there a general formula I can use? If I have n multisets of size l, and for each one I know multiplicities of each item, e.g. for set s1 the multiplicities are (s1m1, s1m2, ...) -- how do I calculate the number of combinations? – Andrey Shchekin Nov 21 '13 at 3:02