Search All of the Math Forum:

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

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

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

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