How can I compute every possible tuple of lists from the elements V, V, V, M, M, M?

Question

I have two lists, and six elements:

V V V M M M

I would like to compute every possible combination of those elements into two lists (left and right):

So, five possible solutions could be:

([V, V, V], [M, M, M])
([], [V, V, V, M, M, M])
([V, V, V, M, M, M], [])
([V, M, V], [V, M, M])
([V], [V, M, V, M, M])

My first approach was reducing the problem to that which had less elements (two). So, all possible solutions in that case are:

([], [V, M])
([], [M, V])
([V, M], [])
([M, V], [])
([V], [M])
([M], [V])

I can't seem to fit this problem into a basic standard combinatorics one, but perhaps there is something I am missing. How can I approach this problem ?

Answer 1

An unordered arrangement is specified by two numbers $n,m$ each between $0$ and $3$. That is, we need to know how many $V's$ and how many $M's$ are in the lefthand list.

Now, given an unordered arrangement $(n,m)$ with $n$ $V's$ and $m$ $M's$ in the lefthand list, we need to order it. The left hand list can be ordered in exactly $\binom {n+m}n$ ways since there are $n+m$ objects in total and we just need to place the $V's$ to specify the order. At the same time, the right hand list has $(3-n,3-m)$ $V's, M's$ so there are $\binom {6-n-m}{3-n}$ ways to order it. The total number of orderings of the state $(n,m)$ is then given by the product $\binom {n+m}n\times \binom {6-n-m}{3-n}$ and we need to sum over the possible states $(n,m)$.

Thus the answer is $$\sum_{0≤n,m≤3}\binom {n+m}n\times \binom {6-n-m}{3-n}=140$$

Computation supplied by Wolfram Alpha

Note that this computation was "easy" because there are only two lists. Specifying the contents of the first list also specified the second. This would not be so easy if there were many lists.

Answer 2

Here is another way to compute this number:

Suppose we have $n$ symbols, with $x_i$ occurences of the $i$th symbol, and denote the total number of symbols with repitions by $X$. And suppose we want to produce a list of $k$ lists.

First, order the list of symbols with repetitions arbitrarily, second, choose $m_1,...,m_k$, with $\sum_{i=1}^k m_i = X$, to be how many go in each list, and put the first $m_1$ symbols in the first list, the next $m_2$ symbols in the second list and so on.

Conversely given a list of lists as required we can recover the $m_i$s and the ordering of the list of symbols.

Now the number of ways to order the list of symbols is $\frac{X!}{\prod_{j=1}^{n} x_j!}$ (also knows as the multinomial coefficient), and for each such ordering we have $\binom{X+k-1}{k-1}$ ways to choose the $m_i$s (by the stars and bars method), so in total we have: $$ \frac{X!}{\prod_{j=1}^{n} x_j!} \cdot \binom{X+k-1}{k-1} $$ Such lists of lists.

In the case of $n=2$, $k=2$, this simplifies to $$ \binom{x_1+x_2}{x_1}\cdot (x_1+x_2+1) $$

for $x_1=x_2=1$ we get $$ \binom{2}{1} \cdot 3=6 $$

and for $x_1=x_2=3$ (the original question): $$ \binom{6}{3}\cdot 7=140 $$