Binomial transform: Difference between revisions
Content added Content deleted
(→{{header|Wren}}: Although we don't have any here, allow for negative sequence members in 'forward' method.) |
(Add Python) |
||
Line 56: | Line 56: | ||
;* [[oeis:A144413|OEIS:A144413 - a(n) = Sum_{k=0..n} (-1)^k * binomial(n, k) * A000931(n-k+4) (Inverse binomial transform of Padovan sequence)]] |
;* [[oeis:A144413|OEIS:A144413 - a(n) = Sum_{k=0..n} (-1)^k * binomial(n, k) * A000931(n-k+4) (Inverse binomial transform of Padovan sequence)]] |
||
=={{header|Python}}== |
|||
<syntaxhighlight lang="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() |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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] |
|||
</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |