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