Some Results Inspired by Covering Rectangles
with 1x1 and 1x3 Rectangles

Congressus Numerantium, Number 122, pp. 119-124, 1996.

Phyllis Z. Chinn* and Dale R. Oliver

Humboldt State University, Arcata, CA
pzc1@axe.humboldt.edu
dro1@axe.humboldt.edu
MS Word 5.1 version of this paper


Cuisenaire rods ("c-rods") are a set of rectangular solids with cross-section of 1 cm by 1 cm squares, color-coded by length, and varying from 1 cm long white rods and 2 cm long red rods to 10 cm long orange rods. A variety of number-theoretic and combi natorial geometry problems can be modeled using the c-rods. In this paper we explore the number of ways of tiling 1 x n, 2 x n, and 3 x n rectangles with 1 x 1 and 1 x 3 c-rods. When the tiled rectangle is 1 by n, the tiling problem is equival ent to the number theory question of how many compositions, i.e. ordered partitions, of n use only 1's and 3's.

Key words: recurrence relations, tiling problems, Fibonacci numbers, Pascal's Triangle, using manipulatives to motivate mathematical discoveries

1. Introduction

Several papers in the last few years [1, 2. 5-8] have presented results on tilings of integer rectangles by rectangles of unit width. Most of this work was initially inspired by using a set of Cuisenaire rods ("c-rods") to explore discrete math questions at NSF-sponsored Project PROMPT (Professors Rethinking Options in Mathematics for Prospective Teachers) workshops. A Cuisenaire rod of length n is a 1xn rectangular solid. Such rods, in sets from n=1 to n=10, are employed in elementary grades to study properties of numbers. The rods in a set are color-coded by length, with white corresponding to n=1, red to n=2, green to n=3, etc. Chinn, et al, [2] explored a number of results when all lengths of rods are allowed. Brigham, et al, [1] restricted thei r attention to white and red rods and used them to derive a variety of relationship involving Fibonacci numbers. Here we will explore results derived from tilings with white and green rods.

One of the more fascinating aspects of studying tilings by Cuisenaire rods is the insight that working with the rods gives to multiple approaches to the same problem. In this paper, we begin by presenting several methods to count the number of ways G(n) i n which white and green rods tile a 1xn rectangle.(*)

2. Forming Trains

In Cuisenaire rod terms, a tiling of a 1xn rectangle with Cuisenaire rods is often called a train of length n.

For n=1, 2, the only possible train uses just white rods. For n=3, there are two such trains. For n=4, there are 3 of them.


(*)In this paper, we consider this as a tiling problem. It could also be viewed as a number theory question, namly, how many compositions of n use only 1's and 3's?

Figure 1. White/Green Trains of Length 3 and 4

A partial table of values follows.

Table 1.

Remark 1. G(n) = G(n-1) + G(n-3) (1)

Proof. A train either ends in a white rod, added to any of trains of length , or ends in a green rod added to any of trains of length .

Corollary. Since G(n-1) = G(n-2) + G(n-4), we also have

G(n) = G(n-2) + G(n-3) + G(n-4)

3. Some Relations Among the G(n)'s

Consider a train of length 2n and the middle point: this can be a split between two rods, or can be spanned by a green rod in either of two positions:
Thus,


.

Likewise from a train of length 2n + 1, again considering the nth position following the unit, we see that

Similarly, a train of length n can be cut following the ith unit with a comparable three outcomes, thus:

4. A Combinatorial point of view

The sequence G(n) is known [3,4] and occurs as equation M0571 in [9]. In the references given in Sloane, the sequence G(n) is derived as a diagonal in Pascal's triangle. In particular, the "Fibonacci diagonals" in Pascal's triangle consist of the numbe rs along lines of slope as shown in Figure 2 below. The sum of the numbers along these diagonals are the Fibonacci numbers.

Figure 2. The Fibonacci diagonals

If, instead, you sum numbers along lines of slope 1/3, the white/green train numbers appear. These lines are shown in Figure 3.

The motivations for this connection to Fibonacci diagrams comes through working with Cuisenaire rods. The rods chosen may have from I=0 to i= green rods with white rods. These rods may be arranged in ways.

Figure 3. The diagonals of slope 1/3

