Newsgroups: rec.puzzles
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 22 Jul 91 21:45:44 GMT
Subject: Re: Placing tiles in a grid (was: Covering a grid with tiles)

a...@hadar.cs.Buffalo.EDU (Ajay Shekhawat) writes:

>Given an NxN grid, and "t" identical tiles of size MxM each. In how many
>ways can we place these t tiles on this grid, so that
>    - There is no overlap
>    - The edges of the tiles are parallel to the boundaries of the grid
>    - The endpoints of the tiles are on the gridpoints.
>    t = 1
>There are (N-M)^2 ways of placing one tile.

You are mistaken.  There are (N-M+1)^2 ways of placing one tile.

>    t = 2
>... (this is where it becomes real tough)...

Pretty easy, actually.  First you count the number of ways of putting
the two tiles down, permitting overlaps.  Then you subtract out the
number of ways of putting the tiles down so they overlap.  The overlap
will always be a rectangle.  It isn't that hard to count, for every
0<I,J<=M, the number of ways of putting two tiles down to intersect in
an IxJ rectangle.

If we let Q=(N-M+1), I get (Q^4 - (Q + (M-1)(2Q-M))^2)/2 ways of
putting two (undistinguished) tiles down without overlap.

Now when you get to t=3, I call that tough.

Dan Hoey
Hoey@ETL.Army.Mil