login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
1, 2, 7, 32, 161, 842, 4495, 24320, 132865, 731282, 4048727, 22523360, 125797985, 704966810, 3961924127, 22321190912, 126027618305, 712917362210, 4039658528935, 22924714957472, 130271906898721, 741188107113962, 4221707080583087, 24070622500965632 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

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

LINKS

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

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

EXAMPLE

a(0) = 1: the empty path.

a(1) = 2: HS, U.

a(2) = 7: HHSS, HSHS, HSSH, HSU, HUS, UHS, UU.

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

PROG

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

CROSSREFS

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

Sequence in context: A168494 A181376 A183951 * A268297 A263532 A108524

Adjacent sequences:  A226991 A226992 A226993 * A226995 A226996 A226997

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Jun 26 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 19 11:09 EST 2019. Contains 329319 sequences. (Running on oeis4.)