\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{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}


\DeclareMathOperator{\pfaffian}{Pf}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\wgt}{wgt}
\DeclareMathOperator{\cross}{cr}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\reduced}{red}
\DeclareMathOperator{\Preduced}{Pred}

\newcommand{\N}{\mbox{$I\!\!N$}}
\newcommand{\Z}{\mbox{$Z\!\!\!Z$}}
\newcommand{\Q}{\mbox{$I\:\!\!\!\!\!Q$}}
\newcommand{\R}{\mbox{$I\!\!R$}}

\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 Pfaffian Transform
}
\vskip 1cm
%\large
Tracale Austin \\
3824 Teton Pass \\
Ellenwood, GA  30294 \\
USA \\
\href{mailto:austintra@gmail.com}{\tt austintra@gmail.com} \\
\ \\
Hans Bantilan \\
Department of Physics\\
Princeton University\\
Princeton, NJ 08544  \\
USA\\
\href{mailto:bantilan@princeton.edu}{\tt bantilan@princeton.edu}\\
\ \\
Eric S. Egge \\
Department of Mathematics \\
Carleton College \\
Northfield, MN 55057 \\
USA \\
\href{mailto:eggee@member.ams.org}{\tt eggee@member.ams.org} \\
\ \\
Isao Jonas\\
Challenge Online Games, Inc.\\
816 Congress Ave, Suite 1470\\
Austin, TX  78701\\
USA \\
\href{mailto:isao.jonas@gmail.com}{\tt isao.jonas@gmail.com}\\
\ \\
Paul Kory\\
Department of Mathematics\\
Indiana University\\
831 East 3rd Street\\
Bloomington, IN  47405\\
USA \\
\href{mailto:pkory@indiana.edu}{\tt pkory@indiana.edu}
\end{center}

\vskip .2 in

\begin{abstract}
We introduce a function on sequences, which we call the Pfaffian
transform, using the Pfaffian of a skew-symmetric matrix.  We establish
several basic properties of the Pfaffian transform, and we use the
transfer matrix method to show that the set of sequences with rational
generating functions is closed under the Pfaffian transform.  We
conclude by computing the Pfaffian transform of a variety of sequences,
including geometric sequences, the sequence of Fibonacci numbers, the
sequence of Pell numbers, the sequence of Jacobsthal numbers, and the
sequence of Tribonacci numbers.  Throughout we describe a
generalization of our results to Pfaffians of skew-symmetric matrices
whose entries satisfy a Pascal-like relation.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}



\section{Introduction}

The Hankel transform of a sequence $\{a_n\}_{n=0}^\infty$ is the sequence $H(\{a_n\}_{n=0}^\infty) = \{h_n\}_{n=0}^\infty$ whose $n$th term is the Hankel determinant
\begin{displaymath}
h_n = \det \left(
\begin{matrix}
a_0 & a_1 & a_2 & \cdots & a_n \\
a_1 & a_2 & \cdots & \cdots & a_{n+1} \\
a_2 & \cdots & \cdots & \cdots & a_{n+2} \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
a_n & \cdots & \cdots & \cdots & a_{2n+2}
\end{matrix}\right).
\end{displaymath}
The Hankel transform was first introduced by Layman \cite{Layman}, who showed that the Hankel transform of a sequence is equal to the Hankel transform of both the Binomial and Invert transforms of that sequence.
Layman's work on the Hankel transform has been extended in
\cite{Chamberland,Cve,Spivey}.
The study of determinants of Hankel matrices predates the introduction of the Hankel transform, so the Hankel transforms of many sequences were already known when \cite{Layman} appeared.
For instance, the sequence of Catalan numbers $C_n = \frac{1}{n+1} {2n \choose n}$ is the unique sequence for which $H(\{C_n\}_{n=0}^\infty)$ and $H(\{C_n\}_{n=1}^\infty)$ are both the sequence consisting entirely of 1s \cite[Ex.\ 6.26b]{stanley}, and Desainte-Catherine and Viennot have shown \cite{DCV} that when $k \ge 2$ the sequence $H(\{C_n\}_{n=k}^\infty)$ has $m$th term ${\displaystyle \prod_{1 \le i \le j \le k-1} \frac{i+j+2m}{i+j}}$.
Generalizing the Catalan result in a different direction, Aigner has shown \cite{AignerM} that the Motzkin numbers have $H(\{M_n\}_{n=0}^\infty) = \{1\}_{n=0}^\infty$, while $H(\{M_n\}_{n=1}^\infty$) is the sequence of period six which begins $1,0,-1,-1,0,1$.
Aigner provides a generalization of these results in \cite{AignerC}.
Other results concerning Hankel determinants and the Hankel transform can be found in \cite{Brualdi,GXin,SXin,Tamm}, though this list is not exhaustive.

The determinant of an $n \times n$ matrix, which plays a central role in the Hankel transform, can be defined as a sum over the set of perfect matchings in the complete bipartite graph $K_{n,n}$.
Here a perfect matching in a graph $G$ is a set of edges in $G$ such that every vertex is incident with exactly one edge in the set.
For $n \times n$ skew-symmetric matrices, one natural analogue of the determinant is the Pfaffian, which is a sum over perfect matchings in the complete graph $K_n$.
Like determinants, Pfaffians have been connected with a variety of combinatorial objects, including plane partitions (through families of nonintersecting lattice paths) \cite{Stembridge}, the Bender-Knuth conjecture \cite{Gordon}, and the matrix-tree theorem \cite{HR}.

In this paper we introduce an analogue of the Hankel transform, called the Pfaffian transform, which uses the Pfaffian of a skew-symmetric Toeplitz matrix in place of the determinant of a Hankel matrix.
Although the Pfaffian transform may be applied to any sequence, we study its action on sequences with rational generating functions in particular.
We first use standard matrix operations to show that computing the Pfaffian transform of a sequence with a rational generating function boils down to computing the Pfaffian transform of a sequence which is eventually 0.
We then use the transfer matrix method to show that the Pfaffian transform of any such sequence has a rational generating function.
This, in turn, enables us to show that the set of sequences with rational generating functions is closed under the Pfaffian transform.
We conclude the paper by computing the Pfaffian transform on a variety of specific sequences, some of which are given in the table below.
\begin{center}
\begin{tabular}{c|c}
$\{a_n\}_{n=1}^\infty$ & Pfaffian transform of $\{a_n\}_{n=1}^\infty$ \\
\hline
$1,2,4,\ldots,2^{n-1},\ldots$ & $1,1,1,\ldots$ \\
$1,3,9,\ldots,3^{n-1},\ldots$ & $1,1,1,\ldots$ \\
$1,1,2,3,\ldots, F_n, \ldots$ & $1,2,4,\ldots, 2^{n-1},\ldots $ \\
$1,1,3,5,11,21,\ldots, J_n, \ldots$ & $1,3,9,\ldots,3^{n-1},\ldots$ \\
$1,1,2,4,7,13,\ldots, T_n, \ldots$ & $1,2,3,\ldots,n,\ldots$ \\
\end{tabular}
\end{center}
Here $F_n$ is the $n$th Fibonacci number, $J_n$ is the $n$th Jacobsthal number (these satisfy $J_n = J_{n-1} + 2J_{n-2}$), and $T_n$ is the $n$th Tribonacci number (these satisfy $T_n = T_{n-1} + T_{n-2} + T_{n-3}$).
Our examples are, in fact, more general than the table above suggests.
For instance, we show that for any $c \neq 0$ the Pfaffian transform of $\{c^{n-1}\}_{n=1}^\infty$ is $1,1,1,\ldots$, and we show that for any sequence $\{a_n\}_{n=1}^\infty$ which satisfies $a_1 = 1$, $a_2 = c$, and $a_n = c a_{n-1} + a_{n-2}$ for $n \ge 3$, where $c$ is arbitrary, the Pfaffian transform of $\{a_n\}_{n=1}^\infty$ is $1,2,4,\ldots,2^{n-1},\ldots$.
In our last example we show that for certain sequences the Pfaffian transform can be given in terms of the matchings polynomial of a path.

\section{The Pfaffian Transform of a Sequence}

In this section we introduce the Pfaffian transform of a sequence, which is defined using the Pfaffian of a skew-symmetric matrix.
The Pfaffian of a skew-symmetric matrix is given in terms of a certain graph, so we begin by adopting some graph theoretic conventions.
Throughout we use graphs with vertex set $[n]:=\{1,2,\ldots,n\}$, and we write edges in a graph with their smaller vertex first.
We recall that the {\em complete graph} with $n$ vertices is the graph in which each pair of vertices is connected by an edge;  we write $K_n$ to denote this graph.
We also recall that a {\em perfect matching} $\alpha$ in a graph $G$ is a set of edges of $G$ such that every vertex is contained in exactly one edge in $\alpha$;  we write $\alpha \vDash G$ to indicate that $\alpha$ is a perfect matching in $G$.
With these conventions in mind, we turn our attention to the Pfaffian of a skew-symmetric matrix.

