Binomial transform

Binomial transform

In combinatorial mathematics the binomial transform is a sequence transformation (ie, a transform of a sequence) 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.

Definition

The binomial transform, "T", of a sequence, {a_n}, is the sequence {s_n} defined by

:s_n = sum_{k=0}^n (-1)^k {nchoose k} a_k.

Formally, one may write (Ta)_n = s_n for the transformation, where "T" is an infinite-dimensional operator with matrix elements T_{nk}:

:s_n = (Ta)_n = sum_{k=0}^infty T_{nk} a_k.

The transform is an involution, that is,

:TT = 1 ,

or, using index notation,

:sum_{k=0}^infty T_{nk}T_{km} = delta_{nm}

where δ is the Kronecker delta function. The original series can be regained by

:a_n=sum_{k=0}^n (-1)^k {nchoose k} s_k.

The binomial transform of a sequence is just the "n"th forward difference of the sequence, namely

:s_0 = a_0:s_1 = - ( riangle a)_0 = -a_1+a_0:s_2 = ( riangle^2 a)_0 = -(-a_2+a_1)+(-a_1+a_0) = a_2-2a_1+a_0:dots, :s_n = (-1)^n ( riangle^n a)_0

where Δ is the forward difference operator.

Some authors define the binomial transform with an extra sign, so that it is not self-inverse:

:t_n=sum_{k=0}^n (-1)^{n-k} {nchoose k} a_k

whose inverse is

:a_n=sum_{k=0}^n {nchoose k} t_k.

hift states

The binomial transform is the shift operator for the Bell numbers. That is,

:B_{n+1}=sum_{k=0}^n {nchoose k} B_k

where the B_n are the Bell numbers.

Ordinary generating function

The transform connects the generating functions associated with the series. For the ordinary generating function, let

:f(x)=sum_{n=0}^infty a_n x^n

and

:g(x)=sum_{n=0}^infty s_n x^n

then

:g(x) = (Tf)(x) = frac{1}{1-x} fleft(frac{-x}{1-x} ight).

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

