Binomial transform

From Rosetta Code
Binomial transform is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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:

and the inverse binomial transform is defined as:

where is the binomial operator 'n choose k'


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


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
first sequence
second sequence
third sequence
fourth sequence


ALGOL 68

Translation of: C

Assumes LONG INT is at least 64 bits, as in Algol 68G. 

BEGIN # binomial transform - translation of the C sample                     #
    # returns factorial n, n must be at most 20                              #
    PROC factorial = ( INT n )LONG INT:
         IF n > 20 THEN 0 # too big for LONG INT                             #
         ELSE
            LONG INT fact := 1;
            FOR i FROM 2 TO n DO fact *:= i OD;
            fact
         FI # factorial # ;
    # returns the binomial coefficient ( n k )                               #
    PROC binomial = ( INT n, k )LONG INT:
         factorial( n ) OVER factorial( n - k ) OVER factorial( k );
    # sets n to the forward transform of a                                   #
    PROC bt forward = ( REF[]LONG INT b, []LONG INT a )VOID:
         BEGIN
            REF[]LONG INT b0 = b[ AT 0 ];
            []LONG INT    a0 = a[ AT 0 ];
            FOR n FROM 0 TO UPB b0 DO
               b0[ n ] := 0;
               FOR k FROM 0 TO n DO b0[ n ] +:= binomial( n, k ) * a0[ k ] OD
            OD
         END # bt forward # ;
    # sets a to the inverse transform of b                                   #
    PROC bt inverse = ( REF[]LONG INT a, []LONG INT b )VOID:
         BEGIN
            REF[]LONG INT a0 = a[ AT 0 ];
            []LONG INT    b0 = b[ AT 0 ];
            FOR n FROM 0 TO UPB a0 DO
                a0[ n ] := 0;
                FOR k FROM 0 TO n DO
                    a0[ n ] +:= binomial( n, k ) * b0[ k ] * IF ODD ( n - k ) THEN -1 ELSE 1 FI
                OD
             OD
         END # bt inverse # ;
    # sets b to the self inverse of a                                        #
    PROC bt self inverting = ( REF[]LONG INT b, []LONG INT a )VOID:
         BEGIN
            REF[]LONG INT b0 = b[ AT 0 ];
            []LONG INT    a0 = a[ AT 0 ];
            FOR n FROM 0 TO UPB b0 DO
                b0[ n ] := 0;
                FOR k FROM 0 TO n DO
                    b0[ n ] +:= binomial( n, k ) * a0[ k ] * IF ODD k THEN -1 ELSE 1 FI
                OD
            OD
         END # bt self inverse # ;

    # task test cases                                                        #
    [][]LONG INT seqs = ( ( 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862
                          , 16796, 58786, 208012, 742900, 2674440, 9694845
                          , 35357670, 129644790, 477638700, 1767263190
                          )
                        , ( 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0 )
                        , ( 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
                          , 233, 377, 610, 987, 1597, 2584, 4181
                          )
                        , ( 1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37 )
                        );
    [ 1 : UPB seqs[ LWB seqs ] ]LONG INT fwd, res;
    []STRING names = ( "Catalan number sequence:"
                     , "Prime flip-flop sequence:"
                     , "Fibonacci number sequence:"
                     , "Padovan number sequence:"
                     );
    FOR i TO UPB seqs DO
        print( ( names[ i ], newline ) );
        FOR j TO UPB seqs[ i ] DO print( ( whole( seqs[ i ][ j ], 0 ), " " ) ) OD;
        print( ( newline, "Forward binomial transform:", newline ) );
        bt forward( fwd, seqs[ i ] );
        FOR j TO UPB fwd DO print( ( whole( fwd[ j ], 0 ), " " ) ) OD;
        print( ( newline, "Inverse binomial transform:", newline ) );
        bt inverse( res, seqs[ i ] );
        FOR j TO UPB res DO print( ( whole( res[ j ], 0 ), " " ) ) OD;
        print( ( newline, "Round trip:", newline ) );
        bt inverse( res, fwd );
        FOR j TO UPB res DO print( ( whole( res[ j ], 0 ), " " ) ) OD;
        print( ( newline, "Self-inverting:", newline ) );
        bt self inverting( fwd, seqs[ i ] );
        FOR j TO UPB fwd DO print( ( whole( fwd[ j ], 0 ), " " ) ) OD;
        print( ( newline, "Re-inverted:", newline ) );
        bt self inverting( res, fwd );
        FOR j TO UPB res DO print( ( whole( res[ j ], 0 ), " " ) ) OD;
        IF i < UPB seqs THEN print( ( newline, newline ) ) ELSE print( ( newline ) ) FI
    OD
