The Pfaffian Transform

Tracale Austin 3824 Teton Pass

Ellenwood, GA 30294

USA

austintra@gmail.com

Hans Bantilan Department of Physics Princeton University Princeton, NJ 08544

USA

bantilan@princeton.edu

Eric S. Egge Department of Mathematics

Carleton College Northfield, MN 55057

USA

eggee@member.ams.org

Isao Jonas

Challenge Online Games, Inc. 816 Congress Ave, Suite 1470

Austin, TX 78701

USA

isao.jonas@gmail.com

Paul Kory Department of Mathematics

Indiana University 831 East 3rd Street

Bloomington, IN 47405

USA

pkory@indiana.edu

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.

1 Introduction

The Hankel transform of a sequence {a_{n}}_{n=0}^{∞} is the sequence H({a_{n}}_{n=0}^{∞}) = {h_{n}}_{n=0}^{∞} whose nth term is the Hankel determinant

h_{n} = det (\begin{matrix}a_{0} & a_{1} & a_{2} & ⋯ & a_{n} \\ a_{1} & a_{2} & ⋯ & ⋯ & a_{n+1} \\ a_{2} & ⋯ & ⋯ & ⋯ & a_{n+2} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ a_{n} & ⋯ & ⋯ & ⋯ & a_{2n+2} \end{matrix}) .

The Hankel transform was first introduced by Layman [11], 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 [4, 5, 12]. 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 [11] appeared. For instance, the sequence of Catalan numbers C_{n} = \frac{1}{n+1} \binom{2n}{n} is the unique sequence for which H({C_{n}}_{n=0}^{∞}) and H({C_{n}}_{n=1}^{∞}) are both the sequence consisting entirely of 1s [13, Ex. 6.26b], and Desainte-Catherine and Viennot have shown [6] that

when k ≥ 2 the sequence H(\{C_{n}\}_{n=k}^{∞}) has mth term ∏_{1≤i≤j≤k−1} \frac{i + j + 2m}{i + j}. Generalizing

the Catalan result in a different direction, Aigner has shown [1] that the Motzkin numbers have H({M_{n}}_{n=0}^{∞}) = {1}_{n=0}^{∞}, while H({M_{n}}_{n=1}^{∞}) is the sequence of period six which begins 1, 0, −1, −1, 0, 1. Aigner provides a generalization of these results in [2]. Other results concerning Hankel determinants and the Hankel transform can be found in [3, 7, 15, 16], though this list is not exhaustive.

The determinant of an n × 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 × 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) [14], the Bender-Knuth conjecture [9], and the matrix-tree theorem [10].

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.

{a_{n}}_{n=1}^{∞}  Pfaffian transform of {a_{n}}_{n=1}^{∞}
1, 2, 4, …, 2^{n−1}, …  1, 1, 1, …
1, 3, 9, …, 3^{n−1}, …  1, 1, 1, …
1, 1, 2, 3, …, F_{n}, …  1, 2, 4, …, 2^{n−1}, …
1, 1, 3, 5, 11, 21, …, J_{n}, …  1, 3, 9, …, 3^{n−1}, …
1, 1, 2, 4, 7, 13, …, T_{n}, …  1, 2, 3, …, n, …

Here F_{n} is the nth Fibonacci number, J_{n} is the nth Jacobsthal number (these satisfy J_{n} = J_{n−1} + 2J_{n−2}), and T_{n} is the nth 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 ≠ 0 the Pfaffian transform of {c^{n−1}}_{n=1}^{∞} is 1, 1, 1, …, and we show that for any sequence {a_{n}}_{n=1}^{∞} which satisfies a_{1} = 1, a_{2} = c, and a_{n} = ca_{n−1} + a_{n−2} for n ≥ 3, where c is arbitrary, the Pfaffian transform of {a_{n}}_{n=1}^{∞} is 1, 2, 4, …, 2^{n−1}, . . .. 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.

2 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, …, n}, and we write edges in a graph with their smaller vertex first. We recall that the 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 perfect matching α in a graph G is a set of edges of G such that every vertex is contained in exactly one edge in α; we write α ⊨ G to indicate that α is a perfect matching in G. With these conventions in mind, we turn our attention to the Pfaffian of a skew-symmetric matrix.

Definition 1. Suppose G is a graph with edges (i, j) and (k, l). We say (i, j) and (k, l) are crossed whenever i < k < j < l or k < i < l < j. For any perfect matching α in G, we write cr(α) to denote the crossing number of α, which is the number of pairs of crossed edges in α.

The Pfaffian of an n × 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.

Definition 2. Suppose S is a 2n × 2n skew-symmetric matrix. For any perfect matching α ⊨ K_{2n}, we write wt(α) to denote the weight of α, which is defined by

wt(α) = (−1)^{cr(α)} ∏_{(i,j)∈α} S_{i,j}.

We also write Pf(S) to denote the Pfaffian of S, which is defined by

