|
|
A287709
|
|
Number of Dyck paths of semilength n such that every peak at level y > 1 is preceded by (at least) one peak at level y-1.
|
|
2
|
|
|
1, 1, 1, 2, 4, 9, 22, 57, 154, 430, 1234, 3625, 10865, 33136, 102598, 321913, 1021963, 3278543, 10617413, 34678693, 114151769, 378436049, 1262822229, 4239469076, 14312153289, 48567846377, 165610404277, 567259571451, 1951218773118, 6738242931451, 23356148951482
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Also number of Dyck paths of semilength (n-1) whose maximum height is attained by the initial ascent. (That is, Dyck paths with prefix U^kD, k>=1, and maximum height k.) For a(3)=2: UDUD, UUDD. For a(4)=3: UDUDUD, UUDUDD, UUDDUD, UUUDDD. (Andrei Asinowski and Vít Jelínek) - Andrei Asinowski, Jun 21 2021
|
|
REFERENCES
|
Andrei Asinowski and Vít Jelínek. Two types of Dyck paths (unpublished manuscript).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: 1 + Sum_{k>=0} x^(k+1)/U_{k+1}(1/(2*x)), where U_{k}(x) is the k-th Chebyshev polynomial of the second kind. - Andrei Asinowski, Jun 21 2021
a(n) = Sum_{j=0..n-2} L(n-2, j) for n > 1 with a(0) = a(1) = 1 where L(n, j) = Sum_{p=0..n - j - 1} binomial(j + p, p)*L(n - j - 1, p) for 0 <= j < n with L(n, n) = 1. Perhaps this recursion can be used to find a simple closed form. See A059715 for similar recursions. - Mikhail Kurkov, Oct 16 2023 [verification needed]
a(n) ~ ((4*Pi)^(5/6) * log(2)^(1/3) / sqrt(3)) * 4^n * exp(-3*(Pi*log(2)/2)^(2/3) * n^(1/3)) * n^(-5/6) [Bacher, 2024, see also Guttmann, 2014, p. 21]. - Vaclav Kotesovec, Mar 14 2024
|
|
EXAMPLE
|
. a(3) = 2: /\
. /\/\/\ /\/ \ ,
.
. a(4) = 4: /\ /\ /\/\
. /\/\/\/\ /\/\/ \ /\/ \/\ /\/ \ .
|
|
MAPLE
|
b:= proc(x, y, k) option remember; `if`(x=0, 1,
`if`(y>0, b(x-1, y-1, max(y, k)), 0)+
`if`(y<=k and y<x-1, b(x-1, y+1, k), 0))
end:
a:= n-> b(2*n, 0$2):
seq(a(n), n=0..35);
|
|
MATHEMATICA
|
b[x_, y_, k_] := b[x, y, k] = If[x == 0, 1, If[y > 0, b[x - 1, y - 1, Max[y, k]], 0] + If[y <= k && y < x - 1, b[x - 1, y + 1, k], 0]];
a[n_] := b[2n, 0, 0];
nmax = 30; CoefficientList[Series[1 + Sum[(Sqrt[x])^(k + 1)/ChebyshevU[k + 1, 1/(2*Sqrt[x])], {k, 0, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, after Andrei Asinowski, Jun 22 2021 *)
|
|
PROG
|
(PARI) upto(n) = if(n < 2, vector(n+1, i, 1), n -= 1; my(v1, v2, v3); v1 = vector(n, i, vector(i, j, i == j)); v2 = vector(n, i, i == 1); v3 = vector(n, i, vector(i, j, (j == 1) || (j == i))); for(i = 3, n, for(j = 2, i - 1, v3[i][j] = v3[i - 1][j] + v3[i - 1][j - 1])); for(i = 1, n - 1, for(j = 0, i - 1, v1[i + 1][j + 1] = sum(p = 0, i - j - 1, v3[j + p + 1][p + 1] * v1[i - j][p + 1])); v2[i + 1] = vecsum(v1[i + 1])); concat([1, 1], v2)) \\ Mikhail Kurkov, Oct 16 2023 [verification needed]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,changed
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|