|
%I #117 Sep 22 2023 07:51:53
%S 0,1,1,3,9,31,113,431,1697,6847,28161,117631,497665,2128127,9183489,
%T 39940863,174897665,770452479,3411959809,15181264895,67833868289,
%U 304256253951,1369404661761,6182858317823,27995941060609,127100310290431,578433619525633,2638370120138751
%N Expansion of g.f. (1-sqrt(1-4*x-4*x^2))/(2*(1+x)).
%C A simple context-free grammar.
%C Number of lattice paths from (0,0) to (2n-2,0) that stay (weakly) in the first quadrant and such that each step is either U=(1,1), D=(1,-1), or L=(3,1). Equivalently, underdiagonal lattice paths from (0,0) to (n-1,n-1) and such that each step is either (1,0), (0,1), or (2,1). E.g., a(4)=9 because in addition to the five Dyck paths from (0,0) to (6,0) [UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD] we have LDUD, LUDD, ULDD and UDLD. - _Emeric Deutsch_, Dec 21 2003
%C Hankel transform of a(n+1) is A006125(n+1). - _Paul Barry_, Apr 01 2007
%C Also, a(n+1) is the number of walks from (0,0) to (n,0) using steps (1,1), (1,-1) and (0,-1). See the U(n,k) array in A071943, where A052709(n+1) = U(n,0). - _N. J. A. Sloane_, Mar 29 2013
%C Diagonal sums of triangle in A085880. - _Philippe Deléham_, Nov 15 2013
%C From _Gus Wiseman_, Jun 17 2021: (Start)
%C Conjecture: For n > 0, also the number of sequences of length n - 1 covering an initial interval of positive integers and avoiding three terms (..., x, ..., y, ..., z, ...) such that x <= y <= z. The version avoiding the strict pattern (1,2,3) is A226316. Sequences covering an initial interval are counted by A000670. The a(1) = 1 through a(4) = 9 sequences are:
%C () (1) (1,1) (1,2,1)
%C (1,2) (1,3,2)
%C (2,1) (2,1,1)
%C (2,1,2)
%C (2,1,3)
%C (2,2,1)
%C (2,3,1)
%C (3,1,2)
%C (3,2,1)
%C (End)
%H N. J. A. Sloane, <a href="/A052709/b052709.txt">Table of n, a(n) for n = 0..499</a>
%H Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, <a href="https://doi.org/10.26493/1855-3974.1679.ad3">Ascending runs in permutations and valued Dyck paths</a>, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 445-463.
%H Paul Barry, <a href="http://dx.doi.org/10.1016/j.laa.2015.10.032">Riordan arrays, generalized Narayana triangles, and series reversion</a>, Linear Algebra and its Applications, 491 (2016) 343-385.
%H Paul Barry, <a href="https://arxiv.org/abs/1802.03443">On a transformation of Riordan moment sequences</a>, arXiv:1802.03443 [math.CO], 2018.
%H Paul Barry, <a href="https://arxiv.org/abs/2001.08799">Characterizations of the Borel triangle and Borel polynomials</a>, arXiv:2001.08799 [math.CO], 2020.
%H Daniel Birmajer, Juan B. Gil, David S. Kenepp, and Michael D. Weiner, <a href="https://arxiv.org/abs/2108.04302">Restricted generating trees for weak orderings</a>, arXiv:2108.04302 [math.CO], 2021.
%H Daniel Birmajer, Juan B. Gil, Peter R. W. McNamara, and Michael D. Weiner, <a href="http://arxiv.org/abs/1602.03550">Enumeration of colored Dyck paths via partial Bell polynomials</a>, arXiv:1602.03550 [math.CO], 2016.
%H Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p8">Combinatorial proofs of addition formulas</a>, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
%H Brian Drake, <a href="http://dx.doi.org/10.1016/j.disc.2008.11.020">Limits of areas under lattice paths</a>, Discrete Math. 309 (2009), no. 12, 3936-3953.
%H M. Dziemianczuk, <a href="http://arxiv.org/abs/1410.5747">On Directed Lattice Paths With Additional Vertical Steps</a>, arXiv preprint arXiv:1410.5747 [math.CO], 2014.
%H James East and Nicholas Ham, <a href="https://arxiv.org/abs/1811.05735">Lattice paths and submonoids of Z^2</a>, arXiv:1811.05735 [math.CO], 2018.
%H L. Ferrari, E. Pergola, R. Pinzani, and S. Rinaldi, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00868-3">Jumping succession rules and their generating functions</a>, Discrete Math., 271 (2003), 29-50.
%H Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, <a href="http://dx.doi.org/10.1016/j.disc.2007.04.007">2-Binary trees: bijections and related issues</a>, Discr. Math., 308 (2008), 1209-1221.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=664">Encyclopedia of Combinatorial Structures 664</a>
%H J. P. S. Kung and A. de Mier, <a href="http://dx.doi.org/10.1016/j.jcta.2012.08.010">Catalan lattice paths with rook, bishop and spider steps</a>, Journal of Combinatorial Theory, Series A 120 (2013) 379-389. - _N. J. A. Sloane_, Dec 27 2012
%H D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, <a href="http://dx.doi.org/10.4153/CJM-1997-015-x">On some alternative characterizations of Riordan arrays</a>, Canad. J. Math., 49 (1997), 301-320.
%F a(n) + a(n-1) = A025227(n).
%F a(n) = Sum_{k=0..floor((n-1)/2)} (2*n-2-2*k)!/(k!*(n-k)!*(n-1-2*k)!). - _Emeric Deutsch_, Nov 14 2001
%F D-finite with recurrence: n*a(n) = (3*n-6)*a(n-1) + (8*n-18)*a(n-2) + (4*n-12)*a(n-3), n>2. a(1)=a(2)=1.
%F a(n) = b(1)*a(n-1) + b(2)*a(n-2) + ... + b(n-1)*a(1) for n>1 where b(n)=A025227(n).
%F G.f.: A(x) = x/(1-(1+x)*A(x)). - _Paul D. Hanna_, Aug 16 2002
%F G.f.: A(x) = x/(1-z/(1-z/(1-z/(...)))) where z=x+x^2 (continued fraction). - _Paul D. Hanna_, Aug 16 2002; revised by _Joerg Arndt_, Mar 18 2011
%F a(n+1) = Sum_{k=0..n} Catalan(k)*binomial(k, n-k). - _Paul Barry_, Feb 22 2005
%F From _Paul Barry_, Mar 14 2006: (Start)
%F G.f. is x*c(x*(1+x)) where c(x) is the g.f. of A000108.
%F Row sums of A117434. (End)
%F a(n+1) = (1/(2*Pi))*Integral_{x=2-2*sqrt(2)..2+2*sqrt(2)} x^n*(4+4x-x^2)/(2*(1+x)). - _Paul Barry_, Apr 01 2007
%F From _Gary W. Adamson_, Jul 22 2011: (Start)
%F For n>0, a(n) is the upper left term in M^(n-1), where M is an infinite square production matrix as follows:
%F 1, 1, 0, 0, 0, 0, ...
%F 2, 1, 1, 0, 0, 0, ...
%F 2, 2, 1, 1, 0, 0, ...
%F 2, 2, 2, 1, 1, 0, ...
%F 2, 2, 2, 2, 1, 1, ...
%F ... (End)
%F G.f.: x*Q(0), where Q(k) = 1 + (4*k+1)*x*(1+x)/(k+1 - x*(1+x)*(2*k+2)*(4*k+3)/(2*x*(1+x)*(4*k+3) + (2*k+3)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 14 2013
%F a(n) ~ sqrt(2-sqrt(2))*2^(n-1/2)*(1+sqrt(2))^(n-1)/(n^(3/2)*sqrt(Pi)). - _Vaclav Kotesovec_, Jun 29 2013
%F a(n+1) = Sum_{k=0..floor(n/2)} A085880(n-k,k). - _Philippe Deléham_, Nov 15 2013
%p spec := [S,{C=Prod(B,Z),S=Union(B,C,Z),B=Prod(S,S)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);
%t InverseSeries[Series[(y-y^2)/(1+y^2), {y, 0, 24}], x] (* then A(x)= y(x) *) (* _Len Smiley_, Apr 12 2000 *)
%t CoefficientList[Series[(1 -Sqrt[1 -4x -4x^2])/(2(1+x)), {x, 0, 33}], x] (* _Vincenzo Librandi_, Feb 12 2016 *)
%o (PARI) a(n)=polcoeff((1-sqrt(1-4*x*(1+x+O(x^n))))/2/(1+x),n)
%o (Magma) [0] cat [(&+[Binomial(n,k+1)*Binomial(2*k,n-1): k in [0..n-1]])/n: n in [1..30]]; // _G. C. Greubel_, May 30 2022
%o (SageMath) [sum(binomial(k, n-k-1)*catalan_number(k) for k in (0..n-1)) for n in (0..30)] # _G. C. Greubel_, May 30 2022
%Y Diagonal entries of A071943 and A071945.
%Y Cf. A000108, A000670, A025227, A052709, A056986, A071943, A085880.
%Y Cf. A102726, A117434, A158005, A226316, A333217, A335479.
%K easy,nonn
%O 0,4
%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000
%E Better g.f. and recurrence from _Michael Somos_, Aug 03 2000
%E More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000
|