Pf(S) = ∑_{α⊨K_{2n}} wt(α).  (1)

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, …, 2n} and {1, 2, …, 2n} in (1) then we obtain det(S) instead of Pf(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.

Proposition 3. Suppose S is a 2n×2n skew-symmetric matrix and P is an arbitrary 2n×2n matrix. Then P SP^{t} is skew-symmetric and

Pf(P SP^{t}) = det(P) Pf(S).  (2)

Proof. First note that (P SP^{t})^{t} = P S^{t}P^{t} = −P SP^{t}, so P SP^{t} is skew-symmetric. To prove (2), first observe that by Definition 2 we have

Pf(P SP^{t}) = ∑_{α⊨K_{2n}}(−1)^{cr(α)} ∏_{(i,j)∈α} ∑_{k=1}^{2n} ∑_{m=1}^{2n} P_{i,k}S_{k,m}P_{j,m}.  (3)

Now note that for each α ⊨ K_{2n}, the associated term in (3) is a product of n entries of S and exactly one entry from each row of P. Therefore we have

∏_{(i,j)∈α} ∑_{k=1}^{2n} ∑_{m=1}^{2n} P_{i,k}S_{k,m}P_{j,m} = ∑_{π} ∏_{r=1}^{n} P_{r,π(r)} ∏_{(i,j)∈α} S_{π(i),π(j)},  (4)

where the sum on the right is over all functions from [2n] to [2n]. If π is such a function and there exists an edge (i, j) ∈ α with π(i) = π(j) then its associated term is zero, since S is skew-symmetric. More generally, we claim that if π 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 π from [2n] to [2n] which is not injective, but for which each edge (i, j) ∈ α has π(i) ≠ π(j). Let a denote the smallest number which is repeated in the image of π. Now let i denote the smallest number in [2n] which maps to a under π or which is matched with such a number via an edge in α, and let (i, j) denote the edge in α which contains i. Define π′ to be the function from [2n] to [2n] given by

π′(k) = \begin{cases}π(i), & if k = j; \\ π(j), & if k = i; \\ π(k), & otherwise. \end{cases}

By construction the map π ↦ π′ is an involution, and since S is skew-symmetric, the terms associated with π and π′ 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 (4) 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 (−1)^{cr(α)} ∏_{(i,j)∈α} S_{i,j}, by reversing the sign of S_{i,j} if r and s share an

edge in α and by changing cr(α) by one if they don’t. Therefore

Pf(P SP^{t}) = ∑_{α}(−1)^{cr(α)} ( ∑_{π∈S_{2n}}(−1)^{inv(π)} ∏_{r=1}^{2n} P_{r,π(r)}) ∏_{(i,j)∈α} S_{i,j}
= det(P) Pf(S),

as desired.

As we show next, Proposition 3 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.

Corollary 4. Let S be a 2n × 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 ≤ r < s ≤ 2n, then Pf(T) = Pf(S).

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 = BSB^{t}. Since B is an uppertriangular matrix, it is easy to see that det(B) = 1. Therefore by Proposition 3 we see that Pf(T) = Pf(S), as desired.

As Corollary 4 suggests, in practice one can compute the Pfaffian of a given skewsymmetric 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 [8].

We are now ready to define the Pfaffian transform.

Definition 5. For any sequence {a_{n}}_{n=1}^{∞} and any k ≥ 1, let S_{k} be the 2k × 2k skewsymmetric matrix given by

S_{k} = (\begin{matrix}0 & a_{1} & a_{2} & a_{3} & ⋯ & a_{2k−1} \\ −a_{1} & 0 & a_{1} & a_{2} & ⋯ & a_{2k−2} \\ −a_{2} & −a_{1} & 0 & a_{1} & ⋯ & a_{2k−3} \\ −a_{3} & −a_{2} & −a_{1} & 0 & ⋯ & a_{2k−4} \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ −a_{2k−1} & −a_{2k−2} & −a_{2k−3} & −a_{2k−4} & ⋯ & 0 \end{matrix}) .  (5)

The Pfaffian transform of {a_{n}}_{n=1}^{∞} is Pf({a_{n}}) = {Pf(S_{k})}_{k=1}^{∞}. In order to facilitate discussion of individual elements of the output we also abbreviate ã_{k} = Pf(S_{k}). Thus we have Pf({a_{n}}) = {ã_{n}}.

Note that we use the notation Pf() 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.

Proposition 6. For any sequence {a_{n}}_{n=1}^{∞} and any constant c, we have c̃a_{k} = c^{k}ã_{k} for all k ≥ 1.

Proof. Let S′_{k} denote the matrix obtained by replacing a_{i} with ca_{i} for 1 ≤ i ≤ 2k − 1 in (5). 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 × 2k identity. By Proposition 3 we have Pf(S′_{k}) = det(\sqrt{c}I) Pf(S_{k}), and the result follows.

3 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.

Definition 7. We say an n × n matrix S is banded whenever there exists m with m < n such that S_{ij} = 0 whenever |i − j| > m.

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

Definition 8. Fix integers k, n, N ≥ 1 and a sequence {a_{m}}_{m=1}^{∞}, and suppose there are constants β_{1}, …, β_{N} for which

a_{m} = ∑_{i=1}^{N} β_{i}a_{m−i} (m ≥ N + k).

Let S denote the n × n skew-symmetric matrix for which S_{i,j} = a_{j−i} whenever j > i. We write red(S) to denote the n × n matrix obtained by performing the following operations on the entries of S.

1. 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 S_{i,j} − ∑_{m=1}^{N} β_{m}S_{i+m,j}.

2. 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 S_{i,j} − ∑_{m=1}^{N} β_{m}S_{i,j+m}.

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.

Proposition 9. Fix k, n, N ≥ 1 and suppose {a_{m}}_{m=1}^{∞} satisfies

a_{m} = ∑_{i=1}^{N} β_{i}a_{m−i}  (m ≥ N + k).  (6)

Let S denote the n × n skew-symmetric matrix for which S_{i,j} = a_{j−i} whenever j > i. Then the following hold.

(i) The matrix red(S) is a banded skew-symmetric matrix with at most N + k nonzero bands.

(ii) The entries in each band of red(S) are constant, except possibly in an N ×N submatrix in the bottom-right corner.

(iii) Pf(red(S)) = Pf(S).

Proof. First observe that the operations used to obtain red(S) are symmetric row and column operations of the type described in Corollary 4, so red(S) is skew-symmetric and Pf(red(S)) = Pf(S).

To show that red(S) is banded with nearly constant bands, first consider the entries of red(S) above its main diagonal. For convenience, let B denote the matrix obtained from step 1 of Definition 8. If j − i ≥ N + k then

B_{i,j} = S_{i,j} − ∑_{m=1}^{N} β_{m}S_{i+m,j}

= a_{j−i} − ∑_{m=1}^{N} β_{m}a_{j−i−m}
= 0,

where the last step follows from (6). When we apply step 2 of Definition 8 to the ijth entry of B we obtain B_{i,j} − ∑_{m=1}^{N} β_{m}B_{i,j+m}. But j − i ≥ N + k so j + m − i ≥ N + k; therefore each term in this sum is 0. It follows that the entries above the main diagonal of red(S) are banded. But red(S) is skew-symmetric, so red(S) is banded with at most N + k nonzero bands.

Now observe that the algorithm which produces red(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 × N.

We conclude this section by describing how one can generalize Proposition 9 to a wider class of skew-symmetric matrices.

Definition 10. Fix complex numbers ν, λ, and β_{1}, …, β_{N}. We say a 2n × 2n skewsymmetric matrix S is a ν, λ-Pascal matrix with coefficients β_{1}, …, β_{N} whenever the following hold.

1. S_{2n−1,2n} = 1 and for all j, 1 ≤ j ≤ 2n − 2, we have S_{j,2n} = ∑_{i=1}^{N} β_{i}S_{j+i,2n}. Here we set S_{i,j} = 0 if i > 2n.

2. For all i, j, 1 ≤ i, j ≤ 2n − 1, we have S_{i,j} = λS_{i+1,j+1} + ν(S_{i+1,j} + S_{i,j+1}).

As we describe next, we can use an analogue of red to turn a ν, λ-Pascal matrix S into a banded skew-symmetric matrix with nearly constant bands.

Definition 11. Fix complex numbers ν, λ, and β_{1}, …, β_{N} and suppose S is a ν, λ-Pascal matrix with coefficients β_{1}, …, β_{N}. We write Pred(S) to denote the matrix obtained from S as follows.

1. Replace S with red(S).

2. For each k from N + 1 to 2n − 1, replace the current matrix S with a new matrix S, as follows.

(a) 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} − νS_{i+1,j}.

(b) 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} − νS_{i,j+1}.

