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.

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