A309976 Vacation Dyck paths. Discrete analog for vacation M/M/1 queue embedded chain.

1, 0, 0, 1, 0, 2, 1, 5, 4, 15, 14, 48, 49, 159, 173, 540, 616, 1869, 2211, 6565, 7994, 23335, 29092, 83756, 106489, 303093, 391815, 1104490, 1448313, 4049108, 5375784, 14922313, 20028144, 55248554, 74869485, 205394737, 280737471, 766396430, 1055627409, 2869157740, 3979545798, 10773488687, 15037617603

Offset

0,6

Comments

The Dyck path starts in red. At any point at any height > 0, the path can take a horizontal step and its color will change to blue. The color remains blue until the first time the path visits the y=0 line, at which point it changes to red again.

Links

Table of n, a(n) for n=0..42.

Formula

G.f: (sqrt(-4*z^2 + 1) + 1)/(z*sqrt(-4*z^2 + 1) + sqrt(-4*z^2 + 1) - z + 1).

D-finite with recurrence: n*a(n) -n*a(n-1) +6*(-n+2)*a(n-2) +3*(n-4)*a(n-3) +8*(n-3)*a(n-4) +4*(n-3)*a(n-5)=0. - R. J. Mathar, Jan 27 2020

Example

For n=0, the only path is the empty path, so a(0)=1.
For n=1 and n=2, it is impossible to construct such a path, so a(1)=a(2)=0.

Prog

(PARI) a(n) = my(z='z+O('z^(n+1))); Vec((sqrt(-4*z^2 + 1) + 1)/(z*sqrt(-4*z^2 + 1) + sqrt(-4*z^2 + 1) - z + 1))[n+1] \\ Jianing Song, Nov 21 2019

Crossrefs

Sequence in context: A079285 A240607 A304298 * A257516 A346800 A124660

Adjacent sequences: A309973 A309974 A309975 * A309977 A309978 A309979

Keyword

nonn

Author

Igor Kleiner, Aug 25 2019

Status

approved