A226996 Number of lattice paths from (0,0) to (n,n) consisting of steps U=(1,1), H=(1,0) and S=(0,1) such that the first step leaving and the last step joining the diagonal (if any) is an H step.

1, 1, 2, 10, 59, 339, 1908, 10660, 59493, 332469, 1861910, 10451086, 58793535, 331434215, 1871929768, 10590886536, 60014622089, 340566437545, 1935134951402, 11008701669202, 62694973984771, 357406440776891, 2039344466594972, 11646264778160300, 66561506740727149

Offset

0,3

Links

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

Formula

G.f.: sqrt(x^2-6*x+1)/(4*(x-1)^2)+1/(4*sqrt(x^2-6*x+1))-1/(2*(x-1)). - Vaclav Kotesovec, Jun 27 2013

a(n) ~ sqrt(8+6*sqrt(2))*(3+2*sqrt(2))^n/(16*sqrt(Pi*n)). - Vaclav Kotesovec, Jun 27 2013

Example

a(0) = 1: the empty path.
a(1) = 1: U.
a(2) = 2: HSSH, UU.
a(3) = 10: HHSSSH, HSHSSH, HSSHSH, HSSHU, HSSSHH, HSSUH, HSUSH, HUSSH, UHSSH, UUU.

Maple

a:= proc(n) option remember; `if`(n<4, [1, 1, 2, 10][n+1],
     ((8*n^3-35*n^2+49*n-21)*a(n-1) -(2*n-3)*(7*n^2-21*n+15)*a(n-2)
      +(8*n^3-37*n^2+55*n-27)*a(n-3) -(n-3)*(n-1)^2*a(n-4))
     / (n*(n-2)^2))
    end:
seq(a(n), n=0..30);

Mathematica

CoefficientList[Series[Sqrt[x^2-6*x+1]/(4*(x-1)^2)+1/(4*Sqrt[x^2-6*x+1])-1/(2*(x-1)), {x, 0, 20}], x] (* Vaclav Kotesovec, Jun 27 2013 *)

Crossrefs

Cf. A001850 (unrestricted paths), A006318 (subdiagonal paths), A226994, A226995.

Sequence in context: A218944 A124964 A026132 * A370247 A370273 A309955

Adjacent sequences: A226993 A226994 A226995 * A226997 A226998 A226999

Keyword

nonn

Author

Alois P. Heinz, Jun 26 2013

Status

approved