Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Have you tried solving the case when $n$ is small, e.g. $n=1,2,3,4,5,\ldots$? –  pharmine Oct 14 '11 at 12:32
1  
The sequence for exactly two $1$s is [Sequence A001499](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. –  joriki Oct 14 '11 at 16:04
2  
Note that this is not posed as a problem in the sense of an exercise in the book; it's just mentioned in passing, so there's not necessarily an implication that it has a nice solution. –  joriki Oct 14 '11 at 21:40
    
@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. –  Quixotic Oct 14 '11 at 21:57
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? –  joriki Oct 15 '11 at 2:51

1 Answer 1

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$.

share|improve this answer
    
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.) –  Douglas S. Stones Apr 12 '12 at 11:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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