
Re: Tiling the plane with checkerboard patterns
Posted:
Jul 14, 2010 6:45 PM


Hello Avni, I am surprised with the discrepancy you have found in the a(6) case. I still hold hope that your formula does give the correct values for all a(n). Could it be that the discrepancy is due to Matlab's floating point arithmetic?
Since you and Mark have both noted the effect of parity of n, I want to point out that I have reason to believe that what matters is not whether n is odd or even, but whether it is prime or composite. I don't have a foolproof argument to support that right now; just a preliminary analysis. I will write about this again if I find out more.
Rouben
 original message  From: Avni Pllana <avniu66@hotmail.com> Date: Wed, 14 Jul 2010 12:14:51 +0000 (UTC) To: approve@support1.mathforum.org To: geometrypuzzles@support1.mathforum.org Subject: Re: Tiling the plane with checkerboard patterns
> 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,
I tried to find further numerical evidence about my sum formula. A comparison of the number of equivalence classes using the Matlab program and using the sum formula is shown below:
n=1 N=1^2=1
Mat_1=[1 1] Sum_1=[1 1]
a(1)=2, Matlab a(1)=2, sum formula ________________________
n=2 N=2^2=4
Mat_2=[1 1 3 1 1] Sum_2=[1 1 3 1 1]
a(2)=7, Matlab a(2)=7, sum formula ________________________
n=3 N=3^2=9
Mat_3=[1 1 4 12 14 14 12 4 1 1] Sum_3=[1 1 4 12 14 14 12 4 1 1]
a(3)=64, Matlab a(3)=64, sum formula ________________________
n=4 N=4^2=16
Mat_4=[1 1 9 35 122 273 511 715 822 715 511 273 122 35 9 1 1] Sum_4=[1 1 15 35 125 273 508 715 810 715 508 273 125 35 15 1 1]
a(4)=4156, Matlab a(4)=4156, sum formula ________________________
n=5 N=5^2=25
Mat_5=[1 1 12 92 506 2130 x x ...] Sum_5=[1 1 12 92 506 2130 .......]
a(5)=1342208, Rouben a(5)=1342208, sum formula ________________________
n=6 N=6^2=36
Mat_6=[1 1 19 201 1649 x x ...] Sum_6=[1 1 35 210 1645 .......]
a(6)= ?, Matlab a(6)=1908874521, sum formula ________________________
Above results show that for n odd the sum formula gives exactly the number of equivalence classes and exact a(n).
For n even the sum formula does not give the exact number of equivalence classes, but it gives exact a(n), at least for n=2 and n=4.
These results resemble somehow the behavior of magic squares.
Best regards, Avni

