In
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, the binomial transform is a
sequence transformation
In mathematics, a sequence transformation is an operator acting on a given space of sequences (a sequence space). Sequence transformations include linear mappings such as convolution with another sequence, and resummation of a sequence and, mo ...
(i.e., a transform of a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
) that computes its
forward differences. It is closely related to the Euler transform, which is the result of applying the binomial transform to the sequence associated with its
ordinary generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary ser ...
.
Definition
The binomial transform, ''T'', of a sequence, , is the sequence defined by
:
Formally, one may write
:
for the transformation, where ''T'' is an infinite-dimensional
operator with matrix elements ''T''
''nk''.
The transform is an
involution, that is,
:
or, using index notation,
:
where
is the
Kronecker delta
In mathematics, the Kronecker delta (named after Leopold Kronecker) is a function of two variables, usually just non-negative integers. The function is 1 if the variables are equal, and 0 otherwise:
\delta_ = \begin
0 &\text i \neq j, \\
1 & ...
. The original series can be regained by
:
The binomial transform of a sequence is just the ''n''th
forward differences of the sequence, with odd differences carrying a negative sign, namely:
:
where Δ is the
forward difference operator.
Some authors define the binomial transform with an extra sign, so that it is not self-inverse:
:
whose inverse is
:
In this case the former transform is called the ''inverse binomial transform'', and the latter is just ''binomial transform''. This is standard usage for example in
On-Line Encyclopedia of Integer Sequences
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to t ...
.
Example
Both versions of the Binomial transform appear in difference tables. Consider the following difference table:
Each line is the difference of the previous line. (The ''n''-th number in the ''m''-th line is ''a''
''m'',''n'' = 3
''n''−2(2
''m''+1''n''
2 + 2
''m''(1+6''m'')''n'' + 2
''m''-19''m''
2), and the difference equation ''a''
''m''+1,''n'' = ''a''
''m'',''n''+1 - ''a''
''m'',''n'' holds.)
The top line read from left to right is = 0, 1, 10, 63, 324, 1485, ... The diagonal with the same starting point 0 is = 0, 1, 8, 36, 128, 400, ... is the noninvolutive binomial transform of .
The top line read from right to left is = 1485, 324, 63, 10, 1, 0, ... The cross-diagonal with the same starting point 1485 is = 1485, 1161, 900, 692, 528, 400, ... is the involutive binomial transform of .
Ordinary generating function
The transform connects the
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary serie ...
s associated with the series. For the
ordinary generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary ser ...
, let
:
and
:
then
:
Euler transform
The relationship between the ordinary generating functions is sometimes called the Euler transform. It commonly makes its appearance in one of two different ways. In one form, it is used to
accelerate the convergence of an
alternating series. That is, one has the identity
:
which is obtained by substituting ''x'' = 1/2 into the last formula above. The terms on the right hand side typically become much smaller, much more rapidly, thus allowing rapid numerical summation.
The Euler transform can be generalized (Borisov B. and Shkodrov V., 2007):
:
where ''p'' = 0, 1, 2,…
The Euler transform is also frequently applied to the
Euler hypergeometric integral . Here, the Euler transform takes the form:
:
The binomial transform, and its variation as the Euler transform, is notable for its connection to the
continued fraction
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer ...
representation of a number. Let
have the continued fraction representation
: