Number of ways to fill the table In how many ways can we fill a $2\times n$ table with $n$ even and $n$ odd numbers so that an odd number is never under an even one? 
We can conclude that columns of type$\binom{EVEN}{ODD}$ don't satisfy the condition. We can, however, include $\binom{EVEN}{EVEN}$, $\binom{ODD}{ODD}$ and $\binom{ODD}{EVEN}$ types of columns. 
If we have $k$ columns of type $\binom{EVEN}{EVEN}$ then we are bound to have $k$ columns of type $\binom{ODD}{ODD}$ and thus $n-2k$ columns of type $\binom{ODD}{EVEN}$. 
The total number of ways to select the three types of columns equals: 
$$\binom{n}{k} \cdot \binom{n-k}{k} \cdot \binom{n-2k}{n-2k}$$ where $k$ takes values from 1 to $\lfloor{\frac{n}{2}}\rfloor$. 
My next step would be to multiply this by $n!$ since we can permute the columns and get valid results. 
The author of the solution, however, multiplies by $(n!)^2$ and claims that for each such set of columns there are $n$ even and $n$ odd cells so the total number of ways we can fill them equals $n! \cdot n!$. 
I can't understand why he is taking account of individual cells and not columns? I mean that we can safely permute columns, but not individual cells. 
What am I missing? 
UPD: I guess I should have specified that natural numbers are considered and each of them can only be used once. 
 A: Like Matti P suggests, if the $n$ even numbers and $n$ odd numbers are not fixed, then there would be no upper limit on the number of ways to fill the array. Thus we select $n$ distinct even numbers and n distinct odd numbers, and we will find the number of ways to fill a $2\times n$ table under the specified requirement for the fixed numbers chosen.
We will first look at the number of possible parity tables (tables whose entries are either "Odd" or "Even"). As you have said in your post, if there are $k$ columns of type $\bigg[\begin{matrix} Odd \\ Odd \end{matrix}\bigg]$, then there will be k columns of type $\bigg[\begin{matrix} Even \\ Even \end{matrix}\bigg]$, and $n-2k$ columns of type $\bigg[\begin{matrix} Odd \\ Even \end{matrix}\bigg]$. Note that k can range from $0$ to $\bigl\lfloor{\frac{n}{2}}\bigr\rfloor$.
Thus for a fixed $k$, the number of parity tables that have $k$ columns of type $\bigg[\begin{matrix} Odd \\ Odd \end{matrix}\bigg]$ is $${n \choose k}\cdot{n-k \choose k}\cdot{n-2k \choose n-2k} = {n \choose k}\cdot{n-k \choose k}$$
Note that this counts all parity tables that have $k$ columns of the form $\bigg[\begin{matrix} Odd \\ Odd \end{matrix}\bigg]$, so there is no need to permute the columns. Summing over k gives a total of $$\sum_{k = 0}^{\bigl\lfloor{\frac{n}{2}}\bigr\rfloor} {n \choose k}{n-k \choose k}$$ acceptable parity tables.
Now we still need to replace the parities with actual numbers (i.e. Every time we see the word "Even", we will choose one of the n even numbers and replace the word "Even" by this number such that there are no repeats. Similarly for every time we see the word "Odd".) 
How many ways are there to do this? Well there are precisely $n!$ ways to choose where the $n$ even numbers go, and there are $n!$ ways to choose where the $n$ odd numbers go. This tells us for any given parity table there are $(n!)^2$ ways to fill it appropriately with our selected numbers.
This gives us a grand total of $$ (n!)^2 \sum_{k = 0}^{\bigl\lfloor{\frac{n}{2}}\bigr\rfloor} {n \choose k}{n-k \choose k}$$
