2
$\begingroup$

How do I implement the binomial transform?

I've tried defining a matrix

P = Table[(-1)^k Binomial[n, k], {n, 0, m}, {k, 0, m}]

and having this act on my sequence (of length m + 1). But this seems quite crude. I shouldn't need to specify the length of my sequence.

Given the relationship to forward differences, can I implement it directly through Differences?

$\endgroup$
3
$\begingroup$
L = {a, b, c, d, e};
binT = NestList[Minus@*Differences, #, Length[#] - 1][[All, 1]] &;
binT[L]

{a, a - b, a - 2 b + c, a - 3 b + 3 c - d, a - 4 b + 6 c - 4 d + e}

Or this (longer, but uses less memory)

binT = Reap[Nest[(Sow[First[#]]; #)& @* Minus @* Differences,
                 (Sow[First[#]]; #), Length[#] - 1]][[2, 1]] &;
$\endgroup$
1
$\begingroup$

This OEIS page has a link to this file which gives the following code:

(* Difference Table (Binomial)  Transforms *)

BinomialTransform[{},___]={};
BinomialTransform[seq_List,way_:1]:=Table[Sum[way^(i - 1 - k)*Binomial[i - 1, k]*seq[[k + 1]], {k, 0, i - 1}],{i,1,Length[seq]}];
BinomialInvTransform[{},___]={};
BinomialInvTransform[seq_List,way_:1]:=BinomialTransform[seq,-way]

(Note that this BinomialTransform is the inverse of the one defined in the question and in wikipedia.)

For example,

 x=Table[n(3^n-2^n),{n,0,4}];
 NestList[BinomialInvTransform,x,6]//TableForm

reproduces Jackson's difference fan of from page 86 of Conway and Guy's Book of Numbers:

0 1 10 57 260
0 1 8 30 88
0 1 6 9 12
$\endgroup$
  • $\begingroup$ Sorry, to the other good answers, but I'm going to accept my own (taken from OEIS) as "canonical", ignoring elegance & efficiency. $\endgroup$ – pdmclean Aug 29 '17 at 0:09
1
$\begingroup$
ClearAll[f0, f1, f2, f3, f4]

f0[x_] := Module[{m = Length@x - 1}, Table[(-1)^k Binomial[n, k], {n, 0, m}, {k, 0, m}].x]
f1[x_] := Module[{r = Range[Length@x] - 1}, Outer[(-1)^#2 Binomial@## &, r , r].x]
f2[x_] := Module[{i = 0}, (-1)^(i++) Differences[x, #][[1]] & /@ Range[0, Length @ x- 1]]
f3[x_] := Module[{r = Range[Length@x] - 1}, (-1)^r (Differences[x, #][[1]] & /@ r)]
f4[x_] := MapIndexed[(-1)^(1 + #2[[1]]) Differences[x, #2[[1]] - 1][[1]] &, x]

Examples:

f0 @ {a, b, c, d, e}

{a, a - b, a - 2 b + c, a - 3 b + 3 c - d, a - 4 b + 6 c - 4 d + e}

f0 @ Array[Subscript[y, #] &, {6}] 

Mathematica graphics

Equal @@ (#@{a, b, c, d, e} & /@ {f0, f1, f2, f3, f4})

True

Equal @@ (#@Array[Subscript[y, #] &, {6}] & /@ {f0, f1, f2, f3, f4})

True

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.