\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf
The Fibonacci Number of a Grid Graph and \\
\vskip .1in
a New Class of Integer Sequences}
\vskip 1cm
\large
Reinhardt Euler \\
Facult\'e des Sciences \\
B.P. 809 \\
20 Avenue Le Gorgeu \\
29285 Brest Cedex \\
France\\
\href{mailto:Reinhardt.Euler@univ-brest.fr}{\tt Reinhardt.Euler@univ-brest.fr} \\
\end{center}
\vskip .2 in
\begin{abstract}
Given a grid graph $G$ of size $mn$, we study the number $i(m,n)$ of
independent sets in $G$, as well as $b(m,n)$, the number of maximal such
sets. It turns out that the initial cases $b(1,n)$ and $b(2,n)$ lead to
a Padovan and a Fibonacci sequence. To determine $b(m,n)$ for $m>2$ we
present an adaptation of the transfer matrix method, well known for
calculating $i(m,n)$. Finally, we apply our method to obtain explicit
values of $b(m,n)$ for $m=3,4,5$ and provide the corresponding
generating functions.
\end{abstract}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]
%\usepackage[dvips]{graphicx}
%\usepackage{amssymb}
%\newtheorem{theorem}{Theorem}
%\newtheorem{proposition}{Proposition}
%\begin{document}
%\maketitle
\section{Introduction}
Let $G_{m,n}=(V,E)$ be the {\em grid graph of size mn} with vertex set
$$V=\{(i,j):1 \le i \le m , 1 \le j \le n\}$$ and edge set $$E=\{\{(i,j),(i',j')\}:|i-i'|+|j-j'|=1\}.$$
A set $I \subseteq V$ is called an {\em independent set}
if no two of its elements are joined by an edge. We let ${\mathcal{I}}_{m,n}$ denote the
collection of independent sets in $G_{m,n}$ and $i(m,n)$ the total number of such sets. A
{\em maximal independent set B} in $G_{m,n}$ (maximal with respect to set-inclusion) is called a
{\em basis}. Again, ${\mathcal{B}}_{m,n}$ represents the collection
of bases in $G_{m,n}$ and $b(m,n)$ is the total number of such sets.
We are interested in calculating $i(m,n)$ and $b(m,n)$ for any $m,n \in \mathbb{N}$ together with the
associated generating functions. The study of $i(m,n)$
is closely related to the ``hard-square model'' as it is used in statistical physics. Of particular interest
is the so-called ``hard-square entropy constant'' defined to be $\lim_{m,n\rightarrow\infty} i(m,n)^{1/mn}$
(see Baxter et al. \cite{Baxter}). Applications also include tiling and, more recently, efficient coding
schemes in data storage (see Roth et al. \cite{Roth}). A basic
reference for work on $i(m,n)$ is Calkin and Wilf \cite{Calkin}. More recently,
Burstein et al. \cite{Burstein} have enumerated independent sets associated with several classes of (almost)
regular graphs and calculated the corresponding generating functions. \\
Whereas this study of $b(m,n)$ is new, distinguishing bases from independent sets is quite
common: just think of matroid theory or weighted independent set problems over graphs with
{\em non-negative} weights on the vertices. The question for the true value of
$\lim_{m,n\rightarrow\infty} b(m,n)^{1/mn}$, however, is open. We recently learned
(see Weigt and Hartmann \cite{Hartmann}) that maximal independent sets may be associated with meta-stable
liquid states of certain hard-core lattice gas models under compaction. \\
The main question we will answer in this paper is that of calculating $b(m,n)$ for
$m,n>2$ by a proper adaptation of the ``transfer matrix method'' as
designed by Engel \cite{Engel} for the calculation of $i(m,n)$.
The initial cases $b(1,n)$ and $b(2,n)$ turn out to produce a
Padovan and a Fibonacci sequence, respectively. Padovan sequences have little history; their study
goes back only to the beginning of the last century.
In the 1990's the architect Richard Padovan popularized these sequences and some closely related
concepts such as the ``plastic constant'', the Padovan-analogue to the golden number.
We refer the interested reader to Stewart's recreational article \cite{Stewart} for further details.
Since $i(m,n)$ is also called the {\em Fibonacci number} of $G_{m,n}$ we think that, this analogy
in mind, it would be convenient to call $b(m,n)$ the {\em Padovan number} of $G_{m,n}$. \\
This paper is organised as follows: the next section is devoted to the Fibonacci number $i(m,n)$.
We review the transfer matrix method for the calculation of $i(m,n)$ and the results obtained for $m=1,2,3,4$.
Section 3 addresses the combinatorial structure of ${\mathcal{B}}_{1,n}$ and ${\mathcal{B}}_{2,n}$ as
well as their respective cardinalities. In section 4 we present the new method to calculate $b(m,n)$,
and in section 5 we apply our method to explicitly describe $b(m,n)$ for $m=3,4,5$. Whenever convenient,
we indicate the associated generating functions that we calculated using Maple.
We conclude with a discussion of open problems. \\
\section{The transfer matrix method for the calculation of $i(m,n)$}
Let us start with the notion of ``orthogonality''. The {\em j-th column $G^{j}=(V^{j},E^{j})$} of $G_{m,n}$
is the subgraph induced by the vertex set
$\{(1,j),(2,j),\ldots,(m,j)\}$ with ${\mathcal{I}}^{j}$ denoting the associated collection of independent
sets. If now, for $j_{1}, j_{2} \in \{1,\ldots,n\}$, $I=\{(i_{1},j_{1}),\ldots,(i_{p},j_{1})\}$ and
$K=\{(k_{1},j_{2}),\ldots,(k_{q},j_{2})\}$ are members of ${\mathcal{I}}^{j_{1}}$ and ${\mathcal{I}}^{j_{2}}$,
respectively, we say that {\em I is orthogonal to K, $I \perp K$},
whenever $\{i_{1},\ldots,i_{p}\} \cap \{k_{1},\ldots,k_{q}\} = \O$. Moreover, for any $I \in {\mathcal{I}}^{j}$
we define the set {\em $l(I)=\{(i_{1},1),\ldots,(i_{p},1)\}$}, which again is a member of ${\mathcal{I}}^{1}$.
For any $k \in\{1,\ldots,n\}$, we will also have to count the number of independent sets in $G_{m,k}$,
whose intersection with $V^{k}$ equals a given set $I$, a number that we represent by $i(m,k,I)$.
The basic idea of the {\em transfer matrix method} (due to Engel \cite{Engel}, see also Stanley \cite{Stanley})
is to start with the values $i(m,1,I)=1$ for $I \in {\mathcal{I}}^{1}$, and to calculate, for $k=1,2,\ldots,n-1$, \\
\begin{equation}\label{1star}
i(m,k+1,J) = \sum_{I \in {\mathcal{I}}^{k}\, \mbox{and}\, I \perp J} i(m,k,I) \mbox{ }
\forall \mbox{ } J \in {\mathcal{I}}^{k+1} , \\
\end{equation}
\noindent in order to finally obtain
\begin{equation}\label{2star}
i(m,n) = \sum_{I \in {\mathcal{I}}^{n}} i(m,n,I) .
\end{equation}
Equations (\ref{1star}) and (\ref{2star}) can be formulated as matrix-vector products by introducing the following matrix
$T \in \{0,1\}^{F_{m+2} \times F_{m+2}}$:
\[
\forall \mbox{ } J,I \in {\mathcal{I}}^{1} \mbox{ } {\rm set} \mbox{ } T_{JI} = 1 \mbox{ } {\rm iff} \mbox{ } J \perp I .
\]
Clearly, for $k=1,\ldots,n-1,$
$$i(m,k+1,J)=\sum_{I \in {\mathcal{I}}^{k}} T_{JI} \cdot i(m,k,I) \mbox{ } \forall \mbox{ }
J \in {\mathcal{I}}^{k+1}$$
\noindent and at the end $i(m,n)$ = {\boldmath $1$}$T^{n-1}${\boldmath $1$}. \\
What really happens with this method is the following: at any stage $k$, ${\mathcal{I}}_{m,k}$ is partitioned
into a fixed number of $F_{m+2}$ classes, each of which is represented by a unique independent set in $G^{k}$.
During the following stages only the size of the classes is increasing, and a simple summation at the end yields
$i(m,n)$. One may think of proceeding the same way to calculate $b(m,n)$. However, as the example with $m=n=3$ shows,
not only do we lose the integrality of the transfer matrix. After a few steps we get fractional values supposed
to represent the cardinalities of the classes. What we really need is to refine our partition,
and this will be the subject of section 4. \\
What are the results we can obtain for small values of $m$? It is well known that $i(1,n)$ equals $F_{n+2}$,
the $(n+2)$nd Fibonacci number. Other recurrence formulas are available for $m=2,3,4$ (see Sloane \cite{Sloane}).
In the following we just resume the related sequences together with their generating functions:
\[
( i(1,n) )_{n \in \mathbb{N}} = ( 2, 3, 5, 8, 13, 21, 34, 55, \ldots )
\]
\noindent with
\[
\sum_{n \geq 1} i(1,n)x^n = \frac{2x+x^2}{1-x-x^2} \mbox{ };
\]
\[
( i(2,n) )_{n \in \mathbb{N}} = ( 3, 7, 17, 41, 99, 239, 577, 1393, \ldots )
\]
\noindent with
\[
\sum_{n \geq 1} i(2,n)x^n = \frac{3x+x^2}{1-2x-x^2} \mbox{ };
\]
\[
( i(3,n) )_{n \in \mathbb{N}} = ( 5, 17, 63, 227, 827, 2999, 10897, 39561, \ldots )
\]
\noindent with
\[
\sum_{n \geq 1} i(3,n)x^n = \frac{5x+7x^2-x^3-x^4}{1-2x-6x^2+x^4} \mbox{ };
\]
\noindent and finally
\[
( i(4,n) )_{n \in \mathbb{N}} = ( 8, 41, 227, 1234, 6743, 36787, 200798, 1095851, \ldots )
\]
\noindent with
\[
\sum_{n \geq 1} i(4,n)x^n = \frac{8x+9x^2-9x^3-3x^4+x^5}{1-4x-9x^2+5x^3+4x^4-x^5} \mbox{ }. \\
\]
If we work ``backwards'', i.e., from column $n$ to column 1 of $G_{m,n}$, we are able to express $i(m,n)$
by a general formula, which for its ``sum of products-form'' might be interesting in its own.
For this and any $I \in {\mathcal{I}}^{1}$, we denote with $s(m,I)$ the number of independent sets
in ${\mathcal{I}}^{1}$, that are orthogonal to $I$. Using the fact that $i(m,1) = F_{m+2}$ and assuming
that $I=\{i_{1},\ldots,i_{p}\}$ with $i_{1}5$ to obtain the following result.
\begin{theorem}
We have \\
\noindent (i) $i(m,1) = F_{m+2}$, (ii) $i(m,2) = \sum_{I \in {\mathcal{I}}^{1}} s(m,I)$, (iii) $i(m,3) = \sum_{I \in {\mathcal{I}}^{1}} (s(m,I))^2$, \\
\noindent (iv) $i(m,4) = \sum_{I \in {\mathcal{I}}^{1}} s(m,I)
\left(\sum_{J \in {\mathcal{I}}^{1} \,\mbox{and}\, J \perp I} s(m,J)\right)$, \\
\noindent (v) $i(m,5) = \sum_{I,J \in {\mathcal{I}}^{1}} s(m,I) s(m,I \cup J) s(m,J)$. \\
\noindent More generally, for $p\geq 3$, \\
\noindent (vi) $i(m,2p) = \sum_{I_{1},\ldots,I_{p} \in {\mathcal{I}}^{1}}
s(m,I_{1}) s(m,I_{1} \cup I_{2}) \cdots s(m,I_{p-2} \cup I_{p-1}) \left(\sum_{J \in {\mathcal{I}}^{1} \,\mbox{and}\,
J \perp I_{p-1}} s(m,J)\right)$, \\
\noindent (vii) $i(m,2p+1) = \sum_{I_{1},\ldots,I_{p} \in {\mathcal{I}}^{1}} s(m,I_{1}) s(m,I_{1} \cup I_{2})
\cdots s(m,I_{p-1} \cup I_{p}) s(m,I_{p})$.
\end{theorem}
\section{${\mathcal{B}}_{1,n}$ and ${\mathcal{B}}_{2,n}$, their structure and cardinality}
Let $m=1$ and $G_{1,n}$ be the corresponding grid graph, a path of length $n$; also, let $B$ be a maximal independent set
in $G_{1,n}$ (an example is depicted in Figure \ref{Figure 1}). \\
\begin{figure}[h]
\begin{center}
\includegraphics[width=12.6cm,height=1.4cm]{basism=1.ps}
\end{center}
\caption{The basis $B=\{(1,1),(1,4),(1,6),\ldots,(1,n-2),(1,n)\}$ for $m=1$.}
\label{Figure 1}
\end{figure}
Obviously, $B$ cannot contain two consecutive vertices on this path, nor
can the complement of such a set contain three such vertices. How can we obtain $b(1,n+1)$?
We take a basis $B$ from ${\mathcal{B}}_{1,n+1}$ and consider the elements it can have in common with the
set $\{n-2,n-1,n,n+1\}$. There are four possibilities for this intersection: $\{n-2,n\}$,
$\{n-1,n+1\}$, $\{n\}$, and $\{n-2,n+1\}$. The first two possibilities lead to a total number of
$b(1,n-1)$, the second to $b(1,n-2)$ bases over $\{1,\ldots,n+1\}$, i.e.,
\begin{eqnarray}
& b(1,n+1)=b(1,n-1)+b(1,n-2) \mbox{ } {\rm for} \mbox{ } n \geq 3 \label{Padovan} \\
& ({\rm with} \mbox{ } b(1,1)=1, b(1,2)=b(1,3)=2) . \nonumber
\end{eqnarray}
But (\ref{Padovan}) is nothing but the definition of a Padovan sequence (see Stewart \cite{Stewart}), whose explicit form is
\[
( b(1,n) )_{n \in \mathbb{N}} = ( 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, \ldots ) \mbox{ }, \\
\]
\noindent and whose generating function is given by
\[
\sum_{n \geq 1} b(1,n)x^n = \frac{x+2x^2+x^3}{1-x^2-x^3} \mbox{ }.
\]
Now let us turn to $m=2$ and consider a basis $B\in {\mathcal{B}}_{2,n}$ (see Figure \ref{Figure 2} for
an example). \\
\begin{figure}[htb]
\begin{center}
\includegraphics[width=12.6cm,height=3.2cm]{basism=2.ps}
\end{center}
\caption{A basis for $m=2$.}
\label{Figure 2}
\end{figure}
Either $(1,n) \in B$ or $(2,n) \in B$, in which case we can augment $B$ by the vertex $(2,n+1)$ or $(1,n+1)$,
respectively, to obtain $b(2,n)$ many bases within ${\mathcal{B}}_{2,n+1}$. Moreover, if the vertices $(1,n)$
and $(2,n-1)$ are in $B$, $B \setminus \{(1,n)\} \cup \{(1,n+1)\}$ will be in ${\mathcal{B}}_{2,n+1}$, and the same
holds for $B \setminus \{(2,n)\} \cup \{(2,n+1)\}$ in case that $(2,n)$ and $(1,n-1)$ are elements of $B$. We hereby
obtain the remaining $b(2,n-1)$ many bases of ${\mathcal{B}}_{2,n+1}$ so that altogether
\begin{eqnarray}
& b(2,n+1)=b(2,n)+b(2,n-1) \mbox{ } {\rm for} \mbox{ } n \geq 2 \label{Fibonacci} \\
& ({\rm with} \mbox{ } b(2,1)=b(2,2)=2) , \nonumber
\end{eqnarray}
\noindent or more explicitly,
\[
( b(2,n) )_{n \in \mathbb{N}} = ( 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, \ldots ) \mbox{ }, \\
\]
\vspace{0.2cm}
\noindent which is nothing but a Fibonacci sequence with generating function \\
\[
\sum_{n \geq 1} b(2,n)x^n = \frac{2x}{1-x-x^2} \mbox{ }. \\
\]
\section{${\mathcal{B}}_{3,n}$ and the general case}
To calculate $b(m,n)$ for $m,n>2$ we maintain the basic ideas underlying the transfer matrix method for
the determination of $i(m,n)$:
\begin{enumerate}
\item Creation of a partition of ${\mathcal{B}}_{m,n}$ that is valid at any stage.
\item Construction of a transfer matrix $T$ reflecting the contribution of a class at stage $k$ to any
other one at stage $k+1$.
\item Determination of $b(m,n)$ by means of $T$ and the cardinality of the classes.
\end{enumerate}
To create our partition it will be convenient to analyse the bases with respect to their
structure {\em within the last two columns}. (Recall that in the independent set case
${\mathcal{I}}_{m,n}$ had been separated into $F_{m+2}$ many classes whose elements had an
identical structure within the {\em last} column). \
We first need to generate ${\mathcal{B}}_{m,3}$ from ${\mathcal{B}}_{m,2}$, for which the
following, general result will be useful:
\begin{theorem}
Given ${\mathcal{B}}_{m,n}$ and a set of vertices $S = \{(s_{1},n),\ldots,(s_{p},n)\} \subseteq V^{n}$ let
$r(S)$ denote the set $\{(s_{1},n+1),\ldots,(s_{p},n+1)\}$.
Then ${\mathcal{B}}_{m,n+1}$ is the collection of all maximal sets
within $\{B^{'}: B^{'} = B \setminus I \cup r(I), for \mbox{ } B \in {\mathcal{B}}_{m,n} \mbox{ }
and \mbox{ } I \in {\mathcal{I}}^{n}\}$.
\end{theorem}
Proof: Let $B \in {\mathcal{B}}_{m,n}$ and $C = V\setminus B$ its complement with respect to $V$.
Then $C$ is a {\em minimal cover} of $E$, i.e., $C$ contains at least one element from all the edges
and $C$ is minimal with respect to this property. We let ${\mathcal{C}}_{m,n}$ denote the
collection of all these covers. Now consider the set of edges $E^{+}$ that we add to $G_{m,n}$
to obtain $G_{m,n+1}$. Obviously,
\[
E^{+} = \{ \{ (i,n),(i,n+1) \} : i=1,\ldots,m \} \cup \{ \{ (i,n+1),(i+1,n+1) \} : i=1,\ldots,m-1 \} .
\]
It is easy to verify that the collection ${\mathcal{C}}^{+}$ of minimal covers of $E^{+}$ is the
following:
\[
{\mathcal{C}}^{+} = \{ C = I \cup r(\bar I) : I \in {\mathcal{I}}^{n}, \bar I = V^{n} \setminus I \} .
\]
By minimality, such a cover $C$ cannot contain two consecutive vertices $(i,n),(i+1,n) \in V^{n}$
with $i \in \{1,\ldots,m-1\}$, and any edge $\{(i,n),(i,n+1)\}$ with $i \in\{1,\ldots,m\}$ not covered by $(i,n)$ has to be
covered by $(i,n+1)$, these latter vertices covering at the same time all edges $\{(i,n+1),(i+1,n+1)\}$ with
$i \in \{1,\ldots,m-1\}$.
Now to obtain the collection ${\mathcal{C}}_{m,n+1}$ of minimal covers of the edges of $G_{m,n+1}$
we simply have to form the sets $C\cup C^{'}$ for any $C \in {\mathcal{C}}_{m,n}, C^{'} \in
{\mathcal{C}}^{+}$ and to retain the minimal ones. By complementation we get ${\mathcal{B}}_{m,n+1}$. \\
It is clear that generating ${\mathcal{B}}_{m,n+1}$ this way will produce a large number of non-minimal
covers. For $n=2$ a thorough analysis of the bases in ${\mathcal{B}}_{m,2}$, however,
will allow us to keep this effort at a minimum level. \\
What is the structure of a basis $B \in {\mathcal{B}}_{m,2}$? For an answer we consider two
elements of $B$ that are consecutive within the first column, i.e., which can be at distance 2, 3, 4, respectively,
together with the position of the first or last element of $B$ in that column (Figure \ref{Figure 3} illustrates the
four cases): \\
\begin{figure}[htb]
\begin{center}
\includegraphics[width=15.8cm,height=6cm]{substructures.ps}
\end{center}
\caption{Substructures of a basis $B \in {\mathcal{B}}_{m,2}.$}
\label{Figure 3}
\end{figure}
\begin{description}
\item[Case i)] $(s,1)$ and $(s+2,1)$ are in $B$ for $s \in \{1,\ldots,m-2\}$: then, by maximality, $(s+1,2)$ has to be
in $B$, too.
\item[Case ii)] $(s,1)$ and $(s+3,1)$ are in $B$: but then either $(s+1,2)$ or $(s+2,2)$ must be in $B$.
\item[Case iii)] $(s,1)$ and $(s+4,1)$ are in $B$: then $(s+2,2)$ has to be in $B$.
\item[Case iv)] If $(s,1) \in B$ for $s=2$ or $m-1$ (or if $(s,1) \in B$ for $s=3$ or $s=m-2$, and $(1,1)$ or $(m,1)
\notin B$, respectively), then $(1,2)$ or $(m,2)$, respectively, has to be in $B$.
\end{description}
Case i) gives rise to the definition of an {\em alternating path AP} as induced by a maximal alternating
sequence in column 1: $$AP=\{(s,1),(s+1,1),\ldots,(s+2t-1,1),(s+2t,1)\}$$
with $$\{(s,1),(s+2,1),\ldots,(s+2t-2,1),(s+2t,1)\} \subseteq B.$$ \\
In such a case, the vertices $(s+1,2),(s+3,2),\ldots,(s+2t-1,2)$ have to be in $B$, too. \\
We now come to the proper generation of ${\mathcal{B}}_{m,3}$. Again, let $B$ be a basis in ${\mathcal{B}}_{m,2}$.
It is our aim to describe all independent sets $I \in {\mathcal{I}}^{2}$ for which $B^{'}=B \setminus I \cup r(I)$
(see Theorem 2) is a member of ${\mathcal{B}}_{m,3}$. To this end we start with $I:= \O$ and
check {\it column 2} of $B$ from top to bottom with respect to the substructures studied above within column 1:
whenever we find an alternating path $AP$ we modify $I$ according to the following rule:
\begin{description}
\item[Rule i)] Reduce $AP \cap B$ to those vertices $(v,2)$, for which $v=1$ or $v=m$, or for which both $(v-1,1)$ and $(v+1,1)$
are contained in $B$; choose among the remaining ones an arbitrary set $BL=\{(b_{1},2),\ldots,(b_{p},2)\}$ and
set $I := I \cup BL$. Within $AP \setminus B$, choose the set $$W=\{(s+1,2),\ldots,(b_{1}-3,2),(b_{1}+3,2),
\ldots,(b_{2}-3,2),(b_{2}+3,2),\ldots,(s+2t-1,2)\}$$ and set $I:=I \cup W$. Also, whenever the vertex $(s,2)$
or $(s+2t,2)$ (with $s>2$, $s+2t3$, hereby producing the sequence \\
\[
( b(3,n) )_{n \in \mathbb{N}} = ( 2, 4, 10, 18, 38, 78, 156, 320, 654, 1326, \ldots ) \mbox{ } ,
\]
\bigskip
whose generating function is \\
\[
\sum_{n \geq 1} b(3,n)x^n = \frac{2x+2x^2+4x^3-2x^4-2x^6}{1-x-x^2-3x^3+x^4+x^5} \mbox{ }. \\
\]
\vspace{1.6cm}
For $m=4$ the partition of ${\mathcal{B}}_{4,n}$ is represented by the following graphs: \\
\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm,height=3.6cm]{m=4graphs.ps}
\end{center}
\caption{Representing graphs for $m=4$.}
\label{Figure 6}
\end{figure}
As above, we can merge classes 6 and 7 to obtain the transfer matrix: \\
\[
T(4) =
\left[
\begin{array}{cccccc}
1 & 1 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 0 & 0\\
1 & 1 & 0 & 0 & 0 & 1\\
1 & 0 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 2 & 0 & 0
\end{array}
\right]
\]
together with the associated class cardinalities: \\
\begin{center}
\begin{tabular}{|c|c|r|r|r|r|r|r|r|}
\hline
classes & n=3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
1 & 2 & 8 & 20 & 50 & 128 & 324 & 820 & 2078\\
2 & 2 & 6 & 12 & 32 & 82 & 204 & 520 & 1316\\
3 & 2 & 4 & 10 & 26 & 64 & 164 & 414 & 1048\\
4 & 4 & 10 & 26 & 64 & 164 & 414 & 1048 & 2656\\
5 & 2 & 2 & 8 & 20 & 50 & 128 & 324 & 820\\
6 & 6 & 12 & 32 & 82 & 204 & 520 & 1316 & 3330\\
\hline
\end{tabular}
\end{center}
We obtain the sequence: \\
\[
( b(4,n) )_{n \in \mathbb{N}} = ( 3, 6, 18, 42, 108, 274, 692, 1754, 4442, 11248, \ldots ) \mbox{ },
\]
\bigskip
whose generating function is \\
\[
\sum_{n \geq 1} b(4,n)x^n = \frac{3x+3x^2+3x^3-3x^4-3x^5-2x^6+x^7}{1-x-3x^2-3x^3+x^4+2x^5+x^6} \mbox{ }. \\
\]
\vspace{2cm}
For $m=5$, finally, we come up with 17 representing graphs: \\
\bigskip
\begin{figure}[h]
\begin{center}
\includegraphics[width=15cm,height=7.2cm]{m=5graphs.ps}
\end{center}
\caption{Representing graphs for $m=5$.}
\label{Figure 7}
\end{figure}
\bigskip
We can merge classes 6 and 11, 9 and 15, 14 and 16 to obtain a $14 \times 14$ transfer matrix: \\
\[
T(5) =
\left[
\begin{array}{cccccccccccccc}
0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0\\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 2 & 0 & 1 & 1 & 2 & 1 & 0 & 1 & 0 & 0 & 0\\
2 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2\\
1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0
\end{array}
\right]
\]
\bigskip
and the corresponding class cardinalities:
\bigskip
\begin{center}
\begin{tabular}{|c|c|r|r|r|r|r|r|r|}
\hline
classes & n=3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
1 & 1 & 8 & 21 & 61 & 218 & 677 & 2097 & 6814\\
2 & 1 & 1 & 8 & 21 & 61 & 218 & 677 & 2097\\
3 & 2 & 6 & 22 & 66 & 206 & 676 & 2124 & 6692\\
4 & 1 & 4 & 15 & 51 & 148 & 485 & 1571 & 4898\\
5 & 4 & 14 & 40 & 134 & 414 & 1340 & 4200 & 13426\\
6 & 6 & 22 & 66 & 206 & 676 & 2124 & 6692 & 21476\\
7 & 4 & 10 & 40 & 126 & 386 & 1244 & 4012 & 12548\\
8 & 1 & 4 & 7 & 29 & 82 & 267 & 841 & 2708\\
9 & 4 & 10 & 28 & 102 & 324 & 988 & 3226 & 10242\\
10 & 2 & 4 & 22 & 64 & 188 & 642 & 2030 & 6318\\
11 & 4 & 8 & 28 & 82 & 278 & 832 & 2722 & 8588\\
12 & 4 & 7 & 29 & 82 & 267 & 841 & 2708 & 8491\\
13 & 2 & 3 & 11 & 36 & 123 & 357 & 1176 & 3765\\
14 & 2 & 7 & 21 & 72 & 209 & 691 & 2194 & 6929\\
\hline
\end{tabular}
\end{center}
\noindent which produce the sequence
\[
( b(5,n) )_{n \in \mathbb{N}} = ( 4, 10, 38, 108, 358, 1132, 3580, 11382, 36270, 114992, \ldots ) \mbox{ }, \\
\]
\noindent with generating function
\[
\sum_{n \geq 1} b(5,n)x^n =
\]
\[
\frac{4x+6x^2+12x^3-10x^4-18x^5+2x^6-20x^7+20x^8-50x^9+38x^{10}-18x^{11}+2x^{12}+6x^{13}+2x^{14}}
{1-x-4x^2-10x^3-4x^4+20x^5-x^6+2x^7-2x^8+16x^9-4x^{10}-x^{13}} \mbox{ }.
\]
\bigskip
We may want to compare this sequence with the corresponding one for the independent set case
(taken from Sloane \cite{Sloane}):
\[
( i(5,n) )_{n \in \mathbb{N}} = ( 13, 99, 827, 6743, 55447, 454385, 3729091, 30584687, 250916131,
2058249165, \ldots ) . \\
\]
The conclusion with respect to their growth is immediate.
\section{Conclusion}
In this paper we have introduced a new class of integer sequences over grid graphs generalizing both Padovan and
Fibonacci sequences, but still maintaining the essential property of independence. Counting the bases of a grid graph
(or other graph families along the same line) and analysing their structure should therefore still be attractive for the
applications mentioned in the introduction: tiling (our bases may have a very regular structure),
efficient coding schemes (when closely related to the hard-square model) and
statistical physics (in particular, the question of the true value of $\lim_{m,n\rightarrow\infty} b(m,n)^{1/mn}$).
\section{Acknowledgments}
We are grateful to the referee for many valuable suggestions.
\begin{thebibliography}{9}
\bibitem[1]{Baxter}
R. J. Baxter, I. G. Enting and S. K. Tsang, Hard square lattice gas, {\it J. Statist. Phys.} {\bf 22} (1980), 465--489.
\bibitem[2]{Burstein}
A. Burstein, S. Kitaev and T. Mansour,
Independent sets in certain classes of (almost) regular graphs,
{\it preprint}, University of Kentucky, Lexington, 2004.
\bibitem[3]{Calkin}
N. Calkin and H. S. Wilf, The number of independent sets in a grid graph, {\it SIAM J. Discrete Math.} {\bf 11} (1997), 54--60.
\bibitem[4]{Engel}
K. Engel, On the Fibonacci number of an $m \times n$ lattice, {\it Fibonacci Quart.} {\bf 28} (1990), 72--78.
\bibitem[5]{Roth}
R. M. Roth, P. H. Siegel and J. K. Wolf, Efficient coding schemes for the hard-square model,
{\it IEEE Trans. Inform. Theory} {\bf 47} (2001), 1166--1176.
\bibitem[6]{Sloane}
N. J. A. Sloane, The on-line encyclopedia of integer sequences,
published electronically at
\href{http://www.research.att.com/\sim njas/sequences/}{http://www.research.att.com/$\sim$njas/sequences/}
\bibitem[7]{Stanley}
R. P. Stanley, {\it Enumerative Combinatorics}, Vol.1, Cambridge University Press, 1997.
\bibitem[8]{Stewart}
I. Stewart, Tales of a neglected number, {\it Sci. Amer.} {\bf 274} (1996), 102--103.
\bibitem[9]{Hartmann}
M. Weigt and A. K. Hartmann, Glassy behavior induced by geometrical frustration in a hard-core lattice gas model,
{\it Europhys. Lett.} {\bf 62} (2003), 533.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 11B39; Secondary 11B83, 05A15, 05C69.
\noindent \emph{Keywords:}
Fibonacci number, Padovan number, transfer matrix method, independent set,
grid graph. \\
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000045}
\seqnum{A000931}
\seqnum{A001333}
\seqnum{A051736}
\seqnum{A051737} and
\seqnum{A089936}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received October 7 2004;
revised versions received February 7 2005;
April 12 2005.
Published in {\it Journal of Integer Sequences},
May 17 2005.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in
\end{document}