2
$\begingroup$

This question is an exact duplicate of:

It is proposed to colour the squares of a $4 \times 4$ board black and white, so that there are exactly two black squares and two white squares in each row or column. enter image description here

In how many ways can this be done?

I've tried this finding out the number of ways column 1 and 2 can be done which is $36 = 6 \cdot 6$ as $\binom{4}{2}$ since the second column doesn't get in the way of the first.

Then I hit a road block. Can anyone provide a hint?

$\endgroup$

marked as duplicate by Jam, N. F. Taussig combinatorics Aug 8 '18 at 19:58

This question was marked as an exact duplicate of an existing question.

0
$\begingroup$

An ad-hoc low level solution can be quickly given. There are $6$ possibilities to fill in the first row. Fix now a solution grid. After applying the one shuffle permutation of columns that map the first, resp. second black square of the first row to the positions 1, 2 of this first row, we get a "special grid". (The shuffle does not change the order of the black and/or white squares of the first line.)

The number of all solution grids is then the number of realizations

XX
????
????
????    times 6 .

The next reduction is to move in the first column the second occurence of a "black square " X to the upper most possible position. There are only three possibilities for the X, so we count realizations like

XX
X???
????
????    times 6 times 3 .

Now let us take a closer look to the second column. The X is either at position $(2,2)$, and we can fill in the picture in exactly one way, or not, then... (we either norm the second column with an X at position $(2,3)$, taking the number times two, a.s.o., or we count the four possibilities in an other way.) We get as answer

[ XX        ( XX           ) ]
[ XX        ( X ??         ) ]
[   XX      (  X??         ) ]
[   XX plus (   ?? times 2 ) ]  times 6 times 3 .

There are thus $(1+2\cdot 2)\cdot 6\cdot 3=90$ solution grids.

Code checking this:

sage: J = [0,1]
....: rows = [ [a,b,c,d] for a in J for b in J for c in J for d in J if a+b+c+d == 2 ]
....: tables = [ matrix( ZZ, 4, 4, [r1, r2, r3, r4] )
....:            for r1 in rows for r2 in rows for r3 in rows for r4 in rows ]
....: tables = [ A for A in tables
....:            if  sum( A[:,0].list() ) == 2
....:            and sum( A[:,1].list() ) == 2
....:            and sum( A[:,2].list() ) == 2
....:            and sum( A[:,3].list() ) == 2 ]
....: 
sage: len(tables)
90
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.