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

%I

%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

%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 Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.

%H Ivan Geffner, 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 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 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, 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^2A(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, ...

%F ... (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 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)

%F 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

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

%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

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

%Y Row sums of A071943.

%Y Cf. A025235. - _Gary W. Adamson_, Sep 03 2010

%K nonn

%O 0,2

%A _N. J. A. Sloane_, Jun 12 2002

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 November 13 02:28 EST 2018. Contains 317120 sequences. (Running on oeis4.)