Counting problem

[Steven G]

How many 4 by 4 arrays with entries 1 or -1 such that all rows and columns sum to 0 are there?

Is the answer 3*4!*4! =1728?

 

[Prof]

You did not explain how you got your answer. Here is my thinking on the problem. You may see an error in what I wrote. If not, see if you can finish my explanation and geet teh answer. (I did not get 1728.)

Each row must have two 1's and two -1's. Just doing the first row, there are 6 ways to fill it out. The second row would also have 6 ways to fill it out, and the first row being filled in does not restrict the second row. The third row will be restricted by filling in the first two rows. If the first two rows are the same, there will only be one way to fill out the third row. If the first two rows are not the same, there will be 4 ways to fill out the third row. The 4th row will only have one way to do it for each choice of the first 3 rows.

 

[pka]

How many 4 by 4 arrays with entries 1 or -1 such that all rows and columns sum to 0 are there?
Is the answer 3*4!*4! =1728?

I too wish yo would tell us how you arrived at that count.
For any who might work on this may I suggest that using the string $\large{+\;\:+\;\:-\;\:-}$ .
There are $\dfrac{4!}{(2!)^2}=6$ ways to rearrange that string.
Copying that string twice and then reverse it twice will give one of the $4\times 4$ grids:
$\large{+\;\:+\;\:-\;\:-}\\\large{+\;\:+\;\:-\;\:-\\-\;\:-\;\:+\;\:+\\-\;\:-\;\:+\;\:+}$
How many ways can those rows be rearranged to get a unique grid?

 

[Steven G]

There are ₄C₂=6 ways of making a column with +, +, -, -.

Now from these 6 we must pick two four for our 4x4 array. This can be done in ₆C₄=15 ways.

Well I look at all 15 of those 4x4 arrays and found that exactly 3 worked.

That is where the 3 came from. Then I realized that I can interchange the rows in 4! ways and the columns in 4! ways (I did not think that any combination of column arrangements along with row arrangements yield a row arrangement).

My final answer being 3*4!*4! ways.

 

[Steven G]

You did not explain how you got your answer. Here is my thinking on the problem. You may see an error in what I wrote. If not, see if you can finish my explanation and geet teh answer. (I did not get 1728.)

Each row must have two 1's and two -1's. Just doing the first row, there are 6 ways to fill it out. The second row would also have 6 ways to fill it out, and the first row being filled in does not restrict the second row. The third row will be restricted by filling in the first two rows. If the first two rows are the same, there will only be one way to fill out the third row. If the first two rows are not the same, there will be 4 ways to fill out the third row. The 4th row will only have one way to do it for each choice of the first 3 rows.

If the first two rows are not the same, there will be 4 ways to fill out the third row. Are you sure of that?

 

[Prof]

I mean that for each choice of the first two rows that is not the same, there will be 4 ways to fill out the third row. For example, if the first row is
1, 1, -1, -1 and the second row is 1, -1, 1, -1, see how many ways you can fill out the 3rd row.

 

[pka]

I mean that for each choice of the first two rows that is not the same, there will be 4 ways to fill out the third row. For example, if the first row is 1, 1, -1, -1 and the second row is 1, -1, 1, -1, see how many ways you can fill out the 3rd row.

There are six possible strings that can be used as rows in a $4\times 4$ grid.
\(\begin{array}{*{20}{c}}
{1}& + & + & - & - \\
{2}& - & - & + & + \\
{3}& + & - & - & + \\
{4}& - & + & + & - \\
{5}& + & - & + & - \\
{6}& - & + & - & + \end{array}\)
Note that the pairs $1,2\;\;3,4~\&\;~5,6$ are compliments( negatives) of each other.
Also that both $3,4$ are palindromes. which complicates over counting.
Consider the $4\times 4$ grid made of rows $1,2,3,4$ that is a successful grid because each row & each column contain two pluses and two minuses. Moreover the rows as a whole can be rearranged in $4!=24$ ways.
At this point we might be temped to say well just take $\mathcal{C}_4^6=15$ grids.
But wait! The $4$-tuple $(1,3,5,6)$is not a successful grid because the first column has three pluses.
Interestingly enough the $4$-tuples $(1,2,3,4),\;(1,2,5,6)\;\&\;(3,4,5,6$ are all a successful grid.
Again wait. The $4$-tuple $(1,1,2,2)$is also a successful grid. BUT how many different ways can it be rearranged?