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

Author

Alois P. Heinz, Jun 26 2013

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

Column k=2 of A330942.

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

Programs

Maple

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

Mathematica

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

PARI

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

Formula

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