3. For all i, j, 1 ≤ i, j ≤ 2n − 2, replace the current entry S_{i,j} with ω^{\frac{3+i+j}{2} −2n}S_{i,j}, where ω = λ + ν^{2}.

If S is a ν, λ-Pascal matrix with coefficients β_{1}, …, β_{N}, then each step in the computation of Pred(S) can be accomplished by replacing the current matrix S with P SP^{t} for a certain upper-triangular matrix P. In the last step det(P) = ω^{−(n−1)^{2}}, where ω = λ + ν^{2}, but in all of the other steps det(P) = 1. As a result, Pf(Pred(S)) = ω^{−(n−1)^{2}} Pf(S) by Proposition 3. In fact, one can also prove the following result concerning the structure of Pred(S).

Proposition 12. Fix complex numbers ν, λ, and β_{1}, …, β_{N} and suppose S is a ν, λ-Pascal matrix with coefficients β_{1}, …, β_{N}. Then the following hold.

(i) The matrix Pred(S) is a banded skew-symmetric matrix with at most N nonzero bands.

(ii) The entries in each band of Pred(S) are constant, except possibly in an N + 2 × N + 2 submatrix in the bottom-right corner.

(iii) Pf(Pred(S)) = ω^{−(n−1)^{2}} Pf(S), where ω = λ + ν^{2}.

4 A Recurrence for the Pfaffian of a Short Sequence

Proposition 9 suggests that if {a_{n}}_{n=1}^{∞} satisfies an N +1-term homogeneous linear recurrence relation with constant coefficients then Pf({a_{n}}) is closely related to the Pfaffian transform of a certain sequence of the form x_{1}, x_{2}, …, x_{N}, 0, 0, . . .. With this in mind, we next study the effect of the Pfaffian transform on such a sequence. To do this, we return to the graphtheoretic 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}^{∞}. Combining Definitions 2 and 5, we see that

ã_{n} = ∑_{α⊨K_{2n}} wt(α) = ∑_{α}(−1)^{cr(α)} ∏_{(i,j)∈α} a_{j−i}.  (7)

