Binomial transform: Difference between revisions
Add Python
(→{{header|Wren}}: Although we don't have any here, allow for negative sequence members in 'forward' method.) |
(Add Python) |
||
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)]]
=={{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}}==
| |||