
Re: Tiling the plane with checkerboard patterns
Posted:
Jul 10, 2010 10:32 AM


> On Fri, Jul 09, 2010 at 06:00:32PM +0000, Avni Pllana > wrote: > > > > I think I found the right algorithm/formula for > a(n): > > > > %%%%%%%%%%%%%%%%%%%%%%%% > > > > for n=1:5 > > > > N=n^2; > > A=2; > > > > for i=1:N1 > > > > A=A+floor(nchoosek(N,i)/N)+mod(nchoosek(N,i),N); > > end > > > > a(n)=A; > > > > end > > > > %%%%%%%%%%%%%%%%%%%%%%%% > > > Avni, that's wonderful! It produces the exact > values for a(n), n=1,2,3,4,5. Do you have a proof > for the general case? > > Rouben > > Aside: Since the Matlab program above is limited > by its dependence on floating point arithmetic > to the range n=1,2,...,7, I recoded your algorithm > in Maple which performs integer arithmetic with no > limits. 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: > > Then the command "seq(a(n), n=1..9);" produces > the values of a(n) for n=1,2,...,9: > > n a(n) > 1 2 > 2 7 > 3 64 > 4 4156 > 5 1342208 > 6 1908874521 > 7 11488774559744 > 8 288230376151712689 > 9 29850020237398251228192 >
Hi Rouben,
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?.
Best regards, Avni

