Combinatorics in a 4x4 Board with White and Black Tiles

Date: 07/27/2006 at 20:05:07
From: Carlos
Subject: Combinatorics in a 4x4 board with white and black tiles

8 white tiles and 8 black tiles are arranged in a 4x4 square board 
with the condition that in each row there are 2 white and 2 black 
tiles, the same in each column.  In how many different forms can the 
tiles be distributed? 

I know the basics of permutations and combinations but I don't know 
how to use the condition in order to make the necessary calculations.

I realize that there are 4C2 = 6 ways to distribute two tiles in each 
row and column.  I think that if I can find all the possible ways to 
arrange the tiles with the first row fixed, then I will just have to 
multiply it by 6 and I would get the answer.

Now, I also believe that the first two rows can be arranged in any 
way (with only the condition of two white and two black in each row) 
but depending on how you arranged those it strictly conditions the 
way to fill the columns. 

It is quite confusing, I appreciate your help.

Date: 07/30/2006 at 10:42:08
From: Doctor Anthony
Subject: Re: Combinatorics in a 4x4 board with white and black tiles

If we consider just the white tiles and arrange them so that there 
are 2 white in each row and 2 white in each column then the black 
tiles will simply fill up the empty spaces.

Start by placing 4 tiles in the following way.

  Choose 2 rows in C(4,2) = 6 ways

  Choose 2 columns in C(4,2) = 6 ways

At the intersection of these rows and columns place a white tile.  
This uses up 4 white tiles and also 2 rows and 2 columns of the grid:

    |     |
    *  *  *  *
  - W  *  W  *
  - W  *  W  *
    *  *  *  *

This will leave 2 further rows and 2 further columns with no tiles.  
Place a white tile at the intersections of these rows and columns 
and we have placed all 8 white tiles such that each row and each 
column has 2 white tiles:

    |     |
    *  W  *  W
  - W  *  W  *
  - W  *  W  *
    *  W  *  W

The total number of such possibilities is 6 x 6 = 36.

But, there will be repeated arrangements.  If we first chose two rows
and two columns and then chose exactly the opposite two rows and
columns, the end results of those two patterns will be the same.  So
the actual number of unique patterns of this form is 36/2 or 18.

Now we need to think about other possible patterns that don't create
two rectangles, as all of the above do:

  *  W-----W
  W--|--W  |
  W--|--W  |
  *  W-----W

For example, we could have:

  W  W  *  *
  *  W  W  *
  *  *  W  W
  W  *  *  W

Here is a typical board to show how we can derive such a layout:

  W  W  *  *

  *  W  *  W  

  *  *  *  *

We can choose the 2 rows in C(4,2) = 6 ways.

We choose the column to have 2 W's in 4 ways and the other two 
columns in 3 ways and then 2 ways.

Total ways of choosing these 4 points = 6 x 4 x 3 x 2 = 144 ways.

But again the other 4 points would crop up amongst these 144 
arrangements and give double counting of the total.  So with non-
rectangular arrangements there are 72 distinguishable layouts.

Combining the rectangular and non-rectangular arrangements we have a 
total of  18 + 72 = 90 distinguishable layouts.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 08/06/2006 at 12:01:48
From: Carlos
Subject: Thank you (Combinatorics in a 4x4 board with white and black
tiles)

Thanks Dr. Anthony for your quick answer and solution.  Now I know a
bit more about how to solve this kind of problem.

Carlos