END
Output:

(same as the C sample) 

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

Arturo

choose: function [n k][
    div div factorial n factorial n - k factorial k
]

forward: function [a][
    map 0..dec size a 'n ->
        sum map 0..n 'k ->
            a\[k] * choose n k
]

inverse: function [b][
    map 0..dec size b 'n ->
        sum map 0..n 'k ->
            b\[k] * mul choose n k pow neg 1 n - k
]

loop [
    "Catalan" [1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190]
    "Prime flip-flop" [0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0]
    "Fibonacci" [0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181]
    "Padovan" [1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37]
] [name seq] [
    print ~« -~~=====<{ |name| }>=====~~-
    print seq
    print "Forward binomial transform:"
    print fwd: <= forward seq
    print "Inverse binomial transform:"
    print inverse seq
    print "Round trip:"
    print inverse fwd
    print ""
]
Output:
-~~=====<{ Catalan }>=====~~-
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 

-~~=====<{ Prime flip-flop }>=====~~-
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 

-~~=====<{ Fibonacci }>=====~~-
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 

-~~=====<{ Padovan }>=====~~-
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

C

#include <stdio.h>
#include <stdint.h>

uint64_t factorial(int n) {
    if (n > 20) return 0; // too big for uint64_t
    if (n < 2) return 1;
    uint64_t fact = 1;
    int i = 2;
    for (i = 2; i <= n; ++i) fact *= i;
    return fact;
}

uint64_t binomial(int n, int k) {
    return factorial(n) / factorial(n-k) / factorial(k);
}

void btForward(int64_t b[], const int64_t a[], size_t c) {
    int n, k;
    for (n = 0; n < c; ++n) {
        b[n] = 0;
        for (k = 0; k <= n; ++k) {
            b[n] += (int64_t)binomial(n, k) * a[k];
        }
    }
}

void btInverse(int64_t a[], const int64_t b[], size_t c) {
    int n, k, sign;
    for (n = 0; n < c; ++n) {
        a[n] = 0;
        for (k = 0; k <= n; ++k) {
            sign = (n-k) & 1 ? -1 : 1;            
            a[n] += (int64_t)binomial(n, k) * b[k] * sign;
        }
    }
}

void btSelfInverting(int64_t b[], const int64_t a[], size_t c) {
    int n, k, sign;
    for (n = 0; n < c; ++n) {
        b[n] = 0;
        for (k = 0; k <= n; ++k) {
            sign = k & 1 ? -1 : 1;            
            b[n] += (int64_t)binomial(n, k) * a[k] * sign;
        }
    }
}

int main() {
    int i, j;
    int64_t fwd[20], res[20], seqs[4][20] = {
        {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190},
        {0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0},
        {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181},
        {1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37}
    };

    const char *names[4] = {
        "Catalan number sequence:",
        "Prime flip-flop sequence:",
        "Fibonacci number sequence:",
        "Padovan number sequence:"
    };

    for (i = 0; i < 4; ++i) {
        printf("%s\n", names[i]);
        for (j = 0; j < 20; ++j) printf("%ld ", seqs[i][j]);
        printf("\nForward binomial transform:\n");
        btForward(fwd, seqs[i], 20);
        for (j = 0; j < 20; ++j) printf("%ld ", fwd[j]); 
        printf("\nInverse binomial transform:\n");
        btInverse(res, seqs[i], 20);
        for (j = 0; j < 20; ++j) printf("%ld ", res[j]);
        printf("\nRound trip:\n");
        btInverse(res, fwd, 20);
        for (j = 0; j < 20; ++j) printf("%ld ", res[j]);
        printf("\nSelf-inverting:\n");
        btSelfInverting(fwd, seqs[i], 20);
        for (j = 0; j < 20; ++j) printf("%ld ", fwd[j]);
        printf("\nRe-inverted:\n");
        btSelfInverting(res, fwd, 20);
        for (j = 0; j < 20; ++j) printf("%ld ", res[j]);    
        if (i < 3) printf("\n\n"); else printf("\n");
    }
    return 0;
}
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

