INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A10

A CONNECTION BETWEEN ORDINARY PARTITIONS AND TILINGS WITH DOMINOES AND SQUARES

Louis W. Kolitsch

Department of Mathematics and Statistics University of Tennessee at Martin Martin, TN 38237, United States

                             lkolitsc@utm.edu

Received: 5/5/06, Revised: 8/21/06, Accepted: 2/8/07, Published: 2/15/07

Abstract

In this paper a way of representing an ordinary partition as a tiling with dominoes and squares is introduced. The generating functions associated with such tilings is developed and explained analytically and combinatorially.

1. Introduction

The results in this paper were inspired by a talk given by Arthur Benjamin at the Southeastern Section meeting of the MAA in 2004 and based on his new book with Jennifer Quinn [2]. At this meeting Benjamin discussed tilings of a 1 × n rectangle with 1 × 1 squares and 1 × 2 dominoes. The total number of such tilings of a 1 × n rectangle is the nth Fibonacci number and these tilings can be used to explain numerous identities involving the Fibonacci numbers. For n < 5 the values of p(n), the number of partitions of n, match the values of the Fibonacci sequence. The natural question that arises is “Can the partitions of n be explained in terms of tilings using squares and dominoes?.” The answer to this question is “yes” as the first theorem below explains.

2. The Main Theorem

Before we state the first theorem, we introduce some notation. In a tiling, we will number the dominoes from left to right as d_{1}, d_{2}, ..., d_{m}. We will let s_{0} be the number of squares preceding d_{1}; s_{i} for 1 ≤ i < m will be the numbers of squares between d_{i} and d_{i+1}; and s_{m} will be the number of squares succeeding d_{m}.

Theorem 1 The number of partitions of n is the number of tilings of a 1×n rectangle where the numbers of squares following successive dominoes form a nondecreasing sequence. That is, s_{1} ≤ s_{2} ≤ ... ≤ s_{m}.

Theorem 1 follows by observing that (1) a tiling of the type described can be converted into the partition of n consisting of s_{0} ones and the parts 2 + s_{i} for 1 ≤ i ≤ m, and (2) a partition n can be converted into a tiling of the type described by making the ones initial squares and converting each part k bigger than one into a domino followed by k − 2 squares.

3. Some Other Results

Unlike the Fibonacci sequence, which has a simple recursion formula, F_{n} = F_{n−1} + F_{n−2}, the recursion formula for the partition function is given by Euler’s Pentagonal Number Theorem, p(n) = p(n−1)+p(n−2)−p(n−5)−p(n−7)+⋯ = ∑_{k=1}^{∞}(−1)^{k+1}(p(n− \frac{3k^{2}−k}{2})+p(n− \frac{3k^{2}+k}{2})). For n > 5, p(n − 1) + p(n − 2) overestimates p(n). The next result can be used to explain this overestimate. We present an analytical and a combinatorial proof of this theorem.

Theorem 2 The following holds: \frac{1}{(q;q)_{∞}} = 1 + \frac{q+q^{2}}{(q;q)_{∞}} − ∑_{i=2}^{∞} \frac{q^{2i+1}}{(1−q)(q^{i};q)_{∞}}.

Analytically, this theorem follows by setting x = 1 in the equation for s(x, q) in identity 10 on page 29 in [1] and then dividing by (q; q)_{∞}. Combinatorially, we can create a tiling representation for a partition of n by placing an extra square to the left of a tiling representation for a partition of n − 1. This will create all partitions of n which contain a one. When we place a domino to the left of a tiling representation for a partition of n − 2 we will create a tiling representation of a partition of n in which the smallest part is at least two unless the partition for n − 2 contains m ≥ 1 ones and a part greater than 1 and less than m + 2. The generating function for these exceptions is given by ∑_{m=1}^{∞} q^{2+m} ∑_{k=2}^{m+1} \frac{q^{k}}{(q^{k};q)_{∞}}, which is equal to the sum being subtracted on the left side of the equation in Theorem 2.

Note that ∑_{i=2}^{∞} \frac{q^{2i+1}}{(1−q)(q^{i};q)_{∞}} enumerates the number of ways of expressing n as x_{1} + x_{2} + ⋯ + x_{r}, where r ≥ 1, x_{i} ≥ 2 for all i, and x_{1} > x_{2} ≤ x_{3} ≤ ⋯ ≤ x_{r}. In other words, we almost have a partition of n into parts greater than 1, since only the first part is out of order.

By observing that \frac{q^{2k}}{(1−q)(q;q)_{k}} is the generating function for partition tilings containing k dominoes we can give a tiling interpretation of the following theorem due to Euler.

Theorem 3 The following holds: \frac{1}{1−q} ∑_{k=0}^{∞} \frac{q^{2k}}{(q;q)_{k}} = ∑_{n=0}^{∞} p(n)q^{n}.

When k = 0 and there are no dominoes, the partition consists of only ones, with generating function \frac{1}{1−q}. For k > 0, to see that the generating function for partition tilings with k

dominoes is \frac{q^{2k}}{(1−q)(q;q)_{k}}, we look at the Ferrers’ graph for a partition containing k parts greater than one, which gives us k dominoes by using the first two nodes of each part greater than one to form the k dominoes; q^{2k}. To the right of the dominoes we have columns containing k or fewer nodes; \frac{1}{(q;q)_{k}}, and below the dominoes we have the parts that are ones; \frac{1}{1−q}.

References

1. Andrews, George, The Theory of Partitions, in “Encyclopedia of Mathematics and Its Applications,” Vol. 2, Addison-Wesley, Reading, MA, 1976.

2. Benjamin, Authur and Quinn, Jennifer, Proofs that Really Count, The Mathematical Association of America, 2003.