user
The binomial transform is a bijective sequence transform based on convolution with binomial coefficients.

It may be thought of as an *nth* forward difference with odd differences carrying a negative sign.

There are two common variants of binomial transforms, one of which is self-inverting; *reapplying the transform to a transformed sequence returns the original sequence,* and one which has separate "forward" and "inverse" transform operations.

The two variants only differ in placement and quantity of signs. The variant standardized on by OEIS, *with the 'forward' and 'inverse' complementary operations*, will be used here.

In this variant, to transform the sequence *a* to sequence *b* and back:

the forward binomial transform is defined as: 

b

n
=

∑

k
=
0

n

(

n
k

)

a

k
.
{\displaystyle {\displaystyle b\_{n}=\sum \_{k=0}^{n}{n \choose k}a\_{k}.}}

and the inverse binomial transform is defined as: 

a

n
=

∑

k
=
0

n
(
−
1

)

n
−
k

(

n
k

)

b

k
{\displaystyle {\displaystyle a\_{n}=\sum \_{k=0}^{n}(-1)^{n-k}{n \choose k}b\_{k}}}

where 

(

n
k

)
{\displaystyle {\displaystyle {n \choose k}}}
 is the binomial operator 'n choose k'

*For reference, the self inverting binomial transform is defined as:* 

b

n
=

∑

k
=
0

n
(
−
1

)

k

(

n
k

)

a

k
{\displaystyle {\displaystyle b\_{n}=\sum \_{k=0}^{n}(-1)^{k}{n \choose k}a\_{k}}}

Task

* Implement both a forward, and inverse binomial transform routine.
* Use those routines to compute the forward binomial transform, the inverse binomial transform, and the inverse of the forward transform *(should return original sequence)* of a few representative sequences.
* Show at least the first 15 values in each sequence.

:   *You may generate the sequences, or may choose to just hard code the values.*

:   Use the following sequences for testing:

    :   Catalan numbers: `1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440`
    :   Prime flip flop sequence: (for an: 1 if prime, 0 otherwise): `0 1 1 0 1 0 1 0 0 0 1 0 1 0 0`
    :   Fibonacci sequence: `0 1 1 2 3 5 8 13 21 34 55 89 144 233 377`
    :   Padovan sequence: (starting with values 1,0,0): `1 0 0 1 0 1 1 1 2 2 3 4 5 7 9`

See also

* Wikipedia: Binomial transform * OEIS wiki: Binomial transform * Related task: Evaluate binomial coefficients * Related task: Catalan numbers * Related task: Riordan numbers * Related task: Fibonacci sequence * Related task: Padovan sequence

:   *first sequence*

* OEIS:A007317 - Binomial transform of Catalan numbers * OEIS:A005043 - Riordan numbers (Inverse binomial transform of Catalan numbers)

:   *second sequence*

* OEIS:A052467 - Binomial transform of {b(n)}, where b(n)=1 for prime n and b(n)=0 otherwise (Binomial transform of Prime flip-flop sequence

:   *third sequence*

* OEIS:A001906 - F(2n) = bisection of Fibonacci sequence (Binomial transform of Fibonacci sequence) * OEIS:A039834 - a(n+2) = -a(n+1) + a(n) (signed Fibonacci numbers) with a(-2) = a(-1) = 1 (Inverse binomial transform of Fibonacci sequence)

:   *fourth sequence*

* OEIS:A034943 - Binomial transform of Padovan sequence * OEIS:A144413 - a(n) = Sum\_{k=0..n} (-1)^k \* binomial(n, k) \* A000931(n-k+4) (Inverse binomial transform of Padovan sequence)
assistant
Generates the sequences on the fly.

```
sub binomial { [×] ($^n … 0) Z/ 1 .. $^p }

sub binomial-transform (*@seq) {
    @seq.keys.map: -> \n { sum (0..n).map: -> \k { binomial(n,k) × @seq[k] } }
}

sub inverse-binomial-transform (*@seq) {
    @seq.keys.map: -> \n { sum (0..n).map: -> \k { binomial(n,k) × @seq[k] × exp(n - k, -1) } }
}

sub si-binomial-transform (*@seq) { #self inverting
    @seq.keys.map: -> \n { sum (0..n).map: -> \k { binomial(n,k) × @seq[k] × exp(k, -1) } }
}

my $upto = 20;

for 'Catalan number',   (1, {[+] @_ Z× @_.reverse}…*),
    'Prime flip-flop',  (1..*).map({.is-prime ?? 1 !! 0}),
    'Fibonacci number', (0,1,*+*…*),
    'Padovan number',   (1,0,0, -> $c,$b,$ {$b+$c}…*)
  -> $name, @seq {
    say qq:to/BIN/;
    $name sequence:
    {@seq[^$upto]}
    Forward binomial transform:
    {binomial-transform(@seq)[^$upto]}
    Inverse binomial transform:
    {inverse-binomial-transform(@seq)[^$upto]}
    Round trip:
    {inverse-binomial-transform(binomial-transform(@seq))[^$upto]}
    Self inverting:
    {si-binomial-transform(@seq)[^$upto]}
    Re inverted:
    {si-binomial-transform(si-binomial-transform(@seq))[^$upto]}
    BIN
}

```

Output:

```
Catalan number sequence:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190
Forward binomial transform:
1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885 390248055 1777495635 8140539950 37463689775 173164232965
Inverse binomial transform:
1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595
Round trip:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190
Self inverting:
1 0 1 -1 3 -6 15 -36 91 -232 603 -1585 4213 -11298 30537 -83097 227475 -625992 1730787 -4805595
Re inverted:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190

Prime flip-flop sequence:
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
Forward binomial transform:
0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 9948 19793 40562 84271 174952
Inverse binomial transform:
0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173 -9918 19761 -40528 84235 -174914
Round trip:
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
Self inverting:
0 -1 -1 0 3 10 25 56 118 237 456 847 1540 2795 5173 9918 19761 40528 84235 174914
Re inverted:
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0

Fibonacci number sequence:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Forward binomial transform:
0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169
Inverse binomial transform:
0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 610 -987 1597 -2584 4181
Round trip:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Self inverting:
0 -1 -1 -2 -3 -5 -8 -13 -21 -34 -55 -89 -144 -233 -377 -610 -987 -1597 -2584 -4181
Re inverted:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

Padovan number sequence:
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37
Forward binomial transform:
1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833 55405 128801 299426 696081 1618192
Inverse binomial transform:
1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 -3185 7137 -13920 24301 -37926
Round trip:
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37
Self inverting:
1 1 1 0 -3 -10 -24 -49 -89 -145 -208 -245 -174 176 1121 3185 7137 13920 24301 37926
Re inverted:
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37
```

You may Attempt This Online!