This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001006 Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.
(Formerly M1184 N0456)

%I M1184 N0456

%S 1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113634,310572,

%T 853467,2356779,6536382,18199284,50852019,142547559,400763223,

%U 1129760415,3192727797,9043402501,25669818476,73007772802,208023278209,593742784829

%N Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.

%C Number of 4321-, (3412,2413)-, (3412,3142)- and 3412-avoiding involutions in S_n.

%C Number of sequences of length n-1 consisting of positive integers such that the opening and ending elements are 1 or 2 and the absolute difference between any 2 consecutive elements is 0 or 1. - _Jon Perry_, Sep 04 2003

%C Also number of Motzkin n-paths: paths from (0,0) to (n,0) in an n X n grid using only steps U = (1,1), F = (1,0) and D = (1,-1). - _David Callan_, Jul 15 2004

%C Number of Dyck n-paths with no UUU. (Given such a Dyck n-path, change each UUD to U, then change each remaining UD to F. This is a bijection to Motzkin n-paths. Example with n=5: U U D U D U U D D D -> U F U D D.) - _David Callan_, Jul 15 2004

%C Number of Dyck (n+1)-paths with no UDU. (Given such a Dyck (n+1)-path, mark each U that is followed by a D and each D that is not followed by a U. Then change each unmarked U whose matching D is marked to an F. Lastly, delete all the marked steps. This is a bijection to Motzkin n-paths. Example with n=6 and marked steps in small type: U U u d D U U u d d d D u d -> U U u d D F F u d d d D u d -> U U D F F D.) - _David Callan_, Jul 15 2004

%C a(n) is the number of strings of length 2n from the following recursively defined set: L contains the empty string and, for any strings a and b in L, we also find (ab) in L. The first few elements of L are e, (), (()), ((())), (()()), (((()))), ((()())), ((())()), (()(())) and so on. This proves that a(n) is less than or equal to C(n), the n-th Catalan number. - Saul Schleimer (saulsch(AT)math.rutgers.edu), Feb 23 2006

%C a(n) = number of Dyck n-paths all of whose valleys have even x-coordinate (when path starts at origin). For example, T(4,2)=3 counts UDUDUUDD, UDUUDDUD, UUDDUDUD. Given such a path, split it into n subpaths of length 2 and transform UU->U, DD->D, UD->F (there will be no DUs for that would entail a valley with odd x-coordinate). This is a bijection to Motzkin n-paths. - _David Callan_, Jun 07 2006

%C Also the number of standard Young tableaux of height <= 3. - _Mike Zabrocki_, Mar 24 2007

%C a(n) is the number of RNA shapes of size 2n+2. RNA Shapes are essentially Dyck words without "directly nested" motifs of the form A[[B]]C, for A, B and C Dyck words. The first RNA Shapes are []; [][]; [][][], [[][]]; [][][][], [][[][]], [[][][]], [[][]][]; ... - Yann Ponty (ponty(AT)lri.fr), May 30 2007

%C Equals right and left borders and row sums of triangle A144218 with offset variations. - _Gary W. Adamson_, Sep 14 2008

%C The sequence is self-generated from top row A going to the left starting (1,1) and bottom row = B, the same sequence but starting (0,1) and going to the right. Take dot product of A and B and add the result to n-th term of A to get the (n+1)-th term of A. Example: a(5) = 21 as follows: Take dot product of A = (9, 4, 2, 1, 1) and (0, 1, 1, 2, 4) = (0, + 4 + 2 + 2 + 4) = 12; which is added to 9 = 21. - _Gary W. Adamson_, Oct 27 2008

%C Equals A005773 / A005773 shifted (i.e., (1,2,5,13,35,96,...) / (1,1,2,5,13,35,96,...)). - _Gary W. Adamson_, Dec 21 2008

%C Starting with offset 1 = iterates of M * [1,1,0,0,0,...], where M = a tridiagonal matrix with [0,1,1,1,...] in the main diagonal and [1,1,1,...] in the super and subdiagonals. - _Gary W. Adamson_, Jan 07 2009

