tiling a 2xn checkerboard with square tetrominoes and dominoes

[Emeric Deutsch]

I haven't read carefully your various messages on tilings and,
unfortunately, I have deleted them. Then it occurred to me to
consider various statistics on these tilings.
At the bottom of this message you will find one sequence (actually
a triangle) that I have just submitted.

Here is one way to count the tilings of a 2xn checkerboard with
square tetrominoes and dominoes.

There are only 3 basic tilings (i.e. tilings that cannot be split 
vertically into smaller tilings). These are:
(i) vertical domino; (ii) two horizontal dominoes; and (iii) 2 X 2
square.
Obviously, the g.f. of these three tilings is g = z + 2z^2 (z marks
the length of the checkerboard). Every tiling is a finite sequence
of basic tilings; consequently, the g.f. G=1/(1-g)=1/(1-z-2z^2).

To keep track of the number of the 2 X 2 squares (marked by t, for
example), we take g = z + z^2 + tz^2. This will lead to a triangle
of numbers T(n,k) = number of tilings of a 2 X n checkerboard with
k squares and n-2k dominoes. I'll submit it later today.

A pertinent reference is:

S. Heubach, Tiling an m X n area with squares of size up to k X k (m <=5), 
Congressus Numerantium 140 (1999), pp. 43-64.

Emeric

P.S.

You say:
>Now we're working on 3xn boards tiled with 1x2 dominoes, 2x2 
>square tetrominoes, and 3x3 square nonominoes.

Also here one can identify first only the basic tilings
and their g.f. g and then G=1/(1-g). However, here the number of
basic tilings is infinite.

xxxxxxxxxxxxxxxxxx

%I A128099
%S A128099 1, 1, 1, 2, 1, 4, 1, 6, 4, 1, 8, 12, 1, 10, 24, 8, 1, 12, 40, 
32, 1, 14, 60, 80, 16, 1, 16, 84, 160, 80, 1, 18, 112, 280, 240, 32, 1, 
20, 144, 448, 560, 192, 1, 22, 180, 672, 1120, 672, 64, 1, 24, 220, 960, 
2016, 1792, 448, 1, 26, 264, 1320, 3360, 4032, 1792, 128, 1, 28, 312, 
1760, 5280, 8064, 5376, 1024, 1, 30, 364, 2288, 7920, 14784, 13440, 4608, 
256
%N A128099 Triangle read by rows: T(n,k) is the number of ways to tile a 3 
X n rectangle with k pieces of 2 X 2 tiles and 3n-4k pieces of 1 X 1 tiles 
(0<=k<=floor(n/2)).
%C A128099 Neil: this is a funny-shaped triangle. END

Row sums are the Jacobstahl numbers (A001045).
Sum(k(T(n,k),k=0..floor(n/2))=A095977(n-1).
%F A128099 T(n,k)=2^k*binom(n-k,k).

G.f.=1/(1-z-2tz^2).
%e A128099 Triangle starts:
1;
1;
1,2;
1,4;
1,6,4;
1,8,12;
1,10,24,8;
1,12,40,32;
%p A128099 T:=proc(n,k) if k<=n/2 then 2^k*binomial(n-k,k) else 0 fi 
end: for n from 0 to 16 do seq(T(n,k),k=0..floor(n/2)) od; # yields 
sequence in triangular form
%Y A128099 A001045,A095977
%O A128099 0
%K A128099 ,nonn,
%A A128099 Emeric Deutsch (deutsch at duke.poly.edu), Feb 18 2007