Go

package main

import "fmt"

func factorial(n int) uint64 {
    if n > 20 {
        return 0 // too big for uint64
    }
    if n < 2 {
        return 1
    }
    fact := uint64(1)
    i := 2
    for i <= n {
        fact *= uint64(i)
        i++
    }
    return fact
}

func binomial(n, k int) uint64 {
    return factorial(n) / factorial(n-k) / factorial(k)
}

func btForward(a []int64) []int64 {
    c := len(a)
    b := make([]int64, c)
    for n := 0; n < c; n++ {
        b[n] = int64(0)
        for k := 0; k <= n; k++ {
            b[n] += int64(binomial(n, k)) * a[k]
        }
    }
    return b
}

func btInverse(b []int64) []int64 {
    c := len(b)
    a := make([]int64, c)
    for n := 0; n < c; n++ {
        a[n] = int64(0)
        for k := 0; k <= n; k++ {
            sign := int64(-1)
            if (n-k)&1 == 0 {
                sign = 1
            }
            a[n] += int64(binomial(n, k)) * b[k] * sign
        }
    }
    return a
}

func btSelfInverting(a []int64) []int64 {
    c := len(a)
    b := make([]int64, c)
    for n := 0; n < c; n++ {
        b[n] = int64(0)
        for k := 0; k <= n; k++ {
            sign := int64(-1)
            if k&1 == 0 {
                sign = 1
            }
            b[n] += int64(binomial(n, k)) * a[k] * sign
        }
    }
    return b
}

func main() {
    seqs := [][]int64{
        {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190},
        {0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0},
        {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181},
        {1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37},
    }

    names := []string{
        "Catalan number sequence:",
        "Prime flip-flop sequence:",
        "Fibonacci number sequence:",
        "Padovan number sequence:",
    }

    for i, seq := range seqs {
        fmt.Println(names[i])
        fmt.Println(seq)
        fmt.Println("Forward binomial transform:")
        fwd := btForward(seq)
        fmt.Println(fwd)
        fmt.Println("Inverse binomial transform:")
        fmt.Println(btInverse(seq))
        fmt.Println("Round trip:")
        fmt.Println(btInverse(fwd))
        fmt.Println("Self-inverting:")
        si := btSelfInverting(seq)
        fmt.Println(si)
        fmt.Println("Re-inverted:")
        fmt.Println(btSelfInverting(si))
        if i < len(seqs)-1 {
            fmt.Println()
        }
    }
}
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]

J

Implementation: 

