login
A304778
Number of Carlitz compositions c of n such that the sequence of ascents and descents of c forms a Dyck path.
3
1, 1, 1, 1, 2, 2, 4, 6, 9, 15, 23, 38, 62, 100, 163, 267, 441, 725, 1198, 1986, 3291, 5472, 9116, 15204, 25399, 42494, 71183, 119396, 200507, 337090, 567318, 955749, 1611672, 2720212, 4595198, 7768975, 13145109, 22258264, 37716358, 63953853, 108515011
OFFSET
0,5
LINKS
FORMULA
a(n) ~ c * d^n / n^(3/2), where d = A241902 = 1.7502412917183090312497386246... and c = 7.0142545527132612683043468956... - Vaclav Kotesovec, May 22 2018
EXAMPLE
a(6) = 4: 132, 141, 231, 6.
a(7) = 6: 12121, 142, 151, 232, 241, 7.
a(8) = 9: 12131, 13121, 143, 152, 161, 242, 251, 341, 8.
a(9) = 15: 12132, 12141, 12321, 13131, 14121, 153, 162, 171, 23121, 243, 252, 261, 342, 351, 9.
MAPLE
b:= proc(n, l, c) option remember; `if`(c<0 and l>0, 0,
`if`(n=0, `if`(l<0 or c=0, 1, 0), add(`if`(i=l, 0,
b(n-i, i, c+`if`(i>l, 1, -1))), i=1..n)))
end:
a:= n-> b(n, -1$2):
seq(a(n), n=0..50);
MATHEMATICA
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}]]];
a[n_] := b[n, -1, -1];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, May 31 2018, from Maple *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, May 18 2018
STATUS
approved