Now note that if there is an integer r for which a_{n} = 0 if n > r, then any perfect matching α ⊨ K_{2n} which includes an edge (i, j) for which j − i > r will have wt(α) = 0. Thus when computing ã_{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.

Definition 13. Suppose r and n are positive integers and x_{1}, …, x_{r} are indeterminates. Then the 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| ≤ r. If 0 < j − i ≤ r then the weight wt(i, j) of the edge between i and j is x_{j−i}

Suppose {a_{n}}_{n=1}^{∞} is a sequence for which a_{n} = 0 if n > r. In view of the comments preceding Definition 13, we have

ã_{n} = ∑_{α⊨C_{2n}^{r}}(−1)^{cr(α)} ∏_{(i,j)∈α} wt(i, j).  (8)

Each perfect matching in C_{2n}^{r} contains an edge (1, 1 + k) for some k, 1 ≤ k ≤ r, and when we group perfect matchings in C_{2n}^{r} according to the value of k, equation (8) becomes

ã_{n} = ∑_{k=1}^{r} a_{k} ( ∑_{α′⊨G_{k}}(−1)^{cr(α′∪(1,k+1))} ∏_{(i,j)∈α′} a_{j−i}) .  (9)

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 (8) 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}), …, (b, v_{b}), the vertices 1, v_{1}, 2, v_{2}, …, 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}, …, 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, …, b + r remain. We introduce notation for these graphs in the next two definitions.

Definition 14. Fix an integer r ≥ 1. For any s, 0 ≤ s ≤ 2^{r} − 1, the sth state of the r-claw is the unique sequence b_{0}, …, b_{r} of 0s and 1s such that

s = ∑_{i=0}^{r} b_{i}2^{r−i}.

Roughly speaking, the sth state records which of the vertices 1, 2, …, r we remove from an r-claw to obtain a certain generalized r-claw.

Definition 15. Fix an integer r ≥ 1, let x_{1}, …, x_{r} be indeterminates, and fix an integer s with 0 ≤ s ≤ 2^{r} − 1. Let b_{0}, …, b_{r} denote the sth state of the r-claw and let b denote the number of ones among b_{0}, …, b_{r}. Then the sth 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.

Note that since we insist that 0 ≤ s ≤ 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 (8).

Definition 16. Fix n ≥ 1, r ≥ 1, and s such that 0 ≤ s ≤ 2^{r} − 1, and let x_{1}, …, x_{r} be indeterminates. Then we define the state polynomial f_{2n}^{s}(x_{1}, …, x_{r}) by

f_{2n}^{s}(x_{1}, …, x_{r}) = ∑_{α⊨C_{2n}^{r,s}}(−1)^{cr(α)} ∏_{(i,j)∈α} x_{j−i}.  (10)

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

Proposition 17. Fix r ≥ 1 and suppose {a_{n}}_{n=1}^{∞} is a sequence for which a_{n} = 0 when n > r. Then for all n ≥ 1 we have

ã_{n} = f_{2n}^{0}(a_{1}, …, a_{r}).  (11)

Proof. Note that C_{2n}^{r,0} = C_{2n}^{r}, so the result follows by setting x_{i} = a_{i} for 1 ≤ i ≤ r in (10) and comparing the result with (7).

In view of (11), equation (9) expresses f_{2n}^{0}(x_{1}, …, x_{r}) as a linear combination of the state polynomials f_{2n−2}^{s}(x_{1}, …, x_{r}) for 0 ≤ s ≤ 2^{r} − 1. In order to obtain a similar recurrence for f_{2n}^{s}(x_{1}, …, x_{r}), we introduce a weight on pairs of states.

Definition 18. Fix r ≥ 1 and let x_{1}, …, x_{r} be indeterminates. Fix i, j with 1 ≤ i, j ≤ 2^{r} − 1, and consider the following modification of the ith state i_{0}, …, i_{r}.

1. Set i_{0} = 1.

2. Choose m such that 1 ≤ m ≤ r and i_{m} = 0, and set i_{m} = 1.

3. 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.

If the jth state can be constructed from ith 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}, …, i_{m−1} of the ith state. Otherwise we define wgt(i, j) = 0.

Note that if we obtain the jth state from the ith state by the process described in Definition 18 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.

Theorem 19. Fix r ≥ 1 and s such that 0 ≤ s ≤ 2^{r} −1, and let x_{1}, …, x_{r} be indeterminates. If 2n ≥ r + 3 then

f_{2n}^{s}(x_{1}, …, x_{r}) = ∑_{j=0}^{2^{r}−1} wgt(s, j)f_{2n−2}^{j}(x_{1}, …, x_{r}).  (12)

Proof. By (10) we have

f_{2n}^{s}(x_{1}, …, x_{r}) = ∑_{α⊨C_{2n}^{r,s}}(−1)^{cr(α)} ∏_{(i,j)∈α} x_{j−i}.  (13)

Each perfect matching in C_{2n}^{r,s} has an edge of the form (1, t + 1), where 1 ≤ t ≤ 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 α is a perfect matching which includes (1, t+1), then the edges in α 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)^{cr(α)} = (−1)^{c_{t}+cr(G_{t})}, where c_{t} is the number of vertices in C_{2n}^{r,s} between 1 and t + 1. If b_{0}, …, b_{r} is the sth state then it follows from (13) that

f_{2n}^{s}(x_{1}, …, x_{r}) = ∑_{{1≤t≤s \atop b_{t}=0}}(−1)^{c_{t}}x_{t} ∑_{α⊨G_{t}}(−1)^{cr(G_{t})} ∏_{(i,j)∈α} x_{j−i}.  (14)

We have observed that G_{t} = C_{2n−2}^{r,j}, where the jth state is obtained from the sth state by the process described in Definition 18, using m = t, so the result follows from (14).

It is rare that we can apply Theorem 19 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 16 and Theorem 19.

