login
Number of Dyck paths of semilength n such that the number of peaks in each level is a Fibonacci number.
2

%I #14 Jun 02 2018 10:37:46

%S 1,1,2,5,13,41,120,389,1251,4137,13853,46808,159861,550275,1905212,

%T 6634122,23214226,81553913,287563509,1017218432,3608376287,

%U 12832434230,45739760100,163366352143,584561531878,2095201468853,7521163557074,27036493662583,97313177034670

%N Number of Dyck paths of semilength n such that the number of peaks in each level is a Fibonacci number.

%H Alois P. Heinz, <a href="/A288388/b288388.txt">Table of n, a(n) for n = 0..600</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci number</a>

%e 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: /\/\/\/\.

%p q:= n-> (t-> issqr(t+4) or issqr(t-4))(5*n^2):

%p b:= proc(n, j) option remember; `if`(n=j, 1, add(b(n-j, i)*

%p add(`if`(q(t), binomial(i, t)*binomial(j-1, i-1-t), 0),

%p t=max(0, i-j)..min(n-j, i-1)), i=1..n-j))

%p end:

%p a:= n-> `if`(n=0, 1, add(`if`(q(k), b(n, k), 0), k=1..n)):

%p seq(a(n), n=0..30);

%t q[n_] := Function[t, IntegerQ @ Sqrt[t+4] || IntegerQ @ Sqrt[t-4]][5n^2];

%t 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}]];

%t a[n_] := If[n == 0, 1, Sum[If[q[k], b[n, k], 0], {k, 1, n}]];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jun 02 2018, from Maple *)

%Y Cf. A000045, A000108, A288390.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Jun 08 2017