A071356 Expansion of (1 - 2*x - sqrt(1 - 4*x - 4*x^2))/(4*x^2).

1, 2, 6, 20, 72, 272, 1064, 4272, 17504, 72896, 307648, 1312896, 5655808, 24562176, 107419264, 472675072, 2091206144, 9296612352, 41507566592, 186045061120, 836830457856, 3776131489792, 17089399689216, 77548125675520, 352766964908032

Offset: 0

Author

N. J. A. Sloane, Jun 12 2002

Keywords

• nonn

Comments

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

Inverse binomial transform of little Schroeder numbers 1,3,11,... (A001003 with first term deleted). - David Callan, Feb 07 2004

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

Hankel transform is A006125(n+1)=2^C(n+1,2). - Paul Barry, Jan 08 2008

Equals binomial transform of A025235: (1, 1, 3, 7, 21, 61, 191, ...). - Gary W. Adamson, Sep 03 2010

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

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

Examples

			a(3) = 20 = sum of top row terms in M^3 = (9 + 7 + 3 + 1).
		

Links

• Fung Lam, Table of n, a(n) for n = 0..1465
• Marcelo Aguiar and Walter Moreira, Combinatorics of the free Baxter algebra, arXiv:math/0510169 [math.CO], 2005-2007, see Corollary 3.3.iii.
• Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
• Miklos Bona, Stack-sorting preimages and 0-1-trees, arXiv:2505.18295 [math.CO], 2025. See p. 3.
• Vuong Bui, Bounding Klarner's constant from above using a simple recurrence, arXiv:2412.20143 [math.CO], 2024.
• Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Applied Mathematics (2019); see also author's copy
• Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
• Colin Defant, Enumeration of Stack-Sorting Preimages via a Decomposition Lemma, arXiv:1904.02829 [math.CO], 2019.
• Serkan Demiriz, Adem Şahin, and Sezer Erdem, Some topological and geometric properties of novel generalized Motzkin sequence spaces, Rendiconti Circ. Mat. Palermo Ser. 2 (2025) Vol. 74, No. 136. See p. 4.
• Ivan Geffner and Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics 24(2) (2017), #P2.3.
• Li Guo and Yunnan Li, Braided dendriform and tridendriform algebras and braided Hopf algebras of planar trees, arXiv:1906.06454 [math.QA], 2019.
• Bin Han, The gamma-positive coefficients arising in segmented permutations, Discrete Math., 344 (2012), #112336. See p. 7.
• Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
• Chetak Hossain, Quotients Derived from Posets in Algebraic and Topological Combinatorics, Ph. D. Dissertation, North Carolina State University (2019).
• Germain Kreweras, Sur les hiérarchies de segments, 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).
• Germain Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy)
• Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
• Donatella Merlini, Douglas G. Rogers, Renzo Sprugnoli, and M. Cecilia Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.
• Louis W. Shapiro and Carol J. Wang, A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height, JIS 12 (2009) 09.3.2.

Crossrefs

A036774(n) = a(n-1) * n! / 2^(n-1).

Row sums of A071943.

Cf. A000108, A025235.

Programs

Magma

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!((1 - 2*x - Sqrt(1 - 4*x - 4*x^2))/(4*x^2))); // Vincenzo Librandi, Jan 21 2020

Mathematica

CoefficientList[Series[(1-2*x-Sqrt[1-4*x-4*x^2])/(4*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Sep 24 2013 *)
a[n_] := 2^n Hypergeometric2F1[(1-n)/2, -n/2, 2, 2];
Table[a[n], {n, 0, 24}] (* Peter Luschny, May 30 2021 *)

PARI

a(n)=if(n<0,0,n++; polcoeff(serreverse(x/(1+2*x+2*x^2)+x*O(x^n)),n))

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))}

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 */

Sage

def A071356_list(n):  # n>=1
    T = [0]*(n+1); R = [1]
    for m in (1..n-1):
        a,b,c = 1,0,0
        for k in range(m,-1,-1):
            r = a + 2*(b + c)
            if k < m : T[k+2] = u;
            a,b,c = T[k-1],a,b
            u = r
        T[1] = u; R.append(u)
    return R
A071356_list(25)  # Peter Luschny, Nov 01 2012

Formula

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

a(n) = Sum_{k=0..floor(n/2)} C(n, 2k)C(k)2^(n-2k)*2^k. - Paul Barry, May 18 2005

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)).

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

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

From Gary W. Adamson, Jul 22 2011: (Start)

a(n) = sum of top row terms of M^n, M = an infinite square production matrix as follows:

1, 1, 0, 0, 0, 0, ...

2, 1, 1, 0, 0, 0, ...

2, 2, 1, 1, 0, 0, ...

2, 2, 2, 1, 1, 0, ...

2, 2, 2, 2, 1, 1, ...

2, 2, 2, 2, 2, 1, ... (End)

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

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)

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

a(n) = A179190(n+2)/4. - R. J. Mathar, Jan 20 2020

a(n) = 2^n * hypergeom((1 - n)/2, -n/2, 2, 2). - Peter Luschny, May 30 2021

a(n) = (-2*î)^(n+2) * (Legendre_P(n+2, i) - Legendre_P(n, i))/(4*(2*n + 3)). - Peter Bala, May 06 2024

From Emanuele Munarini, Jun 13 2024: (Start)

a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)*binomial(n-k, k)*2^(n-k)/(k+1).

a(n) = Sum_{k=0..floor((n+2)/3)} binomial(n-2k+2, 2k)*Catalan(n-2k+1).

a(n) = Sum_{k=0..floor((n+2)/4)} binomial(n-2k+1, 2k+1)*Catalan(n-2k). (End)