A230823 Number of modified skew Dyck paths of semilength n.

1, 1, 2, 6, 20, 73, 281, 1124, 4627, 19474, 83421, 362528, 1594389, 7083078, 31738724, 143281473, 651048571, 2975243348, 13665866849, 63055369522, 292130900461, 1358415528683, 6337824891559, 29660089051015, 139193062791189, 654903798282528, 3088627236146085

Offset

0,3

Comments

A modified skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1) (up), D=(1,-1) (down) and A=(-1,1) (anti-down) so that A and D steps do not overlap.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..600

Formula

a(n) ~ c * 5^n / n^(3/2), where c = 0.27726256768213709977373928535... . - Vaclav Kotesovec, Jul 16 2014

G.f.: 1/(1 - x/(1 - (x + x^2)/(1 - (x + x^2 + x^3)/(1 - (x + x^2 + x^3 + x^4)/(1 - ...))))), a continued fraction (conjecture). - Ilya Gutkovskiy, Jun 08 2017

Example

a(0) = 1: the empty path.
a(1) = 1: UD.
a(2) = 2: UUDD, UDUD.
a(3) = 6: UUUDDD, UUDUDD, UUDDUD, UAUDDD, UDUUDD, UDUDUD.
a(4) = 20: UUUUDDDD, UUUDUDDD, UUUDDUDD, UUUDDDUD, UUAUDDDD, UUDUUDDD, UUDUDUDD, UUDUDDUD, UUDDUUDD, UUDDUDUD, UAUUDDDD, UAUDUDDD, UAUDDUDD, UAUDDDUD, UDUUUDDD, UDUUDUDD, UDUUDDUD, UDUAUDDD, UDUDUUDD, UDUDUDUD.
a(5) = 73: UUUUUDDDDD, UUUUDUDDDD, UUUUDDUDDD, ..., UDUDUAUDDD, UDUDUDUUDD, UDUDUDUDUD.

Maple

b:= proc(x, y, t, n) option remember; `if`(y>n, 0,
      `if`(n=y, `if`(t=2, 0, 1), b(x+1, y+1, 0, n-1)+
      `if`(t<>1 and x>0, b(x-1, y+1, 2, n-1), 0)+
      `if`(t<>2 and y>0, b(x+1, y-1, 1, n-1), 0)))
    end:
a:= n-> b(0$3, 2*n):
seq(a(n), n=0..30);

Mathematica

b[x_, y_, t_, n_] := b[x, y, t, n] = If[y > n, 0, If[n == y, If[t == 2, 0, 1], b[x+1, y+1, 0, n-1] + If[t != 1 && x > 0, b[x-1, y+1, 2, n-1], 0] + If[t != 2 && y > 0, b[x+1, y-1, 1, n-1], 0]] ]; a[n_] := b[0, 0, 0, 2*n]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 16 2013, translated from Maple *)

Crossrefs

Cf. A000108, A128714.

Row sums of A274372 and of A274404.

Sequence in context: A052884 A150140 A061396 * A192497 A104632 A194956

Adjacent sequences: A230820 A230821 A230822 * A230824 A230825 A230826

Keyword

nonn

Author

David Scambler and Alois P. Heinz, Oct 31 2013

Status

approved