forward=: {{ y +/ .* !/~ i.#y }}
reverse=: {{ y +/ .* (!/~ * _1^+/~) i.#y }}
selfinv=: {{ y +/ .* (!/~ * _1^]) i.#y }}

Task examples: 

   NB. Catalan
   ((! +:) % >:) i.15x
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
   forward ((! +:) % >:) i.15x
1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885
   reverse ((! +:) % >:) i.15x
1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537
   selfinv ((! +:) % >:) i.15x
1 0 1 _1 3 _6 15 _36 91 _232 603 _1585 4213 _11298 30537
   reverse forward ((! +:) % >:) i.15x
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
   selfinv selfinv ((! +:) % >:) i.15x
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
   
   NB. natural number is prime
   1 p: 1+i.15
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0
   forward 1 p: 1+i.15
0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201
   reverse 1 p: 1+i.15
0 1 _1 0 3 _10 25 _56 118 _237 456 _847 1540 _2795 5173
   selfinv 1 p: 1+i.15
0 _1 _1 0 3 10 25 56 118 237 456 847 1540 2795 5173
   reverse forward 1 p: 1+i.15
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0
   selfinv selfinv 1 p: 1+i.15
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0
   
   NB. Fibonacci
   (, _1 _2 +/@:{ ])^:15] 0 1
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
   forward (, _1 _2 +/@:{ ])^:15] 0 1
0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309
   reverse (, _1 _2 +/@:{ ])^:15] 0 1
0 1 _1 2 _3 5 _8 13 _21 34 _55 89 _144 233 _377 610 _987
   selfinv (, _1 _2 +/@:{ ])^:15] 0 1
0 _1 _1 _2 _3 _5 _8 _13 _21 _34 _55 _89 _144 _233 _377 _610 _987
   reverse forward (, _1 _2 +/@:{ ])^:15] 0 1
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
   selfinv selfinv (, _1 _2 +/@:{ ])^:15] 0 1
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
   
   NB. Padovan
   (],+/@(_2 _3{]))^:([-3:)&1 0 0(15)
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9
   forward (],+/@(_2 _3{]))^:([-3:)&1 0 0(15)
1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833
   reverse (],+/@(_2 _3{]))^:([-3:)&1 0 0(15)
1 _1 1 0 _3 10 _24 49 _89 145 _208 245 _174 _176 1121
   selfinv (],+/@(_2 _3{]))^:([-3:)&1 0 0(15)
1 1 1 0 _3 _10 _24 _49 _89 _145 _208 _245 _174 176 1121
   reverse forward (],+/@(_2 _3{]))^:([-3:)&1 0 0(15)
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9
   selfinv selfinv (],+/@(_2 _3{]))^:([-3:)&1 0 0(15)
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9

jq

Adapted from Wren

Works with both jq and gojq, the C and Go implementations of jq

The following can also easily be adapted to work with jaq, the Rust implementation of jq. 

# nCk assuming n >= k
def binomial(n; k): 
  if k > n / 2 then binomial(n; n-k)
  else reduce range(1; k+1) as $i (1; . * (n - $i + 1) / $i)
  end;

def forward:
  . as $a
  | reduce range(0; $a|length) as $n (null;
      reduce range(0;$n+1) as $k (.;
        .[$n] += binomial($n; $k) * $a[$k] ) );

def inverse:
  . as $b
  | reduce range (0; $b|length) as $n (null;
      reduce range(0; $n+1) as $k (.; 
        (if (($n - $k) % 2 == 0) then 1 else -1 end) as $sign
        | .[$n] += binomial($n; $k) * $b[$k] * $sign ));

def selfInverting:
  . as $a
  | reduce range(0; $a|length) as $n (null;
      reduce range(0; $n+1) as $k (.;
        (if $k % 2 == 0 then 1 else -1 end) as $sign
        | .[$n] += binomial($n; $k) * $a[$k] * $sign ));

def seqs: [
    [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190],
    [0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0],
    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181],
    [1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37]
];

def names: [
    "Catalan number sequence:",
    "Prime flip-flop sequence:",
    "Fibonacci number sequence:",
    "Padovan number sequence:"
];

def task:
  range(0; seqs|length) as $i
  | names[$i],
    (seqs[$i]|join(" ")),
    "Forward binomial transform:",
    ( (seqs[$i]|forward)
      | join(" "),
      "Inverse binomial transform:",
      ((seqs[$i]|inverse)|join(" ")),
      "Round trip:",
      (inverse|join(" ")) ),
    "Self-inverting:",
    ( (seqs[$i]|selfInverting)
      | join(" "),
        "Re-inverted:",
        (selfInverting|join(" ")) ),
    (select($i < (seqs|length - 1) ) | "") ;

task
Output:

Exactly as at Wren.

Julia

The binomial function is a built-in function in Julia. 

""" forward binomial transform """
binomial_transform(seq) =
    [sum(binomial(n, k) * seq[k+1] for k in 0:n) for n in 0:length(seq)-1]

""" inverse binomial transform """
function inverse_binomial_transform(seq)
    return [sum((-1)^(n - k) * binomial(n, k) * seq[k+1] for k in 0:n) for n in 0:length(seq)-1]
end

const test_sequences = [
    "Catalan number sequence" => [
        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],
    "Fibonacci number sequence" => [
        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],
]

for (s, a) in test_sequences
    println("\n$s:\n", join(a, " "))
    println("Forward binomial transform:\n", join(binomial_transform(a), " "))
    println("Inverse binomial transform:\n", join(inverse_binomial_transform(a), " "))
    println("Re-inverted:\n", join(inverse_binomial_transform(binomial_transform(a)), " "))
end
Output:

Same as C, Go, etc.

Nim

import std/[math, strutils]

const
  Sequences = {"Catalan":
                 [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440],
               "Prime flip-flop":
                 [0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0],
               "Fibonacci":
                 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377],
               "Padovan":
                 [1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]}

func binomialTransform(a: openArray[int]): seq[int] =
  for n in 0..a.high:
    var val = 0
    for k in 0..n:
      val += binom(n, k) * a[k]
    result.add val

func invBinomialSequence(b: openArray[int]): seq[int] =
  for n in 0..b.high:
    var val = 0
    var sign = ord((n and 1) == 0) shl 1 - 1
    for k in 0..n:
      val += binom(n, k) * b[k] * sign
      sign = -sign
    result.add val

for (name, sequence) in Sequences:
  echo name, " sequence:"
  echo sequence.join(" ")
  let forward = binomialTransform(sequence)
  echo "Forward binomial transform:"
  echo forward.join(" ")
  echo "Inverse binomial transform:"
  let inverse = invBinomialSequence(sequence)
  echo inverse.join(" ")
  echo "Inverse of the forward transform:"
  let invForward = invBinomialSequence(forward)
  echo invForward.join(" ")
  echo()
Output:
Catalan sequence:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
Forward binomial transform:
1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885
Inverse binomial transform:
1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537
Inverse of the forward transform:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440

Prime flip-flop sequence:
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0
Forward binomial transform:
0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201
Inverse binomial transform:
0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173
Inverse of the forward transform:
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
Forward binomial transform:
0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811
Inverse binomial transform:
0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377
Inverse of the forward transform:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377

Padovan sequence:
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9
Forward binomial transform:
1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833
Inverse binomial transform:
1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121
Inverse of the forward transform:
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9

Pascal

Free Pascal

Translation of: C
program BinomialTransforms;
{$mode objfpc}{$H+}

uses
  SysUtils;

type
  Int64Array = array[0..19] of Int64;

const
  facs: array[1..20] of UInt64 = (
    1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,
    39916800, 479001600, 6227020800, 87178291200, 1307674368000,
    20922789888000, 355687428096000, 6402373705728000, 121645100408832000,
    2432902008176640000
  );

  Seqs: array[0..3] of Int64Array = (
    (1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900,
    2674440, 9694845, 35357670, 129644790, 477638700, 1767263190),
    (0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0),
    (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181),
    (1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37)
  );

  Names: array[0..3] of string = (
    'Catalan number sequence:',
    'Prime flip-flop sequence:',
    'Fibonacci number sequence:',
    'Padovan number sequence:'
  );

function Factorial(N: Integer): UInt64;
begin
  if (N > 20) or (N < 2) then
    Exit(1);
  Result := facs[N];
end;

function Binomial(N, K: Integer): UInt64;
begin
  Result := Factorial(N) div (Factorial(N - K) * Factorial(K));
end;

procedure BtForward(var B: Int64Array; const A: Int64Array; C: Integer);
var
  N, K: Integer;
begin
  for N := 0 to C - 1 do
  begin
    B[N] := 0;
    for K := 0 to N do
      B[N] := B[N] + Binomial(N, K) * A[K];
  end;
end;

procedure BtInverse(var A: Int64Array; const B: Int64Array; C: Integer);
var
  N, K, Sign: Integer;
begin
  for N := 0 to C - 1 do
  begin
    A[N] := 0;
    for K := 0 to N do
    begin
      Sign := Ord((N - K) and 1 <> 0) * -2 + 1;
      A[N] := A[N] + Binomial(N, K) * B[K] * Sign;
    end;
  end;
end;

procedure BtSelfInverting(var B: Int64Array; const A: Int64Array; C: Integer);
var
  N, K, Sign: Integer;