Definition 20. Fix r ≥ 1 and N with 0 ≤ N ≤ r + 1, let x_{1}, …, x_{r} be indeterminates, and let B denote a skew-symmetric N × N matrix. For all n ≥ N, let T_{n} denote the n × n skew-symmetric matrix with the following entries.

1. If i ≤ n − N and 1 ≤ j − i ≤ r then (T_{n})_{ij} = x_{j−i}.

2. If i ≤ n − N and j − i > r then (T_{n})_{ij} = x_{j−i}.

3. If j ≥ i > n − N then (T_{n})_{ij} = B_{i−n+N,j−n+N}.

Then for all s with 0 ≤ s ≤ 2^{r} − 1 we define the generalized state polynomial by

f_{B,2n}^{s}(x_{1}, …, x_{r}) = ∑_{α⊨C_{2n}^{r,s}}(−1)^{cr(α)} ∏_{(i,j)∈α}(T_{2n})_{ij}.

Note that if B is the 0 × 0 empty matrix then f_{B,2n}^{s}(x_{1}, …, x_{r}) = f_{2n}^{s}(x_{1}, …, x_{r}).

Theorem 21. Fix r ≥ 1, fix N with 0 ≤ N ≤ r + 1, fix s with 0 ≤ s ≤ 2^{r} − 1, and let x_{1}, …, x_{r} be indeterminates. Let B denote a skew-symmetric N ×N matrix. If 2n ≥ N +r+3 then

f_{B,2n}^{s}(x_{1}, …, x_{r}) = ∑_{j=0}^{2^{r}−1} wgt(s, j)f_{B,2n−2}^{j}(x_{1}, …, x_{r}).  (15)

Proof. This is similar to the proof of Theorem 19.

5 The Pfaffian Recurrence Theorem

Fix r ≥ 1 and suppose {a_{n}}_{n=1}^{∞} is a sequence for which a_{n} = 0 if n > r. In this section we interpret (15) as a matrix equation, which allows us to apply the transfer matrix method to obtain a rational generating function for ã_{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 18 are the even states. Therefore we use only these states in our definition of the state digraph.

Definition 22. For any r ≥ 1 the state digraph D_{r} is the weighted directed graph on vertices 0, 1, …, 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) ≠ 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 ≤ i, j ≤ 2^{r−1} − 1.

We can now rewrite (15) in terms of A_{r}, the adjacency matrix for the state digraph.

Proposition 23. Fix r ≥ 1, fix N with 0 ≤ N ≤ r + 1, let x_{1}, …, x_{r} be indeterminates, and let B denote an N × N skew-symmetric matrix. Abbreviating f_{B,m}^{s} = f_{B,m}^{s}(x_{1}, …, x_{r}), for all n with 2n ≥ r + 3 + N we have

(f_{B,2n}^{0} ; f_{B,2n}^{2} ; ⋮ ; f_{B,2n}^{2^{r}−2}) = A_{r} (f_{B,2n−2}^{0} ; f_{B,2n−2}^{2} ; ⋮ ; f_{B,2n−2}^{2^{r}−2}) .  (16)

Proof. Note that if i is even and wgt(i, j) ≠ 0 then j is also even, by Definition 18. Now the result follows from (15) and Definition 22.

We now recall the transfer matrix method, which we paraphrase from [13].

Proposition 24. [13, Theorem 4.7.2] Suppose D is a weighted directed graph with vertices 1, 2, …, 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 ≤ i, j ≤ n we have

∑_{n≥0}(A^{n})_{ij}t^{n} = \frac{(−1)^{i+j} det(I − tA; j, i)}{det(I − tA)},  (17)

where det(B, j, i) is the determinant of the matrix obtained by removing the jth row and ith column of B and I is the n × n identity matrix.

Combining Propositions 23 and 24 allows us to prove our main result, which says that the set of sequences with rational generating functions is closed under the Pfaffian transform.

Theorem 25. Suppose {a_{n}}_{n=1}^{∞} has a rational generating function. Then Pf({a_{n}}) also has a rational generating function.

Proof. Since the generating function for {a_{n}}_{n=1}^{∞} is rational, there exist integers k, N ≥ 1 and numbers β_{1}, …, β_{N} such that

a_{n} = ∑_{m=1}^{N} β_{m}a_{n−m} (n ≥ N + k).

By Proposition 9 and Definition 20 there exists an N × N skew-symmetric matrix B and numbers b_{1}, …, b_{N+k} such that

ã_{n} = f_{B,2n}^{0}(b_{1}, …, b_{N+k}) (n ≥ N + k).

Now it follows from (16) that

ã_{n} = ∑_{j=0}^{2^{N+k−1}−1}(A_{N+k}^{n−N−k})_{0j}f_{B,2N+2k}^{j}(b_{1}, …, b_{N+k}) (n ≥ N + k),

so we have

∑_{n=N+k}^{∞} ã_{n}t^{n} = t^{N+k} ∑_{j=0}^{2^{N+k−1}−1} f_{B,2N+2k}^{j}(b_{1}, …, b_{N+k}) ∑_{n=N+k}^{∞}(A_{N+k}^{n−N−k})_{0j}t^{n−N−k}.

By Proposition 24 each term on the right is a rational function of t, so the generating function

∑_{n=1}^{∞} ã_{n}t^{n} is also a rational function of t.

6 Examples

