Binomial transform: Difference between revisions

Content added Content deleted

Inline

@@ Line 55: / Line 55: @@
 ;* [[oeis:A034943|OEIS:A034943 - 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|C}}==
+<syntaxhighlight lang="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;
+        }
+    }
+}
+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]);
+        if (i < 3) printf("\n\n"); else printf("\n");
+    }
+    return 0;
+}</syntaxhighlight>
+{{out}}
+<pre>
+Catalan number sequence:
+1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190
+Forward binomial transform:
+2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885 390248055 1777495635 8140539950 37463689775 173164232965
+Inverse binomial transform:
+0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595
+Round trip:
+1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190
+Prime flip-flop sequence:
+1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
+Forward binomial transform:
+1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 9948 19793 40562 84271 174952
+Inverse binomial transform:
+1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173 -9918 19761 -40528 84235 -174914
+Round trip:
+1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
+Fibonacci number sequence:
+1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
+Forward binomial transform:
+1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169
+Inverse binomial transform:
+1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 610 -987 1597 -2584 4181
+Round trip:
+1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
+Padovan number sequence:
+0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37
+Forward binomial transform:
+1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833 55405 128801 299426 696081 1618192
+Inverse binomial transform:
+-1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 -3185 7137 -13920 24301 -37926
+Round trip:
+0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37
+</pre>
 =={{header|Go}}==