%C a(n) is the number of involutions of {1,2,...,n} having genus 0. The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q. Example: a(4)=9; indeed, p=3412=(13)(24) is the only involution of {1,2,3,4} with genus >0. This follows easily from the fact that a permutation p of {1,2,...,n} has genus 0 if and only if the cycle decomposition of p gives a noncrossing partition of {1,2,...,n} and each cycle of p is increasing (see Lemma 2.1 of the Dulucq-Simion reference). [Also, redundantly, for p=3412=(13)(24) we have cp'=2341*3412=4123=(1432) and so g(p)=(1/2)(4+1-2-1)=1.] - _Emeric Deutsch_, May 29 2010

%C Let w(i,j,n) denote walks in N^2 which satisfy the multivariate recurrence

%C w(i,j,n) = w(i, j + 1, n - 1) + w(i - 1, j, n - 1) + w(i + 1, j - 1, n - 1) with boundary conditions w(0,0,0) = 1 and w(i,j,n) = 0 if i or j or n is < 0. Then a(n) = Sum_{i = 0..n,j = 0..n} w(i,j,n) is the number of such walks of length n. - _Peter Luschny_, May 21 2011

%C a(n)/a(n-1) tends to 3.0 as Lim N->inf: (1+2*Cos 2Pi/N) relating to longest odd N regular polygon diagonals, by way of example, N=7: Using the tridiagonal generator [Cf. comment of Jan 07 2009], for polygon N=7, we extract an (N-1)/2 = 3 X 3 matrix, [0,1,0; 1,1,1; 0,1,1] with an e-val of 2.24697...; the longest Heptagon diagonal with edge = 1. As N tends to infinity, the diagonal lengths tend to 3.0, the convergent of the sequence. - _Gary W. Adamson_, Jun 08 2011

%C Number of (n+1)-length permutations avoiding the pattern 132 and the dotted pattern 23\dot{1}. - _Jean-Luc Baril_, Mar 07 2012

%C Number of n-length words w over alphabet {a,b,c} such that for every prefix z of w we have #(z,a) >= #(z,b) >= #(z,c), where #(z,x) counts the letters x in word z. The a(4) = 9 words are: aaaa, aaab, aaba, abaa, aabb, abab, aabc, abac, abca. - _Alois P. Heinz_, May 26 2012

%C Number of length-n restricted growth strings (RGS) [r(1), r(2), ..., r(n)] such that r(1)=1, r(k)<=k, and r(k)!=r(k-1); for example, the 9 RGS for n=4 are 1010, 1012, 1201, 1210, 1212, 1230, 1231, 1232, 1234. - _Joerg Arndt_, Apr 16 2013

%C Number of length-n restricted growth strings (RGS) [r(1), r(2), ..., r(n)] such that r(1)=0, r(k)<=k and r(k)-r(k-1) != 1; for example, the 9 RGS for n=4 are 0000, 0002, 0003, 0004, 0022, 0024, 0033, 0222, 0224. - _Joerg Arndt_, Apr 17 2013

%C Number of (4231,5276143)-avoiding involutions in S_n. - _Alexander Burstein_, Mar 05 2014

%C a(n) is the number of increasing unary-binary trees with n nodes who have an associated permutation avoids 132. For more information about unary-binary trees with associated permutations, see A245888. - _Manda Riehl_, Aug 07 2014

%C a(n) is the number of involutions on [n] avoiding the single pattern p, where p is any one of the 8 (classical) patterns 1234, 1243, 1432, 2134, 2143, 3214, 3412, 4321. Also, number of (3412,2413)-, (3412,3142)-, (3412,2413,3142)-avoiding involutions on [n] because each of these 3 sets actually coincides with the 3412-avoiding involutions on [n]. This is a complete list of the 8 singles, 2 pairs, and 1 triple of 4-letter classical patterns whose involution avoiders are counted by the Motzkin numbers. (See Barnabei et al 2011 reference.) - _David Callan_, Aug 27 2014

%C A series created using 2*a(n)+ a(n+1) has Hankel transform of F(2n), offset 3, F being the Fibonacci bisection, A001906 (Empirical observation). - _Tony Foster III_, Jul 28 2016

%C A series created using 2*a(n) + 3*a(n+1) + a(n+2) gives the Hankel transform of Sum_{k=0..n} k*Fibonacci(2*k), offset 3, A197649 (Empirical observation). - _Tony Foster III_, Jul 28 2016

%C Conjecture: 2/n*Sum_{k=1..n}(2k+1)a(k)^2 is an integer for each positive integer n. - _Zhi-Wei Sun_, Nov 16 2017

%C The Rubey and Stump reference proves a refinement of a conjecture of René Marczinzik, which they state as: "The number of 2-Gorenstein algebras which are Nakayama algebras with n simple modules and have an oriented line as associated quiver equals the number of Motzkin paths of length n." - _Eric M. Schmidt_, Dec 16 2017

%D E. Barcucci, R. Pinzani, R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.

%D Marilena Barnabei, Flavio Bonetti, and Matteo Silimbani, Restricted involutions and Motzkin paths, Advances in Applied Mathematics 47 (2011) 102-115.

%D P. Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.

%D Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.

%D A. M. Baxter, L. K. Pudwell, Ascent sequences avoiding pairs of patterns, 2014, http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf

%D F. Bergeron, L. Favreau and D. Krob, Conjectures on the enumeration of tableaux of bounded height, Discrete Math, vol. 139, no. 1-3 (1995), 463-468.

%D F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.

%D R Bojicic, MD Petkovic, Orthogonal Polynomials Approach to the Hankel Transform of Sequences Based on Motzkin Numbers, Bulletin of the Malaysian Mathematical Sciences, 2015, doi:10.1007/s40840-015-0249-3

%D Naiomi Cameron, JE McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.

%D L. Carlitz, Solution of certain recurrences, SIAM J. Appl. Math., 17 (1969), 251-259.

%D Gi-Sang Cheon, S.-T. Jin, L. W. Shapiro, A combinatorial equivalence relation for formal power series, Linear Algebra and its Applications, Available online Mar 30 2015.

%D J. Cigler, Hankel determinants of some polynomial sequences, http://homepage.univie.ac.at/johann.cigler/preprints/hankel.pdf, 2012.

%D Dairyko, Michael; Tyner, Samantha; Pudwell, Lara; Wynn, Casey. Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.

%D D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33.

%D E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

%D R. Donaghey, Restricted plane tree representations for four Motzkin-Catalan equations, J. Combin. Theory, Series B, 22 (1977), 114-121.

%D Robert Donaghey, Automorphisms on Catalan trees and bracketings, Journal of Combinatorial Theory, Series B, Volume 29, Issue 1, August 1980, Pages 75-90.

%D R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.

%D T. Doslic, D. Svrtan and D. Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 67-82.

%D Doslic, Tomislav and Veljan, Darko. Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019)

%D S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.

%D Dziemianczuk, M. "Enumerations of plane trees with multiple edges and Raney lattice paths." Discrete Mathematics 337 (2014): 9-24.

%D I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (5.2.10).

%D N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.

%D Kris Hatch, Presentation of the Motzkin Monoid, Senior Thesis, Univ. Cal. Santa Barbara, 2012; http://ccs.math.ucsb.edu/senior-thesis/Kris-Hatch.pdf.

%D V. Jelinek, T. Mansour and M. Shattuck, On multiple pattern avoiding set partitions, Advances in Applied Mathematics Volume 50, Issue 2, February 2013, pp. 292-326.

%D Hana Kim, R. P. Stanley A refined enumeration of hex trees and related polynomials, http://www-math.mit.edu/~rstan/papers/hextrees.pdf, Preprint 2015.

%D S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7

%D A. Kuznetsov et al., Trees associated with the Motzkin numbers, J. Combin. Theory, A 76 (1996), 145-147.

%D Marie-Louise Lackner, M Wallner, An invitation to analytic combinatorics and lattice path counting; Preprint, Dec 2015, http://dmg.tuwien.ac.at/mwallner/files/lpintro.pdf

%D T. Lengyel, On divisibility properties of some differences of Motzkin numbers, Annales Mathematicae et Informaticae, 41 (2013) pp. 121-136.

