\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{idn}[theorem]{Identity}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\rb}[1]{_{\rm #1}}
\newcommand{\ch}[2]{\begin{bmatrix}#1\\ #2\end{bmatrix}}
\newcommand{\tch}[2]{[\begin{smallmatrix}#1\\ #2\end{smallmatrix}]}
\newcommand{\chb}[2]{\left\langle\begin{matrix}#1\\#2\end{matrix}\right\rangle}
\newcommand{\tchb}[2]{\langle\begin{smallmatrix}#1\\#2\end{smallmatrix}\rangle}
\newcommand{\floor}[1]{\lfloor#1\rfloor}
\newcommand{\ceil}[1]{\lceil#1\rceil}
\begin{center}
\vskip 1cm{\LARGE\bf
New Combinatorial Interpretations of the \\
Fibonacci Numbers Squared, Golden \\
Rectangle Numbers, and Jacobsthal Numbers \\
\vskip .1in
Using Two Types of Tile
}
\vskip 1cm
\large
Kenneth Edwards and Michael A. Allen\footnote{Corresponding author.}\\
Physics Department\\
Faculty of Science\\
Mahidol University\\
Rama 6 Road\\
Bangkok 10400 \\
Thailand \\
\href{mailto:kenneth.edw@mahidol.ac.th}{\tt kenneth.edw@mahidol.ac.th} \\
\href{mailto:maa5652@gmail.com}{\tt maa5652@gmail.com} \\
\end{center}
\vskip .2 in
\begin{abstract}
We consider the tiling of an $n$-board (a board of size $n\times1$)
with squares of unit width and $(1,1)$-fence tiles. A $(1,1)$-fence
tile is composed of two unit-width square sub-tiles separated by a gap
of unit width. We show that the number of ways to tile an $n$-board
using unit-width squares and $(1,1)$-fence tiles is equal to a
Fibonacci number squared when $n$ is even and a golden rectangle
number (the product of two consecutive Fibonacci numbers) when $n$ is
odd. We also show that the number of tilings of boards using $n$ such
square and fence tiles is a Jacobsthal number. Using combinatorial
techniques we prove new
identities involving golden rectangle and Jacobsthal numbers. Two of
the identities involve entries in two Pascal-like triangles. One is a
known triangle (with alternating ones and zeros along one side) whose
$(n,k)$th entry is the number of tilings using $n$ tiles of which $k$
are fence tiles. There is a simple relation between this triangle and
the other which is the analogous triangle for tilings of an $n$-board.
These triangles are related to Riordan arrays and we give a general
procedure for finding which Riordan array(s) a triangle is related to.
The resulting combinatorial interpretation of the Riordan arrays
allows one to derive properties of them via combinatorial
proof.
\end{abstract}
\section{Introduction}
The $(n+1)$th Fibonacci number (\seqnum{A000045} in the
{\it On-Line Encyclopedia of Integer Sequences}), defined by
$F_{n+1}=\delta_{n,1}+F_n+F_{n-1}$, $F_{n<1}=0$, where $\delta_{i,j}$
is 1 if $i=j$ and zero otherwise, can be interpreted as the number of
ways to tile an $n$-board (a board of size $n\times1$ composed of
$1\times1$ cells) with $1\times1$ squares (henceforth referred to
simply as squares) and $2\times1$ dominoes \cite{BCCG96,BQ=03}. More
generally, the number of ways to tile an $n$-board with all the
$r\times1$ $r$-ominoes from $r=1$ up to $r=k$ is the $k$-step (or
$k$-generalized) Fibonacci number
$F^{(k)}_{n+1}=\delta_{n,1}+F^{(k)}_{n}+F^{(k)}_{n-1}+\cdots+F^{(k)}_{n-k+1}$,
with $F^{(k)}_{n<1}=0$ \cite{BQ=03}.
Edwards \cite{Edw08} showed that
it is possible to obtain a combinatorial interpretation of the
tribonacci numbers (the 3-step Fibonacci numbers, \seqnum{A000073}) as
the number of tilings of an $n$-board using just two types of tile,
namely, squares and $(\frac12,1)$-fence tiles. A $(w,g)$-fence tile
is composed of two sub-tiles (called \textit{posts}) of size
$w\times1$ separated by a gap of size $g\times1$. We presented a
bijection between the Fibonacci numbers squared (\seqnum{A007598}) and
the tilings of an $n$-board with half-squares (i.e., $\frac12\times1$
tiles always oriented so that the shorter side is horizontal) and
$(\frac12,\frac12)$-fence tiles \cite{EA19} and this was used to
formulate combinatorial proofs of various identities
\cite{EA19,EA20}. Using two types of tile allows one to generate a
Pascal-like triangle based on the tiling in a natural way
\cite{Edw08}, and one such triangle has been shown to be a
row-reversed Riordan array \cite{EA20}.
Here we show that the number of ways to tile an $n$-board using
square and $(1,1)$-fence tiles is a Fibonacci number squared if $n$ is
even and a golden rectangle number (the product of two successive
Fibonacci numbers, \seqnum{A001654}) if $n$ is odd.
We also consider
the number of ways to tile boards using a total of $n$ of these tiles and
refer to this as an \textit{$n$-tiling}. We show that enumerating
$n$-tilings yields the Jacobsthal numbers
$J_{n\geq0}=0,1,1,3,5,11,21,43,85,171,\ldots$ (\seqnum{A001045})
where the $n$th Jacobsthal number is defined via
\begin{equation}\label{e:Jn}
J_{n}=\delta_{n,1}+J_{n-1}+2J_{n-2}, \quad J_{n<1}=0.
\end{equation}
We use both types of tiling to formulate straightforward combinatorial
proofs of new identities involving the golden rectangle and Jacobsthal
numbers, two of which involve entries in Riordan arrays. These arrays
are shown to be related to two Pascal-like triangles (one for
$n$-tilings, the other for tilings of an $n$-board) whose entries are
the number of tilings with squares and $(1,1)$-fences which use a
given number of fences. This enables one to obtain straightforward
combinatorial proofs of a number of properties of the arrays.
We begin by showing how to determine which row-reversed Riordan array
corresponds to a given Pascal-like triangle derived from tiling with squares
and fences.
\section{Riordan arrays and tiling-derived Pascal-like triangles}
\label{s:riordan}
A $(p(x),q(x))$ Riordan array, where $p(x)=p_0+p_1x+p_2x^2+\cdots$ and
$q(x)=q_1x+q_2x^2+\cdots$, is an infinite lower triangular matrix whose
$(n,k)$th entry, which we will denote by $R(n,k)$, is given by
$R(n,k)=[x^n]p(x)\{q(x)\}^k$, where $[x^n]g(x)$ is the coefficient of
$x^n$ in the series for $g(x)$ \cite{SGWW91}. Notice that the entries
of the $k=0$ column are given by $R(n,0)=p_n$.
The entry $T(n,k)$ of a Pascal-like triangle $T$ associated with
tiling with squares and fences gives the number of tilings containing
$k$ fences where $n$ is either the length of the board or, when
considering $n$-tilings, the number of tiles. We have found that the
row-reversed triangle (or every other row of it) can coincide with a
Riordan array \cite{EA20}. The generating function of the leading
diagonal of $T$ is then the same as that of $p(x)$. To find $q$, we
first row reverse the recursion relation defining $T$. This is done by
replacing term $T(n-m,k-l)$ by $R(n-m,n-m-k+l)$ and then replacing
$n-k$ by $k$. We then substitute in the result
$R(n-a,k-b)=[x^{n-a}]pq^{k-b}=[x^n]x^apq^{k-b}$ and solve for $q$.
\begin{example}
Let $T(n,k)$ be the number of tilings of an $n$-board using $k$
$(\frac12,1)$-fences and $n-k$ squares (\seqnum{A157897}). Then
$T(n,k)=\delta_{n,0}\delta_{k,0}+T(n-1,k)+T(n-2,k-1)+T(n-3,k-3)$ \cite{Edw08}.
$T(n,n)$ is 1 if $n$ is a multiple of 3 and 0 otherwise. Hence
$p(x)=1+x^3+x^6+\cdots=1/(1-x^3)$. Row reversing the recursion
relation gives
$$R(n,k)=\delta_{n,0}\delta_{k,0}+R(n-1,k-1)+R(n-2,k-1)+R(n-3,k).$$
Substituting in the definition of $R(n,k)$ and dividing by $pq^{k-1}$
leaves $q=x+x^2+x^3q$, from which we get $q=x(1+x)/(1-x^3)$.
\end{example}
\section{Tiling boards with squares and fences}
When tiling a board with fences, it is helpful to first determine the
types of metatile, since any tiling of the board can be expressed as a
tiling using metatiles \cite{Edw08}. A \textit{metatile} is an
arrangement of tiles that exactly covers an integral number of
adjacent cells and cannot be split into smaller metatiles
\cite{Edw08,EA15}. When tiling with squares ($S$) and $(1,1)$-fence
tiles (henceforth referred to simply as fences or $F$), the simplest
metatile is the square. To tile adjacent cells by starting with a
single fence we must fill the gap with either a square or the post of
another fence. These generate what we will refer to as the
\textit{filled fence} ($FS$) and \textit{bifence} ($FF$) metatiles,
respectively (Fig.~\ref{f:metatiles}). The filled fence and
bifence have lengths of 3
and 4, respectively. A square which is not inside a filled fence
(and is therefore a metatile) is called a \textit{free square}.
\begin{figure}
\begin{center}
\includegraphics[width=4cm]{1+11metatiles}
\end{center}
\caption{An 8-board tiled with the three possible metatiles: a free
square (cell 1), a filled fence (cells 2--4), and a bifence (cells
5--8). The symbolic representation of this tiling is $SFSFF$.}
\label{f:metatiles}
\end{figure}
\begin{theorem}\label{T:An}
Let $A_n$ be the number of ways to tile an $n$-board using squares and
fences. Then
\begin{equation}
\label{e:An}
A_{n}=\delta_{n,0}+A_{n-1}+A_{n-3}+A_{n-4}, \quad A_{n<0}=0.
\end{equation}
\end{theorem}
\begin{proof}
We condition on the last metatile \cite{BHS03,EA15}. If the
last metatile is of length $l$ there will be $A_{n-l}$ ways to tile
the remaining $n-l$ cells. The result \eqref{e:An} follows from the
fact that there are three possible metatiles and these have lengths of
1, 3, and 4. If $n=l$ there is exactly one tiling (which corresponds to
that metatile filling the entire board) so we make $A_0=1$. There is no
way to tile an $n$-board if $n0$, $n>0$,
\[
f_nf_{n+1}=\sum_{r=0}^{p-1}C^{(r)}_n
+\sum_{j=p}^{n}\binom{j+p-1}{2p-1}f_{n-j}f_{n+1-j}.
\]
\end{idn}
\begin{proof}
How many tilings of a $(2n+1)$-board have at least $2p$ squares?
Answer~1: the total number of tilings minus the tilings
that contain less than $2p$ squares, i.e.,
$A_{2n+1}-\sum_{r=0}^{p-1}C^{(r)}_n$.
Answer~2: we condition on the location of the $2p$th square. If the
metatile containing this lies on the $2j$th cell, in the symbolic
representation, there are $2p-1$ $S$ and $j-p$ $F$ that precede the
$2p$th $S$ and hence $\binom{j+p-1}{2p-1}$ ways to arrange them. There
are $A_{2n+1-2j}$ ways to place the remaining tiles after the $2j$th
cell.
Summing over all possible $j$ and equating the result to
Answer~1 gives
\[
A_{2n+1}-\sum_{r=0}^{p-1}C^{(r)}_n=\sum_{j=p}^n\binom{j+p-1}{2p-1}A_{2(n-j)+1},
\]
and the identity follows from \eqref{e:A2n+1}.
\end{proof}
\section{Combinatorial proofs of new identities involving the
Jacobsthal numbers}
\label{s:jac}
\begin{idn}\label{I:sumkJ} For $n\ge0$,
\[
J_{n+1}=\ceil{\tfrac12(n+1)}+\sum_{j=1}^{n-1}jJ_{n-j}.
\]
\end{idn}
\begin{proof}
How many $n$-tilings have at least two squares?
Answer~1:
$B_n-\frac12(n+1)$ ($B_n-\frac12n-1$) when $n$ is odd (even) since the
possible tilings with one square when $n$ is odd (even) are one filled
fence (free square) placed among $\frac12(n-1)$ ($\frac12(n-2)$)
bifences and there are $\frac12(n+1)$ ($n/2$) such tilings, and the
only possible tiling with no squares is the all-bifence tiling which
only occurs when $n$ is even.
Answer~2: condition on the second
metatile containing an $S$. The symbolic representation of the tiling
up to and including this must end in an $S$. If this $S$ is the $j$th
tile, there are $j-1$ ways to order the symbols preceding it and thus
$(j-1)B_{n-j}$ $n$-tilings.
Summing over all possible $j$, equating to
Answer~1, and simplifying gives
\[
B_n-\ceil{\tfrac12(n+1)}=\sum_{j=2}^n(j-1)B_{n-j}.
\]
The identity is obtained on replacing $j$ by $j+1$ and using
Theorem~\ref{T:bijJ}.
\end{proof}
As before, we can generalize Identity~\ref{I:sumkJ}. We need the
following definition and lemma. Let $D^{(r)}_n$ be the number of
$n$-tilings that contain exactly $r$ squares. As the only tilings with
no squares are the all-bifence tilings, for $n>0$, $D^{(0)}_n$ is 1
(0) when $n$ is
even (odd). For convenience we make $D^{(0)}(0)=1$.
\begin{lemma}\label{L:Dq}
For $n\ge r>0$,
\begin{equation}\label{e:Dq}
D^{(r)}_n=D^{(r)}_{n-2}+\binom{n-1}{r-1}.
\end{equation}
\end{lemma}
\begin{proof}
The symbolic representation of a tiling must end in either $S$ or
$FF$. If $S$, we are free to place the remaining $n-1$ tiles (of which
$r-1$ are squares) in any order; this gives
$\binom{n-1}{r-1}$ possibilities. If $FF$, there are
$D^{(r)}_{n-2}$ ways to place the remaining tiles.
\end{proof}
As will be shown in Theorem~\ref{T:RnkB}, $D^{(r)}_n$ is the
$(1/(1-x^2),x/(1-x))$ Riordan array (\seqnum{A059260}).
\begin{idn}\label{I:sumbinJ} For $p>0$, $n>0$,
\[
J_{n+1}=\sum_{r=0}^{p-1}D^{(r)}_n
+\sum_{k=p}^{n}\binom{k-1}{p-1}J_{n+1-k}.
\]
\end{idn}
\begin{proof}
How many $n$-tilings have at least $p$ squares?
Answer~1: the total number of tilings minus the tilings
that contain less than $p$ squares, i.e.,
$B_n-\sum_{r=0}^{p-1}D^{(r)}_n$.
Answer~2: we condition on the location of the $p$th square. If
it is the $k$th tile, there are $\binom{k-1}{p-1}$ ways
to place the first $k$ tiles and
$B_{n-k}$ ways to place the remaining tiles.
Summing over all
possible $k$ and equating the result to Answer~1 gives
\[
B_n-\sum_{r=0}^{p-1}D^{(r)}_n=\sum_{k=p}^n\binom{k-1}{p-1}B_{n-k},
\]
and the identity follows from Theorem~\ref{T:bijJ}.
\end{proof}
\begin{idn}\label{I:sum2km5J} For $n>0$,
\[
J_{n+1}=n+J_{n-1}+\sum_{k=3}^n(2k-5)J_{n+1-k}.
\]
\end{idn}
\begin{proof}
For $n>0$, how many $n$-tilings have at least two fences?
Answer~1: $B_n-1-(n-2+1)$ since only the all-square tiling and
tilings with 1 filled fence among $n-2$ squares have less than two
fences.
Answer~2: condition on the location of the second fence. If it
is the $k$th tile ($k=3,\ldots,n-1$) and part of a filled fence or the
first tile in a bifence, the first fence is part of a filled fence
among $k-3$ squares and hence there are $2(k-2)B_{n-(k+1)}$ tilings
for these cases. If the second fence is the end of a bifence and is the
$k$th tile ($k=2,\ldots,n$), the tiles before the bifence are all
squares and hence there are $B_{n-k}$ tilings in this case.
Summing
over all possible $k$, changing $k$ to $k-1$ in the first sum, and
equating to Answer~1 gives
\[
B_n-n=2\sum_{k=4}^n(k-3)B_{n-k}+\sum_{k=2}^nB_{n-k}
=B_{n-2}+\sum_{k=3}^n(2k-5)B_{n-k}.
\]
The identity then follows from Theorem~\ref{T:bijJ}.
\end{proof}
Although perhaps not particularly novel, we include this final
identity involving Jacobsthal numbers as it connects them with the
Fibonacci numbers and is quick to prove.
\begin{idn}
For $n\ge0$,
\[
J_{n+1}=F_{n+1}+\sum_{j=2}^nJ_{j-1}F_{n+1-j}.
\]
\end{idn}
\begin{proof}
First note that the number of $n$-tilings with no bifences is given by
$S_n=\delta_{0,n}+S_{n-1}+S_{n-2}$ and hence $S_n=F_{n+1}$. How many
$n$-tilings have at least one bifence?
Answer~1: $B_n-S_n$.
Answer~2:
condition on the last bifence. When the second fence it contains is
the $j$th tile ($j=2,\ldots,n$) then the number of tilings is
$B_{j-2}S_{n-j}$.
Summing over all possible $j$ and equating this to
Answer~1 gives
\[
B_n-S_n=\sum_{j=2}^nB_{j-2}S_{n-j}.
\]
The identity follows from applying $S_n=F_{n+1}$ and Theorem~\ref{T:bijJ}.
\end{proof}
\section{A Pascal-like triangle giving the number of $n$-tilings using
$k$ fences}\label{s:chb}
We define $\tchb{n}{k}$ as the number of $n$-tilings which
contain exactly $k$ fences. We define $\tchb{0}{0}=1$ so that the result
\begin{equation}
\label{e:Bn=sum}
B_n=\sum_{k=0}^n\chb{n}{k}
\end{equation}
is valid for $n\geq0$. We also choose to make $\tchb{n}{k}=0$ when
$k<0$ or $n0$,
\[
\chb{2m-1}{2m-2}=\chb{2m}{2m-1}=m.
\]
\end{idn}
The following identity shows that the third diagonal of the triangle is \seqnum{A002620}.
\begin{idn} For $m>0$,
\[
\chb{2m}{2m-2}=m^2; \quad \chb{2m+1}{2m-1}=m(m+1).
\]
\end{idn}
\begin{proof}
When 2 out of $2m$ tiles are squares there must be either $m-1$
bifences and 2 free squares (totalling $m+1$ metatile positions) or
$m-2$ bifences and 2 filled fences (giving $m$ metatile
positions). There are $\binom{m+1}{2}$ places to put the squares in
the first case and $\binom{m}{2}$ ways to place the filled fences in
the second. The total number of tilings is thus
$\binom{m}{2}+\binom{m+1}{2}=m^2$. When 2 out of $2m+1$ tiles are
squares, there must be $m-1$ bifences, 1 filled fence, and 1 free
square, and thus $m+1$ metatile positions. There are therefore
$2\binom{m+1}{2}=m(m+1)$ ways to place the free square and filled
fence.
\end{proof}
The following two identities show that the third and fourth columns
of the triangle are
\seqnum{A000124} and \seqnum{A003600}, respectively.
\begin{idn}For $n\ge2$,
$\tchb{n}{2}=\binom{n-2}{2}+n-1$.
\end{idn}
\begin{idn}\label{I:chbn3} For $n\ge3$,
$\tchb{n}{3}=\binom{n-3}{3}+2\binom{n-2}{2}$.
\end{idn}
We now turn to obtaining a direct expression for an arbitrary entry in the
triangle.
If $b$, $f$, and $s$ are, respectively,
the numbers of bifences, filled fences, and
free squares in an $n$-tiling using $k$ fences then
it is easily seen that
\begin{subequations}
\label{e:nkbfsB}
\begin{align}
\label{e:nB}
n&=2b+2f+s, \\
k&=2b+f.
\label{e:kB}
\end{align}
\end{subequations}
\begin{idn}\label{I:gfB}
For $n\ge k\ge0$,
\begin{equation}
\chb{n}{k}=\begin{cases}
\displaystyle\sum_{b=b\rb{min}}^{b\rb{max}} \binom{n-k+b}{k-b}\binom{k-b}{b},
&b\rb{min}\leq b\rb{max};\\
0, & b\rb{min}>b\rb{max},
\end{cases}
\label{e:gfB}
\end{equation}
where $b\rb{min}=\max(0,\ceil{k-n/2})$ and
$b\rb{max}=\floor{k/2}$.
\end{idn}
\begin{proof}
For given values of $n$ and $k$ we sum the number of tilings for all
possible values of $b$. The maximum number of
bifences $b\rb{max}$
is obtained from \eqref{e:kB} when $f$ is 0 or 1 depending on
whether $k$ is even or odd, respectively. Eliminating $f$ from
\eqref{e:nkbfsB} gives
$b=\tfrac12(2k-n+s)$.
If $2k-n$ is negative, the minimum possible value of $b$ is
zero. Otherwise $b\rb{min}$ is obtained when $s$ is 0 or 1 when
$2k-n$ is even or odd, respectively.
From \eqref{e:nkbfsB} we have that the total number of metatiles,
$b+f+s=n-k+b$. The number of ways of tiling using $b$ bifences, $f$
filled fences, and $s$ free squares is the multinomial coefficient
$\binom{b+f+s}{b,\,f,\,s}$ which may be re-expressed as a product of
binomial coefficients written in terms of $b$, $n$, and $k$. There
will be no possible values of $b$ and therefore no tilings if
$b\rb{min}>b\rb{max}$.
\end{proof}
We can use the result to expand the Jacobsthal numbers as double sums
of products of two binomial coefficients.
\begin{corollary}
For $n\ge0$,
\begin{align*}
J_{n+1}&=\sum_{k=0}^n\sum_{b=\max(0,\ceil{k-n/2})}^{\floor{k/2}} \binom{n-k+b}{k-b}\binom{k-b}{b}.
\end{align*}
\end{corollary}
\begin{proof}
The result follows from \eqref{e:Bn=sum}, Theorem~\ref{T:bijJ}, and
Identity~\ref{I:gfB}.
\end{proof}
The next two identities show in what sense the
triangle is `Pascal-like'. Both have bijective proofs.
\begin{idn}\label{I:bin=sum}
For $n\ge k>0$,
\begin{equation}
\label{e:bin=sum}
\binom{n}{k}=\chb{n}{k}+\chb{n-1}{k-1}.
\end{equation}
\end{idn}
\begin{proof}
Interpret $\binom{n}{k}$ as the tilings of an $(n+k)$-board with $k$
dominoes ($D$) and $n-k$ squares ($S$). Proceeding from left to right
along the board, replace $DD$ by a bifence, $DS$ by a filled fence,
and then leave any of the remaining $S$ as they are. Except for the
case of a `left over' single $D$
at the right end of the board, this generates all
possible $n$-tilings using $k$ fences. If the $(n+k)$-board ends in an
isolated $D$, ignore it and hence obtain a $(n-1)$-tiling with $k-1$
fences. In both cases the scheme is reversible.
\end{proof}
\begin{idn}\label{I:rrB}
For $n>k>0$,
\begin{equation}
\label{e:rrB}
\chb{n}{k}=\chb{n-1}{k}+\chb{n-1}{k-1}.
\end{equation}
\end{idn}
\begin{proof}
An $n$-tiling such that $n>k$ must contain a free square or filled
fence. Construct a bijection between $n$-tilings using $k$ fences and
$(n-1)$-tilings using $k$ or $k-1$ fences as follows. In the
$n$-tiling find the final square. If it is free, remove it to obtain
an ($n-1$)-tiling with $k$ fences. If the square is part of a filled
fence, remove the fence to obtain an ($n-1$)-tiling with $k-1$ fences.
\end{proof}
We now turn to the connection between the triangle and a Riordan
array. We first need the following two identities.
\begin{idn}\label{I:triDq}
For $n\ge r\ge0$, $\tchb{n}{n-r}=D^{(r)}_n$.
\end{idn}
\begin{proof}
The result follows from the definition of $D^{(r)}_n$ since
$\tchb{n}{n-r}$ is also the number of $n$-tilings containing $r$
squares.
\end{proof}
\begin{idn}\label{I:rr2B}
For all $n,k\in\mathbb{Z}$,
\begin{equation}
\label{e:rr2B}
\chb{n}{k}=\delta_{n,0}\delta_{k,0}+\chb{n-1}{k}+\chb{n-2}{k-1}+\chb{n-2}{k-2}.
\end{equation}
\end{idn}
\begin{proof}
We count $\tchb{n}{k}$ by conditioning on the last metatile on the
board. If the metatile contains $m$ tiles of which $j$ are fences, for
the remaining tiles the number of $(n-m)$-tilings is
$\tchb{n-m}{k-j}$. Summing these for the three types of metatile gives
the result.
\end{proof}
\begin{theorem}\label{T:RnkB}
If $R(n,k)$ is the $(n,k)$th entry of the $(1/(1-x^2),x/(1-x))$
Riordan array then
\begin{equation}\label{e:Rnk}
\chb{n}{k}=R(n,n-k).
\end{equation}
\end{theorem}
\begin{proof}
We use the method explained in Section~\ref{s:riordan}. From
Identity~\ref{I:nn}, $p=1+x^2+x^4+\cdots=1/(1-x^2)$. Row-reversing
\eqref{e:rr2B} gives
$R(n,k)=\delta_{n,0}\delta_{k,0}+R(n-1,k-1)+R(n-2,k-1)+R(n-2,k)$.
Using $R(n,k)=[x^n]pq^k$ and dividing by $pq^{k-1}$ leaves
$q=x+x^2+x^2q$, from which we get $q=x/(1-x)$.
\end{proof}
From Identity~\ref{I:triDq}, $R(n,k)=D^{(k)}_n$. In other words, a
combinatorial interpretation of $R(n,k)$ is the number of $n$-tilings
that use $k$ squares (and $n-k$ $(1,1)$-fences). Then from
Lemma~\ref{L:Dq} we have for $n\ge k\ge0$,
\begin{equation}
R(n,k)=R(n-2,k)+\binom{n-1}{k-1}.
\end{equation}
This allows us to prove a conjecture given in the OEIS entry for
\seqnum{A059259} concerning
\seqnum{A071921} which is the square array $a(n,m)$ given by
$a(0,m\ge0)=1$,
\begin{equation}\label{e:anm}
a(n,m)=\sum_{r=0}^{m-1}\binom{n-1+2r}{n-1}.
\end{equation}
Using our notation, the conjecture is as follows.
\begin{idn} For $m,n\ge0$,
\[
\chb{n+2m}{2m}=a(n,m+1).
\]
\end{idn}
\begin{proof}
From Theorem~\ref{T:RnkB}, $\tchb{n+2m}{2m}=R(n+2m,n)$. Repeatedly
applying \eqref{e:Dq} gives
\[
R(n+2m,m)=\binom{n-1+2m}{n-1}+\binom{n-1+2(m-1)}{n-1}+\cdots
+\binom{n-1+2}{n-1}+R(n,n).
\]
Using the fact that $R(n,n)=1$ the result follows from \eqref{e:anm}.
\end{proof}
The $(n,k)$th entry, which we will denote here by $\tch{n}{k}_{1/2}$,
of the Pascal-like triangle \seqnum{A123521} is the number of ways to
tile an $n$-board using $k$ $(\frac12,\frac12)$-fences and $2(n-k)$
half-squares (with the shorter sides always horizontal) \cite{EA20}.
This triangle was also shown to be related to a Riordan array \cite{EA20}.
We now show that the $\tch{n}{k}_{1/2}$ triangle can be obtained from
the $\tchb{n}{k}$ triangle by removing the odd downward diagonals of
the latter which is equivalent to the following identity.
\begin{idn}\label{I:nkhalf} For $n\ge k\ge0$,
\[
\ch{n}{k}_{1/2}=\chb{2n-k}{k}.
\]
\end{idn}
\begin{proof}
The total post length of a $(\frac12,\frac12)$-fence is 1. The entry
$\tch{n}{k}_{1/2}$ can also be viewed as counting the number of
tilings that use $k$ $(\frac12,\frac12)$-fences and $2(n-k)$
half-squares since the total length occupied by the $n$ tiles is
$k+2(n-k)\frac12=n$. The entry $\tchb{2n-k}{k}$ counts the number of tilings
using $k$ $(1,1)$-fences and $2(n-k)$ squares. This latter tiling differs
from the former only in that the tiles are twice the length.
\end{proof}
\section{A Pascal-like triangle giving the number of tilings of an
$n$-board using $k$ fences}\label{s:ch}
\begin{figure}
\begin{tabular}{c|*{13}{p{1.5em}}}
$n$ $\backslash$ $k$&\mbox{}\hfill0&\mbox{}\hfill1&\mbox{}\hfill2&\mbox{}\hfill3&\mbox{}\hfill4&\mbox{}\hfill5&\mbox{}\hfill6&\mbox{}\hfill7&\mbox{}\hfill8&\mbox{}\hfill9&\mbox{}\hfill10&\mbox{}\hfill11&\mbox{}\hfill12\\\hline
0~~&\mbox{}\hfill 1 \\
1~~&\mbox{}\hfill 1 &\mbox{}\hfill 0 \\
2~~&\mbox{}\hfill 1 &\mbox{}\hfill 0 &\mbox{}\hfill 0 \\
3~~&\mbox{}\hfill 1 &\mbox{}\hfill 1 &\mbox{}\hfill 0 &\mbox{}\hfill 0 \\
4~~&\mbox{}\hfill 1 &\mbox{}\hfill 2 &\mbox{}\hfill 1 &\mbox{}\hfill 0 &\mbox{}\hfill 0 \\
5~~&\mbox{}\hfill 1 &\mbox{}\hfill 3 &\mbox{}\hfill 2 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 \\
6~~&\mbox{}\hfill 1 &\mbox{}\hfill 4 &\mbox{}\hfill 4 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 \\
7~~&\mbox{}\hfill 1 &\mbox{}\hfill 5 &\mbox{}\hfill 7 &\mbox{}\hfill 2 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 \\
8~~&\mbox{}\hfill 1 &\mbox{}\hfill 6 &\mbox{}\hfill 11 &\mbox{}\hfill 6 &\mbox{}\hfill 1 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 \\
9~~&\mbox{}\hfill 1 &\mbox{}\hfill 7 &\mbox{}\hfill 16 &\mbox{}\hfill 13 &\mbox{}\hfill 3 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 \\
10~~&\mbox{}\hfill 1 &\mbox{}\hfill 8 &\mbox{}\hfill 22 &\mbox{}\hfill 24 &\mbox{}\hfill 9 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 \\
11~~&\mbox{}\hfill 1 &\mbox{}\hfill 9 &\mbox{}\hfill 29 &\mbox{}\hfill 40 &\mbox{}\hfill 22 &\mbox{}\hfill 3 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 \\
12~~&\mbox{}\hfill 1 &\mbox{}\hfill 10 &\mbox{}\hfill 37 &\mbox{}\hfill 62 &\mbox{}\hfill 46 &\mbox{}\hfill 12 &\mbox{}\hfill 1 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 &\mbox{}\hfill 0 \\
\end{tabular}
\caption{A Pascal-like triangle with entries $\protect\tch{n}{k}$ (\seqnum{A335964}).}
\label{f:tri}
\end{figure}
We define $\tch{n}{k}$ as the number of tilings of an $n$-board which
contain exactly $k$ fences (Fig.~\ref{f:tri}).
We define $\tch{0}{0}=1$ so that the result
\begin{equation}
\label{e:An=sum}
A_n=\sum_{k=0}^n\ch{n}{k}
\end{equation}
is valid for $n\geq0$. We also make $\tch{n}{k}=0$ when
$k<0$ or $n0$,
$\tch{n}{0}=1$.
\end{idn}
\begin{idn}For $n>2$,
$\tch{n}{1}=n-2$.
\end{idn}
\begin{idn}\label{I:k=2} For $n>3$,
$\tch{n}{2}=\binom{n-4}{2}+n-3$.
\end{idn}
\begin{idn}\label{I:k=3}For $n>5$,
$\tch{n}{3}=\binom{n-6}{3}+2\binom{n-5}{2}$.
\end{idn}
\begin{idn}\label{I:odddiag}For $m>0$,
$\tch{4m-3}{2m-2}=\tch{4m-1}{2m-1}=m$.
\end{idn}
For the general term in the triangle, we can follow a similar method
to that used to obtain Identity~\ref{I:gfB}. However, a more elegant
approach (which leads to different sums of products of two binomial
coefficients) can be used to prove the following two identities.
\begin{idn}\label{I:2n+1kbin} For $n\ge k\ge 0$,
\[
\ch{2n+1}{k}=\sum_{j=k-m}^m\binom{n+1-j}{j}\binom{n-(k-j)}{k-j},
\]
where $m=\min(\floor{(n+1)/2},k)$.
\end{idn}
\begin{proof}
From Lemma~\ref{L:bij}, $\tch{2n+1}{k}$ is also the number of
square-domino tilings of an $(n+1)$-board and an $n$-board using $k$
dominoes in total. The number of ways to tile an $(n+1)$-board with
$j$ dominoes (and $n+1-2j$ squares) is $\binom{n+1-j}{j}$. If the
$(n+1)$-board has $j$ dominoes then the $n$-board will have $k-j$
dominoes (and $n-2(k-j)$ squares). Hence there are
$\binom{n+1-j}{j}\binom{n-(k-j)}{k-j}$ ways to tile the boards if
the $(n+1)$-board has $j$ dominoes. Evidently $j$ cannot exceed $k$ or
$\floor{(n+1)/2}$ and so $m\ge j\ge k-m$. We then sum over all
possible values of $j$.
\end{proof}
\begin{idn}\label{I:2nkbin} For $n\ge k\ge 0$,
\[
\ch{2n}{k}=\sum_{j=k-m}^m\binom{n-j}{j}\binom{n-(k-j)}{k-j},
\]
where $m=\min(\floor{n/2},k)$.
\end{idn}
\begin{proof}
The proof is analogous to that of Identity~\ref{I:2n+1kbin}.
\end{proof}
Identity~\ref{I:2nkbin} is equivalent to Identity~3.2 in
\cite{EA20}. Evidently, summing Identities \ref{I:2n+1kbin} and
\ref{I:2nkbin} over all possible $k$ will, respectively, give
ways of expressing $f_nf_{n+1}$ and $f_n^2$ as double sums
of products of two binomial coefficients.
Before showing that the reversed odd rows of the
triangle are a Riordan array we need
the following two results. (Note that
the even rows of the triangle have already been shown to be the
row-reversed $(1/(1-x^2),x/(1-x)^2)$ Riordan array \cite{EA20}.)
\begin{idn}\label{I:triCq}
For $n\ge r\ge0$, $\tch{2n+1}{n-r}=C^{(r)}_n$.
\end{idn}
\begin{proof}
The result follows from the definition of $C^{(r)}_n$ since
$\tch{2n+1}{n-r}$ is also the number of ways to tile a $(2n+1)$-board
using $2r+1$ squares.
\end{proof}
\begin{idn}\label{I:rr}
For all $n,k\in\mathbb{Z}$,
\begin{equation}
\label{e:rr}
\ch{n}{k}=\ch{n-1}{k}+\ch{n-3}{k-1}+\ch{n-4}{k-2}+\delta_{0,k}\delta_{0,n}.
\end{equation}
\end{idn}
\begin{proof}
We count $\tch{n}{k}$ by conditioning on the last metatile on the
board. If the metatile is of length $l$ and contains $j$ fences, the
number of ways to tile the remaining $n-l$ cells with $k-j$ fences is
$\tch{n-l}{k-j}$. Summing these for the three types of metatile gives
the result.
\end{proof}
To show that $C^{(r)}_n$ is a Riordan array we first need a recursion
relation that involves only the odd rows of the triangle.
\begin{idn}\label{I:rrodd}
For all $n,k\in\mathbb{Z}$,
\begin{equation}
\label{e:rrodd}
\ch{2n+1}{k}=\ch{2n-1}{k}+\ch{2n-1}{k-1}+\ch{2n-3}{k-1}
+\ch{2n-3}{k-2}-\ch{2n-5}{k-3}+\delta_{0,k}\delta_{0,n}.
\end{equation}
\end{idn}
\begin{proof}
Let $E(n,k)$ denote \eqref{e:rr}. Then $E(2n+1,k)+E(2n,k)-E(2n-1,k-1)$
gives the identity.
\end{proof}
\begin{theorem}\label{T:Rnk}
If $\bar{R}(n,k)$ is the $(n,k)$th entry of the $(1/[(1-x)(1-x^2)],x/(1-x)^2)$
Riordan array then
\begin{equation}\label{e:Rbnk}
\ch{2n+1}{k}=\bar{R}(n,n-k).
\end{equation}
\end{theorem}
\begin{proof}
From Identity~\ref{I:odddiag}, the leading diagonal of the odd rows of
the triangle has the generating function
$p=1+x+2x^2+2x^3+\cdots=1/[(1-x)(1-x^2)]$.
Row reversing \eqref{e:rrodd} and making $n$ label the
odd rows gives
$\bar{R}(n,k)=
\delta_{n,0}\delta_{k,0}
+\bar{R}(n-1,k-1)+\bar{R}(n-1,k)+\bar{R}(n-2,k-1)+\bar{R}(n-2,k)-\bar{R}(n-3,k)$.
Substituting in $R(n,k)=[x^n]pq^k$ and dividing by $pq^{k-1}$ leaves
$q=x+xq+x^2+x^2q-x^3q$, from which we get $q=x/(1-x)^2$.
\end{proof}
From Identity~\ref{I:triCq}, $\bar{R}(n,k)=C^{(k)}_n$. In other words, a
combinatorial interpretation of $\bar{R}(n,k)$ is the number of tilings of a
$(2n+1)$-board
that use $2k+1$ squares (and $2(n-k)$ $(1,1)$-fences). Then from
Lemma~\ref{L:Cq} we have for $n\ge k\ge0$,
\begin{equation}
\bar{R}(n,k)=\bar{R}(n-2,k)+\binom{n+k}{2k}.
\end{equation}
\section{Discussion}
In Sections~\ref{s:fibsqr} and \ref{s:jac} we only presented
identities that appear to be new. Some other known identities are
easily obtained via techniques based on those given in the book by
Benjamin and Quinn \cite{BQ=03}. These include considering tilings
that have at least one type of tile or metatile and then conditioning
on the position of the final tile or metatile of that type.
Various generalizations of the tilings examined here can be made. The
simplest of these is tiling an $n$-board with white squares, black
squares, and $(1,1)$-fences. This gives the Pell numbers squared
(\seqnum{A079291}) when $n$ is even and products of consecutive Pell
numbers (\seqnum{A114620}) when $n$ is odd; the overall sequence is
\seqnum{A089928}. The number $B_n$ of $n$-tilings in this case is
given by $B_n=\delta_{n,0}+2B_{n-1}+3B_{n-2}$ (\seqnum{A015518}).
Tiling with squares and $(m-1,1)$-fences when $m>2$ (see
Theorem~\ref{T:Amn}) results in an infinite number of possible
metatiles. Provided one can arrive at an expression for the numbers of
metatiles of a given length, interesting identities can
be obtained simply \cite{EA20a}. Note that although
Theorem~\ref{T:Amn} tells us what sequence such a tiling of an
$n$-board corresponds to, we do not have an equivalent theorem
determining the sequence for the number of $n$-tilings using such tiles.
Another approach for obtaining $p$ and $q$ for a Riordan array is via
the so-called $A$ and $Z$ sequences \cite{Spr94,Bar=17}. This relies on
having an expression for $R(n,k)$ given in terms of entries of the
$(n-1)$-th row. This is not always available with tiling triangles; it
is in the case of $\tchb{n}{k}$ (see Identity~\ref{I:rrB}) but not for
$\tch{n}{k}$. The procedure described in Section~\ref{s:riordan} will
not always yield a Riordan array corresponding to a row-reversed
tiling triangle. It can only succeed if the generating function for
the leading diagonal of the triangle can be found and an expression
for $q$ can obtained explicitly; if the recursion relation is of high
order then this is unlikely. It is also necessary that $q$ is of the
form $q=q_1x+q_2x^2+\cdots$.
\begin{thebibliography}{10}
\providecommand{\url}[1]{\texttt{#1}}
\providecommand{\urlprefix}{URL }
\bibitem{Bar=17}
P.~Barry, \emph{Riordan Arrays: A Primer}, lulu.com, 2017.
\bibitem{BCS19}
A.~T. Benjamin, J.~Crouch, and J.~A. Sellers, Unified tiling proofs of a family
of {Fibonacci} identities, \emph{Fibonacci Quart.} \textbf{57} (2019),
29--31.
\bibitem{BHS03}
A.~T. Benjamin, C.~R.~H. Hanusa, and F.~E. Su, Linear recurrences through
tilings and {Markov} chains, \emph{Utilitas Math.} \textbf{64} (2003), 3--17.
\bibitem{BQ=03}
A.~T. Benjamin and J.~J. Quinn, \emph{Proofs That Really Count: The Art of
Combinatorial Proof}, Mathematical Association of America, 2003.
\bibitem{BCCG96}
R.~C. Brigham, R.~M. Caron, P.~Z. Chinn, and R.~P. Grimaldi, A tiling scheme
for the {Fibonacci} numbers, \emph{J. Recreational Math.} \textbf{28} (1996),
10--16.
\bibitem{Edw08}
K.~Edwards, A {Pascal}-like triangle related to the tribonacci numbers,
\emph{Fibonacci Quart.} \textbf{46/47} (2008/2009), 18--25.
\bibitem{EA15}
K.~Edwards and M.~A. Allen, Strongly restricted permutations and tiling with
fences, \emph{Discrete Appl. Math.} \textbf{187} (2015), 82--90.
\bibitem{EA19}
K.~Edwards and M.~A. Allen, A new combinatorial interpretation of the
{Fibonacci} numbers squared, \emph{Fibonacci Quart.} \textbf{57} (5) (2019),
48--53.
\bibitem{EA20a}
K.~Edwards and M.~A. Allen, A new combinatorial interpretation of the
{Fibonacci} numbers cubed, \emph{Fibonacci Quart.} \textbf{58} (5) (2020),
128--134.
\bibitem{EA20}
K.~Edwards and M.~A. Allen, A new combinatorial interpretation of the
{Fibonacci} numbers squared. {Part II}, \emph{Fibonacci Quart.} \textbf{58}
(2020), 169--177.
\bibitem{SGWW91}
L.~W. Shapiro, S.~Getu, W.-J. Woan, and L.~C. Woodson, The {Riordan} group,
\emph{Discrete Appl. Math.} \textbf{34} (1991), 229--239.
\bibitem{Spr94}
R.~Sprugnoli, Riordan arrays and combinatorial sums, \emph{Discrete Math.}
\textbf{132} (1994), 267--290.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A19; Secondary 11B39.
\noindent \emph{Keywords: }
Fibonacci identity, Jacobsthal identity,
combinatorial proof, combinatorial identity, $n$-tiling,
Pascal-like triangle, Riordan array.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000045},
\seqnum{A000073},
\seqnum{A000124},
\seqnum{A000930},
\seqnum{A001045},
\seqnum{A001654},
\seqnum{A002620},
\seqnum{A003269},
\seqnum{A003600},
\seqnum{A006498},
\seqnum{A007598},
\seqnum{A015518},
\seqnum{A017817},
\seqnum{A059259},
\seqnum{A059260},
\seqnum{A071921},
\seqnum{A079291},
\seqnum{A089928},
\seqnum{A114620},
\seqnum{A123521},
\seqnum{A157897},
\seqnum{A158909}, and
\seqnum{A335964}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received September 9 2020;
revised version received September 12 2020; March 4 2021; March 5 2021.
Published in {\it Journal of Integer Sequences}, March 10 2021.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}