
Re: Tiling the plane with checkerboard patterns
Posted:
Jul 11, 2010 12:39 PM


On Sat, Jul 10, 2010 at 05:11:58PM +0000, Avni Pllana wrote: > On Fri, Jul 9, 2010 Rouben Rostamian wrote: > > Here is the Maple's version of your formula: > > > > a := proc(n::posint) > > local N, b; > > N := n^2; > > b := binomial(N,i); > > return sum( iquo(b,N) + irem(b, N), i=0..N); > > end proc: > > the term ? quo(b,N) + rem(b,N) ? gives enough insight into the > nature of the problem. It is exactly the number of equivalence classes > of nxn binary matrices that correspond to binomial(N,i) combinations > with respect to horizontal and vertical shifts. Since there are (n > horizontal shifts)x(n vertical shifts), the binomial(N,i) should be > divided by N. > > I wrote a Matlab program implementing the above ideas and according to > the numerical results for n=1,2,3, I was able to derive the general > formula that fits perfectly to your numerical results for a(n), > n=1,?,5. The general formula is to nice not to be true, and a formal > proof of it ?is left to the reader?.
Avni, I agree with you that your formula for a(n) is too nice not to be true and chances are good that it is true. I tried to convince myself that it is correct but I couldn't quite get it. The "irem(b,N)" terms in the formula accounts for patterns which are invariant under certain shifts. It certainly does the right thing for the cases n=1,2,3,4,5 because the formula agrees with independently computed results. I would love to prove that it is true in general but I am unable to.
Rouben