%D W. A. Lorenz, Y. Ponty, P. Clote, Asymptotics of RNA Shapes, Journal of Computational Biology. 2008, 15(1): 31-63. doi:10.1089/cmb.2006.0153.

%D Piera Manara and Claudio Perelli Cippo, The fine structure of 4321 avoiding involutions and 321 avoiding involutions, PU. M. A. Vol. 22 (2011), 227-238; http://www.mat.unisi.it/newsito/puma/public_html/22_2/manara_perelli-cippo.pdf.

%D T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76.

%D Mansour, Toufik; Schork, Matthias; Shattuck, Mark. Catalan numbers and pattern restricted set partitions. Discrete Math. 312(2012), no. 20, 2979--2991. MR2956089.

%D T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.

%D Roy Oste and Joris Van der Jeugt, Motzkin paths, Motzkin polynomials and recurrence relations, Electronic Journal of Combinatorics 22(2) (2015), #P2.8.

%D Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.

%D J. Riordan, Enumeration of plane trees by branches and endpoints, J. Combin. Theory, A 23 (1975), 214-222.

%D E. Royer, Interpretation combinatoire des moments negatifs des valeurs de fonctions L au bord de la bande critique, Ann. Sci. Ecole Norm. Sup. (4) 36 (2003), no. 4, 601-620.

%D A. Sapounakis et al., Ordered trees and the inorder transversal, Disc. Math., 306 (2006), 1732-1741.

%D A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

%D E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.

%D L. W. Shapiro et al., The Riordan group, Discrete Applied Math., 34 (1991), 229-239.

%D M. Shattuck, On the zeros of some polynomials with combinatorial coefficients, Annales Mathematicae et Informaticae, 42 (2013) pp. 93-101, http://ami.ektf.hu.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.

%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.37. Also Problem 7.16(b), y_3(n).

%D P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.

%D Z.-W. Sun, Conjectures involving arithmetical sequences, Number Theory: Arithmetic in Shangri-La (eds., S. Kanemitsu, H.-Z. Li and J.-Y. Liu), Proc. the 6th China-Japan Sem. Number Theory (Shanghai, August 15-17, 2011), World Sci., Singapore, 2013, pp. 244-258; http://math.nju.edu.cn/~zwsun/142p.pdf.

%D L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).

%D Wang, Chenying, Piotr Miska, and István Mező. "The r-derangement numbers." Discrete Mathematics 340.7 (2017): 1681-1692.

%D Ying Wang, Guoce Xin, A Classification of Motzkin Numbers Modulo 8, Electron. J. Combin., 25(1) (2018), #P1.54.

%D Wen-Jin Woan, A combinatorial proof of a recursive relation of the Motzkin sequence by lattice paths. Fibonacci Quart. 40 (2002), no. 1, 3-8.

%D Wen-jin Woan, A Recursive Relation for Weighted Motzkin Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.6.

%D F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.

%H N. J. A. Sloane and Seiichi Manyama, <a href="/A001006/b001006.txt">Table of n, a(n) for n = 0..2106</a> (first 501 terms from N. J. A. Sloane)

%H M. Abrate, S. Barbero, U. Cerruti, N. Murru, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barbero/barbero9.html"> Fixed Sequences for a Generalization of the Binomial Interpolated Operator and for some Other Operators</a>, J. Int. Seq. 14 (2011) # 11.8.1.

%H M. Aigner, <a href="http://dx.doi.org/10.1006/eujc.1998.0235">Motzkin Numbers</a>, Europ. J. Comb. 19 (1998), 663-675.

%H M. Aigner, <a href="http://dx.doi.org/10.1016/j.disc.2007.06.012">Enumeration via ballot numbers</a>, Discrete Math., 308 (2008), 2544-2563.

%H J. L. Arregui, <a href="http://arXiv.org/abs/math.NT/0109108">Tangent and Bernoulli numbers</a> related to Motzkin and Catalan numbers by means of numerical triangles, arXiv:math/0109108 [math.NT], 2001.

%H Marcello Artioli, Giuseppe Dattoli, Silvia Licciardi, Simonetta Pagnutti, <a href="https://arxiv.org/abs/1703.07262">Motzkin Numbers: an Operational Point of View</a>, arXiv:1703.07262 [math.CO], 2017.

%H A. Asinowski, G. Rote, <a href="http://arxiv.org/abs/1502.04925">Point sets with many non-crossing matchings</a>, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.

%H C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, <a href="https://doi.org/10.1016/S0012-365X(01)00250-3">Generating Functions for Generating Trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

%H C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, <a href="https://arxiv.org/abs/1609.06473">Explicit formulas for enumeration of lattice paths: basketball and the kernel method</a>, arXiv preprint arXiv:1609.06473 [math.CO], 2016.

%H Elena Barcucci, Alberto Del Lungo, Elisa Pergola, Renzo Pinzani, <a href="http://dx.doi.org/10.1016/S0012-365X(97)00122-2">A methodology for plane tree enumeration</a>, Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995). Discrete Math. 180 (1998), no. 1-3, 45--64. MR1603693 (98m:05090).

%H E. Barcucci et al., <a href="http://dx.doi.org/10.1016/S0012-365X(99)00254-X">From Motzkin to Catalan Permutations</a>, Discr. Math., 217 (2000), 33-49.

%H J.-L. Baril, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p178">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, 18 (2011), #P178.

%H J.-L. Baril, <a href="https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2343.1.html">Avoiding patterns in irreducible permutations</a>, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016).

%H J.-L. Baril, S. Kirgizov, <a href="http://jl.baril.u-bourgogne.fr/Stirling.pdf">The pure descent statistic on permutations</a>, Preprint, 2016.

%H Jean-Luc Baril, Sergey Kirgizov, Armen Petrossian, <a href="http://jl.baril.u-bourgogne.fr/decreasing.pdf">Dyck paths with a first return decomposition constrained by height</a>, Submitted, 2017.

%H J.-L. Baril, T. Mansour, A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/equival.pdf">Equivalence classes of permutations modulo excedances</a>, 2014.

%H J.-L. Baril, J.-M. Pallo, <a href="http://jl.baril.u-bourgogne.fr/Motzkin.pdf">Motzkin subposet and Motzkin geodesics in Tamari lattices</a>, 2013.

