Given a $3m\times m$ table, how many ways can it be filled by $x$'s & $o$'s such that each column has at least $2$ $x$'s? Looking at this treat I thought it's a pretty easy one. Apparently not :]. Well,

Given a $ 3m \times m $ table, how many ways can we fill it with $x$'s and $o$'s, such that each column has at least $2$ $x$'s?

Well, my idea was pretty simple:
Let's have a look at all the possible ways to fill this table. We have $ 3m^2 $ cells, and 2 options for each. Then we have $ 2^{3m^2} $ ways to fill the table. Than, lets subtract all cases where $x$ appears once. This case looks this way:
$$ \prod_{i=1}^{m} \binom{3m}{1} = \binom{3m}{1} \cdot \binom{3m}{1} \cdot \binom{3m}{1}\dots\binom{3m}{1}$$
Then, we have $1$ single option to fill the table without x's at all. In conclusion, we have $$2^{3m^2}-(3m)^m - 1$$
BUT, looking at the final answers in the homework solutions, it says:
$$ (2^{3m} - 3m - 1)^m $$
Seriously, I don't understand how they got that. Does my way makes sense, or do I miss something here?

Given the solution (and working backwards) we understand that the solution considers each column separately:


*

*$2^{3m}$ ways to fill it (without restrictions).

*$3m$ ways with one $x$,

*$1$ way with no $x$


So, there are $(2^{3m}-3m-1)$ ways to fill one column with the given restriction. Since there are $m$ columns which you can fill independently, there are: $$(2^{3m}-3m-1)^m$$ ways to complete the task.

The mistake in your reasoning is that you consider all columns at once. You count the ways that all columns simultaneously have $1$ $x$ or $0$ $x$'s but this ignores cases where for example the first column has no $x$'s and the rest $1$ $x$. You considered the whole table at once, but since the restriction concerns columns and columns can be filled independently, you should have followed the same approach by column-wise (as in the solution).
