In each cell of the table $4 \times 4$, in which the lines are labeled with numbers $1,2,3,4$, and columns with letters $a,b,c,d$, one number is written: $0$ or $1$ . Such a table is called valid if there are exactly two units in each of its rows and in each column. Determine the number of valid tables.
Problem
Source: SRMC 2012
Tags: numbers in a table, table, combinatorics
Kaskade
03.09.2018 21:09
We will solve a more general problem: Given an $n$ by $n$ table, how many such grids are there. I know not of a closed form, but have found a quite simple recurrence relation. Let $f\left(n\right)$ refer to the number of such arrangements.
Imagine permutations of the list $\left[1,\ 1,\ 2,\ 2,\ 3,\ 3,\ ...\ n,\ n\right]$. We can use such permutations to generate valid grid patterns. Simply take the first two numbers, these are the columns of the units in the first row. Then the third and fourth give the second row and so on. However not every permutation gives a valid pattern. Take the starting arrangement. Clearly we cannot put two units in the same square. Not only that, but swapping two different elements will result in the same grid pattern. So to find $f\left(n\right)$, we need to find the number of arrangements such that the $2k+1$th and $2k+2$ elements are different for all $k$, while also taking repeats into account.
We already have $f\left(0\right)=1,\ f\left(1\right)=0$
There are $\binom{n}{2}$ ways of picking the first two numbers. WLOG let this be $1$ and $2$. We now have two cases:
Case 1: The pair $\left\{1,\ 2\right\}$ appears again in the same column.
There are $n-1$ places this pair can appear, and then $f\left(n-2\right)$ ways of choosing the remaining numbers.
Case 2: The pair $\left\{1,\ 2\right\}$ doesn't appear again in the same column.
In this case, we can imagine the remaining $1$ and $2$ as the same number, and so there are $f\left(n-1\right)$ ways of doing this, but then the $1$ and $2$ can be swapped, so we get $2f\left(n-1\right)$
Thus we get the relation $f\left(n\right)=\frac{n\left(n-1\right)}{2}\left(2f\left(n-1\right)+\left(n-1\right)f\left(n-2\right)\right)$
Then we evaluate $f\left(4\right)=90$