%H Jean-Luc Baril, and Jean-Marcel Pallo, <a href="http://jl.baril.u-bourgogne.fr/filter.pdf">A Motzkin filter in the Tamari lattice</a>, Discrete Mathematics 338.8 (2015): 1370-1378.

%H J.-L. Baril, A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/Dyck.pdf">Equivalence classes of Dyck paths modulo some statistics</a>, 2004.

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Barry/barry84.html">A Catalan Transform and Related Transformations on Integer Sequences</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

%H P. Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Barry3/barry93.html">Continued fractions and transformations of integer sequences</a>, JIS 12 (2009) 09.7.6

%H P. Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Barry1/barry95r.html">Generalized Catalan Numbers, Hankel Transforms and Somos-4 Sequences </a>, J. Int. Seq. 13 (2010) #10.7.2.

%H P. Barry, <a href="http://arxiv.org/abs/1205.2565">On sequences with {-1, 0, 1} Hankel transforms</a>, arXiv preprint arXiv:1205.2565 [math.CO], 2012.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry4/bern2.html">Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences</a>, Journal of Integer Sequences, Vol. 15 2012, #12.8.2.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry5/barry223.html">On the Hurwitz Transform of Sequences</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.8.7.

%H Christian Bean, A Claesson, H Ulfarsson, <a href="http://arxiv.org/abs/1512.03226">Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3</a>, arXiv preprint arXiv:1512.03226 [math.CO], 2015.

%H Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, <a href="http://arxiv.org/abs/1310.7003">Pattern-avoiding involutions: exact and asymptotic enumeration</a>, arxiv:1310.7003 [math.CO], 2013.

%H A. Bostan, <a href="https://www-apr.lip6.fr/sem-comb-slides/IHP-bostan.pdf">Computer Algebra for Lattice Path Combinatorics</a>, Seminaire de Combinatoire Ph. Flajolet, Mar 28 2013.

%H Alin Bostan and Manuel Kauers, <a href="https://arxiv.org/abs/0811.2899">Automatic Classification of Restricted Lattice Walks</a>, arXiv:0811.2899 [math.CO], 2009.

%H H. Bottomley, <a href="/A001006/a001006.2.gif">Illustration of initial terms</a>

%H A. Burstein, J. Pantone, <a href="http://arxiv.org/abs/1402.3842">Two examples of unbalanced Wilf-equivalence</a>, arXiv:1402.3842 [math.CO], 2014.

%H N. T. Cameron, <a href="http://www.princeton.edu/~wmassey/NAM03/cameron.pdf">Random walks, trees and extensions of Riordan group techniques</a>

%H Naiomi T. Cameron and Asamoah Nkwanta, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Cameron/cameron46.html">On Some (Pseudo) Involutions in the Riordan Group</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.

%H J. Cigler, <a href="http://arxiv.org/abs/1109.1449">Some nice Hankel determinants</a>. arXiv preprint arXiv:1109.1449 [math.CO], 2011.

%H J. B. Cosgrave, <a href="/A103772/a103772.txt">The Gauss-Factorial Motzkin connection</a> (Maple worksheet, change suffix to .mw)

%H R. De Castro, A. L. Ramírez and J. L. Ramírez, <a href="http://arxiv.org/abs/1310.2449">Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs</a>, arXiv preprint arXiv:1310.2449 [cs.DM], 2013.

%H E. Deutsch and B. E. Sagan, <a href="http://arxiv.org/abs/math.CO/0407326">Congruences for Catalan and Motzkin numbers and related sequences</a>, J. Num. Theory 117 (2006), 191-215.

%H R. M. Dickau, <a href="http://mathforum.org/advanced/robertd/delannoy.html">Delannoy and Motzkin Numbers</a>

%H R. M. Dickau, <a href="/A001006/a001006.4.gif">The 9 paths in a 4 X 4 grid</a>

%H Yun Ding and Rosena R. X. Du, <a href="http://arxiv.org/abs/1109.2661">Counting Humps in Motzkin paths</a>, arXiv preprint arXiv:1109.2661 [math.CO], 2011.

%H Filippo Disanto and Thomas Wiehe, <a href="http://arxiv.org/abs/1210.6908">Some instances of a sub-permutation problem on pattern avoiding permutations</a>, arXiv preprint arXiv:1210.6908 [math.CO], 2012.

%H I. Dolinka, J. East, A. Evangelou, D. FitzGerald, N. Ham, <a href="http://arxiv.org/abs/1507.04838">Idempotent Statistics of the Motzkin and Jones Monoids</a>, arXiv preprint arXiv:1507.04838 [math.CO], 2015.

%H I Dolinka, J East, RD Gray, <a href="http://arxiv.org/abs/1512.02279">Motzkin monoids and partial Brauer monoids</a>, arXiv preprint arXiv:1512.02279 [math.GR], 2015.

%H E. S. Egge, <a href="http://arXiv.org/abs/math.CO/0307050">Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations</a>, sec. 8, arXiv:math/0307050 [math.CO], 2003.

%H S. B. Ekhad, M. Yang, <a href="http://sites.math.rutgers.edu/~zeilberg/tokhniot/oMathar1maple12.txt"> Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences</a>, (2017)

%H Luca Ferrari and Emanuele Munarini, <a href="http://arxiv.org/abs/1203.6792">Enumeration of edges in some lattices of paths</a>, arXiv preprint arXiv:1203.6792 [math.CO], 2012 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Ferrari/ferrari.html">J. Int. Seq. 17 (2014) #14.1.5</a>.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 68, 81

%H Nils Haug, T. Prellberg, G. Siudem, <a href="https://arxiv.org/abs/1605.09643">Scaling in area-weighted generalized Motzkin paths</a>, arXiv preprint arXiv:1605.09643 [cond-mat.stat-mech], 2016.

%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 Cheyne Homberger, <a href="http://arxiv.org/abs/1410.2657">Patterns in Permutations and Involutions: A Structural and Enumerative Approach</a>, arXiv preprint 1410.2657 [math.CO], 2014.

