7
$\begingroup$

I'm trying to get my head around a problem, and it's not working.

The problem: consider an NxN matrix that represents a binary number. For instance, a 4x4 matrix is a 16 bit number, a 6x6 matrix is a 36 bit number. N will always be even.

Now, for any given N, how many matrices / numbers are there where every row and column has exactly half of its values 0 and half 1?

Here is what I have learned so far:

  • From brute force, I know that the answer for a 2x2 matrix is 2. For a 4x4 matrix, the answer is 90.
  • I can calculate the number of rows OR columns that half half of their bits on with the formula: $$ f(n) = {n! \over (n/2)!^2} * 2 ^ {n^2} $$
  • But I can't simply take percentage of rows times percentage of columns, presumably because they are not independent.

This started out of curiosity and has become an obsession. Please help.

$\endgroup$
  • $\begingroup$ nice question! +1 $\endgroup$ – sigmatau Jul 23 '13 at 2:32
3
$\begingroup$

This sequence appears in OEIS, wherein there are references such as this article in the Electronic Journal of Combinatorics, which gives asymptotic results.

The sequence, incidentally, begins $1, 2, 90, 297200, 116963796250, 6736218287430460752,\ldots$

$\endgroup$
  • $\begingroup$ Thanks for that -- it is indeed the correct sequence. And the article is interesting. So far, it looks like there is no general solution, which is pretty frustrating. But thanks for the additional info! $\endgroup$ – user977705 Jul 23 '13 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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