A226995 -id:A226995 - cp's OEIS frontend

A226994 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 the diagonal (if any) is an H step.

1, 2, 7, 32, 161, 842, 4495, 24320, 132865, 731282, 4048727, 22523360, 125797985, 704966810, 3961924127, 22321190912, 126027618305, 712917362210, 4039658528935, 22924714957472, 130271906898721, 741188107113962, 4221707080583087, 24070622500965632

Offset: 0

Alois P. Heinz, Jun 26 2013

nonn

a(n) is also the n-th order truncated expansion in x and y of 1/(1-x*y+x+y) evaluated at x=1, y=1 (see Mathematica code). - Benedict W. J. Irwin, Oct 06 2016

			a(0) = 1: the empty path.
a(1) = 2: HS, U.
a(2) = 7: HHSS, HSHS, HSSH, HSU, HUS, UHS, UU.

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

Column k=2 of A330942.

Cf. A001850 (unrestricted paths), A006318 (subdiagonal paths), A047665, A182626, A226995, A226996.

a:= proc(n) option remember; `if`(n<3, n*(2*n-1)+1,
     ((n-2)*(2*n-1) *a(n-3) -(7*n-4)*(2*n-3) *a(n-2)
      +(2*n-1)*(7*n-10) *a(n-1))/ (n*(2*n-3)))
    end:
seq(a(n), n=0..25);

Table[CoefficientList[Series[1/(1-x*y+x+y), {x, 0, n}, {y, 0, n}], z][[1]] /.x -> 1 /. y -> 1, {n, 0, 10}] (* Benedict W. J. Irwin, Oct 06 2016 *)

a(n) = 1/2 + pollegendre(n, 3)/2; \\ Michel Marcus, Oct 06 2016

G.f.: 1/(2-2*x) + 1/(2*sqrt(1-6*x+x^2)).
a(n) = A001850(n) - A047665(n).
a(n) = 1/2 + LegendreP(n, 3)/2. - Benedict W. J. Irwin, Oct 06 2016
a(n) ~ sqrt(3*sqrt(2) + 4) * (3 + 2*sqrt(2))^n / (4*sqrt(2*Pi*n)). - Vaclav Kotesovec, Oct 07 2016
a(n) = Sum_{k=0..n} (-1)^k * A182626(k). - J. Conrad, Apr 08 2018
a(n) = 1 + Sum_{k=1..n} binomial(n,k)^2 * 2^(k-1). - Ilya Gutkovskiy, Nov 15 2021
a(n) = 1 + A047665(n). - Alois P. Heinz, Nov 15 2021

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.

Original entry on oeis.org

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

Alois P. Heinz, Jun 26 2013

nonn

			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.

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

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

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

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

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

cp's OEIS Frontend

A226994 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 the diagonal (if any) is an H step.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula