Binomial transform: Difference between revisions

=={{header|Arturo}}==

<syntaxhighlight lang="arturo">; by @Krenium

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 ""

]</syntaxhighlight>

{{out}}

<pre>-~~=====<{ 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</pre>