login
Number of hill-free Schroeder paths of length 2n that have no horizontal steps on the x-axis.
7

%I #43 Nov 10 2022 06:31:00

%S 1,0,2,6,26,114,526,2502,12194,60570,305526,1560798,8058714,41987106,

%T 220470942,1165553718,6198683090,33140219946,178012804678,

%U 960232902606,5199384505226,28250295397170,153977094874862,841656387060006

%N Number of hill-free Schroeder paths of length 2n that have no horizontal steps on the x-axis.

%C A Schroeder path of length 2n is a lattice path from (0, 0) to (2n, 0) consisting of U = (1,1), D = (1,-1) and H = (2,0) steps and never going below the x-axis. A hill is a peak at height 1.

%C Hankel transform is 2^C(n+1,2) (A006125(n+1)). Hankel transform of a(n+1) is (2-2^(n+1))*2^C(n+1,2). - _Paul Barry_, Oct 31 2008

%H Michael De Vlieger, <a href="/A114710/b114710.txt">Table of n, a(n) for n = 0..1000</a>

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Barry3/barry252.html">On the Inverses of a Family of Pascal-Like Matrices Defined by Riordan Arrays</a>, Journal of Integer Sequences, 16 (2013), #13.5.6.

%H Shishuo Fu and Yaling Wang, <a href="https://arxiv.org/abs/1908.03912">Bijective recurrences concerning two Schröder triangles</a>, arXiv:1908.03912 [math.CO], 2019.

%F G.f.: A(x) = 2/(1+3*x+sqrt(1-6*x+x^2)).

%F D-finite with recurrence 3*(n+1)*a(n) +(11-16*n)*a(n-1) -9*n*a(n-2) +2*(n-2)*a(n-3)=0. - _R. J. Mathar_, Nov 07 2012

%F G.f.: 1/(Q(0) + 2*x) where Q(k) = 1 + k*(1-x) - x - x*(k+1)*(k+2)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Mar 14 2013

%F a(n) = (-1)^n*Sum_{k=0..n} binomial(n, k)*hypergeom([k - n, n + 1], [k + 2], 2). - _Peter Luschny_, Jan 08 2018

%F O.g.f. A(x) = 1/x * series reversion of x*(1 - 3*x)/((1 - x)*(1 - 2*x)). Cf. A297705. - _Peter Bala_, Nov 08 2022

%F a(n) ~ (9 + 4*sqrt(2)) * (1 + sqrt(2))^(2*n + 1) / (49 * sqrt(Pi) * 2^(3/4) * n^(3/2)). - _Vaclav Kotesovec_, Nov 10 2022

%e a(3) = 6 because we have UHHD, UHUDD, UUDHD, UUDUDD, UUHDD and UUUDDD.

%p G:=2/(1+3*z+sqrt(1-6*z+z^2)): Gser:=series(G,z=0,32):

%p 1,seq(coeff(Gser,z^n),n=1..27);

%p # Alternative:

%p a := proc(n) option remember; if n < 3 then return [1, 0, 2, 6][n+1] fi;

%p ((4 - 2*n)*a(n-3) + (16*n - 11)*a(n-1) + 9*n*a(n-2))/(3*n + 3) end:

%p seq(a(n), n = 0..23); # _Peter Luschny_, Nov 10 2022

%t A114710[n_] := (-1)^n Sum[Binomial[n, k] Hypergeometric2F1[k - n, n + 1, k + 2, 2], {k, 0, n}]; Table[A114710[n], {n, 0, 23}] (* _Peter Luschny_, Jan 08 2018 *)

%t InverseInvertTransform[ser_, n_] := CoefficientList[Series[ser/(1 + x ser), {x, 0, n}], x]; LittleSchroeder := (1 + x - Sqrt[1 - 6 x + x^2])/(4 x); (* A001003 *)

%t InverseInvertTransform[LittleSchroeder, 23] (* _Peter Luschny_, Jan 10 2019 *)

%Y Column 0 of A114709.

%Y Cf. A001003, A104219, A297705.

%K nonn,easy

%O 0,3

%A _Emeric Deutsch_, Dec 26 2005