A179190 -id:A179190 - cp's OEIS frontend

A071356 Expansion of (1 - 2x - sqrt(1 - 4x - 4x^2))/(4x^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

N. J. A. Sloane, Jun 12 2002

nonn

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

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

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.

A036774(n) = a(n-1) * n! / 2^(n-1).
Row sums of A071943.
Cf. A000108, A025235.

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

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

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

{a(n)= if(n<1, n==0, polcoeff( 2/(1 -2*x +sqrt(1 -4*x -4*x^2 +x*O(x^n))), n))}

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

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

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)

A179191 Expansion of o.g.f. (1/2)(-1 + 1/sqrt(1 - 4x - 4*x^2)).

Original entry on oeis.org

0, 1, 4, 16, 68, 296, 1312, 5888, 26672, 121696, 558464, 2574848, 11917952, 55345408, 257741824, 1203224576, 5629027072, 26383656448, 123868321792, 582414688256, 2742116907008, 12926036258816, 60998951747584, 288147689046016, 1362407763795968, 6447125560016896

Offset: 0

Clark Kimberling, Jul 01 2010

nonn

G.f. A(x) satisfies A(x)^2 + A(x) = (x^2 + x)/(1 - 4*x - 4*x^2). - Michael Somos, Jan 28 2019

			G.f. = x + 4*x^2 + 16*x^3 + 68*x^4 + 296*x^5 + 1312*x^6 + 5888*x^7 + ....

G. C. Greubel, Table of n, a(n) for n = 0..1000
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv:1410.5747 [math.CO], 2014.

Cf. A178693, A178694, A179190.

m:=30; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!( (-1 + 1/Sqrt(1-4*x-4*x^2))/2 )); // G. C. Greubel, Jan 25 2019

CoefficientList[1/2 (-1 + (1-4x-4x^2)^(-1/2)) + O[x]^23, x] (* Jean-François Alcover, Jul 27 2018 *)

a(n):=sum(m*sum(sum(binomial(i-1,k-1)*binomial(i,n-i),i,k,n)*sum(binomial(j,2*j-m-k)*binomial(k,j),j,0,k)/k,k,m,n),m,1,n); /* Vladimir Kruchinin, Mar 11 2011 */
a(n):=sum(2^(n-k-1)*binomial(n,k)*binomial(n-k,k),k,0,n); /* Vladimir Kruchinin, Mar 12 2015 */

my(x='x+O('x^30)); concat([0], Vec((-1 +1/sqrt(1-4*x-4*x^2))/2)) \\ G. C. Greubel, Jan 25 2019

((-1 + 1/sqrt(1-4*x-4*x^2))/2).series(x, 20).coefficients(x, sparse=False) # G. C. Greubel, Jan 25 2019

G.f.: (1/2)*(-1 + 1/sqrt(1 - 4*x - 4*x^2)).
G.f.: A(x) = x*A001006(A000045(x)/x-1)/(1-x*A001006(A000045(x)/x-1)).
a(n) = Sum_{m=1..n} m*Sum_{k=m..n} (Sum_{i=k..n} binomial(i-1,k-1)*binomial(i,n-i))*(Sum_{j=0..k} binomial(j,2*j-m-k)*binomial(k,j))/k. - Vladimir Kruchinin, Mar 11 2011
a(n) = Sum_{k=0..n} 2^(n-k-1)*binomial(n,k)*binomial(n-k,k). - Vladimir Kruchinin, Mar 12 2015
From Vaclav Kotesovec, Jan 26 2019: (Start)
D-finite with recurrence: n*a(n) = 2*(2*n - 1)*a(n-1) + 4*(n-1)*a(n-2).
a(n) ~ 2^(n - 7/4) * (1 + sqrt(2))^(n + 1/2) / sqrt(Pi*n). (End)
0 = a(n)*(16*a(n+1) +24*a(n+2) -8*a(n+3)) + a(n+1)*(+8*a(n+1) +16*a(n+2) -6*a(n+3)) + a(n+2)*(-2*a(n+2) +a(n+3)) for all n in Z except n=-1. - Michael Somos, Jan 27 2019
a(n) = A006139(n)/2, n>0. - R. J. Mathar, Jan 24 2020

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

Sage

Formula

A179191 Expansion of o.g.f. (1/2)(-1 + 1/sqrt(1 - 4x - 4*x^2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Sage

Formula

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

Sage

Formula

A179191 Expansion of o.g.f. (1/2)*(-1 + 1/sqrt(1 - 4*x - 4*x^2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Sage

Formula

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

A179191 Expansion of o.g.f. (1/2)(-1 + 1/sqrt(1 - 4x - 4*x^2)).