begin
  for N := 0 to C - 1 do
  begin
    B[N] := 0;
    for K := 0 to N do
    begin
      Sign := Ord(K and 1 <> 0) * -2 + 1;
      B[N] := B[N] + Binomial(N, K) * A[K] * Sign;
    end;
  end;
end;

function LeastSquareDiff(Limit: UInt32): UInt32;
var
  N: UInt32;
begin
  N := Trunc(Sqrt(Limit)) + 1;
  while (N * N) - ((N - 1) * (N - 1)) <= Limit do
    Inc(N);
  Result := N;
end;

var
  I, J: Integer;
  Fwd, Res: Int64Array;

begin

  for I := 0 to 3 do
  begin
    WriteLn(Names[I]);
    for J := 0 to 19 do
      Write(Seqs[I][J], ' ');
    WriteLn;
    
    WriteLn('Forward binomial transform:');
    BtForward(Fwd, Seqs[I], 20);
    for J := 0 to 19 do
      Write(Fwd[J], ' ');
    WriteLn;
    
    WriteLn('Inverse binomial transform:');
    BtInverse(Res, Seqs[I], 20);
    for J := 0 to 19 do
      Write(Res[J], ' ');
    WriteLn;
    
    WriteLn('Round trip:');
    BtInverse(Res, Fwd, 20);
    for J := 0 to 19 do
      Write(Res[J], ' ');
    WriteLn;
    
    WriteLn('Self-inverting:');
    BtSelfInverting(Fwd, Seqs[I], 20);
    for J := 0 to 19 do
      Write(Fwd[J], ' ');
    WriteLn;
    
    WriteLn('Re-inverted:');
    BtSelfInverting(Res, Fwd, 20);
    for J := 0 to 19 do
      Write(Res[J], ' ');
    
  end;
end.
Output:
Same as C

Phix

Translation of: C
with javascript_semantics
function bt_forward(sequence a)
    sequence b = {}
    for n=1 to length(a) do
        atom bn = 0
        for k=1 to n do
            bn += choose(n-1, k-1) * a[k]
        end for
        b &= bn
    end for
    return b
end function

function bt_inverse(sequence b)
    sequence a = {}
    for n=1 to length(b) do
        atom an = 0
        for k=1 to n do
            integer sgn = iff(odd(n-k) ? -1 : 1)
            an += choose(n-1, k-1) * b[k] * sgn
        end for
        a &= an
    end for
    return a
end function

function bt_self_inverting(sequence a)
    sequence b = {}
    for n=1 to length(a) do
        atom bn = 0
        for k=1 to n do
            integer sgn = iff(even(k) ? -1 : 1)
            bn += choose(n-1, k-1) * a[k] * sgn
        end for
        b &= bn
    end for
    return b
end function

sequence tests = {{"Catalan number sequence:",
                   {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}},
                  {"Fibonacci number sequence:",
                   {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}}}

function jd(sequence s) return join(s," ",fmt:="%d") end function

for t in tests do
    sequence {name, s} = t, fwd = bt_forward(s), inv = bt_inverse(s),
                             si = bt_self_inverting(s)
    printf(1,"%s\n%s\n", {name,jd(s)})
    printf(1,"Forward binomial transform:\n%s\n",jd(fwd))
    printf(1,"Inverse binomial transform:\n%s\n",jd(inv))
    printf(1,"Round trip:\n%s\n",jd(bt_inverse(fwd)))
    printf(1,"Self-inverting:\n%s\n",jd(si))
    printf(1,"Re-inverted:\n%s\n\n",jd(bt_self_inverting(si)))
end for
Output:

Same as C, etc.

Python

from math import factorial
from math import pow

from typing import Iterable
from typing import Sequence


def binomial(n: int, k: int) -> int:
    return factorial(n) // (factorial(n - k) * factorial(k))


def binomial_transform(seq: Sequence) -> Iterable[int]:
    for n in range(len(seq)):
        yield sum(binomial(n, k) * seq[k] for k in range(n + 1))


def inverse_binomial_transform(seq: Sequence) -> Iterable[int]:
    for n in range(len(seq)):
        yield int(sum(pow(-1, n - k) * binomial(n, k) * seq[k] for k in range(n + 1)))


