cp's OEIS Frontend

A304778 Number of Carlitz compositions c of n such that the sequence of ascents and descents of c forms a Dyck path.

%I A304778 #15 May 31 2018 13:10:46
%S A304778 1,1,1,1,2,2,4,6,9,15,23,38,62,100,163,267,441,725,1198,1986,3291,
%T A304778 5472,9116,15204,25399,42494,71183,119396,200507,337090,567318,955749,
%U A304778 1611672,2720212,4595198,7768975,13145109,22258264,37716358,63953853,108515011
%N A304778 Number of Carlitz compositions c of n such that the sequence of ascents and descents of c forms a Dyck path.
%H A304778 Alois P. Heinz, <a href="/A304778/b304778.txt">Table of n, a(n) for n = 0..1000</a>
%H A304778 Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path#Counting_lattice_paths">Counting lattice paths</a>
%F A304778 a(n) ~ c * d^n / n^(3/2), where d = A241902 = 1.7502412917183090312497386246... and c = 7.0142545527132612683043468956... - _Vaclav Kotesovec_, May 22 2018
%e A304778 a(6) = 4: 132, 141, 231, 6.
%e A304778 a(7) = 6: 12121, 142, 151, 232, 241, 7.
%e A304778 a(8) = 9: 12131, 13121, 143, 152, 161, 242, 251, 341, 8.
%e A304778 a(9) = 15: 12132, 12141, 12321, 13131, 14121, 153, 162, 171, 23121, 243, 252, 261, 342, 351, 9.
%p A304778 b:= proc(n, l, c) option remember; `if`(c<0 and l>0, 0,
%p A304778       `if`(n=0, `if`(l<0 or c=0, 1, 0), add(`if`(i=l, 0,
%p A304778        b(n-i, i, c+`if`(i>l, 1, -1))), i=1..n)))
%p A304778     end:
%p A304778 a:= n-> b(n, -1$2):
%p A304778 seq(a(n), n=0..50);
%t A304778 b[n_, l_, c_] := b[n, l, c] = If[c<0 && l>0, 0, If[n==0, If[l<0 || c==0, 1, 0], Sum[If[i==l, 0, b[n-i, i, c + If[i>l, 1, -1]]], {i, 1, n}]]];
%t A304778 a[n_] := b[n, -1, -1];
%t A304778 Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, May 31 2018, from Maple *)
%Y A304778 Cf. A003242, A303287, A304777.
%K A304778 nonn
%O A304778 0,5
%A A304778 _Alois P. Heinz_, May 18 2018