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,2

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

References

Bin Han, The gamma-positive coefficients arising in segmented permutations, Discrete Math., 344 (2012), #112336. See p. 7.

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.

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.

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.

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

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

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

D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.

L. W. Shapiro and C. J. Wang, A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height, JIS 12 (2009) 09.3.2

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

Example

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

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

Prog

(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
(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

Crossrefs

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

Row sums of A071943.

Cf. A025235.

Sequence in context: A063376 A161168 A049139 * A141200 A186996 A186576

Adjacent sequences: A071353 A071354 A071355 * A071357 A071358 A071359

Keyword

nonn

Author

N. J. A. Sloane, Jun 12 2002

Status

approved