On math.stackexchange, someone asked how to count the number of ways to place $1$'s into a $10 \times 10$ matrix so that every row and column has $5$ $1$'s.  Each element of the matrix must be either zero or one.I came up with a recursive solution for an $N \times 10$ matrix.  Subproblems are indexed by the counts $c_k$ of how many columns have $k$ $1$'s, for $k =0, 1,2,3,4,5$. The counts $c_k$ have to satisfy $\sum_k c_k = 10$, and they also have to satisfy $\sum_k kc_k = 5N$ and $c_k = 0$ for $k > N$. The complexity of this algorithm basically boils down to how many distinct sets of valid indices $(c_k)_k$ there are.For a $10 \times 10$ matrix I think this approach should work out nicely, but I worry the complexity might get prohibitively large if we wanted to count how many ways to get $M/2$ $1$'s in every row and column of an $M \times M$ matrix. So I'm wondering, is there a more efficient way to solve this counting problem?  In other words, a better way than solving for $N \times M$ in increasing order of $N$ and keeping track of subcases indexed by $(c_k)_k$ such that $\sum_k c_k = M$ and $\sum_k k c_k = NM/2$? Also, for my solution, can anybody work out a good bound for how many sub-cases I have as a function of $M$?
Count number of ways to place ones in an $M \times M$ matrix so that every row and column has $k$ ones?
algorithms;time complexity;combinatorics