Binomial transform: Difference between revisions
Added Go
(Add Python) |
(Added Go) |
||
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|Go}}==
<syntaxhighlight lang="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 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))
if i < len(seqs)-1 {
fmt.Println()
}
}
}</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|Python}}==
| |||