\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[margin=3cm,top=4cm,footskip=2cm,nohead]{geometry}
\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,amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf
The $k$-Binomial Transforms and the \\
\vskip .1in
Hankel Transform}
\vskip 1cm
\large
Michael Z. Spivey \\
Department of Mathematics and Computer Science\\
University of Puget Sound\\
Tacoma, Washington 98416-1043 \\
USA \\
\href{mailto:mspivey@ups.edu}{\tt mspivey@ups.edu}\\
\bigskip
Laura L. Steil \\
Department of Mathematics and Computer Science \\
Samford University \\
Birmingham, Alabama 35229 \\
USA \\
\href{mailto:llsteil@samford.edu}{\tt llsteil@samford.edu} \\
\end{center}
\vskip .2 in
\begin{abstract}
We give a new proof of the invariance of the Hankel transform under the
binomial transform of a sequence. Our method of proof leads to three
variations of the binomial transform; we call these the $k$-binomial
transforms. We give a simple means of constructing these transforms
via a triangle of numbers. We show how the exponential generating
function of a sequence changes after our transforms are applied, and we
use this to prove that several sequences in the On-Line Encyclopedia of
Integer Sequences are related via our transforms. In the process, we
prove three conjectures in the OEIS. Addressing a question of Layman,
we then show that the Hankel transform of a sequence is invariant under
one of our transforms, and we show how the Hankel transform changes
after the other two transforms are applied. Finally, we use these
results to determine the Hankel transforms of several integer
sequences. \end{abstract}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]
%\usepackage{amsmath}
%\usepackage{amssymb}
%\usepackage{graphics}
%\usepackage{amsthm}
%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}{Lemma}
%\newtheorem{corollary}{Corollary}
%\bibliographystyle{plain}
\section{Introduction}
Given a sequence $A = \{a_0, a_1, \ldots \}$,
define the {\it binomial transform $B$ of a sequence $A$}
to be the sequence $B(A) = \{b_n\}$, where $b_n$ is given by
\[
b_n = \sum_{i=0}^n \binom{n}{i} a_i.
\]
Define the {\it Hankel matrix of order $n$ of $A$} to be the $(n+1) \times (n+1)$ upper left submatrix of
\[
\begin{bmatrix}
a_0 & a_1 & a_2 & a_3 & \cdots \\
a_1 & a_2 & a_3 & a_4 & \cdots \\
a_2 & a_3 & a_4 & a_5 & \cdots \\
a_3 & a_4 & a_5 & a_6 & \cdots \\
\vdots & \vdots & \vdots & \vdots & \ddots
\end{bmatrix}.
\]
Let $h_n$ denote the determinant of the Hankel matrix of order $n$.
Then define the {\it Hankel transform $H$ of $A$} to be the sequence
$H(A) = \{h_0, h_1, h_2, \ldots, \}$. For example, the Hankel matrix
of order 3 of the derangement numbers, $\{D_n\} = \{1, 0, 1, 2, 9, 44,
265, \ldots\}$, is
\[
\begin{bmatrix}
1 & 0 & 1 & 2 \\
0 & 1 & 2 & 9 \\
1 & 2 & 9 & 44 \\
2 & 9 & 44 & 265 \\
\end{bmatrix}.
\]
The determinant of this matrix is 144, which is $(0!)^2 (1!)^2 (2!)^2
(3!)^2$. Flajolet \cite{Fla82} and Radoux \cite{Rad91} have shown that
the Hankel transform of the derangement numbers is $\{\prod_{i=0}^n
(n!)^2\}$.
Although the determinants of Hankel matrices had been studied before,
the term ``Hankel transform" was introduced in 2001 by Layman
\cite{Lay01}. Other recent papers involving Hankel determinants
include those by Ehrenborg \cite{Ehr00}, Peart \cite{Pea00}, and Woan
and Peart \cite{WoPe02}.
Layman \cite{Lay01} proves that the Hankel transform is invariant under
the binomial transform, in the sense that $H(B(A)) = H(A)$. He also
proves that the Hankel transform is invariant under the invert
transform (see the On-Line Encyclopedia of Integer Sequences
\cite{Slo05} for the definition), and he asks if there are other
transforms for which the Hankel transform is invariant. This article
partly addresses Layman's question. We provide a new proof of the
invariance of the Hankel transform under the binomial transform. Our
method of proof generalizes to three variations of the binomial
transform that we call the {\it $k$-binomial transform}, the {\it
rising $k$-binomial transform}, and the {\it falling $k$-binomial
transform}. Collectively, we refer to these as the {\it $k$-binomial
transforms}. (There should be no confusion in context.) We give a
simple means of constructing these transforms using a triangle of
numbers, and we provide combinatorial interpretations of the transforms
as well. We show how the exponential generating function of a sequence
changes after applying our transforms, and we use these results to
prove that several sequences in the On-Line Encyclopedia of Integer
Sequences (OEIS) \cite{Slo05} are related by the transforms. In the
process, we prove three conjectures listed in the OEIS concerning the
binomial mean transform. Then, giving an answer to Layman's question,
we show that the Hankel transform is invariant under the falling
$k$-binomial transform. The Hankel transform is not invariant under
the $k$-binomial transform and the rising $k$-binomial transform, but
we give a formula showing how the Hankel transform changes under these
two transforms. These results, together with our proofs of
relationships between sequences in the OEIS, determine the Hankel
transforms of several sequences in the OEIS.
(Unfortunately, this is some discrepancy in the literature in the
definitions of the Hankel determinant and the binomial transform of an
integer sequence. The definitions of the Hankel determinant in Layman
\cite{Lay01} and in Ehrenborg \cite{Ehr00} are slightly different from
each other, and ours is slightly different from both of these. As many
sequences of interest begin indexing with 0, we define the Hankel
determinant and the Hankel transform so that the first elements in the
sequences $A$ and $H(A)$ are indexed by 0. Layman's definition begins
indexing $A$ and $H(A)$ by 1, whereas Ehrenborg's definition results in
indexing $A$ beginning with 0 and $H(A)$ beginning with 1. Our
definition of the binomial transform is that used by Layman
\cite{Lay01} and the OEIS \cite{Slo05}. Somewhat different definitions
are given in Knuth \cite{Kn98} (p. 136) and by MathWorld
\cite{MW_BinTrans}.)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Invariance of the Hankel transform under the binomial transform}
Layman \cite{Lay01} proves that $H(B(A)) = H(A)$ for any sequence $A$.
He does this by showing that the Hankel matrix of order $n$ of $B(A)$
can be obtained by multiplying the Hankel matrix of order $n$ of $A$ by
certain upper and lower triangular matrices, each of which have
determinant 1.
We present a new proof of this result. Our proof technique suggests
generalizations of the binomial transform, which we discuss in
subsequent sections. We require the following lemma.
\begin{lemma}
\label{bintrans}
Given a sequence $A = \{a_0, a_1, a_2, \ldots \}$, create a triangle of numbers $T$ using the following rule:
\begin{enumerate}
\item The left diagonal of the triangle consists of the elements of $A$.
\item Any number off the left diagonal is the sum of the number to its left and the number diagonally above it to the left.
\end{enumerate}
Then the sequence on the right diagonal is the binomial transform of $A$.
\end{lemma}
For example, the binomial transform of the derangement numbers is the
factorial numbers \cite{Lay01}. Figure~\ref{DerangTriangle}
illustrates how the factorial numbers can be generated from the
derangement numbers using the triangle described in
Lemma~\ref{bintrans}.
\begin{figure}[h]
\begin{center}
\begin{tabular}{ccccccccccccc}
& & & & & & 1 & & & & & & \\
& & & & & 0 & & 1 & & & & & \\
& & & & 1 & & 1 & & 2 & & & & \\
& & & 2 & & 3 & & 4 & & 6 & & & \\
& & 9 & & 11 & & 14 & & 18 & & 24 & & \\
& 44 & & 53 & & 64 & & 78 & & 96 & & 120 & \\
265 & & 309 & & 362 & & 426 & & 504 & & 600 & & 720
\end{tabular}
\caption{Derangement triangle}
\label{DerangTriangle}
\end{center}
\end{figure}
Although they do not use the term {\it binomial transform},
Lemma~\ref{bintrans} is essentially proven by Graham, Knuth, and
Patashnik \cite{GrKnPa94} (pp. 187--192). We present a different
proof, one that allows us to prove similar results for the $k$-binomial
transforms we discuss in subsequent sections.
\begin{proof}
Let $t_n$ be the $n^{th}$ element on the right diagonal of the
triangle. By construction of the triangle, we can see from
Figure~\ref{PathTriangle} that the number of times element $a_i$
contributes to the value of $t_n$ is the number of paths from $a_i$ to
$t_n$. To move from $a_i$ to $t_n$ requires $n$ path segments, $i$ of
which move directly to the right. Thus there are $\binom{n}{i}$ ways
to choose which of the $n$ ordered segments are the rightward-moving
segments, and the down segments are completely determined by this
choice. Therefore the contribution of $a_i$ to $t_n$ is $\binom{n}{i}
a_i$, and the value of $t_n$, in terms of the elements on the left
diagonal, is $\sum_{i=0}^{n} \binom{n}{i} a_i$. But this is the
definition of the binomial transform, making the right diagonal of the
triangle the binomial transform of $A$. \end{proof}
\begin{figure}[h]
\begin{center}
\includegraphics{spivey-diagram.eps}
\caption{Directed graph underlying the binomial transform}
\label{PathTriangle}
\end{center}
\end{figure}
The binomial transform has the following combinatorial interpretation:
If $a_n$ represents the number of arrangements of $n$ labeled objects
with some property $P$, then $b_n$ represents the number of ways of
dividing $n$ labeled objects into two groups such that the first group
has property $P$. In terms of the derangement and factorial numbers,
then, as $D_n$ is the number of permutations of $n$ ordered objects in
which no object remains in its original position, $n!$ is the number of
ways that one can divide $n$ labeled objects into two groups, order the
objects in the first group, and then permute the first group objects so
that none remains in its original position.
The numbers in the triangle described in Lemma~\ref{bintrans}, not just
the right and left diagonals, can also have combinatorial
interpretations. For instance, the triangle of numbers in
Figure~\ref{DerangTriangle} is discussed as a combinatorial entity in
its own right in another article by the first author \cite{Spi05}. The
number in row $i$, position $j$, in the triangle is the number of
permutations of $i$ ordered objects such that every object after $j$
does not remain in its original position.
We now give our proof of Layman's result.
\begin{theorem}
\label{Hankbin}
(Layman) The Hankel transform is invariant under the binomial transform.
\end{theorem}
\begin{proof}
We define a procedure for transforming the Hankel matrix of order $n$
of a sequence $A$ to the Hankel matrix of order $n$ of $B(A)$ using
only matrix row and column addition. While perhaps more complicated
than Layman's proof, ours has the virtue of being easily modified to
give proofs for the Hankel transforms of the $k$-binomial transforms
that we discuss subsequently. The procedure is as follows:
\begin{enumerate}
\item Given a sequence $A = \{a_0, a_1, \ldots \}$, create the triangle of numbers described in Lemma~\ref{bintrans}, where $T_{i,j}$ is the $(i,j)^{th}$ entry in the triangle.
\item Let $T_n$ be the following matrix consisting of numbers from the left diagonal of $T$:
\[
\begin{bmatrix}
T_{0,0} & T_{1,0} & T_{2,0} & \cdots & T_{n,0} \\
T_{1,0} & T_{2,0} & T_{3,0} & \cdots & T_{n+1,0} \\
T_{2,0} & T_{3,0} & T_{4,0} & \cdots & T_{n+2,0} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
T_{n,0} & T_{n+1,0} & T_{n+2,0} & \cdots & T_{2n,0} \\
\end{bmatrix}.
\]
Since $a_i = T_{i,0}$, $T_n$ is the Hankel matrix of order $n$ of $A$.
\item Then apply the following transformations to $T_n$, where rows and columns of the matrix are indexed beginning with 0.
\begin{enumerate}
\item Let $i$ range from 1 to $n$.
During stage $i$, for each row $j \geq i$, add row $j-1$ to row $j$ and replace row $j$ with the result.
\item Then let $i$ again range from 1 to $n$.
During stage $i$, for each column $j \geq i$, add column $j-1$ to column $j$ and replace column $j$ with the result.
\end{enumerate}
\end{enumerate}
Claim 1: After stage $i$ in 3(a), row $m$ of the matrix is of the following form:
\[
\begin{bmatrix}
T_{m,m} & T_{m+1,m} & \cdots & T_{n+m,m}
\end{bmatrix},
\mbox{ if $m \leq i$};
\]
\[
\begin{bmatrix}
T_{m,i} & T_{m+1,i} & \cdots & T_{n+m,i}
\end{bmatrix},
\mbox{ if $m > i$}.
\]
The claim is clearly true initially, when $i=0$. Now, assume the claim
is true for all values of $i$ from $0$ to $k-1$. Then, in stage $i=k$,
the only rows that change are rows $k, k+1, \ldots, n$. Row $m$, for
$m \geq k$, is the sum of rows $m$ and $m-1$ from the previous
iteration:
\[
\begin{bmatrix}
T_{m,k-1} + T_{m-1,k-1} & T_{m+1,k-1} + T_{m,k-1} & \cdots & T_{n+m,k-1} + T_{n+m-1,k-1}
\end{bmatrix}.
\]
But, by the definition of $T$, $T_{i,j} + T_{i-1,j} = T_{i,j+1}$. Thus this row is equal to
\[
\begin{bmatrix}
T_{m,k} & T_{m+1,k} & \cdots & T_{n+m,k}
\end{bmatrix},
\]
proving the claim.
After the transformations in 3(a) are applied, then, we have the matrix
\[
\begin{bmatrix}
T_{0,0} & T_{1,0} & T_{2,0} & \cdots & T_{n,0} \\
T_{1,1} & T_{2,1} & T_{3,1} & \cdots & T_{n+1,1} \\
T_{2,2} & T_{3,2} & T_{4,2} & \cdots & T_{n+2,2} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
T_{n,n} & T_{n+1,n} & T_{n+2,n} & \cdots & T_{2n,n} \\
\end{bmatrix}.
\]
Claim 2: After stage $i$ in 3(b), column $m$ of the matrix is of the following form:
\[
\begin{bmatrix}
T_{m,m} & T_{m+1,m+1} & \cdots & T_{n+m,n+m}
\end{bmatrix}^T,
\mbox{ if $m \leq i$};
\]
\[
\begin{bmatrix}
T_{m,i} & T_{m+1,i+1} & \cdots & T_{n+m,n+i}
\end{bmatrix}^T,
\mbox{ if $m > i$}.
\]
The proof is almost the same as that for Claim 1. The claim is clearly
true for $i=0$. Assume the claim is true for all values of $i$ from 0
to $k-1$. In stage $i=k$, the only columns that change are columns $k,
k+1, \ldots, n$. Column $m$, for $m \geq k$, is the sum of columns $m$
and $m-1$ from the previous iteration:
\[
\begin{bmatrix}
T_{m,k-1} + T_{m-1,k-1} & T_{m+1,k} + T_{m,k} & \cdots & T_{n+m,n+k-1} + T_{n+m-1,n+k-1}
\end{bmatrix}^T.
\]
Again, by the definition of $T$, $T_{i,j} + T_{i-1,j} = T_{i,j+1}$. Thus this column is equal to
\[
\begin{bmatrix}
T_{m,k} & T_{m+1,k+1} & \cdots & T_{n+m,n+k}
\end{bmatrix}^T,
\]
which proves the claim. \\
After applying the transformations in 3(b), then, we have the matrix
\[
\begin{bmatrix}
T_{0,0} & T_{1,1} & T_{2,2} & \cdots & T_{n,n} \\
T_{1,1} & T_{2,2} & T_{3,3} & \cdots & T_{n+1,n+1} \\
T_{2,2} & T_{3,3} & T_{4,4} & \cdots & T_{n+2,n+2} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
T_{n,n} & T_{n+1,n+1} & T_{n+2,n+2} & \cdots & T_{2n,2n} \\
\end{bmatrix}.
\]
But this is the Hankel matrix of order $n$ of $B(A)$, as $B(A)$ is the
right diagonal of triangle $T$. Since the only matrix manipulations we
used were adding a row to another row and adding a column to another
column, and the determinant of a matrix is invariant under these
operations \cite{Bre05} (p. 262), the determinant of the Hankel matrix
of order $n$ of $A$ is equal to the determinant of the Hankel matrix of
order $n$ of $B(A)$.
\end{proof}
The operations described in the proof of Theorem~\ref{Hankbin}, when
done in the order prescribed by the procedure, have a simple
interpretation in terms of the triangle. Adding a row to another row
shifts a left diagonal in the triangle one place to the right, and
adding a column to another column shifts a right diagonal one place to
the right. We can see this in the case of the Hankel matrix of order 2
of the derangement numbers by a comparison of
Figure~\ref{DerangTriangle} and the sequence of matrices arising from
the procedure described in the proof of Theorem~\ref{Hankbin}.
\[
\begin{bmatrix}
1 & 0 & 1 \\
0 & 1 & 2 \\
1 & 2 & 9
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 0 & 1 \\
1 & 1 & 3 \\
1 & 3 & 11
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 0 & 1 \\
1 & 1 & 3 \\
2 & 4 & 14
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
2 & 6 & 18
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 1 & 2 \\
1 & 2 & 6 \\
2 & 6 & 24
\end{bmatrix}.
\]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The $k$-binomial transforms}
We now consider three variations of the binomial transform. All three
transforms take two parameters: the input sequence $A$ and a scalar
$k$.
The {\it $k$-binomial transform $W$ of a sequence $A$} is the sequence $W(A,k) = \{w_n\}$, where $w_n$ is given by
\[
w_n = \left\{ \begin{array}{ll}
\sum_{i=0}^n \binom{n}{i} k^n a_i = k^n \sum_{i=0}^n \binom{n}{i} a_i, & \mbox{ if } k \neq 0 \mbox{ or } n \neq 0; \\
a_0, & \mbox{ if } k=0, n = 0.\\
\end{array}
\right.
\]
The {\it rising $k$-binomial transform $R$ of a sequence $A$} is the sequence $R(A,k) = \{r_n\}$, where $r_n$ is given by
\[
r_n = \left\{ \begin{array}{ll}
\sum_{i=0}^n \binom{n}{i} k^i a_i, & \mbox{ if } k \neq 0; \\
a_0, & \mbox{ if } k = 0.
\end{array}
\right.
\]
The {\it falling $k$-binomial transform $F$ of a sequence $A$} is the sequence $F(A,k) = \{f_n\}$, where $f_n$ is given by
\[
f_n = \left\{ \begin{array}{ll}
\sum_{i=0}^n \binom{n}{i} k^{n-i} a_i, & \mbox{ if } k \neq 0; \\
a_n, & \mbox{ if } k = 0.
\end{array}
\right.\]
The case $k = 0$ must be dealt with separately because $0^0$ would
occur in the formulas otherwise. Our definitions effectively take
$0^0$ to be 1. These turn out to be ``good" definitions, in the sense
that all the results discussed subsequently hold under our definitions
for the $k=0$ case. When $k=0$, the $k$-binomial transform of $A$ is
the sequence $\{a_0, 0, 0, 0, \ldots \}$, the rising $k$-binomial
transform of $A$ is $\{a_0, a_0, a_0, \ldots \}$, and the falling
$k$-binomial transform is the identity transform.
The $k$-binomial transform when $k=1/2$ is of special interest; this is
the {\it binomial mean transform}, defined in the OEIS \cite{Slo05},
sequence A075271.
When $k$ is a positive integer, these variations of the binomial
transform all have combinatorial interpretations similar to that of the
binomial transform, although, unlike the binomial transform, they have
a two-dimensional component. If $a_n$ represents the number of
arrangements of $n$ labeled objects with some property $P$, then $w_n$
represents the number of ways of dividing $n$ objects such that
\begin{itemize}
\item In one dimension, the $n$ objects are divided into two groups so that the first group has property $P$.
\item In a second dimension, the $n$ objects are divided into $k$ labeled groups.
\end{itemize}
The interpretation of the second dimension could be something as simple
as a coloring of each object from a choice of $k$ colors, independent
of the division of the objects in the first dimension. For example, if
the input sequence is the derangement numbers, $w_n$ is the number of
ways of dividing $n$ labeled objects into two groups such that the
objects in the first group are deranged and each of the $n$ objects has
been colored one of $k$ colors, independently of the initial division
into two groups. With this interpretation of $w_n$ in mind, $r_n$
represents the number of ways of dividing $n$ labeled objects into two
groups such that the first group has property $P$ and each object in
the first group is further placed into one of $k$ labeled groups (e.g.,
colored using one of $k$ colors). Similarly, $f_n$ represents the
number of ways of dividing $n$ labeled objects into two groups such
that the first group has property $P$ and the objects in the second
group are further placed into $k$ labeled groups (e.g., colored using
one of $k$ colors).
Each of the $k$-binomial transforms can also be replicated via a triangle like that described in Lemma~\ref{bintrans}.
\begin{theorem}
\label{k-binom}
Given a sequence $A = \{a_0, a_1, a_2, \ldots \}$,
\begin{enumerate}
\item Create a triangle of numbers so that the left diagonal consists
of the elements of $A$, and any number off the left diagonal is $k$
times the sum of the numbers to its left and diagonally above it to the
left. Then the right diagonal is the $k$-binomial transform $W(A,k)$
of $A$.
\item Create a triangle of numbers so that the left diagonal consists
of the elements of $A$, and any number off the left diagonal is the sum
of the number diagonally above it to the left and $k$ times the number
to its left. Then the right diagonal is the rising $k$-binomial
transform $R(A,k)$ of $A$.
\item Create a triangle of numbers so that the left diagonal consists
of the elements of $A$, and any number off the left diagonal is the sum
of the number to its left and $k$ times the number diagonally above it
to the left. Then the right diagonal is the falling $k$-binomial
transform $F(A,k)$ of $A$.
\end{enumerate}
\end{theorem}
For example, applying the procedure in Part 1 with $k=2$ to the derangement numbers (sequence A000166) yields the triangle of numbers in Figure~\ref{W_DT}.
\begin{figure}[h]
\begin{center}
\begin{tabular}{ccccccccccccc}
& & & & & & 1 & & & & & & \\
& & & & & 0 & & 2 & & & & & \\
& & & & 1 & & 2 & & 8 & & & & \\
& & & 2 & & 6 & & 16 & & 48 & & & \\
& & 9 & & 22 & & 56 & & 144 & & 384 & & \\
& 44 & & 106 & & 256 & & 624 & & 1536 & & 3840 & \\
265 & & 618 & & 1448 & & 3408 & & 8064 & & 19,200 & & 46,080
\end{tabular}
\caption{Derangement triangle with 2-binomial transform}
\label{W_DT}
\end{center}
\end{figure}
As we shall see, the sequence on the right diagonal is the double
factorial numbers (sequence A000165), the 2-binomial transform of the
derangement numbers.
We now prove Theorem~\ref{k-binom}.
\begin{proof}
Suppose $k \neq 0$.
({\it Part 1}.) The proof is similar to that of Lemma~\ref{bintrans}.
Let $t_n$ be the $n^{th}$ element on the right diagonal of the
triangle. There are still $n$ path segments from $a_i$ to $t_n$;
however, traversing a path segment now incurs a multiplicative factor
of $k$ rather than the understood factor of 1 incurred with the
binomial transform. Thus each path from $a_i$ to $t_n$ contributes
$k^n a_i$ to the value of $t_n$. With $i$ moves to the right, there
are still $\binom{n}{i}$ different paths from $a_i$ to $t_n$; thus the
total contribution from $a_i$ to the value of $t_n$ is $\binom{n}{i}
k^n a_i$. Therefore, $t_n = \sum_{i=0}^n \binom{n}{i} k^n a_i$, the
$n^{th}$ element of $W(A,k)$.
({\it Part 2}.) The proof is similar to that of Part 1. The
difference is that the multiplicative factor of $k$ only appears on
moves to the right, not moves down. With $i$ rightward-moving path
segments, the contribution from $a_i$ along one path to $t_n$ is thus
$k^i a_i$. The total contribution from $a_i$ over all paths is
therefore $\binom{n}{i} k^i a_i$, and we have $t_n = \sum_{i=0}^n
\binom{n}{i} k^i a_i$, the $n^{th}$ element of $R(A,k)$.
({\it Part 3}.) The proof is identical to that of Part 2, except that
the multiplicative factor of $k$ occurs on down path segments rather
than on right-moving segments. As there are $n-i$ down path segments
from $a_i$ to $t_n$, we have $t_n = \sum_{i=0}^n \binom{n}{i} k^{n-i}
a_i$, the $n^{th}$ element of $F(A,k)$.
Now, suppose $k=0$. For the triangle described in Part 1, every path
from the left diagonal to $t_n$ is a zero path, except for the empty
path from $a_0$ to $t_0$. Thus $t_0 = a_0$, and $t_n = 0$ for $n \neq
0$. For the triangle in Part 2, the only nonzero path to $t_n$ from
the left diagonal is the one straight down from $a_0$; thus $t_n = a_0$
for all $n$. For Part 3, the only nonzero path to $t_n$ from the left
diagonal is the one straight right from $a_n$; therefore, $t_n = a_n$
for each $n$.
\end{proof}
There are also some nice relationships between our transforms, the
binomial transform, and the inverse binomial transform. Given a
sequence $A = \{a_0, a_1, \ldots\}$, the {\it inverse binomial
transform of $A$} is defined to be the sequence $B^{-1}(A) = \{c_n\}$,
where $c_n$ is given by
\[
c_n = \sum_{i=0}^n \binom{n}{i} (-1)^{n-i} a_i.
\]
It is easy to show that $B^{-1}(B(A)) = B(B^{-1}(A)) = A$.
For $k \in \mathbb{Z}^+$, let $B^k(A)$ denote $k$ successive
applications of the binomial transform; i.e., $B^k(A) = B(B(\cdots B(A)
\cdots))$, where $B$ occurs $k$ times. For $k \in \mathbb{Z}^-$, let
$B^k(A)$ denote $k$ successive applications of the inverse binomial
transform. Finally, let $B^0(A)$ denote the identity transform. Then
we have
\begin{theorem}
\label{falling_equiv}
If $k \in \mathbb{Z}$, $B^k(A) = F(A,k)$. In other words, $k$ successive applications of the binomial transform (or the inverse binomial transform, if $k \in \mathbb{Z}^-$) is equivalent to the falling $k$-binomial transform.
\end{theorem}
\begin{proof}
The theorem is clearly true when $k=1$. Assume the theorem is true for values of $k$ from 1 to $m$. Let $b^k_n$ denote the $n^{th}$ element in the sequence $B^k(A)$, and let $f^k_n$ denote the $n^{th}$ element in the sequence $F(A,k)$. For $k = m+1$, we have
\begin{align*}
b^{m+1}_n &= \sum_{i=0}^n \binom{n}{i} b^m_i
= \sum_{i=0}^n \binom{n}{i} f^m_i
= \sum_{i=0}^n \binom{n}{i} \sum_{j=0}^i \binom{i}{j} m^{i-j} a_j
= \sum_{j=0}^n \sum_{i=j}^n \binom{n}{i} \binom{i}{j} m^{i-j} a_j \\
&= \sum_{j=0}^n \sum_{i=j}^n \binom{n}{j} \binom{n-j}{i-j} m^{i-j} a_j
= \sum_{j=0}^n \binom{n}{j} a_j \sum_{i=j}^n \binom{n-j}{i-j} m^{i-j}
= \sum_{j=0}^n \binom{n}{j} a_j \sum_{l=0}^{n-j} \binom{n-j}{l} m^l \\
&= \sum_{j=0}^n \binom{n}{j} a_j (m+1)^{n-j}
= f^{m+1}_n.
\end{align*}
The second equality holds by the induction hypothesis, the fifth by
trinomial revision \cite{Ro00} (p. 104), and the second-to-last by the
Binomial Theorem. This proves the relationship for positive values of
$k$. The proof for $k \in \mathbb{Z}^-$ is an almost identical
induction with $k=-1$ as the base case and moving down. When $k=0$ we
have the identity transform in both cases.
\end{proof}
We also have the following relationship
between the $W$, $R$, and $F$ transforms.
\begin{theorem}
\label{WRF}
$W(A,k) = F(R(A,k),k-1)$. In other words, the $k$-binomial transform is equivalent to the composition of the falling $(k-1)$-binomial transform with the rising $k$-binomial transform.
\end{theorem}
\begin{proof}
For $k = 1$, we have $W(A,1) = B(A)$, and $F(R(A,1),0) = F(B(A),0) = B(A)$.
For $k = 0$, $R(A,0) = \{a_0, a_0, a_0, \ldots \}$. Then the $n^{th}$ term of $F(R(A,0),-1)$ is given by
\[
\sum_{i=0}^n \binom{n}{i} (-1)^{n-i} a_0 = a_0 \sum_{i=0}^n \binom{n}{i} (-1)^{n-i}.
\]
But the summation on the right-hand side is 1 if $n=0$ and 0 otherwise \cite{Ro00} (p. 104). Thus $F(R(A,0),-1) = \{a_0, 0, 0, \ldots \}$, which is the sequence $W(A,0)$.
Assuming $k \neq 0$ and $k \neq 1$, the $n^{th}$ term of $F(R(A,k),k-1)$ is given by
\begin{align*}
& \sum_{i=0}^n \binom{n}{i} (k-1)^{n-i} \sum_{j=0}^i \binom{i}{j} k^j a_j
= \sum_{j=0}^n \sum_{i=j}^n \binom{n}{i} \binom{i}{j} (k-1)^{n-i} k^j a_j \\
&= \sum_{j=0}^n \sum_{i=j}^n \binom{n}{j} \binom{n-j}{i-j} (k-1)^{n-i} k^j a_j
= \sum_{j=0}^n \binom{n}{j} k^j a_j \sum_{i=j}^n \binom{n-j}{i-j} (k-1)^{n-i} \\
&= \sum_{j=0}^n \binom{n}{j} k^j a_j \sum_{l=0}^{n-j} \binom{n-j}{l} (k-1)^{n-j-l}
= \sum_{j=0}^n \binom{n}{j} k^j a_j k^{n-j}
= \sum_{j=0}^n \binom{n}{j} k^n a_j.
\end{align*}
The last term is the $n^{th}$ term of $W(A,k)$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Integer sequences related by the $k$-binomial transforms}
\label{sequences}
The $k$-binomial transforms relate many sequences listed in the On-Line
Encyclopedia of Integer Sequences \cite{Slo05}. Several of these
relationships are given in Layman \cite{Lay01}. He lists a number of
tables of integer sequences related by repeated applications of the
binomial transform and thus (via Theorem~\ref{falling_equiv}) by the
falling $k$-binomial transform.
The sequences in Tables~\ref{k-binom_table}, \ref{rising_table}, and
\ref{falling_table} are related or appear to be related by the
$k$-binomial transform, the rising $k$-binomial transform, and the
falling $k$-binomial transform, respectively.
(Table~\ref{falling_table} is short because we do not duplicate
Layman's lists \cite{Lay01}.) The tables were mostly obtained by an
investigation of several of the entries in the OEIS; undoubtedly there
are more sequences related by these transforms. Under the ``status"
column, $K$ (``known") means that we were able to find a reference for
the transform relationship, $P$ (``proved") means that we could not
find a reference for the transform relationship but that it can be
proved via the techniques in the following section, and $C$
(``conjecture") means that we were not able to find a reference for the
transform relationship and were not able to prove it. In addition, the
expression $(E)$ in front of a sequence means that the sequence has
been shifted; its first term has been deleted.
\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|r|c|}
\hline
Status & $A$ & Name (if common) & $k$ & $W(A,k)$ & Name (if common) \\ \hline \hline
$P$ & A000142 & \small Factorial Numbers & 2 & A082032 & \\ \hline
$P$ & A000142 & \small Factorial Numbers & 3 & A097814 & \\ \hline
$P$ & A000142 & \small Factorial Numbers & 4 & A097815 & \\ \hline
$P$ & A000142 & \small Factorial Numbers & 5 & A097816 & \\ \hline
$P$ & A000166 & \small Derangement Numbers & 2 & A000165 & \small Double Factorial Numbers \\ \hline
$P$ & A000166 & \small Derangement Numbers & 3 & A032031 & \small Triple Factorial Numbers \\ \hline
$P$ & A000166 & \small Derangement Numbers & 4 & A047053 & \small Quadruple Factorial Numbers \\ \hline
$P$ & A000166 & \small Derangement Numbers & 5 & A052562 & \small Quintuple Factorial Numbers \\ \hline
$K$ & A000354 & & 1/2 & A000142 & \small Factorial Numbers \\ \hline
$P$ & ($E$)A000354 & & 1/2 & A007680 & \\ \hline
$P$ & A000354 & & 2 & A047053 & \small Quadruple Factorial Numbers \\ \hline
$K$ & A000364 & \small Euler or Secant Numbers & 1/2 & A005799 & \\ \hline
$C$ & A000609 & & 1/2 & A002078 & \\ \hline
$P$ & A001006 & \small Motzkin Numbers & 2 & A003645 & \\ \hline
$C$ & A001653 & & 1/2 & A007052 & \\ \hline
$P$ & A001907 & & 1/2 & A000165 & \small Double Factorial Numbers \\ \hline
$P$ & A002315 & & 1/2 & A007070 & \small NSW Numbers \\ \hline
$P$ & A002426 & \small Central Trinomial Coefficients & 2 & A059304 & \\ \hline
$C$ & A007696 & & 1/2 & A002801 & \\ \hline
$K$ & A075271 & & 1/2 & A075272 & \\ \hline
\end{tabular}
\caption{$k$-binomial transforms}
\label{k-binom_table}
\end{center}
\end{table}
\begin{table}[h!]
\begin{center}
\begin{tabular}{|c|c|c|c|r|c|}
\hline
Status & $A$ & Name (if common) & $k$ & $R(A,k)$ & Name (if common) \\ \hline \hline
$K$ & A000032 & \small Lucas Numbers & 2 & A014448 & \small Even Lucas Numbers, or $L_{3n}$ \\ \hline
$K$ & A000045 & \small Fibonacci Numbers & 2 & A014445 & \small Even Fibonacci Numbers, or $F_{3n}$ \\ \hline
$C$ & ($E$)A000108 & \small Catalan Numbers & 2 & \small A059231 & \\ \hline
$P$ & A000142 & \small Factorial Numbers & 2 & A010844 & \\ \hline
$P$ & A000142 & \small Factorial Numbers & 3 & A010845 & \\ \hline
$P$ & A000142 & \small Factorial Numbers & 4 & A056545 & \\ \hline
$P$ & A000142 & \small Factorial Numbers & 5 & A056546 & \\ \hline
$P$ & A000984 & \small Central Binomial Coefficients & 2 & A084771 & \\ \hline
\end{tabular}
\caption{Rising $k$-binomial transforms}
\label{rising_table}
\end{center}
\end{table}
\begin{table}[h!]
\begin{center}
\begin{tabular}{|c|c|c|c|r|c|}
\hline
Status & $A$ & Name (if common) & $k$ & $F(A,k)$ & Name (if common) \\ \hline \hline
$P$ & A000354 & & 2 & A010844 & \\ \hline
\end{tabular}
\caption{Falling $k$-binomial transforms}
\label{falling_table}
\end{center}
\end{table}
A close examination of Table~\ref{k-binom_table} indicates that a
couple of new binomial transform relationships should exist as well;
these are given in Table~\ref{binom_table}.
\begin{table}[h!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
Status & $A$ & Name (if common) & $B(A)$ & Name (if common) \\ \hline \hline
$P$ & A000354 & & A000165 & Double Factorial Numbers \\ \hline
$P$ & A001907 & & A047053 & Quadruple Factorial Numbers \\ \hline
\end{tabular}
\caption{New binomial transforms}
\label{binom_table}
\end{center}
\end{table}
The relationships in the tables were found primarily by determining
that the first several terms of a sequence correspond to a transform of
another sequence. This, of course, does not constitute proof, and so
the relationships that we were unable to prove and for which we could
not find references remain conjectures. The relationships involving
the Lucas numbers and the Fibonacci numbers are given in Benjamin and
Quinn \cite{BeQu03} (p. 135), and the other known relationships are
mentioned in their respective entries in the OEIS~\cite{Slo05}. The
relationships indicated by a $P$ in the status column we were able to
prove via the generating function method we discuss in the next
section. In particular, the entries in Table~\ref{k-binom_table}
involving the binomial mean transform $W(A,1/2)$ and the input
sequences ($E$)A000354, A001907, and A002315 are listed as conjectures
in the OEIS, and we prove these conjectures in the next section.
Finally, we note that the Hankel transforms of many of these sequences,
such as the derangement numbers, the factorial numbers, and the Catalan
numbers, are known. Thus Tables~\ref{k-binom_table},
\ref{rising_table}, \ref{falling_table}, and \ref{binom_table},
together with Theorems~\ref{Hankfalling}, \ref{Hankrising}, and
\ref{Hank-k} (proved in Section~\ref{Hankel}), contain several results
and conjectures concerning the Hankel transforms of various integer
sequences.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Exponential generating functions of the $k$-binomial transforms}
\label{GenFunc}
The method we use to prove the relationships indicated with a $P$ in
Tables~\ref{k-binom_table}, \ref{rising_table}, \ref{falling_table},
and \ref{binom_table} is that of generating functions. (See Wilf's
text \cite{Wil94} for an extensive discussion of generating functions
and their uses.)
The {\it exponential generating function (egf) $f$ of a sequence $A =
\{a_0, a_1, \ldots \}$} is the formal power series $f(x) = a_0 + a_1 x
+ a_2 x^2/2! + \cdots = \sum_{i=0}^\infty a_i x^i/i!$.
We have the following:
\begin{theorem}
\label{egf}
If $g(x)$ is the exponential generating function of a sequence $A = \{a_0, a_1, \ldots \}$, then:
\begin{enumerate}
\item The exponential generating function of the sequence $F(A,k)$ is $e^{kx} g(x)$.
\item The exponential generating function of the sequence $W(A,k)$ is $e^{kx} g(kx)$.
\item The exponential generating function of the sequence $R(A,k)$ is $e^x g(kx)$.
\end{enumerate}
\end{theorem}
\begin{proof}
For the special case $k=0$, the theorem states that the egf of $F(A,k)$
is $g(x)$, which is the egf of $A$. The theorem gives the egf of
$W(A,k)$ to be $g(0)$, which generates the sequence $\{a_0, 0, 0, 0,
\ldots \}$. The theorem gives the egf of $R(A,k)$ to be $e^x g(0)$,
which generates the sequence $\{a_0, a_0, a_0, \ldots \}$ \cite{Wil94}
(p. 52). These are all consistent with the definitions of the
$k$-binomial transforms when $k=0$. Now, suppose $k \neq 0$.
({\it Part 1.}) It is known \cite{Wil94} (p. 42) that if $f$ is the egf of some sequence $\{a_n\}$ and $h$ is the egf of some sequence $\{b_n\}$, then $fh$ is the egf of the sequence
\begin{equation}
\label{binomconv}
\bigg\{ \sum_{i=0}^n \binom{b}{i} a_i b_{n-i} \bigg\}.
\end{equation}
(This is known as the {\it binomial convolution} of $\{a_n\}$ and $\{b_n\}$.) $F(A,k)$ is, again, the sequence
\[\bigg\{ \sum_{i=0}^n \binom{b}{i} k^{n-i} a_i \bigg\}.
\]
With (\ref{binomconv}) in mind, then, $b_n = k^n$ for each $n$. The egf of the sequence $\{1, k, k^2, \ldots \}$ is $e^{kx}$ \cite{GrKnPa94} (p. 366). Thus the egf of $F(A,k)$ is $e^{kx} g(x)$.
({\it Part 2.})
By definition, $W(A,k) = \{k^n b_n\}$, where $\{b_n\} = B(A)$. From
the proof of Part 1, we know that the egf of $B(A)$ is $e^x g(x)$. By
definition, it is also $\sum_{i=0}^{\infty} b_i x^i / i!$. The egf of
$W(A,k)$ is thus $\sum_{i=0}^{\infty} k^i b_i x^i / i! =
\sum_{i=0}^{\infty} b_i (kx)^i / i! = e^{kx}g(kx)$.
({\it Part 3.}) By Theorem~\ref{WRF}, $W(A,k) = F(R(A,k),k-1)$. Thus
the egf of the sequence on the left must equal that of the sequence on
the right. Letting $G(x)$ denote the egf of $R(A,k)$, we have, by
Parts 1 and 2, $e^{kx} g(kx) = e^{(k-1)x} G(x)$. Thus $G(x) = e^x
g(kx)$. \end{proof}
We now use Theorem~\ref{egf} to prove three relationships listed in
Table~\ref{k-binom_table} that are given as conjectures in the OEIS.
They all involve the binomial mean transform $W(A,1/2)$. The proofs of
the other relationships indicated with a $P$ in
Tables~\ref{k-binom_table}, \ref{rising_table}, \ref{falling_table},
and \ref{binom_table} are similar in flavor to these, and so we do not
prove them explicitly here. In fact, most can be proved simply by
applying Theorem~\ref{egf} to a direct comparison of the egf's given in
the OEIS~\cite{Slo05}.
\begin{corollary}
The binomial mean transform of sequence ($E$)A000354 is sequence A007680.
\end{corollary}
\begin{proof}
The egf of sequence A000354 is given by the OEIS as $e^{-x}/(1-2x)$. The egf of sequence ($E$)A000354 is thus $d/dx[e^{-x}/(1-2x)]$ \cite{Wil94} (p. 40), which is
\[
\frac{e^{-x}(1+2x)}{(1-2x)^2}.
\]
By Theorem~\ref{egf}, the egf of the binomial mean transform of ($E$)A000354 is therefore
\[
e^{x/2}\bigg(\frac{e^{-x/2}(1+x)}{(1-x)^2}\bigg) = \frac{1+x}{(1-x)^2},
\]
which is the egf of sequence A007680 as listed in the OEIS.
\end{proof}
\begin{corollary}
The binomial mean transform of sequence A001907 is sequence A000165 (the double factorial numbers).
\end{corollary}
\begin{proof}
The egf of sequence A001907 is given by the OEIS as $e^{-x}/(1-4x)$. Thus the egf of the binomial mean transform of A001907 is
\[
e^{x/2} \bigg(\frac{e^{-x/2}}{1-2x}\bigg) = \frac{1}{1-2x},
\]
which, according to the OEIS, is the egf of sequence A000165.
\end{proof}
\begin{corollary}
The binomial mean transform of sequence A002315 is sequence A007070.
\end{corollary}
\begin{proof}
The OEIS does not list egf's for these sequences. It does, however,
list two-term recurrence relationships for the sequences, and we can
use these relationships to set up differential equations for the
egf's. Sequence A002315 is generated by the recursive relationship
$a_n = 6a_{n-1} - a_{n-2}$, for $n \geq 2$, with initial values $a_0 =
1$, $a_1 = 7$. This means that the egf $f$ of sequence A002315
satisfies the initial-value problem $f^{\prime \prime} - 6f^{\prime} +
f = 0$, $f(0) = 1$, $f^\prime(0) = 7$ \cite{Wil94} (p. 40). The
characteristic equation for the differential equation is $r^2 - 6r + 1
= 0$, which has solution $r = 3 \pm 2\sqrt{2}$. Thus the solution to
the differential equation, and therefore the egf of A002315, is $f(x) =
c_1 e^{(3+2\sqrt{2})x} + c_2 e^{(3-2\sqrt{2})x}$. Using the initial
conditions, the constants are found to be $c_1 = 1/2 + 1/\sqrt{2}$,
$c_2 = 1/2 - 1/\sqrt{2}$. The recurrence relation for sequence A007070
is given by $a_n = 4a_{n-1} - 2a_{n-2}$, for $n \geq 2$, with $a_0 =
1$, $a_1 = 4$. Using the same method as before, its egf is found to be
$c_1 e^{(2+\sqrt{2})x} + c_2 e^{(2-\sqrt{2})x}$, for the same values of
$c_1$ and $c_2$ found previously. This is also the egf of the binomial
mean transform of sequence A002315:
\[
e^{x/2} \big[c_1 e^{(3/2+\sqrt{2})x} + c_2 e^{(3/2-\sqrt{2})x}\big] = c_1 e^{(2+\sqrt{2})x} + c_2 e^{(2-\sqrt{2})x}.
\]
\end{proof}
Theorem~\ref{egf} can also be used to prove many additional
relationships between sequences in the OEIS involving compositions of
the $k$-binomial transforms. For example, let $D(a,b)$ denote the
sequence of central coefficients of $(1+ax+bx^2)^n$, and let $C$ denote
the sequence of central binomial coefficients (A000984). Then we have
\begin{corollary}
\label{central}
$D(a,b) = F(R(C,\sqrt{b}),a-2\sqrt{b}-1)$.
\end{corollary}
\begin{proof}
The central binomial coefficients have $e^{2x} \mbox{BesselI}(0,2x)$ as
their exponential generating function. Thus the egf of
$F(R(C,\sqrt{b}), a-2\sqrt{b}-1)$ is $e^{(a-2\sqrt{b}-1)x} e^x
e^{2\sqrt{b}x} \mbox{BesselI}(0,2\sqrt{b}x)$, which is $e^{ax}
\mbox{BesselI}(0,2\sqrt{b}x)$. This last expression, according to the
comments under sequence A084770 in the OEIS, is the egf of the central
coefficients of $(1+ax+b x^2)^n$.
\end{proof}
Another example involves the Motzkin numbers (sequence A001006) and the
super-Catalan numbers with the first element deleted (sequence
($E$)A001003). Denoting the sequence of Motzkin numbers by $M$ and the
sequence of super-Catalan numbers by $S$, we have
\begin{corollary}
\label{motzkin}
$(E) S = F(R(M,\sqrt{2}),2-\sqrt{2})$.
\end{corollary}
\begin{proof}
The Motzkin numbers have egf $e^x \mbox{BesselI}(1,2x)/x$. The egf of
$F(R(M,\sqrt{2}),2-\sqrt{2})$ is therefore $e^{(2-\sqrt{2})x} e^x
e^{\sqrt{2}x} \mbox{BesselI}(1,2\sqrt{2}x)/(\sqrt{2}x)$. Simplified,
this is $e^{3x} \mbox{BesselI}(1,2\sqrt{2}x)/(\sqrt{2}x)$, which is the
egf of the super-Catalan numbers with the first element deleted.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Hankel transforms of the $k$-binomial transforms}
\label{Hankel}
At the end of his article \cite{Lay01}, Layman asks if there are
transforms besides the binomial and invert under which the Hankel
transform is invariant. We now address this question for the three
$k$-binomial transforms.
\begin{theorem}
\label{Hankfalling}
The Hankel transform is invariant under the falling $k$-binomial transform. In other words, for a given sequence $A = \{a_0, a_1, \ldots\}$, $H(F(A,k)) = H(A)$.
\end{theorem}
For $k \in \mathbb{Z}$, this follows from Theorems~\ref{Hankbin} and \ref{falling_equiv}. However, the theorem is true for $k \not\in \mathbb{Z}$ as well. Our proof of this entails a slight modification of the proof of Theorem~\ref{Hankbin}.
\begin{proof}
Create a triangle of numbers $T$ by letting the left diagonal consist
of $A$ and every number off of the left diagonal be the sum of the
number to its left and $k$ times the number diagonally above it to the
left. Then, via Theorem~\ref{k-binom}, the right diagonal consists of
the sequence $F(A,k)$. Construct the matrix $T_n$ as in the proof of
Theorem~\ref{Hankbin}. Change the transformation rules in part 3 of
the procedure described in that proof so that one adds $k$ times row
(column) $j-1$ to row (column) $j$ and replaces row (column) $j$ with
the result. By thus mimicking the rule for the creation of the numbers
off the left diagonal of $T$, Claims 1 and 2 in the proof of
Theorem~\ref{Hankbin} still hold. Therefore, the final matrix
resulting from the transformation procedure is the Hankel matrix of
order $n$ of $F(A,k)$. Since the transformation rules only involve
adding a multiple of a row to another row and adding a multiple of a
column to another column, and the determinant is invariant under these
operations, the determinant of the Hankel matrix of order $n$ of
$F(A,k)$ is equal to the determinant of the Hankel matrix of order $n$
of $A$.
\end{proof}
This proof technique works for determining how the Hankel transforms of
$A$, $W(A,k)$, and $R(A,k)$ relate as well. However, the relationships
are more complicated, as the Hankel transform is not invariant under
$W(A,k)$ and $R(A,k)$. We begin with the transform for $R(A,k)$.
\begin{theorem}
\label{Hankrising}
Given a sequence $A = \{a_0, a_1, \ldots \}$, let $H(A) = \{h_n\}$. Then $H(R(A,0)) = \{a_0, 0, 0, \ldots \}$. If $k \neq 0$, $H(R(A,k)) = \{k^{n(n+1)} h_n\}$.
\end{theorem}
\begin{proof}
If $k=0$, then $H_n$ is the $(n+1) \times (n+1)$ matrix whose entries are all $a_0$. Thus $\det(H_0) = a_0$, and for $n > 0$, $\det(H_n) = 0$.
Now, assume $k \neq 0$. Create a triangle of numbers $T$ by letting
the left diagonal consist of $A$ and letting each number off the left
diagonal be the sum of the number diagonally above it to the left and
$k$ times the number to its left. By Theorem~\ref{k-binom}, the right
diagonal of $T$ is $R(A,k)$. Construct the matrix $T_n$ as in the
proofs of Theorems~\ref{Hankbin} and \ref{Hankfalling}, but change the
transformation rule so that one adds row (column) $j-1$ to $k$ times
row (column) $j$ and replaces row (column) $j$ with that result.
Again, Claims 1 and 2 in the proof of Theorem~\ref{Hankbin} hold, and
so the final matrix resulting from the transformation procedure is the
Hankel matrix of order $n$ of $R(A,k)$.
The transformation rule can be broken into two parts: First multiply a
row (column) by $k$. Then replace that row (column) with the sum of
itself and the previous row (column). Multiplying a row of a matrix by
a factor of $k$ changes the determinant by a factor of $k$, while
replacing a row by the sum of itself and another row does not affect
the determinant. The same is true for columns \cite{Bre05} (p. 262).
In order to determine how the Hankel transform changes under the rising
$k$-binomial transform, then, we need to determine the number of times
a row or column is multiplied by a factor of $k$.
According to the transformation procedure, row $i$ is multiplied by a
factor of $k$ in stages $1, 2, \ldots, i$. Thus row $i$ is multiplied
by a factor of $k$ a total of $i$ times. Therefore the total number of
times a row is multiplied by a factor of $k$ is $\sum_{i=0}^n i =
n(n+1)/2$. Similarly, the number of times a column is multiplied by a
factor of $k$ is $n(n+1)/2$. Thus the determinant of the Hankel matrix
of order $n$ of $R(A,k)$ is $k^{n(n+1)}$ times that of the Hankel
matrix of order $n$ of $A$.
\end{proof}
Finally, we have
\begin{theorem}
\label{Hank-k}
Given a sequence $A = \{a_0, a_1, \ldots \}$, let $H(A) = \{h_n\}$. Then $H(W(A,0)) = \{a_0, 0, 0, \ldots \}$. If $k \neq 0$, $H(W(A,k)) = \{k^{n(n+1)} h_n\}$.
\end{theorem}
\begin{proof}
By Theorems~\ref{WRF} and \ref{Hankfalling}, $H(W(A,k)) =
H(F(R(A,k),k-1) = H(R(A,k))$. Alternatively, one can prove this result
with a modification of the proofs of Theorems~\ref{Hankfalling} and
\ref{Hankrising}. The transformation rule would be adding row (column)
$j-1$ to row (column) $j$ and replacing row (column) $j$ with $k$ times
that sum. This is equivalent to first multiplying row (column) $j$ by
a factor of $k$ and then adding $k$ times row (column) $j-1$ to that
and replacing row (column) $j$ with this sum. As we just noted,
multiplying a row or column by a factor of $k$ changes the determinant
by a factor of $k$, while adding a multiple of a row to another row or
a multiple of a column to another column does not change the
determinant. The analysis of the number of times a row or column is
multiplied by a factor of $k$ is exactly the same as that in the proof
of Theorem~\ref{Hankrising}.
\end{proof}
Theorems~\ref{Hankfalling}, \ref{Hankrising}, and \ref{Hank-k},
together the relationships given in Tables~\ref{k-binom_table},
\ref{rising_table}, \ref{falling_table}, and \ref{binom_table}, allow
us to determine the Hankel transforms of several integer sequences.
Given that the factorial numbers (A000142) and the derangement numbers
(A000166) have Hankel transform $\{\prod_{i=0}^n (i!)^2\}$ (sequence
A055209), the Motzkin numbers (A001006) have Hankel transform $\{1, 1,
1, \ldots\}$ (sequence A000012), and the central binomial coefficients
(A000984) and trinomial coefficients (A002426) have Hankel transform
$\{2^n\}$ (sequence A000079) \cite{Lay01}, we have the Hankel
transforms of several integer sequences given in
Table~\ref{Hank_table}.
\begin{table}[h!]
\begin{center}
\begin{tabular}{|c|l|}
\hline
Hankel Transform & Some sequences with this Hankel transform \\ \hline \hline
$\{2^{n(n+1)}\}$ & A003645 \\ \hline
$\{2^{n(n+2)}\}$ & A059304, A084771 \\ \hline
$\{2^{n(n+1)} \prod_{i=0}^n (i!)^2\}$ & A000165, A000354, A010844, A082032 \\ \hline
$\{3^{n(n+1)} \prod_{i=0}^n (i!)^2\}$ & A010845, A032031, A097814 \\ \hline
$\{4^{n(n+1)} \prod_{i=0}^n (i!)^2\}$ & A001907, A047053, A056545, A097815 \\ \hline
$\{5^{n(n+1)} \prod_{i=0}^n (i!)^2\}$ & A052562, A056546, A097816 \\ \hline
\end{tabular}
\caption{Hankel transforms of some integer sequences}
\label{Hank_table}
\end{center}
\end{table}
In addition, Theorems~\ref{Hankfalling}, \ref{Hankrising}, and
\ref{Hank-k} can be used to relate the Hankel transforms of sequences
that are themselves related by compositions of the $k$-binomial
transforms. For example, Theorems~\ref{Hankfalling} and
\ref{Hankrising} applied to Corollary~\ref{central} tell us that the
Hankel transform of the central coefficients of $(1+ax+bx^2)^n$ is
$\{2^n b^{n(n+1)/2}\}$. Applied to Corollary~\ref{motzkin}, they tell
us that the Hankel transform of the super-Catalan numbers with the
first element deleted is $\{2^{n(n+1)/2}\}$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusions}
We have introduced three generalizations of the binomial transform: the
$k$-binomial transform, the rising $k$-binomial transform, and the
falling $k$-binomial transform. We have given a simple method for
constructing these transforms, and we have given combinatorial
interpretations of each of them. We have also shown how the generating
function of a sequence changes after applying one of the transforms.
This allows us to prove that several sequences in the On-Line
Encyclopedia of Integer Sequences are related by one of these
transforms, as well as prove three specific conjectures in the OEIS.
In addition, we have shown how the Hankel transform of a sequence
changes after applying one of the transforms. These results determine
the Hankel transforms of several sequences listed in the OEIS.
We see several areas of further study. One involves continuing to
answer Layman's question \cite{Lay01}. We have proved that the Hankel
transform is invariant under the falling $k$-binomial transform, and he
proves that the Hankel transform is invariant under the binomial and
invert transforms. Are there other interesting transforms under which
the Hankel transform is invariant?
Second, are there variations of our triangle method that would prove
for other transforms $T$ how $H(A)$ and $H(T(A))$ relate?
Third, we conjecture four relationships in Tables~\ref{k-binom_table}
and \ref{rising_table}: Sequences A002078, A007052, and A002801 are the
binomial mean transforms of A000609, A001653, and A007696,
respectively, and sequence A059231 is the rising 2-binomial transform
of ($E$)A000108. (The first three are also conjectured in the OEIS.)
Can these conjectures be proved?
Finally, what sequences, other than those listed in Layman~\cite{Lay01}
and in Tables~\ref{k-binom_table}, \ref{rising_table},
\ref{falling_table}, and \ref{binom_table}, are related by the
$k$-binomial transforms?
\begin{thebibliography}{10}
\bibitem{BeQu03}
Arthur~T. Benjamin and Jennifer~J. Quinn,
\newblock {\em Proofs That Really Count},
\newblock MAA, Washington, D.~C., 2003.
\bibitem{Bre05}
Otto~M. Bretscher,
\newblock {\em Linear Algebra with Applications},
\newblock Pearson Prentice Hall, Upper Saddle River, NJ, third ed., 2005.
\bibitem{Ehr00}
Richard Ehrenborg,
\newblock The Hankel determinant of exponential polynomials,
\newblock {\em Amer. Math. Monthly}, {\bf 107} (2000), 557--560.
\bibitem{Fla82}
Philippe Flajolet,
\newblock On congruences and continued fractions for some classical
combinatorial quantities,
\newblock {\em Discrete Math.}, {\bf 41} (1982), 145--153.
\bibitem{GrKnPa94}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik,
\newblock {\em Concrete Mathematics},
\newblock Addison-Wesley, Reading, MA, second ed., 1994.
\bibitem{Kn98}
Donald E. Knuth,
\newblock {\em The Art of Computer Programming, Vol. III: Sorting and
Searching},
\newblock Addison-Wesley, Reading, MA, second ed., 1998.
\bibitem{Lay01}
John~W. Layman,
\newblock The Hankel transform and some of its properties,
\newblock {\em J. Integer Seq.}, {\bf 4} (2001), Article 01.1.5.
\bibitem{Pea00}
Paul Peart,
\newblock Hankel determinants via Stieltjes matrices,
\newblock {\em Congr. Numer.}, {\bf 144} (2000), 153--159.
\bibitem{Rad91}
Christian Radoux,
\newblock D\'{e}terminant de Hankel construit sur des polyn\^{o}mes li\'{e}s
aux nombres de d\'{e}rangements,
\newblock {\em European J. Combin.}, {\bf 12} (1991) 327--329.
\bibitem{Ro00}
Kenneth~H. Rosen, ed.,
\newblock {\em Handbook of Discrete and Combinatorial Mathematics},
\newblock CRC Press, Boca Raton, FL, 2000.
\bibitem{Slo05}
Neil J.~A. Sloane,
\newblock {\em The On-Line Encyclopedia of Integer Sequences},
\newblock 2005,
\newblock published electronically at
http://www.research.att.com/$\sim$njas/sequences/.
\bibitem{Spi05}
Michael~Z. Spivey,
\newblock Exams with deranged questions,
\newblock in preparation.
\bibitem{MW_BinTrans}
Eric~W. Weisstein,
\newblock Binomial transform,
\newblock from MathWorld -- A Wolfram Web Resource,
http://mathworld.wolfram.com/BinomialTransform.html.
\bibitem{Wil94}
Herbert~S. Wilf,
\newblock {\em Generatingfunctionology},
\newblock Academic Press, Boston, second ed., 1994.
\bibitem{WoPe02}
Win-Jin Woan and Paul Peart,
\newblock Determinants of Hankel matrices of aerated sequences,
\newblock {\em Congressus Numerantium}, {\bf 157} (2002), 103--111.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}: Primary 11B65;
Secondary 11B75. \\
\noindent {\it Keywords}: binomial transform, Hankel transform.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000012},
\seqnum{A000032},
\seqnum{A000045},
\seqnum{A000079},
\seqnum{A000108},
\seqnum{A000142},
\seqnum{A000165},
\seqnum{A000166},
\seqnum{A000354},
\seqnum{A000364},
\seqnum{A000609},
\seqnum{A000984},
\seqnum{A001003},
\seqnum{A001006},
\seqnum{A001653},
\seqnum{A001907},
\seqnum{A002078},
\seqnum{A002315},
\seqnum{A002426},
\seqnum{A002801},
\seqnum{A003645},
\seqnum{A005799},
\seqnum{A007052},
\seqnum{A007070},
\seqnum{A007680},
\seqnum{A007696},
\seqnum{A010844},
\seqnum{A010845},
\seqnum{A014445},
\seqnum{A014448},
\seqnum{A032031},
\seqnum{A047053},
\seqnum{A052562},
\seqnum{A055209},
\seqnum{A056545},
\seqnum{A056546},
\seqnum{A059231},
\seqnum{A059304},
\seqnum{A075271},
\seqnum{A075272},
\seqnum{A082032},
\seqnum{A084770},
\seqnum{A084771},
\seqnum{A097814},
\seqnum{A097815}, and
\seqnum{A097816}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 24 2005;
revised version received November 1 2005.
Published in {\it Journal of Integer Sequences}, November 15 2005.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}