test_sequences = {
    "Catalan number sequence": [
        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,
    ],
    "Fibonacci number sequence": [
        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,
    ],
}

if __name__ == "__main__":
    import pprint

    for desc, seq in test_sequences.items():
        print(desc + ":")
        pprint.pprint(seq, compact=True, indent=2)
        print("Forward binomial transform:")
        pprint.pprint(list(binomial_transform(seq)), compact=True, indent=2)
        print("Inverse binomial transform:")
        pprint.pprint(list(inverse_binomial_transform(seq)), compact=True, indent=2)
        print("Round trip:")
        pprint.pprint(
            list(inverse_binomial_transform(list(binomial_transform(seq)))),
            compact=True,
            indent=2,
        )
        print()
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]

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]

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]

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]

Raku

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

RPL

We use here the SEQ and ∑LISTinstructions, available for HP-48G or newer models only.

RPL code Comment 
≪ DUP SIZE → seq n 
   ≪ { 1 } 2 n FOR j
        'COMB(j-1,k)' 'k' 0 j 1 - 1 SEQ
        seq 1 j SUB 
        * ∑LIST +
   NEXT
≫ ≫ ‘FBITR’ STO

≪ DUP SIZE → seq n 
   ≪ { 1 } 2 n FOR j
        '(-1)^(j-k-1)*COMB(j-1,k)' 'k' 0 j 1 - 1 SEQ
        seq 1 j SUB * ∑LIST + 
      NEXT
≫ ≫ ‘RBITR’ STO

FBITR ( { a(n) }  -- { b(n) } ) 
output = { 2 } ; loop for j=2 to n
   get a j-list of c(j-1,k) with k from 0 to j-1
   get a j-list of a(k)
   multiply the 2 lists, reduce and append result to output 
end loop
return list

RBITR ( { b(n) }  -- { a(n) } ) 
same implementation as FBITR 
only the formula for kth term is different here

If wanting to stick to the basic HP-28 instruction set and no algebraic expressions: 

≪ DUP SIZE → seq n 
   ≪ { } 1 n FOR j
         0 1 j FOR k
            seq k GET j 1 - k 1 - COMB * +
      NEXT + NEXT
≫ ≫ ‘FBITR’ STO

≪ DUP SIZE → seq n 
   ≪ { } 1 n FOR j
         0 1 j FOR k
            seq k GET j 1 - k 1 - COMB * -1 j k - ^ * +
      NEXT + NEXT
≫ ≫ ‘RBITR’ STO
Input:
 { 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 } 'ZCAT' STO
 { 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 } 'ZPFF' STO
 { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 } 'ZFIB' STO
 { 1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 }  'ZPAD' STO
 ZCAT FBITR ZCAT RBITR ZCAT FBITR RBITR 
 ZPFF FBITR ZPFF RBITR ZPFF FBITR RBITR 
 ZFIB FBITR ZFIB RBITR ZFIB FBITR RBITR 
 ZPAD FBITR ZPAD RBITR ZPAD FBITR RBITR
Output:
12: { 1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885 }
11: { 1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 }
10: { 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 }
9: { 0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 }
8: { 0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173 }
7: { 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 }
6: { 0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 }
5: { 0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 }
4: { 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 }
3: { 1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833 }
2: { 1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 }
1: { 1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 }

Wren

Library: Wren-long

This hard-codes the sequences to be tested as I couldn't see much point in repeating code from the related tasks. 

import "./long" for Long, ULong

class BT {
    static forward(a) {
        var c = a.count
        var b = List.filled(c, null)
        for (n in 0...c) {
            b[n] = Long.zero
            for (k in 0..n) b[n] = b[n] + ULong.binomial(n, k).toLong * a[k]
        }
        return b
    }

    static inverse(b) {
        var c = b.count
        var a = List.filled(c, null)
        for (n in 0...c) {
            a[n] = Long.zero
            for (k in 0..n) {
                var sign = ((n - k) % 2 == 0) ? 1 : -1
                a[n] = a[n] + ULong.binomial(n, k).toLong * b[k] * sign
            }
        }
        return a
    }

