Wikipedia:Reference desk/Archives/Mathematics/2013 February 7

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 7

3 in each column and row of 6 by 6 grid?

How many ways are there to put 18 items into a 6 by 6 grid so that 1 item goes in each grid square and there are a total of 3 items in each row and each column. For example, you could have rows 1-3 filled in for columns 1-3 and rows 4-6 filled in for columns 4-6 or conversely row n could be filled in from column n+2 to n+4 mod 6. Secondly, how many of them are unique in that they can not be changed into each other by any combination of row switches or column switches? I'm hoping for formulae since what I'm actually looking for is a 20 by 20 grid with 200 items. :) Naraht (talk) 20:18, 7 February 2013 (UTC)

You are looking for the number X of 6x6 bitmatrices A_ij satisfying the column sum condition Σ_i A_ij = 3 and the row sum condition Σ_j A_ij = 3. You have initially that X ≤ 2³⁶ = 68719476736. The row condition Σ_j A_ij = 3 says that there are only ${\binom {6}{3}}$ = 20 possible rows, and so X ≤ 20⁶ = 64000000. The column sum condition tells you that once you have the first 5 rows in place the 6'th row is fixed, so X ≤ 20⁵ = 3200000. Switching rows reduces the possibilities further. You may demand that the rows are in nondescending order. Number the 20 possible rows from 1 through 20. How many nondescending 5-tupples of numbers from 1 through 20 are there? Bo Jacoby (talk) 11:05, 8 February 2013 (UTC).

But even with that number of nondescending 5-tuples, each nondescending 5-tuple must be tested to see if actually has 3 in 3 of the columns and 2 in the other three (so as to give the ability to have a fixed sixth row. For example, a 5-tuple that contains 4 of the first 10 possible rows isn't allowed since that would have 4 in column 1, but keeping track of which rows would give 4 in column 3 isn't as easy to remember.Naraht (talk) 01:19, 9 February 2013 (UTC)

Yes, surely, but it could further improve the upper boundary. Bo Jacoby (talk) 12:35, 10 February 2013 (UTC).

I ran a computer simulation, and got 297,200 possibilities for the 6×6 case. I don't know how many of those are unique, though. I don't think I can brute force the 20×20 case, unfortunately. StuRat (talk) 02:24, 9 February 2013 (UTC)

Surely you mean "distinct" (or something like "essentially distinct"), not "unique". If there are 297,200 of them, they aren't unique. :-) —Bkell (talk) 03:26, 11 February 2013 (UTC)

I'm using "unique" in the way the OP defined it: "unique in that they can not be changed into each other by any combination of row switches or column switches". And, I don't believe they are all unique, in this sense. StuRat (talk) 04:33, 11 February 2013 (UTC)