login
A288388
Number of Dyck paths of semilength n such that the number of peaks in each level is a Fibonacci number.
2
1, 1, 2, 5, 13, 41, 120, 389, 1251, 4137, 13853, 46808, 159861, 550275, 1905212, 6634122, 23214226, 81553913, 287563509, 1017218432, 3608376287, 12832434230, 45739760100, 163366352143, 584561531878, 2095201468853, 7521163557074, 27036493662583, 97313177034670
OFFSET
0,3
LINKS
EXAMPLE
a(4) = 13 = A000108(4) - 1 because one Dyck path of semilength 4 has 4 peaks in the first level and 4 is not a Fibonacci number: /\/\/\/\.
MAPLE
q:= n-> (t-> issqr(t+4) or issqr(t-4))(5*n^2):
b:= proc(n, j) option remember; `if`(n=j, 1, add(b(n-j, i)*
add(`if`(q(t), binomial(i, t)*binomial(j-1, i-1-t), 0),
t=max(0, i-j)..min(n-j, i-1)), i=1..n-j))
end:
a:= n-> `if`(n=0, 1, add(`if`(q(k), b(n, k), 0), k=1..n)):
seq(a(n), n=0..30);
MATHEMATICA
q[n_] := Function[t, IntegerQ @ Sqrt[t+4] || IntegerQ @ Sqrt[t-4]][5n^2];
b[n_, j_] := b[n, j] = If[n == j, 1, Sum[b[n - j, i]*Sum[If[q[t], Binomial[i, t]*Binomial[j - 1, i - 1 - t], 0], {t, Max[0, i - j], Min[n - j, i - 1]}], {i, 1, n - j}]];
a[n_] := If[n == 0, 1, Sum[If[q[k], b[n, k], 0], {k, 1, n}]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 02 2018, from Maple *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jun 08 2017
STATUS
approved