    static selfInverting(a) {
        var c = a.count
        var b = List.filled(c, null)
        for (n in 0...c) {
            b[n] = Long.zero
            for (k in 0..n) {
                var sign = k % 2 == 0 ? 1 : -1
                b[n] = b[n] + ULong.binomial(n, k).toLong * a[k] * sign
            }
        }
        return b
    }
}

var seqs = [
    [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190],
    [0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0],
    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181],
    [1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37]
]

var names = [
    "Catalan number sequence:",
    "Prime flip-flop sequence:",
    "Fibonacci number sequence:",
    "Padovan number sequence:"
]

var saved
for (i in 0...seqs.count) {
    System.print(names[i])
    System.print(seqs[i].join(" "))
    System.print("Forward binomial transform:")
    System.print((saved = BT.forward(seqs[i])).join(" "))
    System.print("Inverse binomial transform:")
    System.print(BT.inverse(seqs[i]).join(" "))
    System.print("Round trip:")
    System.print(BT.inverse(saved).join(" "))
    System.print("Self-inverting:")
    System.print((saved = BT.selfInverting(seqs[i])).join(" "))
    System.print("Re-inverted:")
    System.print(BT.selfInverting(saved).join(" "))
    if (i < seqs.count - 1) System.print()
}
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

XPL0

Translation of: C
func real Factorial(N);
int  N, I;
real F;
[F:= 1.;
for I:= 2 to N do F:= F * float(I);
return F;
];

func real Binomial(N, K);
int N, K;
return Factorial(N) / Factorial(N-K) / Factorial(K);

proc BinomialFwd(A, B, M);
real A, B; int M;
int  N, K;
[for N:= 0 to M-1 do
    [B(N):= 0.;
    for K:= 0 to N do
        B(N):= B(N) + Binomial(N, K) * A(K);
    ];
];

proc BinomialInv(A, B, M);
real A, B; int M;
int N, K, Sign;
[for N:= 0 to M-1 do
    [A(N):= 0.;
    for K:= 0 to N do
        [Sign:= if N-K & 1 then -1 else 1;            
        A(N):= A(N) + float(Sign) * Binomial(N, K) * B(K);
        ];
    ];
];

real Fwd(20), Inv(20), Seqs;
int  Title, I, J;
[Seqs:= [
 [1., 1., 2., 5., 14., 42., 132., 429., 1430., 4862., 16796., 58786., 208012.,
  742900., 2674440., 9694845., 35357670., 129644790., 477638700., 1767263190.],
 [0., 1., 1., 0., 1., 0., 1., 0., 0., 0., 1., 0., 1., 0., 0., 0., 1., 0., 1., 0.],
 [0., 1., 1., 2., 3., 5., 8., 13., 21., 34., 55., 89., 144., 233., 377., 610.,
  987., 1597., 2584., 4181.],
 [1., 0., 0., 1., 0., 1., 1., 1., 2., 2., 3., 4., 5., 7., 9., 12., 16., 21., 28., 37.]];
Title:= [
    "Catalan number sequence:",
    "Prime flip-flop sequence:",
    "Fibonacci number sequence:",
    "Padovan number sequence:" ];
Format(1,0);
for I:= 0 to 4-1 do
    [Text(0, Title(I));  CrLf(0);
    for J:= 0 to 20-1 do [RlOut(0, Seqs(I,J));  ChOut(0, ^ )];

    Text(0, "^m^jForward binomial transform:^m^j");
    BinomialFwd(Seqs(I), Fwd, 20);
    for J:= 0 to 20-1 do [RlOut(0, Fwd(J));  ChOut(0, ^ )];

    Text(0, "^m^jInverse binomial transform:^m^j");
    BinomialInv(Inv, Seqs(I), 20);
    for J:= 0 to 20-1 do [RlOut(0, Inv(J));  ChOut(0, ^ )];

    Text(0, "^m^jRound trip:^m^j");
    BinomialInv(Inv, Fwd, 20);
    for J:= 0 to 20-1 do [RlOut(0, Inv(J));  ChOut(0, ^ )];
    if I < 3 then CrLf(0);
    CrLf(0);
    ];
]
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 

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 

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 

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
Retrieved from "https://rosettacode.org/wiki/Binomial_transform?oldid=363339"