%H Anders Hyllengren, <a href="/A258710/a258710.pdf">Letter to N. J. A. Sloane, Oct 04 1985</a>

%H Anders Hyllengren, <a href="/A001006/a001006_5.pdf">Four integer sequences</a>, Oct 04 1985. Observes essentially that A000984 and A002426 are inverse binomial transforms of each other, as are A000108 and A001006.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=50">Encyclopedia of Combinatorial Structures 50</a>

%H D. E. Knuth, <a href="/A001006/a001006_3.pdf">Letter to L. W. Shapiro, R. K. Guy. N. J. A. Sloane, R. P. Stanley, H. Wilf regarding A001006 and A005043</a>, Jan 18, 1989

%H Dmitry V. Kruchinin and Vladimir V. Kruchinin, <a href="http://www.emis.de/journals/JIS/VOL18/Kruchinin/kruch9.pdf">A Generating Function for the Diagonal T_{2n,n} in Triangles</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.6.

%H J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.

%H W. A. Lorenz, Y. Ponty and P. Clote, <a href="http://bioinformatics.bc.edu/~ponty/docs/AsymptoticsRNAShapes-JCompBiol-LorenzPontyClote.pdf">Asymptotics of RNA Shapes</a>, Journal of Computational Biology 15:1 (2008), pp. 31-63.

%H K Manes, A Sapounakis, I Tasoulas, P Tsikouras, <a href="http://arxiv.org/abs/1510.01952">Equivalence classes of ballot paths modulo strings of length 2 and 3</a>, arXiv preprint arXiv:1510.01952 [math.CO], 2015.

%H Toufik Mansour, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Mansour/mansour86.html">Statistics on Dyck Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.

%H T. Mansour, <a href="http://arXiv.org/abs/math.CO/0110039">Restricted 1-3-2 permutations and generalized patterns</a>, arXiv:math/0110039 [math.CO], 2001.

%H V. Mazorchuk and B. Steinberg, <a href="http://arxiv.org/abs/1105.5313">Double Catalan monoids</a>, arXiv preprint arXiv:1105.5313 [math.GR], 2011.

%H Cam McLeman and Erin McNicholas, <a href="http://arxiv.org/abs/1108.3588">Graph Invertibility</a>, arXiv preprint arXiv:1108.3588 [math.CO], 2011.

%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 T. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1945-08486-9">The hypersurface cross ratio</a>, Bull. Amer. Math. Soc., 51 (1945), 976-984.

%H Heinrich Niederhausen, <a href="http://arxiv.org/abs/1105.3713">Inverses of Motzkin and Schroeder Paths</a>, arXiv preprint arXiv:1105.3713 [math.CO], 2011.

%H J.-C. Novelli and J.-Y. Thibon, <a href="http://arXiv.org/abs/math.CO/0512570">Noncommutative Symmetric Functions and Lagrange Inversion</a>, arXiv:math/0512570 [math.CO], 2005-2006.

%H Roy Oste and Joris Van der Jeugt, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p8">Motzkin paths, Motzkin polynomials and recurrence relations</a>, The Electronic Journal of Combinatorics, 22(2) (2015), #P2.8 1.

%H Ville H. Pettersson, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p7">Enumerating Hamiltonian Cycles</a>, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca:16080/~plouffe/OEIS/b001006.txt">The first 4431 terms</a>

%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/notredame.pdf">Pattern avoidance in trees</a> (slides from a talk, mentions many sequences), 2012

%H L. Pudwell, A. Baxter, <a href="http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf">Ascent sequences avoiding pairs of patterns</a>, 2014

%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf">Pattern-avoiding ascent sequences</a>, Slides from a talk, 2015

%H José L. Ramírez, <a href="http://arxiv.org/abs/1511.04577">The Pascal Rhombus and the Generalized Grand Motzkin Paths</a>, arXiv:1511.04577 [math.CO], 2015.

%H J. L. Ramírez, V. F. Sirvent, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p38">A Generalization of the k-Bonacci Sequence from Riordan Arrays</a>, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.

%H Alon Regev, Amitai Regev, Doron Zeilberger, <a href="http://arxiv.org/abs/1507.03499">Identities in character tables of S_n</a>, arXiv preprint arXiv:1507.03499 [math.CO], 2015.

%H John Riordan, <a href="/A001006/a001006_1.pdf">Letter to N. J. A. Sloane</a>, 1974.

%H Dan Romik, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Romik/romik5.html">Some formulas for the central trinomial and Motzkin numbers</a>, J. Integer Seqs., Vol. 6, 2003.

%H E. Rowland, R. Yassawi, <a href="http://arxiv.org/abs/1310.8635">Automatic congruences for diagonals of rational functions</a>, arXiv preprint arXiv:1310.8635 [math.NT], 2013.

%H E. Rowland, D. Zeilberger, <a href="http://arxiv.org/abs/1311.4776">A Case Study in Meta-AUTOMATION: AUTOMATIC Generation of Congruence AUTOMATA For Combinatorial Sequences</a>, arXiv preprint arXiv:1311.4776 [math.CO], 2013.

%H E. Royer, <a href="http://www.carva.org/emmanuel.royer">Interpretation combinatoire des moments negatifs des valeurs de fonctions L au bord de la bande critique</a>

%H Martin Rubey and Christian Stump, <a href="https://arxiv.org/abs/1708.05092">Double deficiencies of Dyck paths via the Billey-Jockusch-Stanley bijection</a>, arXiv:1708.05092 [math.CO], 2017.

%H J. Salas and A. D. Sokal, Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models. V. Further Results for the Square-Lattice Chromatic Polynomial, J. Stat. Phys. 135 (2009) 279-373, <a href="http://arxiv.org/abs/0711.1738">arXiv preprint</a>, arXiv:0711.1738 [cond-mat.stat-mech], 2007-2009. Mentions this sequence.

%H A. Sapounakis and P. Tsikouras, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Tsikouras/tsikouras43.html">On k-colored Motzkin words</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.5.

%H E. Schröder, <a href="/A000108/a000108_9.pdf">Vier combinatorische Probleme</a>, Z. f. Math. Phys., 15 (1870), 361-376. [Annotated scanned copy]

