# Binomial transform

## Background

Binomial transform is a transform on a finite or infinite integer sequence, which yields another integer sequence. The binomial transform of a sequence $$\\{a_n\}\$$ is given by

$$s_n = \sum_{k=0}^{n}{(-1)^k \binom{n}{k} a_k}$$

It has an interesting property that applying the transform twice will yield the original, i.e. the transform is an involution.

## Example

Take the sequence 1, 3, 9, 27, 81. The binomial transform of this sequence is computed as follows:

\begin{align} s_0 &= a_0 = 1\\ s_1 &= a_0 - a_1 = -2\\ s_2 &= a_0 - 2a_1 + a_2 = 4\\ s_3 &= a_0 - 3a_1 + 3a_2 - a_3 = -8\\ s_4 &= a_0 - 4a_1 + 6a_2 - 4a_3 + a_4 = 16 \end{align}

So the binomial transform of 1, 3, 9, 27, 81 is 1, -2, 4, -8, 16. Verifying that the binomial transform of 1, -2, 4, -8, 16 is indeed 1, 3, 9, 27, 81 is left as an exercise to the reader.

Compute the binomial transform of a given finite integer sequence.

Standard rules apply. The shortest code in bytes wins.

## Test cases

Note that each test case works in both directions, i.e. if the left side is given as input, then the right side must be output, and vice versa.

 <-> 
[20, 21] <-> [20, -1]
[1, 3, 9, 27, 81] <-> [1, -2, 4, -8, 16]
[20, 21, 6, 15, 8, 48] <-> [20, -1, -16, -40, -80, -183]
[0, 1, 2, 3, 4, 5, 6] <-> [0, -1, 0, 0, 0, 0, 0]
[0, 1, 1, 2, 3, 5, 8, 13, 21]
<-> [0, -1, -1, -2, -3, -5, -8, -13, -21]
[1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0]
<-> [1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, 1]

• Must we handle the case of integer sequences of length 0? Jun 19, 2021 at 19:10
• No, you can assume the input is not empty. Jun 20, 2021 at 3:13

# Jelly, 5 bytes

_ƝƬZḢ


Try it online!

_ƝƬZḢ  Main Link
Ƭ    While results are unique (until we hit the empty list)
Ɲ     To each (overlapping) pair,
_      Subtract
Z   Zip; columns to rows
Ḣ  The first column


On the Wikipedia page, it says that the binomial transform is just the Nth forward differences. So, we just keep getting the difference array until we hit the empty list and stop, and then just grab the left column.

# Python 3.8, 45 bytes

def f(h,*t):print(h);f(*[h-(h:=x)for x in t])


Try it online!

Takes input splatted like f(1,2,3), outputs by printing entries one per line, terminates with error.

Computes repeated differences, taking advantage of the Python 3.8 walrus operator := to do so in a list comprehension.

• As usual you nailed it..... Jun 16, 2021 at 1:58

# K (ngn/k), 13 bytes

