|
%I #44 Nov 15 2021 17:08:29
%S 1,2,7,32,161,842,4495,24320,132865,731282,4048727,22523360,125797985,
%T 704966810,3961924127,22321190912,126027618305,712917362210,
%U 4039658528935,22924714957472,130271906898721,741188107113962,4221707080583087,24070622500965632
%N 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.
%C 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
%H Alois P. Heinz, <a href="/A226994/b226994.txt">Table of n, a(n) for n = 0..1000</a>
%F G.f.: 1/(2-2*x) + 1/(2*sqrt(1-6*x+x^2)).
%F a(n) = A001850(n) - A047665(n).
%F a(n) = 1/2 + LegendreP(n, 3)/2. - _Benedict W. J. Irwin_, Oct 06 2016
%F a(n) ~ sqrt(3*sqrt(2) + 4) * (3 + 2*sqrt(2))^n / (4*sqrt(2*Pi*n)). - _Vaclav Kotesovec_, Oct 07 2016
%F a(n) = Sum_{k=0..n} (-1)^k * A182626(k). - _J. Conrad_, Apr 08 2018
%F a(n) = 1 + Sum_{k=1..n} binomial(n,k)^2 * 2^(k-1). - _Ilya Gutkovskiy_, Nov 15 2021
%F a(n) = 1 + A047665(n). - _Alois P. Heinz_, Nov 15 2021
%e a(0) = 1: the empty path.
%e a(1) = 2: HS, U.
%e a(2) = 7: HHSS, HSHS, HSSH, HSU, HUS, UHS, UU.
%p a:= proc(n) option remember; `if`(n<3, n*(2*n-1)+1,
%p ((n-2)*(2*n-1) *a(n-3) -(7*n-4)*(2*n-3) *a(n-2)
%p +(2*n-1)*(7*n-10) *a(n-1))/ (n*(2*n-3)))
%p end:
%p seq(a(n), n=0..25);
%t 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 *)
%o (PARI) a(n) = 1/2 + pollegendre(n, 3)/2; \\ _Michel Marcus_, Oct 06 2016
%Y Column k=2 of A330942.
%Y Cf. A001850 (unrestricted paths), A006318 (subdiagonal paths), A047665, A182626, A226995, A226996.
%K nonn
%O 0,2
%A _Alois P. Heinz_, Jun 26 2013
|