In this section we apply the techniques we have developed to compute Pf({a_{n}}) for a variety of interesting sequences {a_{n}}_{n=1}^{∞}. We will find it useful to have weighted adjacency matrices for the digraphs D_{1} and D_{2}, which are as follows.

A_{1} = (x_{1})  A_{2} = (\begin{matrix}x_{1} & −x_{2} \\ x_{2} & 0 \end{matrix})  (18)

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

Example 26. Suppose c is a constant and a_{n} = c^{n−1} for all n ≥ 1. Then we routinely find that for all k ≥ 1,

red(S_{k}) = (\begin{matrix}0 & 1 & ⋯ & 0 & 0 \\ −1 & 0 & ... & 0 & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ... & 0 & 1 \\ 0 & 0 & ⋯ & −1 & 0 \end{matrix}) .

Therefore ã_{n} = f_{2n}^{0}(1) for all n ≥ 1. Since A_{1} = (x_{1}), it follows from (12) that ã_{n} = 1 for all n ≥ 1.

Example 26 allows us to find the Pfaffian transform of any constant sequence.

Example 27. Suppose c is a constant and a_{n} = c for all n ≥ 1. By Example 26, when c = 1 we have ã_{n} = 1 for all n ≥ 1. Combining this with Proposition 6, we find that ã_{n} = c^{n} in general.

We can also generalize Example 26 to Pascal matrices.

Example 28. Fix n ≥ 1 and suppose is a 2n × 2n ν, λ-Pascal matrix with coefficient c. Then

Pred(S) = (\begin{matrix}0 & aν + λ & ⋯ & 0 & 0 & 0 & 0 \\ −(aν + λ) & 0 & ... & 0 & 0 & 0 & 0 \\ ⋮ & ... & ... & ... & ⋮ & ⋮ & ⋮ \\ 0 & 0 & ... & 0 & aν + λ & 0 & 0 \\ 0 & 0 & ... & −(aν + λ) & 0 & \frac{aν+λ}{\sqrt[4]{ω}} & 0 \\ 0 & 0 & ... & 0 & −\frac{aν+λ}{\sqrt[4]{ω}} & 0 & 1 \\ 0 & 0 & ⋯ & 0 & 0 & −1 & 0 \end{matrix}) ,

where ω = λ + ν^{2}. Therefore Pf(S) = ω^{(n−1)^{2}}(aν + λ)^{n−1}.