\begin{definition}
Suppose $G$ is a graph with edges $(i,j)$ and $(k,l)$.
We say $(i,j)$ and $(k,l)$ are {\em crossed} whenever $i < k < j < l$ or $k < i < l < j$.
For any perfect matching $\alpha$ in $G$, we write $\cross(\alpha)$ to denote the {\em crossing number} of $\alpha$, which is the number of pairs of crossed edges in $\alpha$.
\end{definition}

The Pfaffian of an $n\times n$ skew-symmetric matrix is a sum over perfect matchings in $K_n$.
When $n$ is odd no such perfect matchings exist, so we define the Pfaffian only when $n$ is even.

\begin{definition}
\label{defn:PfaffianMatrix} 
Suppose $S$ is a $2n \times 2n$ skew-symmetric matrix.
For any perfect matching $\alpha \vDash K_{2n}$, we write $\wt(\alpha)$ to denote the {\em weight of $\alpha$}, which is defined by
$$\wt(\alpha) = (-1)^{\cross(\alpha)} \prod_{(i,j)\in \alpha}{S_{i,j}}.$$
We also write $\pfaffian(S)$ to denote the {\em Pfaffian of $S$}, which is defined by
\begin{equation}
\label{eqn:PfA}
\pfaffian(S) = \sum_{\alpha \vDash K_{2n}} {\wt(\alpha)}.
\end{equation}
\end{definition}

The Pfaffian is closely related to the determinant, and in particular one can show that if we replace $K_{2n}$ with the complete bipartite graph with parts $\{1,2,\ldots,2n\}$ and $\{1,2,\ldots,2n\}$ in (\ref{eqn:PfA}) then we obtain $\det(S)$ instead of $\pfaffian(S)$.
In view of this, it's not surprising that the Pfaffian behaves well with respect to certain products of matrices, as we show next.

\begin{proposition}
\label{prop:symmetricoperations}
Suppose $S$ is a $2n \times 2n$ skew-symmetric matrix and $P$ is an arbitrary $2n \times 2n$ matrix.
Then $P S P^t$ is skew-symmetric and
\begin{equation}
\label{eqn:BABT}
\pfaffian(P S P^t) = \det(P) \pfaffian(S).
\end{equation}
\end{proposition}
\begin{proof}
First note that $(P S P^t)^t = P S^t P^t = - P S P^t$, so $P S P^t$ is skew-symmetric.

To prove (\ref{eqn:BABT}), first observe that by Definition \ref{defn:PfaffianMatrix} we have
\begin{equation}
\label{eqn:babt1}
\pfaffian(P S P^t) = \sum_{\alpha \vDash K_{2n}} (-1)^{\cross(\alpha)} \prod_{(i,j) \in \alpha} \sum_{k=1}^{2n} \sum_{m=1}^{2n} P_{i,k} S_{k,m} P_{j,m}.
\end{equation}
Now note that for each $\alpha \vDash K_{2n}$, the associated term in (\ref{eqn:babt1}) is a product of $n$ entries of $S$ and exactly one entry from each row of $P$.
Therefore we have
\begin{equation}
\label{eqn:functionsum}
\prod_{(i,j) \in \alpha} \sum_{k=1}^{2n} \sum_{m=1}^{2n} P_{i,k} S_{k,m} P_{j,m} = \sum_\pi \prod_{r=1}^n P_{r,\pi(r)} \prod_{(i,j) \in \alpha} S_{\pi(i),\pi(j)},
\end{equation}
where the sum on the right is over all functions from $[2n]$ to $[2n]$.
If $\pi$ is such a function and there exists an edge $(i,j) \in \alpha$ with $\pi(i) = \pi(j)$ then its associated term is zero, since $S$ is skew-symmetric.
More generally, we claim that if $\pi$ is not injective, then its associated term cancels from this sum.
To prove this, we construct a sign-reversing involution on such terms.

Fix a function $\pi$ from $[2n]$ to $[2n]$ which is not injective, but for which each edge $(i,j) \in \alpha$ has $\pi(i) \neq \pi(j)$.
Let $a$ denote the smallest number which is repeated in the image of $\pi$.
Now let $i$ denote the smallest number in $[2n]$ which maps to $a$ under $\pi$ or which is matched with such a number via an edge in $\alpha$, and let $(i,j)$ denote the edge in $\alpha$ which contains $i$.
Define $\pi'$ to be the function from $[2n]$ to $[2n]$ given by
$$
\pi'(k) =
\begin{cases}
\pi(i), & \hbox{if $k=j$}; \\
\pi(j), & \hbox{if $k=i$}; \\
\pi(k), & \hbox{otherwise}. \\
\end{cases}
$$
By construction the map $\pi \mapsto \pi'$ is an involution, and since $S$ is skew-symmetric, the terms associated with $\pi$ and $\pi'$ are negatives of one another, and thus cancel.
This completes the proof of the claim.
This allows us to take the sum on the right side of (\ref{eqn:functionsum}) to be over $S_{2n}$, the set of permutations of $[2n]$.

To complete the proof of the Proposition, note that switching two numbers $r$ and $s$ in $[2n]$ reverses the sign of ${\displaystyle (-1)^{\cross(\alpha)} \prod_{(i,j) \in \alpha} S_{i,j}}$, by reversing the sign of $S_{i,j}$ if $r$ and $s$ share an edge in $\alpha$ and by changing $\cross(\alpha)$ by one if they don't.
Therefore
\begin{eqnarray*}
\pfaffian(P S P^t) &=& \sum_\alpha (-1)^{\cross(\alpha)} \left( \sum_{\pi\in S_{2n}} (-1)^{\inv(\pi)} \prod_{r=1}^{2n} P_{r,\pi(r)}\right) \prod_{(i,j) \in \alpha} S_{i,j}\\
&=& \det(P) \pfaffian(S),
\end{eqnarray*}
as desired.
\end{proof}

As we show next, Proposition \ref{prop:symmetricoperations} allows us to perform row and column operations on a skew symmetric matrix without changing its Pfaffian, as long as we perform the same operations on the columns as on the rows.

\begin{corollary}
\label{cor:src}
Let $S$ be a $2n \times 2n$ skew-symmetric matrix and let $c$ be a constant.
If $T$ is the matrix obtained from $S$ by adding $c$ times row $s$ to row $r$ and $c$ times column $s$ to column $r$, where $0 \le r < s \le 2n$, then $\pfaffian(T) = \pfaffian(S)$.
\end{corollary}
\begin{proof}
Consider the row and column operations in terms of matrix multiplication.
The row operation is equivalent to multiplying $S$ by a matrix $B$ on the left, where $B_{rs} = c$, $B$ has ones on the main diagonal, and zeros everywhere else.
Similarly, the column operation is equivalent to multiplying $S$ by $B^t$ on the right.
Thus $T = B S B^t$.
Since $B$ is an upper-triangular matrix, it is easy to see that $\det(B) = 1$.
Therefore by Proposition \ref{prop:symmetricoperations} we see that $\pfaffian(T) = \pfaffian(S)$, as desired.
\end{proof}

As Corollary \ref{cor:src} suggests, in practice one can compute the Pfaffian of a given skew-symmetric matrix using Gaussian elimination, much as one can compute a determinant.
Although we do not use it here, there is also a Pfaffian analogue of the standard Laplace expansion of a determinant \cite{godsil}.

We are now ready to define the Pfaffian transform.

\begin{definition}
\label{defn:Pfaffiantransform}
For any sequence $\{a_n\}_{n=1}^\infty$ and any $k \ge 1$, let $S_k$ be the $2k \times 2k$ skew-symmetric matrix given by
\begin{equation}
\label{eqn:Sk}
S_k =
\left(
\begin{matrix}
0 & a_1 & a_2 & a_3 & \cdots & a_{2k-1} \\
-a_1 & 0 & a_1 & a_2 & \cdots & a_{2k-2} \\
-a_2 & -a_1 & 0 & a_1 & \cdots & a_{2k-3} \\
-a_3 & -a_2 & -a_1 & 0 & \cdots & a_{2k-4} \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
-a_{2k-1} & -a_{2k-2} & -a_{2k-3} & -a_{2k-4} & \cdots & 0
\end{matrix}
\right).
\end{equation}
The {\em Pfaffian transform} of $\{a_n\}_{n=1}^\infty$ is $\pfaffian(\{a_n\}) = \{\pfaffian(S_k)\}_{k=1}^\infty$.
In order to facilitate discussion of individual elements of the output we also abbreviate $\tilde a_k = \pfaffian(S_k)$.
Thus we have $\pfaffian(\{a_n\})=\{\tilde a_n\}$.
\end{definition}

Note that we use the notation $\pfaffian()$ for both the Pfaffian of a matrix and the Pfaffian transform of a sequence.  
This is not ambiguous so long as we are careful with our parentheses, but as an additional aid to clarity we generally use uppercase letters for matrices and lowercase letters for scalars.

We conclude this section by showing that the Pfaffian transform behaves well under scaling by a constant.

