2
$\begingroup$

How many ways to fill the $4 \times 4$ board by nonnegative integers, such that sum of the numbers of each row and each column is $3$?

I wrote a brute-force and got $2008$ which seems to be the right answer. I was wondering what is the combinatorial way of solving this one? How about the general problem of $N\times N$ or $N\times K$ with sum a $R$?

  • 0
    http://www.math.binghamton.edu/dennis/Birkhoff/2012-04-02
  • 0
    @deinst: What do you mean?2012-04-02
  • 0
    @Fool The problem you ask (in the NxN case) is counting the number of lattice points in a Birkhoff polytope. The number is a polynomial in the row/column sum. They computed this polynomial for N up to 10.2012-04-02
  • 1
    For a simpler approach see http://math.stackexchange.com/questions/69000/iterating-over-all-matrices-with-fixed-row-and-column-sums2012-04-02

0 Answers 0