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

Author

David Scambler and Alois P. Heinz, Oct 31 2013

Keywords

• nonn

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.

Examples

			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.
		

Links

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

Crossrefs

Cf. A000108, A128714.

Row sums of A274372 and of A274404.

Programs

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 *)

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