,/*'(-/'2':)\


Try it online!

• (...)\ run a converge-scan, repeating until consecutive executions return the same result, or a result matches the initial input
• -/'2': take the forward differences
• ,/*' take the first value of each row, and flatten to remove the trailing empty list, ()

# J, 13 bytes

-/@:*!/~@i.@#


Try it online!

For e.g. 1 3 9 27:

!/~@i.@# table of bionimal coefficients

1 1 1 1
0 1 2 3
0 0 1 3
0 0 0 1


* times the input

1 1 1  1
0 3 6  9
0 0 9 27
0 0 0 27


-/@: reduce bottom to top with minus

  1 1 1  1 => + 1 1 1  1
- 0 3 6  9    - 0 3 6  9
- 0 0 9 27    + 0 0 9 27
- 0 0 0 27    - 0 0 0 27
----------
1_2 4 _8


# JavaScript (ES6),  47  45 bytes

Using forward differences, as hyper-neutrino first did.

Returns a comma-separated string.

f=([n,...a])=>a+a?n+[,f(a.map(v=>n-(n=v)))]:n


Try it online!

### How?

At each iteration, we extract the leading term $$\n\$$ of the array, append it to the final output and do recursive calls with the forward differences until the array is empty.

Example:

[   20,   21,    6,   15,    8,   48 ] < input
[   -1,   15,   -9,    7,  -40 ]
[  -16,   24,  -16,   47 ]
[  -40,   40,  -63 ]
[  -80,  103 ]
[ -183 ]
^
output

# JavaScript (ES6), 74 bytes

A naive implementation that actually computes the binomial coefficients.

a=>a.map((_,n)=>a.reduce((t,v,i)=>t+(g=k=>k?g(--k)*(k-n)/~k:i&1?-v:v)(i)))


Try it online!

# Factor, 48 bytes

[ [ dup first . differences vneg ] until-empty ]


Try it online!

Output the first member of the input sequence to stdout followed by a newline, take the differences, and flip the sign of each element until empty.

# R, 45 bytes

function(x)for(i in x){show(x);x=-diff(x)}


Try it online!

• Jun 16, 2021 at 8:12
• @DominicvanEssen - post it! I tried recursion, but somehow it all came out longer... Jun 16, 2021 at 8:54

# Charcoal, 18 bytes

Ｗθ«Ｉ…θ¹≔ＥΦθλ⁻§θλκθ


Try it online! Link is to verbose version of code. Explanation:

Ｗθ«


Repeat until there are no more terms.

Ｉ…θ¹


Output the next term on its own line.

≔ＥΦθλ⁻§θλκθ


Calculate reverse differences.

The binomial transform can be represented as a sort of reverse Pascal's Triangle where each value is the sum of the two below (here using the original 1, 3, 9, 27, 81 example):

             1
3    -2
9    -6     4
27   -18    12    -8
81   -54    36   -24    16


The transform then appears on the rightmost entries on each row. Since addition is commutative, the symmetry demonstrates that transform is thus an involution.

The above code calculates the transform by calculating the bottomleft-topright diagonals in turn from topleft to bottomright. It's also possible to calculate the topleft to bottomright diagonals in turn from bottomleft to topright. The natural code to do this in Charcoal would normally take 17 bytes but unfortunately a combination of factors prevents this from working:

Ｆ⮌θ≔⁻ιＥ⊕ＬυΣ…υλυＩυ


Don't try it online! Explanation:

Ｆ⮌θ


Loop over the terms in reverse order.

≔⁻ιＥ⊕ＬυΣ…υλυ


Theoretically calculate the next diagonal by vectorised subtraction of sums of prefixes (i.e. cumulative sums but including a leading zero term) from the next term. This doesn't work because a) Charcoal can't calculate CycleChop([], 0) at all and b) Charcoal returns None for Sum([]). The cheapest fix for both of these is to use And(l, ...) at a cost of 2 bytes to avoid trying to sum the empty prefix at all, or alternatively each issue can be worked around separately at a cost of 1 byte each.

Ｉυ


Output the final diagonal.

# Stax, 10 7 bytes

É¿F▒x"╢


Run and debug it

the lack of a short method to get fixpoint made this a bit more interesting.

## Explanation

rwcHP:-c
r        reverse
w       do-while top of stack is truthy
cHP     print last element of the array
:-   get deltas (returns [] for 2-element arrays)
c  copy


# Vyxal, 5 bytes

⁽¯↔vh


Try it Online!

Me when very many yes.

• More Yes. Jun 16, 2021 at 13:19

# Jelly, 10 bytes

J’cþNÐeZḋ


Try it online!

## Explanation

J          | 1..length of sequence
’         | Decrement by 1
cþ      | Outer product using nCr
NÐe   | Negate even indices
Z  | Transpose
ḋ | Dot product with input


# APL (Dyalog Unicode), 27 bytes

,\(+/⊣×⊢(!⍨×¯1*⊢)1⍳⍤+⊢)¨⍳∘≢


Try it online!

I was too lazy to read the article, here's a stupid solution. I don't know why it doesn't work in TIO, but it does work on my computer. Requires zero-indexing.

• I think you forgot to set ⎕IO←0 in the header. Also having an R there looks pretty sus, so I suggest to change it to the actual symbol ⍤ (just in the post). Jun 15, 2021 at 23:19
• @Bubbler Oh yeah, let me change those
– user
Jun 15, 2021 at 23:21
• {⊃2-/⍣⍵⊢a}¨⍳≢a←⎕ Jun 15, 2021 at 23:22
• @rak1507 That's a lot better than mine, you should post your own answer :)
– user
Jun 15, 2021 at 23:27

# Python 3, 62 bytes

f=lambda a:len(a)>1and f([x-y for x,y in zip(a,a[1:])])or a


Try it online!

Recursive deltas until one element left.

# Wolfram Language (Mathematica), 34 31 bytes

(a=Most@a-{##2};#)&@@a&/@(a=#)&


Try it online!

Uses the differences method.

                         (a=#)  assign a to input
/@       step through input:
a=Most@a-{##2};                    update a to its forward differences
(               #)&@@a&             while taking its first element (pre-update)


# Red, 95 bytes

func[v][v: make vector! v until[print v/1 u: copy v
move back tail u u take v: u - v empty? v]]


Try it online!

# R, 44 bytes

f=function(x)if(sum(x|1))c(x,f(-diff(x)))


Try it online!

Recursive function, taking inspiration from pajonk's answer.

# Japt-g, 9 bytes

Nc¡=ä-})y


Try it

Nc¡=ä-})y     :Implicit input of array U
N             :Array of all inputs
c            :Concatenate
¡           :  Map U
=          :    Reassign to U
ä-        :    Consecutive pairs, reduced by subtraction
}       :  End map
)      :End concat
y     :Transpose
:Implicit output of first element


# Java (JDK), 69 bytes

a->{for(int l=a.length,i=0,j;++i<l;)for(j=l;j-->i;)a[j]=a[j-1]-a[j];}


Try it online!

# Ruby, 49 43 42 bytes

f=->a{k,*a=a;k ?[k]+f[a.map{|x|k-k=x}]:[]}


Try it online!

# MMIX, 52 bytes (13 instrs)

Prototype: void __mmixware bintran(int64_t *seq, size_t len)

jxd:

00000000: 3b020101 5a010002 f8000000 27020201  ;£¢¢Z¢¡£ẏ¡¡¡'££¢
00000010: 2c030200 8d040308 8dff0300 2604ff04  ,¤£¡⁽¥¤®⁽”¤¡&¥”¥
00000020: ad040308 5b02fffa 27010101 e7000008  Ḍ¥¤®[£”«'¢¢¢ḃ¡¡®
00000030: f0fffff4                             ṅ””ṡ


Disassembly:

bintran SUB   $2,$1,1       // i = len - 1
PBNZ  $2,0F // if(i) goto loop POP 0,0 // return 0H SUBU$2,$2,1 // loop: i-- 8ADDU$3,$2,$0      // int64_t t = seq + i
LDO   $4,$3,8       // a = t
LDO   $255,$3,0     // b = t
SUBU  $4,$255,$4 // a = b - a STO$4,$3,8 // t = a PBNZ$2,0B         // if(i) goto loop
SUBU  $1,$1,1       // len--
INCL  $0,8 // seq++ JMP bintran // bintran(seq, len) (tail recursion eliminated)  If you wish to add early exit on zero length, this costs four bytes more. bintran BZ$1,1F
2H      PBNZ $2,0F 1H POP 0,0 0H SUBU$2,\$2,1
(etc)
JMP  2B


The resulting machine code is identical except by prefixing of 42010001 (B¢¡¢).

# Pari/GP, 35 bytes

a->[a*Col((x-1)^n,#a)|n<-[0..#a-1]]


Try it online!

# Pari/GP, 38 bytes

a->Vec(subst(Ser(a),x,-x/t=1-x)/t+y)%y


Try it online!