% ----------------------------------------------------------------
% AMS-LaTeX Paper ************************************************
% **** -----------------------------------------------------------
\documentclass[12pt]{article}
\textwidth=6.5in \textheight=9.0in \topmargin=-20pt
\evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt
\parskip=10pt
\font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9


% ----------------------------------------------------------------

\makeatletter %% this should really go into a style file!

\renewcommand\section{\@startsection {section}{1}{\z@}%
                                 % {-3.5ex \@plus -1ex \@minus -.2ex}%
        % here is your vskip of 30pt:
                                   {-30pt  \@plus -1ex \@minus -.2ex}%
                                   {2.3ex \@plus.2ex}%
                                   {\normalfont\normalsize\bfseries}}

\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
                                     {-3.25ex\@plus -1ex \@minus -.2ex}%
                                     {1.5ex \@plus .2ex}%
                                     {\normalfont\normalsize\bfseries}}
        % add a point after section numbers:

\renewcommand{\@seccntformat}[1]{\csname the#1\endcsname. } %\quad}

\makeatother


\begin{document}
\vspace*{-40pt}
\centerline{\smalltt INTEGERS: \smallrm
ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7
(2007), \#A10}
\begin{center}
{\bf A CONNECTION BETWEEN ORDINARY PARTITIONS AND TILINGS WITH
DOMINOES AND SQUARES} \vskip 10pt
{\bf Louis W. Kolitsch}\\
{\smallit Department of Mathematics and Statistics}\\ {\smallit
University of
Tennessee at Martin}\\ {\smallit Martin, TN 38237, United States}\\
{\tt lkolitsc@utm.edu}\\
\end{center}
\vskip 15pt \centerline{\smallit Received: 5/5/06,
Revised: 8/21/06, Accepted: 2/8/07,
Published: 2/15/07} \vskip 15pt


% ----------------------------------------------------------------
\centerline{\bf Abstract}

\noindent 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.

\pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm
ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 7
(2007), \#A10\hfill}

\thispagestyle{empty} \baselineskip=14pt 


% ----------------------------------------------------------------
\section*{\normalsize 1. Introduction}
\vspace*{-10pt}
 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 \times n$ rectangle with $1 \times 1$ squares and $1 \times 2$
dominoes.  The total number of such tilings of a $1 \times n$ rectangle is
the $n$th 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.

\vspace*{-10pt}
\section*{\normalsize 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 \leq 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$.

\noindent
{\bf Theorem 1} The number of partitions of n is the number of tilings of
a $1 \times n$ rectangle where the numbers of squares following successive
dominoes form a nondecreasing sequence.  That is, $s_1 \leq s_2 \leq
. . . \leq 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 \leq i \leq 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.

\vspace*{-10pt}
\section*{\normalsize 3. Some Other Results}
\vspace*{-10pt}
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) + \cdots = \sum_{k=1}^{\infty}
(-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.

\noindent
{\bf Theorem 2} The following holds:
$\frac{1}{(q; q)_{\infty}} = 1 + \frac{q+q^2}{(q; q)_\infty} -
\sum_{i=2}^{\infty} \frac{q^{2i+1}}{(1-q)(q^i; q)_{\infty}}$.

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)_{\infty}$.  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 \geq 1$ ones and a part greater than 1 and less
than $m+2$.  The generating function for these exceptions is given
by $\sum_{m=1}^{\infty} q^{2+m} \sum_{k=2}^{m+1}
\frac{q^k}{(q^k;q)_{\infty}}$, which is equal to the sum being
subtracted on the left side of the equation in Theorem 2.

Note that $\sum_{i=2}^{\infty}
\frac{q^{2i+1}}{(1-q)(q^i; q)_{\infty}}$ enumerates the number of ways
of expressing $n$ as $x_{1}+x_{2}+\cdots + x_{r}$, where $r \geq 1$,
$x_{i} \geq 2$ for all $i$, and $x_{1} > x_{2} \leq x_{3}
\leq \cdots \leq 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.

\noindent
{\bf Theorem 3}  The following holds:  $\frac{1}{1-q} \sum_{k=0}^{\infty}
\frac{q^{2k}}{(q;q)_k} = \sum_{n=0}^{\infty} 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}$.









% ----------------------------------------------------------------
\bibliographystyle{amsplain}
\bibliography{}

\noindent
{\bf References} \footnotesize \parindent=0pt

1.  Andrews, George, The Theory of Partitions, in ``Encyclopedia of
Mathematics and Its Applications," Vol.
\vskip -7pt \hskip 13pt 2, Addison-Wesley, Reading,
MA, 1976.

2.  Benjamin, Authur and Quinn, Jennifer, Proofs that Really Count,
The Mathematical Association of America, 2003.
\end{document}
% ----------------------------------------------------------------