Combinatorics in a 4x4 Board with White and Black TilesDate: 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 |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/