:sum_{n=0}^infty (-1)^n a_n = sum_{n=0}^infty (-1)^n frac {Delta^n a_0} {2^{n+1

which is obtained by substituting "x"=1/2 into the above. The terms on the right hand side typically become much smaller, much more rapidly, thus allowing rapid numerical summation.

The Euler transform is also frequently applied to the hypergeometric series ,_2F_1. Here, the Euler transform takes the form:

:,_2F_1 (a,b;c;z) = (1-z)^{-b} ,_2F_1 left(c-a, b; c;frac{z}{z-1} ight)

The binomial transform, and its variation as the Euler transform, is notable for its connection to the continued fraction representation of a number. Let 0 < x < 1 have the continued fraction representation

:x= [0;a_1, a_2, a_3,cdots]

then

:frac{x}{1-x}= [0;a_1-1, a_2, a_3,cdots]

and

:frac{x}{1+x}= [0;a_1+1, a_2, a_3,cdots]

Exponential generating function

For the exponential generating function, let

:overline{f}(x)= sum_{n=0}^infty a_n frac{x^n}{n!}

and

:overline{g}(x)= sum_{n=0}^infty s_n frac{x^n}{n!}

then

:overline{g}(x) = (Toverline{f})(x) = e^x overline{f}(-x)

The Borel transform will convert the ordinary generating function to the exponential generating function.

Integral representation

When the sequence can be interpolated by a complex analytic function, then the binomial transform of the sequence can be represented by means of a Nörlund-Rice integral on the interpolating function.

Generalizations

Prodinger gives a related, modular-like transformation: letting

:u_n = sum_{k=0}^n {nchoose k} a^k (-c)^{n-k} b_k

gives

:U(x) = frac{1}{cx+1} Bleft(frac{ax}{cx+1} ight)

where "U" and "B" are the ordinary generating functions associated with the series {u_n} and {b_n}, respectively.

The rising "k"-binomial transform is sometimes defined as

:sum_{j=0}^n {nchoose j} j^k a_j

The falling "k"-binomial transform is

:sum_{j=0}^n {nchoose j} j^{n-k} a_j.

Both are homomorphisms of the kernel of the Hankel transform of a series.

In the case where the binomial transform is defined as

:sum_{i=0}^n(-1)^{n-i}inom{n}{i}a_i=b_n

Let this be equal to the function mathfrak J(a)_n=b_n

If a new forward difference table is made and the first elements from each row of this table are taken to form a new sequence {b_n}, then the second binomial transform of the original sequence is,

:mathfrak J^2(a)_n=sum_{i=0}^n(-2)^{n-i}inom{n}{i}a_i

If the same process is repeated "k" times, then it follows that,

:mathfrak J^k(a)_n=b_n=sum_{i=0}^n(-k)^{n-i}inom{n}{i}a_i

It's inverse is,

:mathfrak J^{-k}(b)_n=a_n=sum_{i=0}^nk^{n-i}inom{n}{i}b_i

This can be generalized as,

:mathfrak J^k(a)_n=b_n=(mathbf E-k)^na_0

where mathbf E is the shift operator

It's inverse is

:mathfrak J^{-k}(b)_n=a_n=(mathbf E+k)^nb_0

ee also

* Newton series
* Hankel matrix
* Möbius transform
* Stirling transform
* List of factorial and binomial topics

References

* John H. Conway and Richard K. Guy, "The Book of Numbers", (1996)
* Donald E. Knuth, "The Art of Computer Programming Vol. 3", (1973) Addison-Wesley, Reading, MA.
* Helmut Prodinger, " [http://math.sun.ac.za/~prodinger/abstract/abs_87.htm Some information about the Binomial transform] ", (1992)
* Michael Z. Spivey and Laura L. Steil, " [http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.pdf The k-Binomial Transforms and the Hankel Transform] ", (2006)

External links

* [http://mathworld.wolfram.com/BinomialTransform.html Binomial Transform]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Binomial coefficient — The binomial coefficients can be arranged to form Pascal s triangle. In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the… …   Wikipedia

  • Binomial heap — In computer science, a binomial heap is a heap similar to a binary heap but also supporting the operation of merging two heaps quickly. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap …   Wikipedia

  • Binomial-QMF — Orthonormal Binomial Quadrature Mirror Filter (Binomial QMF) bank with perfect reconstruction (PR) was designed by Ali Akansu, et.al. in 1990 using discrete time Binomial polynomials. They also showed that these Binomial QMF filters are identical …   Wikipedia

  • Transformada binomial — En matemáticas, en el campo de la combinatoria, la transformada binomial es una transformación de sucesiones, o sea, una transformación de una sucesión, que se obtiene calculando sus diferencias anteriores. Esta relacionada con la transformada de …   Wikipedia Español

  • Mellin transform — In mathematics, the Mellin transform is an integral transform that may be regarded as the multiplicative version of the two sided Laplace transform. This integral transform is closely connected to the theory of Dirichlet series, and is often used …   Wikipedia

  • List of factorial and binomial topics — This is a list of factorial and binomial topics in mathematics, by Wikipedia page. See also binomial (disambiguation).*Alternating factorial *Antichain *Beta function *Binomial coefficient *Binomial distribution *Binomial proportion confidence… …   Wikipedia

  • Stirling transform — In combinatorial mathematics, the Stirling transform of a sequence { a n : n = 1, 2, 3, ... } of numbers is the sequence { b n : n = 1, 2, 3, ... } given by:b n=sum {k=1}^n left{egin{matrix} n k end{matrix} ight} a k,where left{egin{matrix} n k …   Wikipedia

  • Discrete Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… …   Wikipedia

  • Anscombe transform — In statistics, the Anscombe transform (1948) is a variance stabilizing transformation that transforms a random variable with a Poisson distribution into one with an approximately Gaussian distribution. The Anscombe transform is widely used in… …   Wikipedia

  • BTRID — binomial transform reduced interference distribution …   Medical dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”