%I #127 Jun 13 2024 17:15:45
%S 1,2,6,20,72,272,1064,4272,17504,72896,307648,1312896,5655808,
%T 24562176,107419264,472675072,2091206144,9296612352,41507566592,
%U 186045061120,836830457856,3776131489792,17089399689216,77548125675520,352766964908032
%N Expansion of (1 - 2*x - sqrt(1 - 4*x - 4*x^2))/(4*x^2).
%C Number of underdiagonal lattice paths from (0,0) to the line x=n, using only steps R=(1,0), V=(0,1) and D=(1,2). Also number of Motzkin paths of length n in which both the "up" and the "level" steps come in two colors. E.g., a(2)=6 because we have RR, RVR, RRV, RD, RVRV and RRVV. - _Emeric Deutsch_, Dec 21 2003
%C Inverse binomial transform of little Schroeder numbers 1,3,11,... (A001003 with first term deleted). - _David Callan_, Feb 07 2004
%C a(n) is the number of planar trees satisfying: 1) Every internal node has at least two children, 2) Among the children of a node, only the leftmost and the rightmost children can be leaves, 3) The tree has n+1 leaves. For instance, a(3)=6. - Marcelo Aguiar (maguiar(AT)math.tamu.edu), Oct 14 2005
%C Hankel transform is A006125(n+1)=2^C(n+1,2). - _Paul Barry_, Jan 08 2008
%C Equals binomial transform of A025235: (1, 1, 3, 7, 21, 61, 191, ...). - _Gary W. Adamson_, Sep 03 2010
%C Conjecturally, the number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) > e(j) <= e(k). [Martinez and Savage, 2.19] - _Eric M. Schmidt_, Jul 17 2017
%C Let s denote West's stack-sorting map, and let Av_n(tau_1, ..., tau_r) denote the set of permutations of [n] that avoid the patterns tau_1, ..., tau_r. It is conjectured that a(n) = |s^{-1}(Av_{n+1}(132, 231))| = |s^{-1}(Av_{n+1}(132, 312))| = |s^{-1}(Av_{n+1}(231, 312))|. Only the last of these equalities is known. - _Colin Defant_, Sep 16 2018
%D Bin Han, The gamma-positive coefficients arising in segmented permutations, Discrete Math., 344 (2012), #112336. See p. 7.
%H Fung Lam, <a href="/A071356/b071356.txt">Table of n, a(n) for n = 0..1465</a>
%H Marcelo Aguiar and Walter Moreira, <a href="http://arxiv.org/abs/math/0510169">Combinatorics of the free Baxter algebra</a>, arXiv:math/0510169 [math.CO], 2005-2007, see Corollary 3.3.iii.
%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 Wenqin Cao, Emma Yu Jin, and Zhicong Lin, <a href="https://doi.org/10.1016/j.dam.2019.01.035">Enumeration of inversion sequences avoiding triples of relations</a>, Discrete Applied Mathematics (2019); see also <a href="http://www.emmayujin.at/Pubs/CaoJinLin19.pdf">author's copy</a>
%H Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.
%H Colin Defant, <a href="https://arxiv.org/abs/1904.02829">Enumeration of Stack-Sorting Preimages via a Decomposition Lemma</a>, arXiv:1904.02829 [math.CO], 2019.
%H Ivan Geffner and Marc Noy, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p3">Counting Outerplanar Maps</a>, Electronic Journal of Combinatorics 24(2) (2017), #P2.3.
%H Li Guo and Yunnan Li, <a href="https://arxiv.org/abs/1906.06454">Braided dendriform and tridendriform algebras and braided Hopf algebras of planar trees</a>, arXiv:1906.06454 [math.QA], 2019.
%H Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H Chetak Hossain, <a href="https://repository.lib.ncsu.edu/bitstream/handle/1840.20/36970/etd.pdf">Quotients Derived from Posets in Algebraic and Topological Combinatorics</a>, Ph. D. Dissertation, North Carolina State University (2019).
%H G. Kreweras, <a href="http://www.numdam.org/item?id=BURO_1973__20__3_0">Sur les hiérarchies de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973), p. 32-33 (same sequence but with offset 1).
%H G. Kreweras, <a href="/A001844/a001844.pdf">Sur les hiérarchies de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy)
%H Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016.
%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.
%H L. W. Shapiro and C. J. Wang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Shapiro/shapiro7.html">A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height</a>, JIS 12 (2009) 09.3.2
%F G.f. A(x) satisfies 2x^2*A(x)^2+(2x-1)*A(x)+1=0 and A(x)=1/(1-2x-2x^2/A(x)). - _Michael Somos_, Sep 06 2003
%F a(n) = Sum_{k=0..floor(n/2)} C(n, 2k)C(k)2^(n-2k)*2^k. - _Paul Barry_, May 18 2005
%F G.f.: (1 - 2*x - sqrt(1 - 4*x - 4*x^2) )/(4*x^2) = 2/(1 - 2*x +sqrt(1 - 4*x - 4*x^2)).
%F Moment representation is a(n) = (1/(4*Pi))*int(x^n*sqrt(4-4x-x^2), x, -2*sqrt(2)-2, 2*sqrt(2)-2). - _Paul Barry_, Jan 08 2008
%F G.f.: 1/(1-2x-2x^2/(1-2x-2x^2/(1-2x-2x^2/(1-2x-2x^2/(1-2x-2x^2/.... (continued fraction). - _Paul Barry_, Dec 06 2008
%F From _Gary W. Adamson_, Jul 22 2011: (Start)
%F a(n) = sum of top row terms of M^n, M = 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 2, 2, 2, 2, 2, 1, ... (End)
%F E.g.f.: a(n) = n!* [x^n] exp(2*x)*BesselI(1, 2*sqrt(2)*x)/(sqrt(2)*x). - _Peter Luschny_, Aug 25 2012
%F D-finite with recurrence: (n+2)*a(n) +2*(-2*n-1)*a(n-1) +4*(-n+1)*a(n-2)=0. - _R. J. Mathar_, Dec 02 2012 (Formula verified and used for computations. - _Fung Lam_, Feb 24 2014)
%F a(n) ~ 2^(n - 1/4) * (1+sqrt(2))^(n + 3/2) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Sep 24 2013, simplified Jan 26 2019
%F a(n) = A179190(n+2)/4. - _R. J. Mathar_, Jan 20 2020
%F a(n) = 2^n * hypergeom((1 - n)/2, -n/2, 2, 2). - _Peter Luschny_, May 30 2021
%F a(n) = (-2*î)^(n+2) * (Legendre_P(n+2, i) - Legendre_P(n, i))/(4*(2*n + 3)). - _Peter Bala_, May 06 2024
%F From _Emanuele Munarini_, Jun 13 2024: (Start)
%F a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)*binomial(n-k, k)*2^(n-k)/(k+1).
%F a(n) = Sum_{k=0..floor((n+2)/3)} binomial(n-2k+2, 2k)*Catalan(n-2k+1).
%F a(n) = Sum_{k=0..floor((n+2)/4)} binomial(n-2k+1, 2k+1)*Catalan(n-2k). (End)
%e a(3) = 20 = sum of top row terms in M^3 = (9 + 7 + 3 + 1).
%t CoefficientList[Series[(1-2*x-Sqrt[1-4*x-4*x^2])/(4*x^2), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Sep 24 2013 *)
%t a[n_] := 2^n Hypergeometric2F1[(1-n)/2, -n/2, 2, 2];
%t Table[a[n], {n, 0, 24}] (* _Peter Luschny_, May 30 2021 *)
%o (PARI) a(n)=if(n<0,0,n++; polcoeff(serreverse(x/(1+2*x+2*x^2)+x*O(x^n)),n))
%o (PARI) {a(n)= if(n<1, n==0, polcoeff( 2/(1 -2*x +sqrt(1 -4*x -4*x^2 +x*O(x^n))), n))}
%o (PARI) {a(n)= local(A); if(n<0, 0, A= x*O(x^n); n!*simplify(polcoeff( exp(2*x +A)* besseli(1, 2*x* quadgen(8) +A), n)))} /* _Michael Somos_, Mar 31 2007 */
%o (Sage)
%o def A071356_list(n): # n>=1
%o T = [0]*(n+1); R = [1]
%o for m in (1..n-1):
%o a,b,c = 1,0,0
%o for k in range(m,-1,-1):
%o r = a + 2*(b + c)
%o if k < m : T[k+2] = u;
%o a,b,c = T[k-1],a,b
%o u = r
%o T[1] = u; R.append(u)
%o return R
%o A071356_list(25) # _Peter Luschny_, Nov 01 2012
%o (Magma) R<x>:=PowerSeriesRing(Rationals(), 30); Coefficients(R!((1 - 2*x - Sqrt(1 - 4*x - 4*x^2))/(4*x^2))); // _Vincenzo Librandi_, Jan 21 2020
%Y A036774(n) = a(n-1) * n! / 2^(n-1).
%Y Row sums of A071943.
%Y Cf. A000108, A025235.
%K nonn
%O 0,2
%A _N. J. A. Sloane_, Jun 12 2002