%H N. J. A. Sloane, <a href="/A001006/a001006.gif">Illustration of initial terms</a>

%H N. J. A. Sloane, <a href="/classic.html#MOTZKIN">Classic Sequences</a>

%H N. J. A. Sloane, <a href="/A001006/a001006_Vg.jpg">An Application of the OEIS</a> (Vugraph from a talk about the OEIS)

%H P. R. Stein and M. S. Waterman, <a href="/A001006/a001006_4.pdf">On some new sequences generalizing the Catalan and Motzkin numbers</a> [Corrected annotated scanned copy]

%H R. A. Sulanke, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/SULANKE/sulanke.html">Moments of generalized Motzkin paths</a>, J. Integer Sequences, Vol. 3 (2000), #00.1.

%H Hua Sun, Yi Wang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Wang/wang11.html">A Combinatorial Proof of the Log-Convexity of Catalan-Like Numbers</a>, J. Int. Seq. 17 (2014) # 14.5.2

%H Yidong Sun and Fei Ma, <a href="http://arxiv.org/abs/1305.2015">Minors of a Class of Riordan Arrays Related to Weighted Partial Motzkin Paths</a>, arXiv preprint arXiv:1305.2015 [math.CO], 2013.

%H Zhi-Wei Sun, <a href="http://arxiv.org/abs/1208.2683">Conjectures involving arithmetical sequences</a>, in: Number Theory: Arithmetic in Shangri-La (eds., S. Kanemitsu, H. Li and J. Liu), Proc. 6th China-Japan Seminar (Shanghai, August 15-17, 2011), World Sci., Singapore, 2013, pp. 244-258.

%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016.

%H Paul Tarau, <a href="http://www.cse.unt.edu/~tarau/research/2015/dbx.pdf">On logic programming representations of lambda terms: de Bruijn indices, compression, type inference, combinatorial generation, normalization</a>, 2015.

%H P. Tarau, <a href="http://arxiv.org/abs/1507.06944">A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations</a>, arXiv preprint arXiv:1507.06944 [cs.LO], 2015.

%H Paul Tarau, <a href="https://arxiv.org/abs/1608.03912">A Hiking Trip Through the Orders of Magnitude: Deriving Efficient Generators for Closed Simply-Typed Lambda Terms and Normal Forms</a>, arXiv preprint arXiv:1608.03912 [cs.PL], 2016.

%H Yi Wang and Bao-Xuan Zhu, <a href="http://arxiv.org/abs/1303.5595">Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences</a>, arXiv preprint arXiv:1303.5595 [math.CO], 2013.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MotzkinNumber.html">Motzkin Number</a>

%H W.-J. Woan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WOAN/hankel2.html">Hankel Matrices and Lattice Paths</a>, J. Integer Sequences, 4 (2001), #01.1.2.

%H J. Y. X. Yang, M. X. X. Zhong, R. D. P. Zhou, <a href="http://arxiv.org/abs/1406.2583">On the Enumeration of (s, s+ 1, s+2)-Core Partitions</a>, arXiv preprint arXiv:1406.2583 [math.CO], 2014.

%H Huan Xiong, <a href="http://arxiv.org/abs/1409.7038">The number of simultaneous core partitions</a>, arXiv preprint arXiv:1409.7038 [math.CO], 2014.

%H Yan X. Zhang, <a href="http://arxiv.org/abs/1508.00318">Four Variations on Graded Posets</a>, arXiv preprint arXiv:1508.00318 [math.CO], 2015.

%H Zhuang, Yan. <a href="https://arxiv.org/abs/1508.02793">A generalized Goulden-Jackson cluster method and lattice path enumeration</a>, Discrete Mathematics 341.2 (2018): 358-379. Also arXiv: 1508.02793v2.

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F G.f.: A(x) = ( 1 - x - (1-2*x-3*x^2)^(1/2) ) / (2*x^2).

%F G.f. A(x) satisfies A(x) = 1 + x*A(x) + x^2*A(x)^2.

%F G.f. F(x)/x where F(x) is the reversion of x/(1+x+x^2). - _Joerg Arndt_, Oct 23 2012

%F a(n) = (-1/2) Sum_(-3)^i C(1/2, i) C(1/2, j); i+j=n+2, i >= 0, j >= 0.

%F a(n) = (3/2)^(n+2) * Sum_{k >= 1} 3^(-k) * Catalan(k-1) * binomial(k, n+2-k). [Doslic et al.]

%F a(n) ~ 3^(n+1)sqrt(3)[1+1/(16n)]/[(2n+3)sqrt((n+2)Pi)]. [Barcucci, Pinzani and Sprugnoli]

%F Lim_{n->infinity} a(n)/a(n-1) = 3. [Aigner]

%F a(n+2) - a(n+1) = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0). [Bernhart]

%F a(n) = (1/(n+1)) * Sum_{i} (n+1)!/(i!*(i+1)!*(n-2*i)!). [Bernhart]

%F a(n) = sum((-1)^(n-k)*binomial(n, k)*A000108(k+1), k=0..n). a(n) = sum(binomial(n+1, k)*binomial(n+1-k, k-1), k=0..ceil((n+1)/2))/(n+1); (n+2)a(n) = (2n+1)a(n-1)+(3n-3)a(n-2). - _Len Smiley_

%F a(n) = sum{ k=0..n, C(n, 2k)*A000108(k) }. - _Paul Barry_, Jul 18 2003

%F E.g.f.: exp(x)*BesselI(1, 2*x)/x. - _Vladeta Jovovic_, Aug 20 2003

%F a(n) = A005043(n) + A005043(n+1).

%F The Hankel transform of this sequence gives A000012 = [1, 1, 1, 1, 1, 1, ...]. E.g., Det([1, 1, 2, 4; 1, 2, 4, 9; 2, 4, 9, 21; 4, 9, 21, 51]) = 1. - _Philippe Deléham_, Feb 23 2004

%F a(m+n) = Sum_{k>=0} A064189(m, k)*A064189(n, k). - _Philippe Deléham_, Mar 05 2004

