6
$\begingroup$

How many ways are there of filling an $n×n$ square grid with $0$s and $1$s if you are allowed at most two $1$s in each row and two $1$s in each column?

I need some ideas for solving this problem.

PS:This problem is from the book Princeton Companion Mathematics.

  • 2
    Have you tried solving the case when $n$ is small, e.g. $n=1,2,3,4,5,\ldots$?2011-10-14
  • 2
    The sequence for *exactly* two $1$s is [Sequence A001499](http://oeis.org/A001499) in OEIS. The first few values for *at most* two $1$s are $1,2,16,265,7343,304186$; this isn't in OEIS.2011-10-14
  • 2
    Note that this is not posed as a problem in the sense of an exercise in [the book](http://books.google.com/books?id=ZOfUsvemJDMC&lpg=PP1&pg=PA6#v=snippet&q=%22if%20you%20are%20allowed%20at%20most%20two%22&f=false); it's just mentioned in passing, so there's not necessarily an implication that it has a nice solution.2011-10-14
  • 0
    @joriki:Yes,you are correct,but I don't understand what do you mean by "not a nice solution"?:)Since,this doesn't seems to a be a bad problem to me.2011-10-14
  • 0
    @joriki: Are you sure about those values? I got $1,7,65$ for $n=1,2,3$.2011-10-14
  • 1
    @Brian: About $265,7343,304186$, I'm only as sure as I am about the program I wrote, but if $2$ and $16$ are wrong I must be misunderstanding the question. For $n=1$ and $n=2$, there are always at most two $1s$ in each row and column, so all patterns are allowed, and there are $2^{1\cdot1}$ and $2^{2\cdot2}$ of those, respectively. Is that not what the question is asking?2011-10-15
  • 0
    @FoolForMath: Well, does the Collatz problem seem like a bad problem to you? There's not necessarily a direct relationship between the simplicity of the problem statement and the simplicity of the solution. I don't have any strong intuition on whether this should have a simple solution, and I wonder whether you do.2011-10-15
  • 0
    @Brian: To remove one potential source of misunderstanding: in the book, "at most" is repeated, "at most two $1$s in each row and at most two $1$s in each column", so in the shortened version here it's intended to apply to both rows and columns.2011-10-15
  • 0
    @joriki: I understood that it applied to both rows and columns; I just now realized that I was making the unconscious assumption that there must also be at least one $1$ in each row and each column.2011-10-15
  • 0
    @joriki; if I deduced correctly, it's your code on Sloane's [A197458](https://oeis.org/A197458). Perhaps you'd like to answer this question now? (I'm particularly curious about the recursion.)2012-04-12
  • 0
    @Douglas: I posted an answer -- I hope this is what you were looking for?2012-04-12

1 Answers 1

4

Due to popular demand, here's an explanation of the recurrence used in the code I posted at OEIS.

Let $a(k,l,m,n)$ be the number of binary $m\times n$ matrices with at most two $1$s per row, $k$ column sums of $0$, $l$ column sums of $1$ and the remaining $n-k-l$ column sums of $2$. In the following, I'll call a column with sum $n$ an $n$-column for short. Since the numbers we're looking for have no restrictions on $k$ and $l$, they're given by

$$a(n)=\sum_{k=0}^n\sum_{l=0}^{n-k}a(k,l,n,n)\;.$$

There is exactly one $0\times n$ matrix, and it has $n$ column sums of $0$, so $a(n,0,0,n)=1$ and $a(k,l,0,n)=0$ otherwise. To find a recurrence relation for $a(k,l,m,n)$, we can go through all admissible ways of adding a new row to an $(m-1)\times n$ matrix.

We can add a row without $1$s; that doesn't change the column sums and gives a contribution $a(k,l,m-1,n)$.

We can add a row with one $1$, and the $1$ can be in a $0$-column or a $1$-column. If it's in a $0$-column, it reduces $k$ and increases $l$, and there are $k+1$ columns to choose from, for a contribution of $a(k+1,l-1,m-1,n)(k+1)$. If it's in a $1$-column, it leaves $k$ unchanged and reduces $l$, and there are $l+1$ columns to choose from, for a contribution of $a(k,l+1,m-1,n)(l+1)$.

Or we can add a row with two $1$s, and the columns they're in can be either two $0$-columns, one $0$-column and one $1$-column, or two $1$-columns. If they're two $0$-columns, $k$ is reduced by $2$ and $l$ is increased by $2$, and there are $(k+2)(k+1)/2$ pairs of columns to choose from, for a contribution of $a(k+2,l-2,m-1,n)(k+2)(k+1)/2$. If they're one $0$-column and one $1$-column, $k$ is reduced by $1$ and $l$ is unchanged, and there are $(k+1)l$ pairs of columns to choose from, for a contribution of $a(k+1,l,m-1,n)(k+1)l$. If they're two $1$-columns, $l$ is reduced by $2$ and $k$ is unchanged, and there are $(l+2)(l+1)/2$ columns to choose from, for a contribution of $a(k,l+2,m-1,n)(l+2)(l+1)/2$.

Summing it all up, we have

$$ \begin{eqnarray} a(k,l,m,n) =&& a(k,l,m-1,n) \\ &+&a(k+1,l-1,m-1,n)(k+1)+a(k,l+1,m-1,n)(l+1) \\ &+& a(k+2,l-2,m-1,n)(k+2)(k+1)/2 \\ &+& a(k+1,l,m-1,n)(k+1)l \\ &+& a(k,l+2,m-1,n)(l+2)(l+1)/2\;, \end{eqnarray} $$

where terms with indices out of range are taken to be $0$.

  • 0
    Thanks for that. It's much easier to prove than I thought from just looking at the equation! (I suppose the hint should have been the fixed n and m->m-1.)2012-04-12