[Question]
  [
## Background
[**Binomial transform**](https://en.wikipedia.org/wiki/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.
## Task
Compute the binomial transform of a given finite integer sequence.
Standard [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") 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.
```
[0] <-> [0]
[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]
```
  
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 5 bytes
```
_ƝƬZḢ
```
[Try it online!](https://tio.run/##y0rNyan8/z/@2Nxja6Ie7lj0//9/Qx0FYx0FSx0FI3MdBQtDAA "Jelly – 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.
[Answer]
# [Python 3.8](https://docs.python.org/3.8/), 45 bytes
```
def f(h,*t):print(h);f(*[h-(h:=x)for x in t])
```
[Try it online!](https://tio.run/##TZAxC4MwEIVn/RU3JnKCUWutpWOH7qWLOJQaiSAaQgrx19vTFBGS49737nEkerZqGrNSm2VpZQcdUxhZXmnTj5Ypfu1YVKuYqermeDcZcNCPYBu@rGJYRR1CnTRINU0QUrG1AiFDuJA@I5TiYCMUCOJEFCEvN4M44XSL5AjkFQe@Wz4jsuMSOjQVC3/3wJHRaFOFgTUz1YDeM/AwkO4jtQX2eg9feTdmMgiPsZXu3z9n7TFfQ/43@PID "Python 3.8 (pre-release) – 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](https://codegolf.stackexchange.com/a/180041/20260) `:=` to do so in a list comprehension.
[Answer]
# [K (ngn/k)](https://codeberg.org/ngn/k), 13 bytes
```
,/*'(-/'2':)\
```
[Try it online!](https://ngn.bitbucket.io/k#eJw9jEEOgCAQA++8ojfUQKALKvIWzvz/CS5BTDZtOplsry4cdvPBiq17M6Y3FzUkQqhNJDyQG4WL4gJPFOSiJIIQdTJO5R+YaDhM6w0R4TluGv96AXuaGE8=)
* `(...)\` 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, `()`
[Answer]
# [J](http://jsoftware.com/), 13 bytes
```
-/@:*!/~@i.@#
```
[Try it online!](https://tio.run/##hVBLDsIgEN17iqcuas20BfoRSUyamLhy5QVYGBt14w28Og5gsboxYQK8eZ@Bu1uU2YCdQQaCgOEqSuxPx4Mrqt6s59Wzv5X90uWzy/n6wGqAyFEYkEiAEgQlA@qPVqaOJNSELbc3BB0pjFlFaHjTBNn92BA6RlumM0dPTH1xyzb@pgOk689Q5I1VyGNr1ndB@5aK6foRJV0MlXV6TcqNI1vu2DbObT3Nqq@nxpxRkcyn2PgD/3gMuBc "J – 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
```
[Answer]
# JavaScript (ES6), ~~47~~ 45 bytes
Using forward differences, [as hyper-neutrino first did](https://codegolf.stackexchange.com/a/229775/58563).
Returns a comma-separated string.
```
f=([n,...a])=>a+a?n+[,f(a.map(v=>n-(n=v)))]:n
```
[Try it online!](https://tio.run/##jVJfT8MgEH/vp7hHmh2s0K2ihvrkp2h4IHWdmgnLZvr160FdJXFmEghw/P7cXXh3ozv3p7fjJ/fhZTdNg2GdRyGEs6Vp3co9@VWHA3Piwx3ZaFrPmTdjWZb2wU@PXQHQVRbhP2O9jtjIUBWCkrdpkRGxXCaaRKgR7ol7h6D/5kcaYblC2NCmEWST@SI0FNmSBL3rayo/vnERmm/iTaeQrpMWnelVpZTIheSaqwmlqmepKp@ZyKIz5yTrX93JRPh3ZZxQfDuXxyOFq6VLs9cFvZjkMXvp0i0gBWxhCzGE07PrX5kD00If/DkcduIQ9ow@B32H6Qs "JavaScript (Node.js) – 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!](https://tio.run/##jVLNToNAEL7zFHMyuzoDLLSINdCTT9EQs6GASIWGIkdfHWfBIoltKlnC7rffz8yEd93rU9qWx47qZp8NeTToKNb2hz4K8Yq1NIc223@mmRAd9lgy0j2IIqqiuNoWgqiS96KiWjpf1aa8U1vqN70UpZRyeN5ZADs3QfjP4ziGaxSei@Cp2zKjMFxSo0wh@AhPrH1ECK/rjYy55CGs@BMiqGCRixAwsmYLvg8vufzmmpfZtDKncIRCf/TiPd96Y0mcwnbBxYLGricrd7kWJrPPVJPy/0xnYUI/nRGzaD21R0ZC3jylKevMnkOWWHKe0i0iA4mVWHbetC86fRMaohjSpj41h8w@NIXIhTb/wjc "JavaScript (Node.js) – Try It Online")
[Answer]
# [Factor](https://factorcode.org/), 48 bytes
```
[ [ dup first . differences vneg ] until-empty ]
```
[Try it online!](https://tio.run/##XY9NbsJADIX3OcW7AFEmQAn0AFU3bFBXiMVocGBEMpmOHVSEcvZ0oiD@LC/8nr9nyaU20oT@Z/O9/lrhRMFRBabflpwhhg8kcvHBOkGt5ZieaeAZthk1ixbLYg0/Uin9SdCMzyS5Joh1RYbuNuUZcnVXClMskS9QqDfiA2qOArPi7meRziM/wzxun93RH3A1fb2u4n6ihs7eVJd0/RZb7FuP0gYWpNjbsqQwfn52dMAOrRNbTaj2csEuBlwVTdPUvmECaXPs/wE "Factor – 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.
[Answer]
# [R](https://www.r-project.org/), 45 bytes
```
function(x)for(i in x){show(x[1]);x=-diff(x)}
```
[Try it online!](https://tio.run/##jY/dCgIhEIXvfYq5VHAg3Z@M2CeJrjYkb3ZhKxKiZ7dRW9e7AkU9850zzhLsEOxjGu9unrgXdl64AzeBF6/bdX5yf1JncfQDXpy1BLyD5SNXEhoJBwl6L8EoIVjSUEto6TASVC8Yi6jeEZWJeEUl2P8JW4CEnqSOWAJMFRc3lbCNL5Mk02QnPaisUycKJXOfjF/frl61o5hyO9WUCUrH/FOkCnb5uxgx1Nt4ucOKl@RaW6f@xZEgwgc "R – Try It Online")
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 18 bytes
```
Ｗθ«Ｉ…θ¹≔ＥΦθλ⁻§θλκθ
```
[Try it online!](https://tio.run/##S85ILErOT8z5/788IzMnVUGjUFOhmoszoCgzr0TDObEYSFQm56Q6Z@QXaBTqKBhqampac3E6Fhdnpudp@CYWaLhl5pSkFoHkcjR1FHwz80qLNRxLPPNSUitggtmaQKIQqK/2///oaEMdBWMdBUsdBSNzHQULw9jY/7plOQA "Charcoal – 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.
[Answer]
# [Stax](https://github.com/tomtheisen/stax), ~~10~~ 7 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
É¿F▒x"╢
```
[Run and debug it](https://staxlang.xyz/#p=90a846b17822b6&i=%5B0%5D+%0A%5B20,+21%5D+%0A%5B1,+3,+9,+27,+81%5D+%0A%5B20,+21,+6,+15,+8,+48%5D+%0A%5B0,+1,+2,+3,+4,+5,+6%5D+%0A%5B0,+1,+1,+2,+3,+5,+8,+13,+21%5D++++%0A%5B1,+1,+0,+-1,+-1,+0,+1,+1,+0,+-1,+-1,+0%5D++++%0A&m=2)
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
```
[Answer]
# [Vyxal](https://github.com/Lyxal/Vyxal), 5 bytes
```
⁽¯↔vh
```
[Try it Online!](http://lyxal.pythonanywhere.com?flags=&code=%E2%81%BD%C2%AF%E2%86%94vh&inputs=%5B1%2C%203%2C%209%2C%2027%2C%2081%5D&header=&footer=)
Me when very many yes.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 10 bytes
```
J’cþ`NÐeZḋ
```
[Try it online!](https://tio.run/##y0rNyan8/9/rUcPM5MP7EvwOT0iNerij@////4Y6xjqWOkbmOhaGAA "Jelly – 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
```
[Answer]
# [APL (Dyalog Unicode)](https://www.dyalog.com/), 27 bytes
```
,\(+/⊣×⊢(!⍨×¯1*⊢)1⍳⍤+⊢)¨⍳∘≢
```
[Try it online!](https://tio.run/##SyzI0U2pTMzJT/8f9KhtQvWj3l1ApADBW4EIRNUCibkKAfk5lWmZOTkKaflFQIElXI/6pnr6AzUZ/E8DkjoxGtr6j7oWH57@qGuRhuKj3hWHpx9ab6gF5GkaPurdHKQNYh1aAWQ@6pjxqHPR//9pCgZcaQpGBgpGhkDaUMFYwVLByFzBwhAsqgMU1lEw01EwNNVRsNBRMLEACgNFgYJGOgrGQAEdBaCMGVwULgFRb2isAzUYLAVUA3QOlIBrQBUFAA "APL (Dyalog Unicode) – 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.
[Answer]
# [Python 3](https://docs.python.org/3/), 62 bytes
```
f=lambda a:len(a)>1and f([x-y for x,y in zip(a,a[1:])])or a[0]
```
[Try it online!](https://tio.run/##HcrBCoMwEIThV5ljFlIwtooI9UVCDls0NKBrkByML5@aXj5@hok5fXd5luLfK2@fmcHjuohimgzLDK/s@cjw@4FTZwTBFaJizdaMjhzdO9vGlXgESep@A2gbXTVV9FXT/XuovgY4ovID "Python 3 – Try It Online")
Recursive deltas until one element left.
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), ~~34~~ 31 bytes
```
(a=Most@a-{##2};#)&@@a&/@(a=#)&
```
[Try it online!](https://tio.run/##PYzNCsIwEITveY1AUZhiNv2xIpW8gCB4FA9LsbSHVtDcQvrqsaEY2MPMNx87sR1eE9ux49C3Ycft9f21hnMnpfZnuc@M4exg1mHN4fYZZ/uQ@aU38pkt947nxQmnPITTCppiIBQ4QR/RUOKoQRUalE1ECgS9WiUq1H@woShRkT4RFHKKtympeeHDDw "Wolfram Language (Mathematica) – 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)
```
[Answer]
# [Red](http://www.red-lang.org), 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!](https://tio.run/##TU/LCoNADLz7FVPvUmPVWintP/S65KDrSsXHiqwL/Xq7VikmgSSTmZBMqlpeqhLs1TmWeh6ksCxsjr5oFaySRk8nWMyDaToxTs1gYM@EOYfU4wfW67VVKAvZwhRNh9m5@WlzVwVOqvrRfJ6wzEutJ1XIN0oID85EyFuOQkS014QLboiuyOg4RQpKkCHOdjQEIXLcGAnSA7ahK5Uux62EEAGtsbH@HXu8fyZ63VXuOv8ePHxGjZKXLw "Red – Try It Online")
[Answer]
# [R](https://www.r-project.org/), 44 bytes
```
f=function(x)if(sum(x|1))c(x[1],f(-diff(x)))
```
[Try it online!](https://tio.run/##jY9NDsIgEIX3nIIlk8wkhf6IC09iXNVM0oU1UZt04d1xAEvZaQIB3nzvDfMIgU@8zONrus9mhYnNc7mZ9W0BRrOe7QXZ0HViliJAYDMai7pFfUTtDqi9gCpp5FB3cnjUdgClIuoaoTIRr2RB/Z@wB6AeROqFFcBXcXFLibr48knybXbKQ8oudZJQMQ/J@PU19aodxZTb2bZMUDrmn5JUqM/fpYiR28fLHTa8JNfaNvUvTgQIHw "R – Try It Online")
Recursive function, taking inspiration from [pajonk's answer](https://codegolf.stackexchange.com/a/229798/95126).
[Answer]
# [Japt](https://github.com/ETHproductions/japt) [`-g`](https://codegolf.meta.stackexchange.com/a/14339/), 9 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
Nc¡=ä-})y
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&flags=LWc&code=TmOhPeQtfSl5&input=WzEsIDMsIDksIDI3LCA4MV0)
```
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
```
[Answer]
# [Java (JDK)](http://jdk.java.net/), 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!](https://tio.run/##bVFda8IwFH33V1wEoZ1JseqcW2xh7HnswUfpQ1Zbly5NS5IKIv3t3e2HRXCQz3POPTf3JuNnTrPjbyPystAWMrx7lRXSe2KTByytVGxFoVoyltwY@ORCwXUCUFbfUsRgLLe4nQtxhBw5Z2@1UKdDBFyfjNtJAT4KZao80Tuh7CEKIQ0aTsNrWmgHEZAB92SiTvaHiGBBMjafi51kbstngWQZpaFgLj9kUYAL9SPanlndsM6@c8WUNjHWQDAkBbjCAmoyXpYLAkv/HvEJrAi8IvxCYOs/iglsCPjPSBJYb@95pJFddgZrAijZPNKjonfwV/88AAeKqd/PMe4eu0XUfbnYFnDOXHf1vvVVu2PRLaETU0mLnXjXml@MFxfl5St1WiXp9EO7XTYEpR6P46S0Th854vuLsUnuFZX1SvxXmzrTmYEdDWFmZmpKbgls0f97l8J9hAfbwbeetLNu/gA "Java (JDK) – Try It Online")
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~49 43~~ 42 bytes
```
f=->a{k,*a=a;k ?[k]+f[a.map{|x|k-k=x}]:[]}
```
[Try it online!](https://tio.run/##KypNqvz/P81W1y6xOltHK9E20TpbwT46O1Y7LTpRLzexoLqmoiZbN9u2ojbWKjq29n@BQlp0tJGBjoKRoY6CmY6CoamOgoWOgolFbOx/AA "Ruby – Try It Online")
[Answer]
# 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[1]
        LDO   $255,$3,0     // b = t[0]
        SUBU  $4,$255,$4    // a = b - a
        STO   $4,$3,8       // t[1] = 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¢¡¢`).
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 35 bytes
```
a->[a*Col((x-1)^n,#a)|n<-[0..#a-1]]
```
[Try it online!](https://tio.run/##TY1BCoNADEWvEnQzUxIxaq2F1k2PMUwhG4sgdpAuWujdp7GCCknIf/@HBJl6eoTYwTUKtU4Ot@dgzJvY3kdMxX7HC7k8y1Ih9j5KCMPHCFALYerHl67JLBLojFiL4FzudRY5QsHzxgglwlnlCaHhzUSoEfioEKFqZq5YafE/qBDUqje8OssFl7sHWhoiXnrN75n3Nv4A "Pari/GP – Try It Online")
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 38 bytes
```
a->Vec(subst(Ser(a),x,-x/t=1-x)/t+y)%y
```
[Try it online!](https://tio.run/##TY3RCoMwDEV/JQiDlqVo1Dn3oD8x2Iv0oRs6BBlFO6hf38UJKiQhOfdeYs3Yq7cNHVTBqPrRvsT0fU5O3NtRGIkelY9dRcrL2J1neZqDsXaYhQFVgx37j@M1Wo4IOk5IhKZJNM80QUhp2QghQ7jxeUUoaRcRCgS6METIy4UzZpr@AzkCS8WON2VNUHZ4wMUmRWtv/iPTWoYf "Pari/GP – Try It Online")
]