%F a(n) = sum((-1)^j*binomial(n+1, j)*binomial(2n-3j, n), j=0..floor(n/3))/(n+1). - _Emeric Deutsch_, Mar 13 2004

%F a(n) = A086615(n)-A086615(n-1) (n>=1). - _Emeric Deutsch_, Jul 12 2004

%F G.f.: A(x)=(1-y+y^2)/(1-y)^2 where (1+x)*(y^2-y)+x=0; A(x)=4*(1+x)/(1+x+sqrt(1-2*x-3*x^2))^2; a(n)=(3/4)*(1/2)^n*sum(k=0..2*n, 3^(n-k)*C(k)*C(k+1, n+1-k) ) + 0^n/4 [after Doslic et al.]. - _Paul Barry_, Feb 22 2005

%F G.f.: c(x^2/(1-x)^2)/(1-x), c(x) the g.f. of A000108. - _Paul Barry_, May 31 2006

%F Asymptotic formula : a(n) ~ sqrt(3/4/Pi)*3^(n+1)/n^(3/2). - _Benoit Cloitre_, Jan 25 2007

%F a(n) = A007971(n+2)/2. - _Zerinvary Lajos_, Feb 28 2007

%F a(n)=(1/(2*pi))*int(x^n*sqrt((3-x)*(1+x)),x,-1,3) is the moment representation. - _Paul Barry_, Sep 10 2007

%F Equals inverse binomial transform of A000108 starting (1, 2, 5, 14, 42,...). - _Gary W. Adamson_, Dec 10 2007

%F Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n-1} + a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-2}*a_1 for n >= t. For example, Phi([1]) is the Catalan numbers A000108. The present sequence is Phi([0,1,1]), see the 6th formula. - _Gary W. Adamson_, Oct 27 2008

%F G.f.: 1/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/.... (continued fraction). - _Paul Barry_, Dec 06 2008

