Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Tiling the plane with checkerboard patterns
Replies: 21   Last Post: Jul 14, 2010 10:33 PM

 Messages: [ Previous | Next ]
 Avni Pllana Posts: 546 Registered: 12/6/04
Re: Tiling the plane with checkerboard patterns
Posted: Jul 14, 2010 7:52 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:N-1
> >

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

Date Subject Author
7/6/10 Rouben Rostamian
7/7/10 Avni Pllana
7/8/10 mark
7/9/10 Rouben Rostamian
7/9/10 Avni Pllana
7/9/10 Rouben Rostamian
7/10/10 Avni Pllana
7/10/10 mark
7/11/10 Rouben Rostamian
7/11/10 mark
7/11/10 Rouben Rostamian
7/11/10 mark
7/12/10 Rouben Rostamian
7/13/10 mark
7/14/10 Rouben Rostamian
7/14/10 mark
7/11/10 Rouben Rostamian
7/14/10 Avni Pllana
7/14/10 Rouben Rostamian
7/13/10 Mary Krimmel
7/14/10 Rouben Rostamian
7/14/10 mark