\begin{proposition}
\label{prop:constant}
For any sequence $\{a_n\}_{n=1}^\infty$ and any constant $c$, we have $\tilde{c a}_k = c^k \tilde{a}_k$ for all $k \ge 1$.
\end{proposition}
\begin{proof}
Let $S_k'$ denote the matrix obtained by replacing $a_i$ with $c a_i$ for $1 \le i \le 2k-1$ in (\ref{eqn:Sk}).
If $\sqrt{c}$ is any square root of $c$ then $S_k' = (\sqrt{c}I) S_k (\sqrt{c}I)^t$, where $I$ is the $2k \times 2k$ identity.
By Proposition \ref{prop:symmetricoperations} we have $\pfaffian(S_k') = \det(\sqrt{c}I) \pfaffian(S_k)$, and the result follows.
\end{proof}

\section{Reducing Long Sequences to Short Sequences}

For the rest of this paper we study the action of the Pfaffian transform on sequences with rational generating functions, which are exactly those sequences which (eventually) satisfy a linear homogeneous recurrence relation with constant coefficients.
In this section we describe an algorithm that reduces such an input sequence to a sequence which is eventually zero, without changing the image under the Pfaffian transform.
We begin with some terminology.

\begin{definition}
\label{defn:bandedmatrix}
We say an $n\times n$ matrix $S$ is {\em banded} whenever there exists $m$ with $m < n$ such that $S_{ij} = 0$ whenever $|i-j|>m$.
\end{definition}

The diagonal matrices are the banded matrices with $m=1$, while banded matrices with $m=2$ are often called tri-diagonal matrices.

\begin{definition}
\label{defn:generalreduction}
Fix integers $k,n,N \ge 1$ and a sequence $\{a_m\}_{m=1}^\infty$, and suppose there are constants $\beta_1,\ldots,\beta_N$ for which
\begin{displaymath}
a_m = \sum_{i=1}^N \beta_i a_{m-i} \hspace{30pt} (m \ge N+k).
\end{displaymath}
Let $S$ denote the $n \times n$ skew-symmetric matrix for which $S_{i,j} = a_{j-i}$ whenever $j>i$.
We write $\reduced(S)$ to denote the $n \times n$ matrix obtained by performing the following operations on the entries of $S$.
\begin{enumerate}
\item
For each $i$ from 1 to $n$, do the following.
For each $j$ from 1 to $n$, replace the current entry $S_{i,j}$ with ${\displaystyle S_{i,j} - \sum_{m=1}^N \beta_m S_{i+m,j}}$.
\item 
For each $j$ from 1 to $n$, do the following.
For each $i$ from 1 to $n$, replace the current entry $S_{i,j}$ with ${\displaystyle S_{i,j} - \sum_{m=1}^N \beta_m S_{i,j+m}}$.
\end{enumerate}
\end{definition}

Note that step 1 in this definition amounts to subtracting, from each row of the current matrix $S$, a sum of all subsequent rows, in which the terms are weighted by the coefficients in the given recurrence relation.
Similarly, step 2 amounts to subtracting, from each column of the current matrix $S$, a sum of all subsequent columns, in which the terms are again weighted by the coefficients in the given recurrence relation.
As we show next, these operations simplify the matrix considerably without changing its Pfaffian.

\begin{proposition}
\label{prop:generalreduction}
Fix $k,n,N \ge 1$ and suppose $\{a_m\}_{m=1}^\infty$ satisfies
\begin{equation}
\label{eqn:rr}
a_m = \sum_{i=1}^N \beta_i a_{m-i} \hspace{30pt} (m \ge N+k).
\end{equation}
Let $S$ denote the $n \times n$ skew-symmetric matrix for which $S_{i,j} = a_{j-i}$ whenever $j>i$.
Then the following hold.
\begin{enumerate}
\item[{\upshape (i)}]
The matrix $\reduced(S)$ is a banded skew-symmetric matrix with at most $N+k$ nonzero bands.
\item[{\upshape (ii)}]
The entries in each band of $\reduced(S)$ are constant, except possibly in an $N \times N$ submatrix in the bottom-right corner.
\item[{\upshape (iii)}]
$\pfaffian(\reduced(S)) = \pfaffian(S)$.
\end{enumerate}
\end{proposition}
\begin{proof}
First observe that the operations used to obtain $\reduced(S)$ are symmetric row and column operations of the type described in Corollary \ref{cor:src}, so $\reduced(S)$ is skew-symmetric and $\pfaffian(\reduced(S)) = \pfaffian(S)$.

To show that $\reduced(S)$ is banded with nearly constant bands, first consider the entries of $\reduced(S)$ above its main diagonal.
For convenience, let $B$ denote the matrix obtained from step 1 of Definition \ref{defn:generalreduction}.
If $j - i \ge N+k$ then
\begin{eqnarray*}
B_{i,j} &=& S_{i,j} - \sum_{m=1}^N \beta_m S_{i+m,j} \\
&=& a_{j-i} - \sum_{m=1}^N \beta_m a_{j-i-m} \\
&=& 0,
\end{eqnarray*}
where the last step follows from (\ref{eqn:rr}).
When we apply step 2 of Definition \ref{defn:generalreduction} to the $ij$th entry of $B$ we obtain $B_{i,j} - \sum_{m=1}^N \beta_m B_{i,j+m}$.
But $j-i \ge N+k$ so $j+m-i \ge N+k$;  therefore each term in this sum is 0.
It follows that the entries above the main diagonal of $\reduced(S)$ are banded.
But $\reduced(S)$ is skew-symmetric, so $\reduced(S)$ is banded with at most $N+k$ nonzero bands.

Now observe that the algorithm which produces $\reduced(S)$ performs the same operations on all entries in a given band except for those entries that are $N$ rows away from the last row or $N$ columns away from the last column.
Therefore the bands are constant, with the possible exception of a submatrix in the bottom-right corner of size at most $N \times N$.
\end{proof}

We conclude this section by describing how one can generalize Proposition \ref{prop:generalreduction} to a wider class of skew-symmetric matrices.

\begin{definition}
Fix complex numbers $\nu$, $\lambda$, and $\beta_1,\ldots,\beta_N$.
We say a $2n \times 2n$ skew-symmetric matrix $S$ is a {\em $\nu,\lambda$-Pascal matrix with coefficients $\beta_1,\ldots,\beta_N$} whenever the following hold.
\begin{enumerate}
\item
$S_{2n-1,2n} = 1$ and for all $j$, $1 \le j \le 2n-2$, we have $S_{j,2n} = \sum_{i=1}^N \beta_i S_{j+i,2n}$.
Here we set $S_{i,j} = 0$ if $i > 2n$.
\item
For all $i,j$, $1 \le i,j \le 2n-1$, we have $S_{i,j} = \lambda S_{i+1,j+1} + \nu (S_{i+1,j} + S_{i,j+1})$.
\end{enumerate}
\end{definition}

As we describe next, we can use an analogue of $\reduced$ to turn a $\nu,\lambda$-Pascal matrix $S$ into a banded skew-symmetric matrix with nearly constant bands.

\begin{definition}
Fix complex numbers $\nu$, $\lambda$, and $\beta_1,\ldots,\beta_N$ and suppose $S$ is a $\nu,\lambda$-Pascal matrix with coefficients $\beta_1,\ldots,\beta_N$.
We write $\Preduced(S)$ to denote the matrix obtained from $S$ as follows.
\begin{enumerate}
\item
Replace $S$ with $\reduced(S)$.
\item
For each $k$ from $N+1$ to $2n-1$, replace the current matrix $S$ with a new matrix $S$, as follows.
\begin{enumerate}
\item
For each $i$ from 1 to $2n-k$, do the following.
For each $j$ from 1 to $2n$, replace $S_{i,j}$ with $S_{i,j}-\nu S_{i+1,j}$.
\item
For each $j$ from 1 to $2n-k$, do the following.
For each $i$ from 1 to $2n$, replace $S_{i,j}$ with $S_{i,j} - \nu S_{i,j+1}$.
\end{enumerate}
\item
For all $i,j$, $1 \le i,j \le 2n-2$, replace the current entry $S_{i,j}$ with $\omega^{\frac{3+i+j}{2}-2n} S_{i,j}$, where $\omega = \lambda + \nu^2$.
\end{enumerate}
\end{definition}

If $S$ is a $\nu,\lambda$-Pascal matrix with coefficients $\beta_1,\ldots,\beta_N$, then each step in the computation of $\Preduced(S)$ can be accomplished by replacing the current matrix $S$ with $PSP^t$ for a certain upper-triangular matrix $P$.
In the last step $\det(P) = \omega^{-(n-1)^2}$, where $\omega = \lambda + \nu^2$, but in all of the other steps $\det(P) = 1$.
As a result, $\pfaffian(\Preduced(S)) = \omega^{-(n-1)^2} \pfaffian(S)$ by Proposition \ref{prop:symmetricoperations}.
In fact, one can also prove the following result concerning the structure of $\Preduced(S)$.

\begin{proposition}
\label{prop:Predform}
Fix complex numbers $\nu$, $\lambda$, and $\beta_1,\ldots,\beta_N$ and suppose $S$ is a $\nu,\lambda$-Pascal matrix with coefficients $\beta_1,\ldots,\beta_N$.
Then the following hold.
\begin{enumerate}
\item[{\upshape (i)}]
The matrix $\Preduced(S)$ is a banded skew-symmetric matrix with at most $N$ nonzero bands.
\item[{\upshape (ii)}]
The entries in each band of $\Preduced(S)$ are constant, except possibly in an $N+2 \times N+2$ submatrix in the bottom-right corner.
\item[{\upshape (iii)}]
$\pfaffian(\Preduced(S)) = \omega^{-(n-1)^2} \pfaffian(S)$, where $\omega = \lambda + \nu^2$.
\end{enumerate}
\end{proposition}

\section{A Recurrence for the Pfaffian of a Short Sequence}

Proposition \ref{prop:generalreduction} suggests that if $\{a_n\}_{n=1}^\infty$ satisfies an $N+1$-term homogeneous linear recurrence relation with constant coefficients then $\pfaffian(\{a_n\})$ is closely related to the Pfaffian transform of a certain sequence of the form $x_1,x_2, \ldots,x_N,0,0,\ldots$.
With this in mind, we next study the effect of the Pfaffian transform on such a sequence.
To do this, we return to the graph-theoretic definition of the Pfaffian, which leads us to consider a particular family of graphs that arise when we construct perfect matchings in $K_{2n}$ recursively.

Consider a sequence $\{a_n\}_{n=1}^\infty$.
Combining Definitions \ref{defn:PfaffianMatrix} and \ref{defn:Pfaffiantransform}, we see that 
\begin{equation}
\label{eqn:atildeP}
\tilde a_n = \sum_{\alpha \vDash K_{2n}} {\wt(\alpha)} = \sum_{\alpha} (-1)^{\cross(\alpha)} \prod_{(i,j)\in \alpha}{a_{j-i}}.
\end{equation}
Now note that if there is an integer $r$ for which $a_n = 0$ if $n > r$, then any perfect matching $\alpha \vDash K_{2n}$ which includes an edge $(i,j)$ for which $j-i>r$ will have $\wt(\alpha) = 0$.
Thus when computing $\tilde a_n$ we need only consider perfect matchings that do not contain any such ``long'' edges.
With this in mind, we introduce a graph which includes only ``short'' edges.

\begin{definition}
\label{defn:clawgraph}
Suppose $r$ and $n$ are positive integers and $x_1,\ldots, x_r$ are indeterminates.
Then the {\em $r$-claw} on $n$ vertices is the weighted graph $C_n^r$ in which vertices $i$ and $j$ are connected with an edge exactly when $|j-i|\le r$.
If $0 < j-i \le r$ then the weight $\wt(i,j)$ of the edge between $i$ and $j$ is $x_{j-i}$
\end{definition}

Suppose $\{a_n\}_{n=1}^\infty$ is a sequence for which $a_n = 0$ if $n > r$.
In view of the comments preceding Definition \ref{defn:clawgraph}, we have
\begin{equation}
\label{eqn:edge0}
\tilde a_n =\sum_{\alpha \vDash C_{2n}^r} (-1)^{\cross(\alpha)} \prod_{(i,j)\in \alpha}{\wt(i,j)}.
\end{equation}
Each perfect matching in $C_{2n}^r$ contains an edge $(1,1+k)$ for some $k$, $1 \le k \le r$, and when we group perfect matchings in $C_{2n}^r$ according to the value of $k$, equation (\ref{eqn:edge0}) becomes 
\begin{equation}
\label{eqn:edge1}
\tilde a_n =\sum^r_{k=1}a_{k}\left(\sum_{\alpha' \vDash G_k} (-1)^{\cross(\alpha' \cup (1,k+1))} \prod_{(i,j)\in \alpha'}{a_{j-i}}\right).
\end{equation}
Here $G_k$ is the graph constructed from $C_{2n}^r$ by removing the vertices $1$ and $k+1$, along with all of their incident edges.
We can repeat this process on the inner sums, obtaining yet more sums over perfect matchings in graphs obtained by removing various vertices and edges from $C_{2n}^r$.
The form of these summands suggests we should generalize (\ref{eqn:edge0}) to graphs obtained from the claw graph by removing certain edges and vertices.

To characterize the graphs we wish to consider, suppose we start with the $r$-claw and remove the edges $(1,v_1), (2,v_2), (3,v_3), \ldots, (b,v_b)$, the vertices $1,v_1,2,v_2,\ldots,b,v_b$, and all of the edges incident with these vertices.
Note that the smallest vertex which might remain after this process is $b+1$.
Since vertices in an edge differ by at most $r$, the largest vertex which could be removed is $b+r$.
The order in which $1,v_1,2,v_2,\ldots,b,v_b$ and their incident edges are removed does not affect the structure of the resulting graph, so the final graph is determined by which of the vertices $b+1,b+2,\ldots,b+r$ remain.
We introduce notation for these graphs in the next two definitions.

\begin{definition}
\label{def:state}
Fix an integer $r \ge 1$.
For any $s$, $0 \le s \le 2^r-1$, the {\em $s$th state} of the $r$-claw is the unique sequence $b_0,\ldots, b_r$ of 0s and 1s such that
\begin{displaymath}
s = \sum_{i=0}^r b_i 2^{r-i}.
\end{displaymath}
\end{definition}

Roughly speaking, the $s$th state records which of the vertices $1,2,\ldots,r$ we remove from an $r$-claw to obtain a certain generalized $r$-claw.

\begin{definition}
\label{def:stategraph}
Fix an integer $r \ge 1$, let $x_1, \ldots, x_r$ be indeterminates, and fix an integer $s$ with $0 \le s \le 2^r - 1$.
Let $b_0, \ldots, b_r$ denote the $s$th state of the $r$-claw and let $b$ denote the number of ones among $b_0, \ldots, b_r$.
Then the {\em $s$th state graph of the $r$-claw on $2n$ vertices}, which we denote by $C_{2n}^{r,s}$, is the graph obtained from the $r$-claw on $2n+b$ vertices by removing vertex $i$ and all of its incident edges whenever $b_{i-1} = 1$.
\end{definition}

Note that since we insist that $0 \le s \le 2^r-1$, we always have $b_0 = 0$.
Therefore we never remove 1 from $C_{2n+b}^r$ when we construct $C_{2n}^{r,s}$.
We can now generalize (\ref{eqn:edge0}).

\begin{definition}
\label{defn:statepolynomial}
Fix $n \ge 1$, $r \ge 1$, and $s$ such that $0 \le s \le 2^r-1$, and let $x_1, \ldots,x_r$ be indeterminates.
Then we define the {\em state polynomial} $f_{2n}^s(x_1,\ldots,x_r)$ by
\begin{equation}
\label{eqn:sp}
f_{2n}^s(x_1,\ldots,x_r) = \sum_{\alpha \vDash C_{2n}^{r,s}} (-1)^{\cross(\alpha)} \prod_{(i,j) \in \alpha} x_{j-i}.
\end{equation}
\end{definition} 

As we show next, the state polynomials include the Pfaffian transform of any sequence $\{a_n\}_{n=1}^\infty$ for which $a_n = 0$ if $n > r$.

\begin{proposition}
Fix $r \ge 1$ and suppose $\{a_n\}_{n=1}^\infty$ is a sequence for which $a_n = 0$ when $n > r$.
Then for all $n \ge 1$ we have
\begin{equation}
\label{eqn:f0}
\tilde{a}_n = f_{2n}^0(a_1,\ldots,a_r).
\end{equation}
\end{proposition}
\begin{proof}
Note that $C_{2n}^{r,0} = C_{2n}^r$, so the result follows by setting $x_i = a_i$ for $1 \le i \le r$ in (\ref{eqn:sp}) and comparing the result with (\ref{eqn:atildeP}).
\end{proof}

In view of (\ref{eqn:f0}), equation (\ref{eqn:edge1}) expresses $f_{2n}^0(x_1,\ldots,x_r)$ as a linear combination of the state polynomials $f_{2n-2}^s(x_1,\ldots,x_r)$ for $0 \le s \le 2^r-1$.
In order to obtain a similar recurrence for $f_{2n}^s(x_1,\ldots,x_r)$, we introduce a weight on pairs of states.

\begin{definition}
\label{defn:stateweights}
Fix $r \ge 1$ and let $x_1, \ldots,x_r$ be indeterminates.
Fix $i,j$ with $1 \le i,j \le 2^r-1$, and consider the following modification of the $i$th state $i_0,\ldots,i_r$.
\begin{enumerate}
\item
Set $i_0 = 1$.
\item
Choose $m$ such that $1 \le m \le r$ and $i_m = 0$, and set $i_m=1$.
\item
If the current sequence begins with a 1, remove it and append a 0 to the end of the sequence; repeat this step until the sequence begins with a 0.
\end{enumerate}
If the $j$th state can be constructed from $i$th state by this process, then we define the weight $\wgt(i,j)$ to be $(-1)^c x_m$, where $c$ is the number of 0's among the entries $i_1,\ldots,i_{m-1}$ of the $i$th state.
Otherwise we define $\wgt(i,j) = 0$.
\end{definition}

Note that if we obtain the $j$th state from the $i$th state by the process described in Definition \ref{defn:stateweights} with a given $m$, then we obtain the state graph $C_{2n-2}^{r,j}$ from the state graph $C_{2n}^{r,i}$ by removing vertices $1$ and $m+1$, along with all of their incident edges.

\begin{theorem}
\label{thm:purestatepolyrecurrence}
Fix $r \ge 1$ and $s$ such that $0 \le s \le 2^r-1$, and let $x_1,\ldots,x_r$ be indeterminates.
If $2n \ge r+3$ then
\begin{equation}
\label{eqn:purestatepolyrecurrence}
f_{2n}^s(x_1,\ldots,x_r)=\sum^{2^r-1}_{j=0} \wgt(s,j) f_{2n-2}^j(x_1,\ldots,x_r).
\end{equation}
\end{theorem}
\begin{proof}
By (\ref{eqn:sp}) we have
\begin{equation}
\label{eqn:sp2}
f_{2n}^s(x_1,\ldots,x_r) = \sum_{\alpha \vDash C_{2n}^{r,s}} (-1)^{\cross(\alpha)} \prod_{(i,j) \in \alpha} x_{j-i}.
\end{equation}
Each perfect matching in $C_{2n}^{r,s}$ has an edge of the form $(1,t+1)$, where $1 \le t \le r$.
For each such $t$, let $G_t$ denote the graph obtained from $C_{2n}^{r,s}$ by removing vertices $1$ and $t+1$, along with all of their incident edges.
Now note that if $\alpha$ is a perfect matching which includes $(1,t+1)$, then the edges in $\alpha$ which contain a vertex between $1$ and $t+1$ either cross $(1,t+1)$ or involve two vertices between $1$ and $t+1$.
Therefore, $(-1)^{\cross(\alpha)} = (-1)^{c_t + \cross(G_t)}$, where $c_t$ is the number of vertices in $C_{2n}^{r,s}$ between $1$ and $t+1$.
If $b_0,\ldots,b_r$ is the $s$th state then it follows from (\ref{eqn:sp2}) that
\begin{equation}
\label{eqn:sp3}
f_{2n}^s(x_1,\ldots,x_r) = \sum_{\genfrac{}{}{0pt}{1}{1 \le t \le s}{b_t=0}} (-1)^{c_t} x_t \sum_{\alpha \vDash G_t} (-1)^{\cross(G_t)} \prod_{(i,j) \in \alpha} x_{j-i}.
\end{equation}
We have observed that $G_t = C_{2n-2}^{r,j}$, where the $j$th state is obtained from the $s$th state by the process described in Definition \ref{defn:stateweights}, using $m=t$, so the result follows from (\ref{eqn:sp3}).
\end{proof}

It is rare that we can apply Theorem \ref{thm:purestatepolyrecurrence} directly to the Pfaffian transform of a sequence, since the matrices we encounter usually have a submatrix in their lower-right corner in which the bands parallel to the main diagonal are not constant.
To handle these matrices, we will need the following generalization of Definition \ref{defn:statepolynomial} and Theorem \ref{thm:purestatepolyrecurrence}.

\begin{definition}
\label{defn:gsp}
Fix $r \ge 1$ and $N$ with $0 \le N \le r+1$, let $x_1,\ldots,x_r$ be indeterminates, and let $B$ denote a skew-symmetric $N \times N$ matrix.
For all $n \ge N$, let $T_n$ denote the $n \times n$ skew-symmetric matrix with the following entries.
\begin{enumerate}
\item
If $i \le n-N$ and $1 \le j-i \le r$ then $(T_n)_{ij} = x_{j-i}$.
\item
If $i \le n-N$ and $j-i > r$ then $(T_n)_{ij} = x_{j-i}$.
\item
If $j \ge i > n-N$ then $(T_n)_{ij} = B_{i-n+N,j-n+N}$.
\end{enumerate}
Then for all $s$ with $0 \le s \le 2^r-1$ we define the generalized state polynomial by
\begin{displaymath}
f_{B,2n}^s(x_1,\ldots,x_r) = \sum_{\alpha \vDash C_{2n}^{r,s}} (-1)^{\cross(\alpha)} \prod_{(i,j) \in \alpha} (T_{2n})_{ij}.
\end{displaymath}
\end{definition}

Note that if $B$ is the $0 \times 0$ empty matrix then $f_{B,2n}^s(x_1,\ldots,x_r) = f_{2n}^s(x_1,\ldots,x_r)$.

\begin{theorem}
\label{thm:statepolyrecurrence}
Fix $r \ge 1$, fix $N$ with $0 \le N \le r+1$, fix $s$ with $0 \le s \le 2^r-1$, and let $x_1, \ldots, x_r$ be indeterminates.
Let $B$ denote a skew-symmetric $N \times N$ matrix.
If $2n \ge N+r+3$ then
\begin{equation}
\label{eqn:statepolyrecurrence}
f_{B,2n}^s(x_1,\ldots,x_r) = \sum_{j=0}^{2^r-1} \wgt(s,j) f_{B,2n-2}^j(x_1,\ldots,x_r).
\end{equation}
\end{theorem}
\begin{proof}
This is similar to the proof of Theorem \ref{thm:purestatepolyrecurrence}.
\end{proof}

\section{The Pfaffian Recurrence Theorem}

Fix $r \ge 1$ and suppose $\{a_n\}_{n=1}^\infty$ is a sequence for which $a_n = 0$ if $n > r$.
In this section we interpret (\ref{eqn:statepolyrecurrence}) as a matrix equation, which allows us to apply the transfer matrix method to obtain a rational generating function for $\tilde{a}_n$.
To do this, we need to construct a directed graph whose vertices are states and in which an edge from state $i$ to state $j$ has weight $\wgt(i,j)$.
Before introducing this graph, we note that the only states one can obtain from state $0$ by the process in Definition \ref{defn:stateweights} are the even states.
Therefore we use only these states in our definition of the state digraph.

\begin{definition}
\label{defn:statedigraph}
For any $r \ge 1$ the {\em state digraph} $D_r$ is the weighted directed graph on vertices $0,1,\ldots,2^{r-1}-1$ in which there is a directed edge from $i$ to $j$ with weight $\wgt(2i,2j)$ exactly when $\wgt(2i,2j) \neq 0$.
We write $A_r$ to denote the weighted adjacency matrix for $D_r$, which has $(A_r)_{ij} = \wgt(2i,2j)$ for all $i,j$ with $0 \le i,j \le 2^{r-1}-1$.
\end{definition}

We can now rewrite (\ref{eqn:statepolyrecurrence}) in terms of $A_r$, the adjacency matrix for the state digraph.

\begin{proposition}
\label{prop:matrixrr}
Fix $r \ge 1$, fix $N$ with $0 \le N \le r+1$, let $x_1,\ldots,x_r$ be indeterminates, and let $B$ denote an $N \times N$ skew-symmetric matrix.
Abbreviating $f_{B,m}^s = f_{B,m}^s(x_1,\ldots,x_r)$, for all $n$ with $2n \ge r+3+N$ we have
\begin{equation}
\label{eqn:dynamicalsystem}
\left( 
\begin{matrix}
f_{B,2n}^0 \\ 
f_{B,2n}^2 \\ 
\vdots \\
f_{B,2n}^{2^r-2} \\
\end{matrix} 
\right)  
= A_r \left( 
\begin{matrix} 
f_{B,2n-2}^0 \\ 
f_{B,2n-2}^2 \\ 
\vdots \\
f_{B,2n-2}^{2^r-2} \\
\end{matrix} 
\right).
\end{equation}
\end{proposition}
\begin{proof}
Note that if $i$ is even and $\wgt(i,j) \neq 0$ then $j$ is also even, by Definition \ref{defn:stateweights}.
Now the result follows from (\ref{eqn:statepolyrecurrence}) and Definition \ref{defn:statedigraph}.
\end{proof}

We now recall the transfer matrix method, which we paraphrase from \cite{stanley}.

\begin{proposition}
\label{prop:tmm}
\cite[Theorem 4.7.2]{stanley}
Suppose $D$ is a weighted directed graph with vertices $1,2,\ldots,n$ and adjacency matrix $A$, so that $A_{ij}$ is the weight of the edge from $i$ to $j$.
Then for all $i,j$ with $1 \le i,j \le n$ we have
\begin{equation}
\label{eqn:tmm}
\sum_{n \ge 0} (A^n)_{ij} t^n = \frac{(-1)^{i+j} \det(I - t A;j,i)}{\det(I-tA)},
\end{equation}
where $\det(B,j,i)$ is the determinant of the matrix obtained by removing the $j$th row and $i$th column of $B$ and $I$ is the $n \times n$ identity matrix.
\end{proposition}

Combining Propositions \ref{prop:matrixrr} and \ref{prop:tmm} allows us to prove our main result, which says that the set of sequences with rational generating functions is closed under the Pfaffian transform.

\begin{theorem}
Suppose $\{a_n\}_{n=1}^\infty$ has a rational generating function.
Then $\pfaffian(\{a_n\})$ also has a rational generating function.
\end{theorem}
\begin{proof}
Since the generating function for $\{a_n\}_{n=1}^\infty$ is rational, there exist integers $k,N \ge 1$ and numbers $\beta_1,\ldots,\beta_N$ such that
\begin{displaymath}
a_n = \sum_{m=1}^N \beta_m a_{n-m} \hspace{30pt} (n \ge N+k).
\end{displaymath}
By Proposition \ref{prop:generalreduction} and Definition \ref{defn:gsp} there exists an $N \times N$ skew-symmetric matrix $B$ and numbers $b_1, \ldots, b_{N+k}$ such that
\begin{displaymath}
\tilde{a}_n = f_{B,2n}^0(b_1,\ldots,b_{N+k}) \hspace{30pt} (n \ge N+k).
\end{displaymath}
Now it follows from (\ref{eqn:dynamicalsystem}) that
\begin{displaymath}
\tilde{a}_n = \sum_{j=0}^{2^{N+k-1}-1} (A_{N+k}^{n-N-k})_{0j} f_{B,2N+2k}^j(b_1,\ldots,b_{N+k}) \hspace{30pt} (n \ge N+k),
\end{displaymath}
so we have
\begin{displaymath}
\sum_{n=N+k}^\infty \tilde{a}_n t^n = t^{N+k} \sum_{j=0}^{2^{N+k-1}-1} f_{B,2N+2k}^j(b_1,\ldots,b_{N+k}) \sum_{n=N+k}^\infty (A_{N+k}^{n-N-k})_{0j} t^{n-N-k}.
\end{displaymath}
By Proposition \ref{prop:tmm} each term on the right is a rational function of $t$, so the generating function ${\displaystyle \sum_{n=1}^\infty \tilde{a}_n t^n}$ is also a rational function of $t$.
\end{proof}

\section{Examples}

In this section we apply the techniques we have developed to compute $\pfaffian(\{a_n\})$ for a variety of interesting sequences $\{a_n\}_{n=1}^\infty$.
We will find it useful to have weighted adjacency matrices for the digraphs $D_1$ and $D_2$, which are as follows.
\begin{equation}
\label{eqn:A12}
A_1 = \left(
\begin{matrix}
x_1
\end{matrix}
\right)
\hspace{90pt}
A_2 = \left(
\begin{matrix}
x_1 & -x_2 \\
x_2 & 0 \\
\end{matrix}
\right)
\end{equation}

In our first example, we compute the Pfaffian transform of $\{c^{n-1}\}_{n=1}^\infty$, where $c$ is a constant.

\begin{example}
\label{ex:c}
Suppose $c$ is a constant and $a_n = c^{n-1}$ for all $n \ge 1$.
Then we routinely find that for all $k \ge 1$,
\begin{displaymath}
\reduced(S_k) = 
\left(
\begin{matrix}
0 & 1 & \cdots & 0 & 0 \\
-1 & 0 & \ddots & 0 & 0 \\
\vdots & \ddots & \ddots & \ddots & \vdots \\
0 & 0 & \ddots & 0 & 1 \\
0 & 0 & \cdots & -1 & 0 \\
\end{matrix}
\right).
\end{displaymath}
Therefore $\tilde{a}_n = f_{2n}^0(1)$ for all $n \ge 1$.
Since $A_1 = (x_1)$, it follows from (\ref{eqn:purestatepolyrecurrence}) that $\tilde{a}_n = 1$ for all $n \ge 1$.
\end{example}

Example \ref{ex:c} allows us to find the Pfaffian transform of any constant sequence.

\begin{example}
Suppose $c$ is a constant and $a_n = c$ for all $n \ge 1$.
By Example \ref{ex:c}, when $c=1$ we have $\tilde{a}_n = 1$ for all $n \ge 1$.
Combining this with Proposition \ref{prop:constant}, we find that $\tilde{a}_n = c^n$ in general.
\end{example}

We can also generalize Example \ref{ex:c} to Pascal matrices.

\begin{example}
Fix $n \ge 1$ and suppose is a $2n \times 2n$ $\nu,\lambda$-Pascal matrix with coefficient $c$.
Then
\begin{displaymath}
\Preduced(S) = 
\left(
\begin{matrix}
0 & a\nu+\lambda & \cdots & 0 & 0 & 0 & 0 \\
-(a\nu+\lambda) & 0 & \ddots & 0 & 0 & 0 & 0\\
\vdots & \ddots & \ddots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & \ddots & 0 & a\nu+\lambda & 0 & 0 \\
0 & 0 & \ddots & -(a\nu+\lambda) & 0 & \frac{a\nu+\lambda}{\sqrt[4]{\omega}} & 0 \\
0 & 0 & \ddots & 0 & -\frac{a\nu+\lambda}{\sqrt[4]{\omega}} & 0 & 1 \\
0 & 0 & \cdots & 0 & 0 & -1 & 0 \\
\end{matrix}
\right),
\end{displaymath}
where $\omega = \lambda + \nu^2$.
Therefore $\pfaffian(S) = \omega^{(n-1)^2} (a \nu + \lambda)^{n-1}$.
\end{example}

In Example \ref{ex:c} we found $\pfaffian(\{a_n\})$ for a family of sequences satisfying a two-term linear homogeneous recurrence relation.
A natural next step is to compute the Pfaffian transform of the most well known sequence satisfying a three-term linear homogeneous recurrence relation, the sequence of Fibonacci numbers.
To do this, we first consider a more general family of sequences.

\begin{example}
\label{ex:1afib}
Suppose $a$ and $b$ are constants, set $a_1 = 1$, $a_2 = a$, and $a_n = a a_{n-1}+ b a_{n-2}$ for all $n \ge 3$.
Then we routinely find that for all $k \ge 1$,
\begin{displaymath}
\reduced(S_k) = 
\left(
\begin{matrix}
0 & b+1 & 0 & \cdots & 0 & 0 & 0 \\
-b-1 & 0 & b+1 & \cdots & 0 & 0 & 0 \\
0 & -b-1 & 0 & \cdots & 0 & 0 & 0 \\
\vdots & \vdots & \ddots & \ddots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & \cdots & 0 & b+1 & 0 \\
0 & 0 & 0 & \cdots & -b-1 & 0 & 1 \\
0 & 0 & 0 & \cdots & 0 & -1 & 0 \\
\end{matrix}
\right).
\end{displaymath}
Therefore $\tilde{a}_n = f_{B,2n}^0(b+1)$ for $n \ge 2$, where $B = \left(\begin{matrix} 0 & 1 \\ -1 & 0 \end{matrix}\right).$
Since $A_1 = \left(x_1\right)$, it follows from (\ref{eqn:dynamicalsystem}) that $\tilde{a}_n = (b+1) \tilde{a}_{n-1}$ for $n \ge 2$, so $\tilde{a}_n = (b+1)^{n-1}$ for $n \ge 1$.
In particular, $\tilde{a}_n$ is independent of $a$.
Setting $a=b=1$, we find that the Pfaffian transform of the sequence of Fibonacci numbers is $\{2^{n-1}\}_{n=1}^\infty$.
\end{example}

We can also generalize Example \ref{ex:1afib} to Pascal matrices.

\begin{example}
Fix $n \ge 1$ and suppose is a $2n \times 2n$ $\nu,\lambda$-Pascal matrix with coefficients $a,b$.
Then $\Preduced(S)$ has two nonzero bands:  the first band above the diagonal is $\frac{(a \nu + \lambda + b)(\lambda+2\nu^2)}{\omega}, \ldots, \frac{(a \nu + \lambda + b)(\lambda+2\nu^2)}{\omega}, a\nu + \lambda + b, \frac{a\nu + \lambda + b}{\sqrt[4]{\omega}}, 1$ and the second band above the diagonal is $\frac{\nu (a\nu + \lambda + b)}{\sqrt{\omega}},\ldots,\frac{\nu (a\nu + \lambda + b)}{\sqrt{\omega}}, \frac{\nu (a\nu + \lambda + b)}{\sqrt[4]{\omega^3}}, 0$, where $\omega = \lambda + \nu^2$.
Therefore $\pfaffian(S) = \omega^{(n-1)^2} (a \nu + \lambda + b)^{n-1}$.
\end{example}

In Example \ref{ex:1afib} the matrix $\reduced(S_k)$ has one fewer nonzero band than the maximum that Proposition \ref{prop:generalreduction} predicts.
This occurs because the extended sequence $0,1,a,a^2+b,a^3+2ab,\ldots$, which includes the diagonal entries of $S_k$, continues to satisfy the recurrence $a_n = a a_{n-1} + b a_{n-2}$.
In the next example we compute the Pfaffian transform of the sequence of Lucas numbers, which satisfy the Fibonacci recurrence relation, but whose initial conditions are not compatible with prepending a 0 to the sequence.

\begin{example}
\label{ex:Lucas}
Suppose $a_1 = 2$, $a_2 = 1$, and $a_n = a_{n-1} + a_{n-2}$ for $n \ge 3$.
Then we routinely find that for all $k \ge 1$,
\begin{displaymath}
\reduced(S_k) =
\left(
\begin{matrix}
0 & 5 & -1 & 0 & \cdots & 0 & 0 & 0 & 0 \\
-5 & 0 & 5 & -1 & \cdots & 0 & 0 & 0 & 0 \\
1 & -5 & 0 & 5 & \cdots & 0 & 0 & 0 & 0 \\
0 & 1 & -5 & 0 & \ddots & 0 & 0 & 0 & 0 \\
\vdots & \vdots & \vdots & \ddots & \ddots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & 0 & 0 & \ddots & 0 & 5 & -1 & 0 \\
0 & 0 & 0 & 0 & \cdots & -5 & 0 & 5 & -1 \\
0 & 0 & 0 & 0 & \cdots & 1 & -5 & 0 & 2 \\
0 & 0 & 0 & 0 & \cdots & 0 & 1 & -2 & 0 \\
\end{matrix}
\right).
\end{displaymath}
Therefore $\tilde{a}_n = f_{B,2n}^0(5,-1)$ for $n \ge 2$, where $B = \left(\begin{matrix} 0 & 2 \\ -2 & 0\end{matrix} \right)$.
By Proposition \ref{prop:tmm} and the expression for $A_2$ in (\ref{eqn:A12}), the denominator of the generating function for $\{\tilde{a}_n\}_{n=1}^\infty$ is $1-5t+t^2$.
In particular, $\tilde{a}_1 = 2$, $\tilde{a}_2 = 9$, and $\tilde{a}_n = 5 \tilde{a}_{n-1} - \tilde{a}_{n-2}$ for $n \ge 3$.
\end{example}

Having found the Pfaffian transform for a variety of sequences satisfying a three-term recurrence relation, we now turn our attention to sequences satisfying a four-term recurrence relation.
We begin with the so-called Tribonacci numbers, which satisfy the recurrence $a_n = a_{n-1} + a_{n-2} + a_{n-3}$.

\begin{example}
\label{ex:trib}
Suppose $a_1 = a_2 = 1$, $a_3 = 2$, and $a_n = a_{n-1}+a_{n-2}+a_{n-3}$ for $n \ge 4$.
Then we routinely find that for all $k \ge 1$,
\begin{displaymath}
\reduced(S_k) = 
\left(
\begin{matrix}
0 & 2 & 1 & 0 & \cdots & 0 & 0 & 0 & 0 \\
-2 & 0 & 2 & 1 & \cdots & 0 & 0 & 0 & 0 \\
-1 & -2 & 0 & 2 & \cdots & 0 & 0 & 0 & 0 \\
0 & -1 & -2 & 0 & \cdots & 0 & 0 & 0 & 0 \\
\vdots & \vdots & \ddots & \ddots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & 0 & 0 & \ddots & 0 & 2 & 1 & 0\\
0 & 0 & 0 & 0 & \cdots & -2 & 0 & 2 & 0 \\
0 & 0 & 0 & 0 & \cdots & -1 & -2 & 0 & 1 \\
0 & 0 & 0 & 0 & \cdots & 0 & 0 & -1 & 0 \\
\end{matrix}
\right).
\end{displaymath}
Therefore $\tilde{a}_n = f_{B,2n}^0(2,1)$ for $n \ge 3$, where $B = \left(\begin{matrix} 0 & 2 & 0\\ -2 & 0 & 1 \\ 0 & -1 & 0 \end{matrix}\right).$
By Proposition \ref{prop:tmm} and the expression for $A_2$ in (\ref{eqn:A12}), the denominator of the generating function for $\{\tilde{a}_n\}_{n=1}^\infty$ is $1-2t+t^2$.
Since $\tilde{a}_1 = 1$, $\tilde{a}_2 = 2$, and $\tilde{a}_3 = 3$, it is routine to show that $\tilde{a}_n = n$ for all $n \ge 1$.
\end{example}

We conclude our examples by generalizing Example \ref{ex:trib} in a somewhat more combinatorial direction.
To set the stage for this generalization, we first recall the matchings polynomial of a graph.

Suppose $G$ is a graph with $n$ vertices, and recall that a $k$-matching in $G$ is a set of $k$ edges in $G$, no two of which share a vertex.
Set $p(G,0) = 1$, and let $p(G,k)$ denote the number of $k$-matchings in $G$ for all $k \ge 1$.
Then the {\em matchings polynomial} $\mu(G,x)$ of $G$ is defined by
\begin{displaymath}
\mu(G,x) = \sum_{k \ge 0} (-1)^k p(G,k) x^{n-2k}.
\end{displaymath}
For instance, the matchings polynomial for the path $P_n$ with $n$ vertices is \cite[p. 2]{godsil}
\begin{displaymath}
\mu(P_n, x) = \sum_{k \ge 0} (-1)^r {n-k \choose k} x^{2n-k}.
\end{displaymath}
For more information on the matchings polynomial, see \cite[Chap. 1]{godsil}.
Here we give the Pfaffian transform of a certain family of sequences in terms of this polynomial.

\begin{proposition}
\label{prop:matchings}
Suppose $a$, $b$, and $c \neq 0$ are constants and set $a_1 = 1$, $a_2 = a$, and $a_3 = a^2+b$.
For all $n \ge 4$, set $a_n = a a_{n-1} + b a_{n-2} + c a_{n-3}$.
Then
\begin{displaymath}
\tilde{a}_n = c^{n+1} \mu\left(P_{n-1}, \frac{b+1}{c}\right) = c^{n+1} \sum_{k\ge0} (-1)^k {n-1-k \choose k} \left(\frac{b+1}{c}\right)^{n-1-2k}
\end{displaymath}
for all $n \ge 1$.
\end{proposition}
\begin{proof}
First note that
\begin{displaymath}
\reduced(S_n) = 
\left(
\begin{matrix}
0 & b+1 & c & 0 & \cdots & 0 & 0 & 0 & 0 \\
-b-1 & 0 & b+1 & c & \cdots & 0 & 0 & 0 & 0 \\
-c & -b-1 & 0 & b+1 & \cdots & 0 & 0 & 0 & 0 \\
0 & -c & -b-1 & 0 & \ddots & 0 & 0 & 0 & 0 \\
\vdots & \vdots & \vdots & \ddots & \ddots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & 0 & 0 & \ddots & 0 & b+1 & c & 0 \\
0 & 0 & 0 & 0 & \cdots & -b-1 & 0 & b+1 & 0 \\
0 & 0 & 0 & 0 & \cdots & -c & -b-1 & 0 & 1 \\
0 & 0 & 0 & 0 & \cdots & 0 & 0 & -1 & 0 \\
\end{matrix}
\right).
\end{displaymath}
Now let $\sqrt{c}$ be any square root of $c$ and observe that
\begin{equation}
\label{eqn:redS1}
\reduced(S_n) = (\sqrt{c} I) T_n (\sqrt{c} I)^t,
\end{equation}
where
\begin{displaymath}
T_n = 
\left(
\begin{matrix}
0 & \frac{b+1}{c} & 1 & 0 & \cdots & 0 & 0 & 0 & 0 \\
-\frac{b+1}{c} & 0 & \frac{b+1}{c} & 1 & \cdots & 0 & 0 & 0 & 0 \\
-1 & -\frac{b+1}{c} & 0 & \frac{b+1}{c} & \cdots & 0 & 0 & 0 & 0 \\
0 & -1 & -\frac{b+1}{c} & 0 & \ddots & 0 & 0 & 0 & 0 \\
\vdots & \vdots & \vdots & \ddots & \ddots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & 0 & 0 & \ddots & 0 & \frac{b+1}{c} & 1 & 0 \\
0 & 0 & 0 & 0 & \cdots & -\frac{b+1}{c} & 0 & \frac{b+1}{c} & 0 \\
0 & 0 & 0 & 0 & \cdots & -1 & -\frac{b+1}{c} & 0 & c \\
0 & 0 & 0 & 0 & \cdots & 0 & 0 & -c & 0 \\
\end{matrix}
\right).
\end{displaymath}
To compute $\pfaffian(T_n)$, first notice that any perfect matching in $K_{2n}$ which contributes to $\pfaffian(T_n)$ must include the edge $(2n-1,2n)$, which will cross no other edges in the matching.
Therefore 
\begin{equation}
\label{eqn:redS2}
\pfaffian(T_n) = c f^0_{2n-2}\left(\frac{b+1}{c}, 1\right).
\end{equation}

We now see that $\pfaffian(T_n)$ is a sum over perfect matchings in $C_{2n-2}^2$;  to each such perfect matching we associate a matching (not necessarily perfect) in the path $P_{n-1}$ with vertices $v_1, \ldots, v_{n-1}$.
In particular, given a perfect matching $\alpha \vDash C_{2n-2}^2$, the associated matching $\alpha'$ in $P_{n-1}$ consists of those edges $(v_i,v_{i+1})$ for which $(2i-1,2i+1)$ is an edge in $\alpha$.
Since $\alpha$ is a matching in $C_{2n-2}^2$, no two edges in $\alpha'$ share a vertex, so $\alpha'$ is a matching in $P_{n-1}$.

To show that we have a bijection between matchings in $P_{n-1}$ and perfect matchings in $C_{2n-2}^2$, suppose $\alpha'$ is a matching in $P_{n-1}$.
To construct $\alpha$, first construct edges $(2i-1,2i+1)$ for each edge $(v_i,v_{i+1})$ in $\alpha'$.
Now suppose $2i-1$ is not yet incident with any edges in our partial $\alpha$.
If $(2i-2,2i-1)$ were an edge in $\alpha$, then $\alpha$ would contain a perfect matching in $C_{2i-3}^2$.
But this is impossible, since $C_{2i-3}^2$ has an odd number of vertices.
Therefore to construct $\alpha$ we must connect every as-yet unmatched odd vertex $2i-1$ with the even vertex $2i$.
Now suppose some even vertex $2i$ is not yet incident with any edges in our partial $\alpha$.
Then we must already have added $(2i-1,2i+1)$ or $(2i-3,2i-1)$ to $\alpha$.
In the first case, adding $(2i-2,2i)$ to $\alpha$ forces a perfect matching of a graph with an odd number of vertices.
However, $2i+1$ is not connected with $2i+2$, so we must include $(2i,2i+2)$ in $\alpha$.
By similar reasoning, in the second case we must include $(2i-2,2i)$ in $\alpha$.
At this point every vertex in $C_{2n-2}^2$ is incident with exactly one edge in $\alpha$, so $\alpha$ is a perfect matching.
Moreover, by construction $\alpha'$ is the perfect matching in $P_{n-1}$ associated with $\alpha$.

To complete the proof, suppose $\alpha$ is a perfect matching in $C_{2n-2}^2$ and $\alpha'$ is the associated matching in $P_{n-1}$.
If $\alpha'$ has $k$ edges then $\alpha$ has exactly $k$ edges of the form $(2i-1,2i+1)$, exactly $k$ edges of the form $(2i,2i+2)$, and $n-1-2k$ edges of the form $(2i-1,2i)$.
By construction each edge of the form $(2i-1,2i+1)$ yields a crossing in $\alpha$, and all crossings in $\alpha$ are of this type.
Moreover, the only edges in $\alpha$ whose weight is not 1 are those of the form $(2i-1,2i)$, each of which has weight $\frac{b+1}{c}$.
Combining these observations, we find that
\begin{equation}
\label{eqn:redS3}
f^0_{2n-2}\left(\frac{b+1}{c}, 1\right) = \sum_{k \ge 0} (-1)^k p(P_{n-1},k) \left(\frac{b+1}{c}\right)^{n-1-2k}.
\end{equation}
Putting everything together, we have
$$
\begin{array}{rclll}
\tilde{a}_n &=& \pfaffian(\reduced(S_n)) &\hspace{20pt}& \hbox{(by Prop. \ref{prop:generalreduction})}\\[2ex]
&=& \pfaffian((\sqrt{c} I) T_n (\sqrt{c} T)^t) & & \hbox{(by (\ref{eqn:redS1}))} \\[2ex]
&=& \det(\sqrt{c} I) \pfaffian(T_n) & & \hbox{(by Prop. \ref{prop:symmetricoperations})}\\[2ex]
&=& c^{n+1} f_{2n-2}^0\left(\frac{b+1}{c},1\right) & & \hbox{(by (\ref{eqn:redS2}))}\\[2ex]
&=& c^{n+1} \mu\left( P_{n-1}, \frac{b+1}{c}\right) & & \hbox{(by (\ref{eqn:redS3}))},
\end{array}
$$
as desired.
\end{proof}

\section{Acknowledgment}

The authors thank the anonymous referee who described how their results could be generalized to compute the Pfaffian of a Pascal matrix.

\begin{thebibliography}{10}

\bibitem{AignerM}
M.~Aigner, {M}otzkin numbers, \emph{European J. Combin.} \textbf{19} (1998),
  663--675.

\bibitem{AignerC}
M.~Aigner, {C}atalan-like numbers and determinants, \emph{J. Combin. Theory Ser.
  A} \textbf{87} (1999), 33--51.

\bibitem{Brualdi}
R.~A. Brualdi and S.~Kirkland, Aztec diamonds and digraphs, and {H}ankel
  determinants of {S}chr{\"o}der numbers,
  \emph{J. Combin. Theory Ser. B} \textbf{94} (2005), 334--351.

\bibitem{Chamberland}
M.~Chamberland and C.~French, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Chamberland/chamberland12.html}{Generalized {C}atalan numbers and
  generalized {H}ankel} transformations, \emph{J. Integer Seq.}
  \textbf{10} (2007), Article 07.1.1.

\bibitem{Cve}
A.~Cvetkovi\'c, P.~Rajkovi{\'c}, and M.~Ivkovi{\'c}, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Ivkovic/ivkovic3.html}{{C}atalan numbers,
  and {H}ankel transform, and} {F}ibonacci numbers,
  \emph{J. Integer Seq.} \textbf{5} (2002), Article 02.1.3.

\bibitem{DCV}
M.~Desainte-Catherine and X.~G. Viennot, Enumeration of certain {Y}oung
  tableaux with bounded height, in {\it Combinatoire
  \'Enum\'erative (Montreal 1985)},
  Lect. Notes. in Math., Vol.\ 1234, Springer, 1986, pp.~58--67.

\bibitem{GXin}
I.~M. Gessel and G.~Xin, The generating function of ternary trees and
  continued fractions, \emph{Electron. J. Combin.} \textbf{13} (2006), 
  Article \#R53, available electronically at
  \href{http://www.combinatorics.org/Volume_13/Abstracts/v13/v13i1r53.html}{\tt http://www.combinatorics.org/Volume\_13/Abstracts/v13/v13i1r53.html}.

\bibitem{godsil}
C.~D. Godsil, \emph{Algebraic Combinatorics}, Chapman and Hall, 1993.

\bibitem{Gordon}
B.~Gordon, A proof of the {B}ender-{K}nuth conjecture, \emph{Pacific J. Math.}
  \textbf{108} (1983), 99--113.

\bibitem{HR}
S.~Hirschman and V.~Reiner, Note on the {P}faffian matrix-tree theorem,
  \emph{Graphs Combin.} \textbf{20} (2004), 59--63.

\bibitem{Layman}
J.~W. Layman, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html}{The {H}ankel transform and some of its properties}, \emph{J.
  Integer Seq.} \textbf{4} (2001), Article 01.1.5.

\bibitem{Spivey}
M.~Z. Spivey and L.~L. Steil, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html}{The $k$-binomial transforms and the
  {H}ankel transform}, \emph{J. Integer Seq.} \textbf{9} (2006), Article 06.1.1.

\bibitem{stanley}
R.~P. Stanley, \emph{Enumerative Combinatorics}, Vol.~1, Cambridge University
  Press, 1997.

\bibitem{Stembridge}
J.~R. Stembridge, Nonintersecting paths, {P}faffians, and plane
  partitions, \emph{Adv. Math.} \textbf{83} (1990), 96--131.

\bibitem{SXin}
R.~A. Sulanke and G.~Xin, {H}ankel determinants for some common lattice
  paths, \emph{Adv. in Appl. Math.} \textbf{40} (2008), 149--167.

\bibitem{Tamm}
U.~Tamm, Some aspects of {H}ankel matrices in coding theory and
  combinatorics, \emph{Electron. J. Combin.} \textbf{8} (2001), Article \#A1,
  available electronically at \href{http://www.combinatorics.org/Volume_8/Abstracts/v8i1a1.html}{\tt http://www.combinatorics.org/Volume\_8/Abstracts/v8i1a1.html}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent
2000 {\it Mathematics Subject Classification}:  Primary 15A15; 
Secondary 05C50, 05C70.

\noindent
{\it Keywords:}
Pfaffian, skew-symmetric matrix, Toeplitz matrix, transfer matrix
method, perfect matching, Hankel transform.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000045},
\seqnum{A000073},
\seqnum{A000079},
\seqnum{A000108},
\seqnum{A000244},
\seqnum{A001006},
and
\seqnum{A001045}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 8 2008;
revised version received December 16 2008.
Published in {\it Journal of Integer Sequences}, December 17 2008.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}