login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A071356 Expansion of (1 - 2*x - sqrt(1 - 4*x - 4*x^2))/(4*x^2). 12
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 (list; graph; refs; listen; history; text; internal format)
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

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.

Ivan Geffner, Marc Noy, Counting Outerplanar Maps, Electronic Journal of Combinatorics 24(2) (2017), #P2.3.

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.

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, 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^2A(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

Conjecture: (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) ~ (3+2*sqrt(2))*sqrt(2-sqrt(2)) * 2^(n-1/2)*(1+sqrt(2))^n/ (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Sep 24 2013

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

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

CROSSREFS

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

Row sums of A071943.

Cf. A025235. - Gary W. Adamson, Sep 03 2010

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 12:59 EST 2018. Contains 299623 sequences. (Running on oeis4.)