%F G.f.: 1/(1-(x+x^2)/(1-x^2/(1-(x+x^2)/(1-x^2/(1-(x+x^2)/(1-x^2/(1-.... (continued fraction). - _Paul Barry_, Feb 08 2009

%F a(n) = (-3)^(1/2)/(6*(n+2)) * (-1)^n*(3*hypergeom([1/2, n+1],[1],4/3) - hypergeom([1/2, n+2],[1],4/3)). - _Mark van Hoeij_, Nov 12 2009

%F G.f.: 1/(1-x/(1-x/(1-x^2/(1-x/(1-x/(1-x^2/(1-x/(1-x/(1-x^2/(1-... (continued fraction). - _Paul Barry_, Mar 02 2010

%F G.f.: 1/(1-x/(1-x/(1+x-x/(1-x/(1+x-x/(1-x/(1+x-x/(1-x/(1+x-x/(1-... (continued fraction). - _Paul Barry_, Jan 26 2011 [Adds apparently a third '1' in front. - _R. J. Mathar_, Jan 29 2011]

%F Let A(x) be the g.f., then B(x)=1+x*A(x) = 1 +1*x +1*x^2 +2*x^3 +4*x^4 +9*x^5 +... = 1/(1-z/(1-z/(1-z/(...)))) where z=x/(1+x) (continued fraction); more generally B(x)=C(x/(1+x)) where C(x) is the g.f. for the Catalan numbers (A000108). - _Joerg Arndt_, Mar 18 2011

%F a(n) = (2/Pi)*integral(x=-1..1, (1+2*x)^n*sqrt(1-x^2)). - _Peter Luschny_, Sep 11 2011

%F G.f.: (1-x-sqrt(1-2*x-3*(x^2)))/(2*(x^2)) = 1/2/(x^2)-1/2/x-1/2/(x^2)*G(0); G(k) = 1+(4*k-1)*x*(2+3*x)/(4*k+2-x*(2+3*x)*(4*k+1)*(4*k+2) /(x*(2+3*x)*(4*k+1)+(4*k+4)/G(k+1)), if -1 < x < 1/3; (continued fraction). - _Sergei N. Gladkovskii_, Dec 01 2011

%F G.f.: (1-x-sqrt(1-2*x-3*(x^2)))/(2*(x^2)) = (-1 + 1/G(0))/(2*x) ; G(k) = 1-2*x/(1+x/(1+x/(1-2*x/(1-x/(2-x/G(k+1)))))); (continued fraction). - _Sergei N. Gladkovskii_, Dec 11 2011

%F 0 = a(n) * (9*a(n+1) + 15*a(n+2) - 12*a(n+3)) + a(n+1) * ( -3*a(n+1) + 10*a(n+2) - 5*a(n+3)) + a(n+2) * (a(n+2) + a(n+3)) unless n=-2. - _Michael Somos_, Mar 23 2012

%F a(n) = (-1)^n*hypergeometric([-n,3/2],[3],4). - _Peter Luschny_, Aug 15 2012

%F Representation in terms of special values of Jacobi polynomials P(n,alpha,beta,x), in Maple notation: a(n)= 2*(-1)^n*n!*JacobiP(n,2,-3/2-n,-7)/(n+2)!, n>=0. - _Karol A. Penson_, Jun 24 2013

%F G.f.: Q(0)/x - 1/x, where Q(k) = 1 + (4*k+1)*x/((1+x)*(k+1) - x*(1+x)*(2*k+2)*(4*k+3)/(x*(8*k+6)+(2*k+3)*(1+x)/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 14 2013

%F Catalan(n+1) = Sum_{k=0..n} binomial(n,k)*a(k). E.g.: 42 = 1*1 + 4*1 + 6*2 + 4*4 + 1*9. _Doron Zeilberger_, Mar 12, 2015.

%F G.f. A(x) with offset 1 satisfies: A(x)^2 = A( x^2/(1-2*x) ). - _Paul D. Hanna_, Nov 08 2015

%F Conjecture: +(n+2)*a(n) +(-2*n-1)*a(n-1) +3*(-n+1)*a(n-2)=0. - _R. J. Mathar_, Sep 06 2016 Conjecture follows from the D.E. (3*x^3+2*x^2-x)*g'(x)+(3*x^2+3*x-2)*g(x)+2=0 satisfied by the g.f.. - _Robert Israel_, Mar 16 2018

%F a(n) = GegenbauerPoly(n,-n-1,-1/2)/(n+1). - _Emanuele Munarini_, Oct 20 2016

%F a(n) = a(n-1)+A002026(n-1). Number of Motzkin paths that start with an F step plus number of Motzkin paths that start with an U step. - _R. J. Mathar_, Jul 25 2017

%F G.f. A(x) satisfies A(x)*A(-x) = F(x^2), where F(x) is the g.f. of A168592. - _Alexander Burstein_, Oct 04 2017

%F G.f.: A(x) = exp(int((E(x)-1)/x dx), where E(x) is the g.f. of A002426. Equivalently, E(x) = 1 + x*A'(x)/A(x). - _Alexander Burstein_, Oct 05 2017

%e G.f.: 1 + x + 2*x^2 + 4*x^3 + 9*x^4 + 21*x^5 + 51*x^6 + 127*x^7 + 323*x^8 + ...

%p # Three different Maple scripts for this sequence:

%p [seq(add(binomial(n+1,k)*binomial(n+1-k,k-1),k=0..ceil((n+1)/2))/(n+1), n=0..50)];

%p A001006 := proc(n) option remember; local k; if n <= 1 then 1 else procname(n-1) + add(procname(k)*procname(n-k-2),k=0..n-2); fi; end;

%p Order := 20: solve(series(x/(1+x+x^2),x)=y,x);

%p zl:=4*(1-z+sqrt(1-2*z-3*z^2))/(1-z+sqrt(1-2*z-3*z^2))^2/2: gser:=series(zl, z=0, 35): seq(coeff(gser, z, n), n=0..29); # _Zerinvary Lajos_, Feb 28 2007

%p # n -> [a(0),a(1),..,a(n)]

%p A001006_list := proc(n) local w, m, j, i; w := proc(i,j,n) option remember;

%p if min(i,j,n) < 0 or max(i,j) > n then 0

%p elif n = 0 then if i = 0 and j = 0 then 1 else 0 fi else

%p w(i, j + 1, n - 1) + w(i - 1, j, n - 1) + w(i + 1, j - 1, n - 1) fi end:

%p [seq( add( add( w(i, j, m), i = 0..m), j = 0..m), m = 0..n)] end:

%p A001006_list(29); # _Peter Luschny_, May 21 2011

%t a[0] = 1; a[n_Integer] := a[n] = a[n - 1] + Sum[a[k] * a[n - 2 - k], {k, 0, n - 2}]; Array[a[#] &, 30]

%t CoefficientList[Series[(1 - x - (1 - 2x - 3x^2)^(1/2))/(2x^2), {x, 0, 29}], x] (* _Jean-François Alcover_, Nov 29 2011 *)

%t Table[Hypergeometric2F1[(1-n)/2, -n/2, 2, 4], {n,0,29}] (* _Peter Luschny_, May 15 2016 *)

%t Table[GegenbauerC[n,-n-1,-1/2]/(n+1),{n,0,100}] (* _Emanuele Munarini_, Oct 20 2016 *)

%o (PARI) {a(n) = polcoeff( ( 1 - x - sqrt((1 - x)^2 - 4 * x^2 + x^3 * O(x^n))) / (2 * x^2), n)}; /* _Michael Somos_, Sep 25 2003 */

%o (PARI) {a(n) = if( n<0, 0, n++; polcoeff( serreverse( x / (1 + x + x^2) + x * O(x^n)), n))}; /* _Michael Somos_, Sep 25 2003 */

%o (PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp(x + x * O(x^n)) * besseli(1, 2 * x + x * O(x^n)), n))}; /* _Michael Somos_, Sep 25 2003 */

%o (Maxima) a[0]:1$

%o a[1]:1$

%o a[n]:=((2*n+1)*a[n-1]+(3*n-3)*a[n-2])/(n+2)$

%o makelist(a[n],n,0,12); /* _Emanuele Munarini_, Mar 02 2011 */

%o (Maxima)

%o M(n) := coeff(expand((1+x+x^2)^(n+1)),x^n)/(n+1);

%o makelist(M(n),n,0,60); /* _Emanuele Munarini_, Apr 04 2012 */

%o (Maxima) makelist(ultraspherical(n,-n-1,-1/2)/(n+1),n,0,12); /* _Emanuele Munarini_, Oct 20 2016 */

%o (Haskell)

%o a001006 n = a001006_list !! n

%o a001006_list = zipWith (+) a005043_list $ tail a005043_list

%o -- _Reinhard Zumkeller_, Jan 31 2012

%o (Python)

%o from gmpy2 import divexact

%o A001006 = [1, 1]

%o for n in range(2,10**3):

%o ....A001006.append(divexact(A001006[-1]*(2*n+1)+(3*n-3)*A001006[-2],n+2))

%o # _Chai Wah Wu_, Sep 01 2014

%o (Sage)

%o def mot():

%o a, b, n = 0, 1, 1

%o while True:

%o yield b//n

%o n += 1

%o a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)//((n+1)*(n-1))

%o A001006 = mot()

%o print([A001006.next() for n in range(30)]) # _Peter Luschny_, May 16 2016

%Y Cf. A026300, A005717, A020474, A001850, A004148. First column of A064191, A064189, A000108, A088615, A007971, A001405, A005817, A049401, A007579, A007578, A097862, A144218, A005773, A178515, A217275. First row of A064645.

%Y Bisections: A026945, A099250.

%Y Sequences related to chords in a circle: A001006, A054726, A006533, A006561, A006600, A007569, A007678. See also entries for chord diagrams in Index file.

%Y a(n) = A005043(n)+A005043(n+1).

%Y A086246 is another version, although this is the main entry. Column k=3 of A182172.

%Y Motzkin numbers A001006 read mod 2,3,4,5,6,7,8,11: A039963, A039964, A299919, A258712, A299920, A258711, A299918, A258710.

%Y Cf. A004148, A004149, A023421, A023422, A023423.

%K nonn,core,easy,nice,changed

%O 0,3

%A _N. J. A. Sloane_

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 March 19 16:57 EDT 2018. Contains 300868 sequences. (Running on oeis4.)