Thus,

(5)

Yet another equation can be derived by a focus on green rods. In particular, if there are any green rods in a train, the first one can occur starting after i white rods, . There is only one way to fill the portion with no green rods, and ways to fill t he end. There is also one train of all white rods. Thus,

(6)

i.e., G(n) = 1 + G(n-3 + G(n-4) + ... + G(1) + G(0) (7)

This result can also be derived directly from the recurrence relation (1).

5. Tilings of Rectangles

Let us now consider a few results regarding tiling wider rectangles. We will use the notation to denote the number of ways to tile a rectangle that is n units long and i units wide using white and green rods. Clearly by rotational symmetry. This resu lt can be used to calculate for small values of i.

Remark 2. The number of tilings of a 3xn rectangle using only green rods = .

Proof: If one horizontal rod is used, three of them must be stacked on top of one another. Thus, the whole tiling is determined by the top row where a green rod in a train corresponds to 3 horizontal rods and a white rod in a train corresponds to a vert ical green rod.

The number of green/white tilings of a 2xn rectangle satisfies G(n,2) = G(n,1)*G(n,1) , since no rods can cross between the two rows. A partial table of these values is given below.

Table 2

Let us next consider tilings of a nx3 rectangle with white/green rods. If no green rod is placed vertically, there are possible tilings. If there are vertical green rods, and the first one occurs after i positions , then the ix3 r ectangle to the left can be filled ways and the by 3 rectangle to the right can be filled ways. Thus,

(8)

Note the slight similarity between this recurrence relation and the one that generates Catalan numbers. A partial table of values is given below.

Table 3

Again, considering nx3 rectangles with white and green rods, there are a variety of things that can happen in one vertical position (as considered from either the right end or the left end of the rectangle) that could be used for some recursive ways of ex tending trains. In particular, there could be

  1. A clear break.
  2. Just one green extending one position out -- in any of 3 rows.
  3. One green extending two units out -- in any of 3 ways.
  4. Two greens extending one unit each (3 ways to arrange).
  5. Two greens extending two units each (3 ways to arrange).
  6. One green extending two units, one extending one unit (6 ways to arrange).
  7. Two greens extending one unit each, one green extending two units (3 ways).
  8. Two greens extending two units each, one green extending one unit (3 ways).

A recursive procedure could be established for generating all the trains, in a fashion similar to what Hare [6] did for 3 x n rectangles using white and red rods. The multiplication of possibilities created by having a longer second-color rod seems to ma ke this method too cumbersome to pursue here, although clearly a computer program could be established to generate the tilings or, at least, to count how many there are.

References:

1. Brigham, Robert C., Richard M. Caron, Phyllis Z. Chinn and Ralph Grimaldi, "A Tiling Scheme for the Fibonacci Numbers". To appear, J. Recreational Mathematics, Spring 1992.

2. Chinn, Phyllis Z., Greg Colyer, Martin Flashman and Ed Migliore, "Cuisenaire Rods Go to College", In PRIMUS, Problems, Resources, and Issues in Mathematics Undergraduate Studies, June 1992, Vol. II, Number 2, p 118 - 130.

3. Fernberg, Mark, "New Slants" Fibonacci Quarterly, Vol. 2, 1964, p 223-230.

4. Green, Thomas M., "Recurrent Sequences and Pascal's Triangle." Mathematics Magazine, Vol. 41, 1968, p 13-21.

5. Hare, E. O. "Tiling a 2xn area with Cuisenaire rods of length less than or equal to k." Submitted, Discrete Mathematics.

6. Hare, E. O., "Tiling a 3xn Area with Cuisenaire Rods of Length Less Than or Equal to k." Submitted

7. Hare, E. O. and P. Z. Chinn, "Tiling with Cuisenaire Rods." G. E. Bergum et al. (eds.), Applications of Fibonacci Numbers, Volume 6, 165-171.1996 Kluwer Academic Publishers.

8. Larson, J. A., and W. J. Mitchell, "Transition matrices and some recursions based on tilings." Preprint manuscript, University of Florida, Department of Mathematics.

9. Sloane, N. J. A. and Simon Plouffe, The Encyclopedia of Integer Sequences. Academic Press, San Diego, CA, 1995.