In Example 26 we found Pf({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.

Example 29. Suppose a and b are constants, set a_{1} = 1, a_{2} = a, and a_{n} = aa_{n−1} + ba_{n−2} for all n ≥ 3. Then we routinely find that for all k ≥ 1,

red(S_{k}) = (\begin{matrix}0 & b + 1 & 0 & ⋯ & 0 & 0 & 0 \\ −b − 1 & 0 & b + 1 & ⋯ & 0 & 0 & 0 \\ 0 & −b − 1 & 0 & ⋯ & 0 & 0 & 0 \\ ⋮ & ⋮ & ... & ... & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & ⋯ & 0 & b + 1 & 0 \\ 0 & 0 & 0 & ⋯ & −b − 1 & 0 & 1 \\ 0 & 0 & 0 & ⋯ & 0 & −1 & 0 \end{matrix}) .

Therefore ã_{n} = f_{B,2n}^{0}(b + 1) for n ≥ 2, where B = (\begin{matrix}0 & 1 \\ −1 & 0 \end{matrix}) . Since A_{1} = (x_{1}), it follows

from (16) that ã_{n} = (b + 1)ã_{n−1} for n ≥ 2, so ã_{n} = (b + 1)^{n−1} for n ≥ 1. In particular, ã_{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}^{∞}.

We can also generalize Example 29 to Pascal matrices.

Example 30. Fix n ≥ 1 and suppose is a 2n × 2n ν, λ-Pascal matrix with coefficients a, b. Then Pred(S) has two nonzero bands: the first band above the diagonal is \frac{(aν+λ+b)(λ+2ν^{2})}{ω}, …, \frac{(aν+λ+b)(λ+2ν^{2})}{ω}, aν + λ + b, \frac{aν+λ+b}{\sqrt[4]{ω}}, 1 and the second band above the

diagonal is \frac{ν(aν+λ+b)}{\sqrt{ω}}, …, \frac{ν(aν+λ+b)}{\sqrt{ω}}, \frac{ν(aν+λ+b)}{\sqrt[4]{ω^{3}}}, 0, where ω = λ + ν^{2}. Therefore Pf(S) = ω^{(n−1)^{2}}(aν + λ + b)^{n−1}.

In Example 29 the matrix red(S_{k}) has one fewer nonzero band than the maximum that Proposition 9 predicts. This occurs because the extended sequence 0, 1, a, a^{2} +b, a^{3} +2ab, …, which includes the diagonal entries of S_{k}, continues to satisfy the recurrence a_{n} = aa_{n−1} + ba_{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.

Example 31. Suppose a_{1} = 2, a_{2} = 1, and a_{n} = a_{n−1}+a_{n−2} for n ≥ 3. Then we routinely find that for all k ≥ 1,

red(S_{k}) = (\begin{matrix}0 & 5 & −1 & 0 & ⋯ & 0 & 0 & 0 & 0 \\ −5 & 0 & 5 & −1 & ⋯ & 0 & 0 & 0 & 0 \\ 1 & −5 & 0 & 5 & ⋯ & 0 & 0 & 0 & 0 \\ 0 & 1 & −5 & 0 & ... & 0 & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ... & ... & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & ... & 0 & 5 & −1 & 0 \\ 0 & 0 & 0 & 0 & ⋯ & −5 & 0 & 5 & −1 \\ 0 & 0 & 0 & 0 & ⋯ & 1 & −5 & 0 & 2 \\ 0 & 0 & 0 & 0 & ⋯ & 0 & 1 & −2 & 0 \end{matrix}) .

Therefore ã_{n} = f_{B,2n}^{0}(5, −1) for n ≥ 2, where B = (\begin{matrix}0 & 2 \\ −2 & 0 \end{matrix}). By Proposition 24 and the

expression for A_{2} in (18), the denominator of the generating function for {ã_{n}}_{n=1}^{∞} is 1−5t+t^{2}. In particular, ã_{1} = 2, ã_{2} = 9, and ã_{n} = 5ã_{n−1} − ã_{n−2} for n ≥ 3.

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}.

Example 32. Suppose a_{1} = a_{2} = 1, a_{3} = 2, and a_{n} = a_{n−1} + a_{n−2} + a_{n−3} for n ≥ 4. Then we routinely find that for all k ≥ 1,

red(S_{k}) = (\begin{matrix}0 & 2 & 1 & 0 & ⋯ & 0 & 0 & 0 & 0 \\ −2 & 0 & 2 & 1 & ⋯ & 0 & 0 & 0 & 0 \\ −1 & −2 & 0 & 2 & ⋯ & 0 & 0 & 0 & 0 \\ 0 & −1 & −2 & 0 & ⋯ & 0 & 0 & 0 & 0 \\ ⋮ & ⋮ & ... & ... & ... & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & ... & 0 & 2 & 1 & 0 \\ 0 & 0 & 0 & 0 & ⋯ & −2 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & ⋯ & −1 & −2 & 0 & 1 \\ 0 & 0 & 0 & 0 & ⋯ & 0 & 0 & −1 & 0 \end{matrix}) .

Therefore ã_{n} = f_{B,2n}^{0}(2, 1) for n ≥ 3, where B = (\begin{matrix}0 & 2 & 0 \\ −2 & 0 & 1 \\ 0 & −1 & 0 \end{matrix}) . By Proposition 24 and

the expression for A_{2} in (18), the denominator of the generating function for {ã_{n}}_{n=1}^{∞} is 1 − 2t + t^{2}. Since ã_{1} = 1, ã_{2} = 2, and ã_{3} = 3, it is routine to show that ã_{n} = n for all n ≥ 1.

We conclude our examples by generalizing Example 32 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 ≥ 1. Then the matchings polynomial μ(G, x) of G is defined by

μ(G, x) = ∑_{k≥0}(−1)^{k}p(G, k)x^{n−2k}.

For instance, the matchings polynomial for the path P_{n} with n vertices is [8, p. 2]

μ(P_{n}, x) = ∑_{k≥0}(−1)^{r}\binom{n − k}{k}x^{2n−k}.

For more information on the matchings polynomial, see [8, Chap. 1]. Here we give the Pfaffian transform of a certain family of sequences in terms of this polynomial.

Proposition 33. Suppose a, b, and c ≠ 0 are constants and set a_{1} = 1, a_{2} = a, and a_{3} = a^{2} + b. For all n ≥ 4, set a_{n} = aa_{n−1} + ba_{n−2} + ca_{n−3}. Then

ã_{n} = c^{n+1}μ (P_{n−1}, \frac{b + 1}{c}) = c^{n+1} ∑_{k≥0}(−1)^{k}\binom{n − 1 − k}{k} (\frac{b + 1}{c})^{n−1−2k}

for all n ≥ 1.

Proof. First note that

red(S_{n}) = (\begin{matrix}0 & b + 1 & c & 0 & ⋯ & 0 & 0 & 0 & 0 \\ −b − 1 & 0 & b + 1 & c & ⋯ & 0 & 0 & 0 & 0 \\ −c & −b − 1 & 0 & b + 1 & ⋯ & 0 & 0 & 0 & 0 \\ 0 & −c & −b − 1 & 0 & ... & 0 & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ... & ... & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & ... & 0 & b + 1 & c & 0 \\ 0 & 0 & 0 & 0 & ⋯ & −b − 1 & 0 & b + 1 & 0 \\ 0 & 0 & 0 & 0 & ⋯ & −c & −b − 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & ⋯ & 0 & 0 & −1 & 0 \end{matrix}) .

Now let \sqrt{c} be any square root of c and observe that

red(S_{n}) = (\sqrt{c}I)T_{n}(\sqrt{c}I)^{t},  (19)

where

T_{n} = (\begin{matrix}0 & \frac{b+1}{c} & 1 & 0 & ⋯ & 0 & 0 & 0 & 0 \\ −\frac{b+1}{c} & 0 & \frac{b+1}{c} & 1 & ⋯ & 0 & 0 & 0 & 0 \\ −1 & −\frac{b+1}{c} & 0 & \frac{b+1}{c} & ⋯ & 0 & 0 & 0 & 0 \\ 0 & −1 & −\frac{b+1}{c} & 0 & ... & 0 & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ... & ... & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & ... & 0 & \frac{b+1}{c} & 1 & 0 \\ 0 & 0 & 0 & 0 & ⋯ & −\frac{b+1}{c} & 0 & \frac{b+1}{c} & 0 \\ 0 & 0 & 0 & 0 & ⋯ & −1 & −\frac{b+1}{c} & 0 & c \\ 0 & 0 & 0 & 0 & ⋯ & 0 & 0 & −c & 0 \end{matrix}) .

To compute Pf(T_{n}), first notice that any perfect matching in K_{2n} which contributes to Pf(T_{n}) must include the edge (2n−1, 2n), which will cross no other edges in the matching. Therefore

Pf(T_{n}) = cf_{2n−2}^{0} (\frac{b + 1}{c}, 1) .  (20)

We now see that Pf(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}, …, v_{n−1}. In particular, given a perfect matching α ⊨ C_{2n−2}^{2}, the associated matching α′ in P_{n−1} consists of those edges (v_{i}, v_{i+1}) for which (2i − 1, 2i + 1) is an edge in α. Since α is a matching in C_{2n−2}^{2}, no two edges in α′ share a vertex, so α′ 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 α′ is a matching in P_{n−1}. To construct α, first construct edges (2i − 1, 2i + 1) for each edge (v_{i}, v_{i+1}) in α′. Now suppose 2i − 1 is not yet incident with any edges in our partial α. If (2i − 2, 2i − 1) were an edge in α, then α 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 α 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 α. Then we must already have added (2i − 1, 2i + 1) or (2i − 3, 2i − 1) to α. In the first case, adding (2i − 2, 2i) to α 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 α. By similar reasoning, in the second case we must include (2i − 2, 2i) in α. At this point every vertex in C_{2n−2}^{2} is incident with exactly one edge in α, so α is a perfect matching. Moreover, by construction α′ is the perfect matching in P_{n−1} associated with α.

To complete the proof, suppose α is a perfect matching in C_{2n−2}^{2} and α′ is the associated matching in P_{n−1}. If α′ has k edges then α 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 α, and all crossings in α are of this type. Moreover, the only edges in α 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

f_{2n−2}^{0} (\frac{b + 1}{c}, 1) = ∑_{k≥0}(−1)^{k}p(P_{n−1}, k) (\frac{b + 1}{c})^{n−1−2k} .  (21)

Putting everything together, we have

ã_{n} = Pf(red(S_{n}))  (by Prop. 9)
= Pf((\sqrt{c}I)T_{n}(\sqrt{c}T)^{t})  (by (19))
= det(\sqrt{c}I) Pf(T_{n})  (by Prop. 3)
= c^{n+1}f_{2n−2}^{0} (\frac{b+1}{c}, 1)  (by (20))
= c^{n+1}μ (P_{n−1}, \frac{b+1}{c})  (by (21)),

as desired.

7 Acknowledgment

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

References

[1] M. Aigner, Motzkin numbers, European J. Combin. 19 (1998), 663–675.

[2] M. Aigner, Catalan-like numbers and determinants, J. Combin. Theory Ser. A 87 (1999), 33–51.

[3] R. A. Brualdi and S. Kirkland, Aztec diamonds and digraphs, and Hankel determinants of Schröder numbers, J. Combin. Theory Ser. B 94 (2005), 334–351.

[4] M. Chamberland and C. French, Generalized Catalan numbers and generalized Hankel transformations, J. Integer Seq. 10 (2007), Article 07.1.1.

[5] A. Cvetković, P. Rajković, and M. Ivković, Catalan numbers, and Hankel transform, and Fibonacci numbers, J. Integer Seq. 5 (2002), Article 02.1.3.

[6] M. Desainte-Catherine and X. G. Viennot, Enumeration of certain Young tableaux with bounded height, in Combinatoire Énumérative (Montreal 1985), Lect. Notes. in Math., Vol. 1234, Springer, 1986, pp. 58–67.

[7] I. M. Gessel and G. Xin, The generating function of ternary trees and continued fractions, Electron. J. Combin. 13 (2006), Article #R53, available electronically at

http://www.combinatorics.org/Volume 13/Abstracts/v13/v13i1r53.html.

[8] C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, 1993.

[9] B. Gordon, A proof of the Bender-Knuth conjecture, Pacific J. Math. 108 (1983), 99– 113.

[10] S. Hirschman and V. Reiner, Note on the Pfaffian matrix-tree theorem, Graphs Combin. 20 (2004), 59–63.

[11] J. W. Layman, The Hankel transform and some of its properties, J. Integer Seq. 4 (2001), Article 01.1.5.

[12] M. Z. Spivey and L. L. Steil, The k-binomial transforms and the Hankel transform, J. Integer Seq. 9 (2006), Article 06.1.1.

[13] R. P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1997.

[14] J. R. Stembridge, Nonintersecting paths, Pfaffians, and plane partitions, Adv. Math. 83 (1990), 96–131.

[15] R. A. Sulanke and G. Xin, Hankel determinants for some common lattice paths, Adv. in Appl. Math. 40 (2008), 149–167.

[16] U. Tamm, Some aspects of Hankel matrices in coding theory and combinatorics, Electron. J. Combin. 8 (2001), Article #A1, available electronically at

http://www.combinatorics.org/Volume 8/Abstracts/v8i1a1.html.

2000 Mathematics Subject Classification: Primary 15A15; Secondary 05C50, 05C70.

Keywords: Pfaffian, skew-symmetric matrix, Toeplitz matrix, transfer matrix method, perfect matching, Hankel transform.

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

Received June 8 2008; revised version received December 16 2008. Published in Journal of Integer Sequences, December 17 2008.

Return to Journal of Integer Sequences home page.