ENUMERATION SMOOTH LEGO TOWERS

abstract

1. Introduction

In the following, we use the definitions from [1]. Recall that “Lego” is a construction toy of interlocking plastic building blocks. For our purpose, we will consider them as rectangular tiles of dimensions 1 × a (a ∈ ℕ). A polyomino can be realized in terms of a Lego tower as follows: Assume that we have an infinite supply of Lego pieces of dimensions 1 × a. Then every floor of the tower contains a finite (horizontal) sequence of pieces separated by gaps. A vertical sequence of floors constitutes a polyomino if the resulting configuration is connected. All the Lego towers depicted in Figure 1 are polyominoes.

Figure 1. Examples of Lego towers.

Definition 1.1. A k-Lego tower is a Lego tower with a finite number of floors, where each floor contains exactly one Lego piece of size 1 × a with 1 ≤ a ≤ k.

For k-Lego towers, we introduce some more terminology. Given a k-Lego tower of two Lego pieces as described in Figure 2, we call ℓ ∈ ℤ the left overhang and ℓ′ ∈ ℤ the right overhang of the second floor with respect to the first floor; note that both overhangs can be positive or negative (in Figure 2, ℓ < 0 and ℓ′ > 0) .

ℓ  1 × a  1 × b  ℓ′

Figure 2. Lego tower with two Lego pieces with b − ℓ′ − ℓ = a.

A Lego tower or k-lego tower is called double side smooth if the left overhang ℓ and the right overhang ℓ′ satisfy ℓ, ℓ′ ∈ {−1, 1, 0}, and is called left side smooth (respectively, right side smooth) if the left overhang ℓ (respectively, the right overhang ℓ′) satisfy ℓ ∈ {−1, 1, 0} (respectively, ℓ′ ∈ {−1, 1, 0}).

2. Enumeration of left side smooth Lego tower adn k-Lego tower

.

References

[1] D. Zeilberger, Automated counting of LEGO towers, J. Differ. Equations Appl. 5 (1999), 323–333.