A001006 - OEIS

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A001006 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A001006" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA001006">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A001006 - OEIS"></a> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> A001006 </div> <div class=seqname> Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle. <br><font size=-1>(Formerly M1184 N0456)</font> </div> </div> <div class=scorerefs> 590 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, 1697385471211</div> <div class=seqdatalinks> (<a href="/A001006/list">list</a>; <a href="/A001006/graph">graph</a>; <a href="/search?q=A001006+-id:A001006">refs</a>; <a href="/A001006/listen">listen</a>; <a href="/history?seq=A001006">history</a>; <a href="/search?q=id:A001006&fmt=text">text</a>; <a href="/A001006/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,3</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline>Number of 4321-, (3412,2413)-, (3412,3142)- and 3412-avoiding involutions in S_n.</div> <div class=sectline>Number of sequences of length n-1 consisting of positive integers such that the first and last elements are 1 or 2 and the absolute difference between any 2 consecutive elements is 0 or 1. - <a href="/wiki/User:Jon_Perry">Jon Perry</a>, Sep 04 2003</div> <div class=sectline>From <a href="/wiki/User:David_Callan">David Callan</a>, Jul 15 2004: (Start)</div> <div class=sectline>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).</div> <div class=sectline>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.)</div> <div class=sectline>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.) (End)</div> <div class=sectline>a(n) is the number of strings of length 2n+2 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. See Orrick link (2024). - Saul Schleimer (saulsch(AT)math.rutgers.edu), Feb 23 2006 (Additional linked comment added by <a href="/wiki/User:William_P._Orrick">William P. Orrick</a>, Jun 13 2024.)</div> <div class=sectline>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. - <a href="/wiki/User:David_Callan">David Callan</a>, Jun 07 2006</div> <div class=sectline>Also the number of standard Young tableaux of height <= 3. - <a href="/wiki/User:Mike_Zabrocki">Mike Zabrocki</a>, Mar 24 2007</div> <div class=sectline>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</div> <div class=sectline>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. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Oct 27 2008</div> <div class=sectline>Equals <a href="/A005773" title="Number of directed animals of size n (or directed n-ominoes in standard position).">A005773</a> / <a href="/A005773" title="Number of directed animals of size n (or directed n-ominoes in standard position).">A005773</a> shifted (i.e., (1,2,5,13,35,96,...) / (1,1,2,5,13,35,96,...)). - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Dec 21 2008</div> <div class=sectline>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. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Jan 07 2009</div> <div class=sectline>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.] - <a href="/wiki/User:Emeric_Deutsch">Emeric Deutsch</a>, May 29 2010</div> <div class=sectline>Let w(i,j,n) denote walks in N^2 which satisfy the multivariate recurrence 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. - <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, May 21 2011</div> <div class=sectline>a(n)/a(n-1) tends to 3.0 as N->infinity: (1+2*cos(2*Pi/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. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Jun 08 2011</div> <div class=sectline>Number of (n+1)-length permutations avoiding the pattern 132 and the dotted pattern 23\dot{1}. - <a href="/wiki/User:Jean-Luc_Baril">Jean-Luc Baril</a>, Mar 07 2012</div> <div class=sectline>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. - <a href="/wiki/User:Alois_P._Heinz">Alois P. Heinz</a>, May 26 2012</div> <div class=sectline>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. - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Apr 16 2013</div> <div class=sectline>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. - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Apr 17 2013</div> <div class=sectline>Number of (4231,5276143)-avoiding involutions in S_n. - <a href="/wiki/User:Alexander_Burstein">Alexander Burstein</a>, Mar 05 2014</div> <div class=sectline>a(n) is the number of increasing unary-binary trees with n nodes that have an associated permutation that avoids 132. For more information about unary-binary trees with associated permutations, see <a href="/A245888" title="Number of labeled increasing unary-binary trees on n nodes whose breadth-first reading word avoids 231.">A245888</a>. - <a href="/wiki/User:Manda_Riehl">Manda Riehl</a>, Aug 07 2014</div> <div class=sectline>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.) - <a href="/wiki/User:David_Callan">David Callan</a>, Aug 27 2014</div> <div class=sectline>From <a href="/wiki/User:Tony_Foster_III">Tony Foster III</a>, Jul 28 2016: (Start)</div> <div class=sectline>A series created using 2*a(n) + a(n+1) has Hankel transform of F(2n), offset 3, F being the Fibonacci bisection, <a href="/A001906" title="F(2n) = bisection of Fibonacci sequence: a(n) = 3*a(n-1) - a(n-2).">A001906</a> (empirical observation).</div> <div class=sectline>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, <a href="/A197649" title="a(n) = Sum_{k=0..n} k*Fibonacci(2*k).">A197649</a> (empirical observation). (End)</div> <div class=sectline>Conjecture: (2/n)*Sum_{k=1..n} (2k+1)*a(k)^2 is an integer for each positive integer n. - <a href="/wiki/User:Zhi-Wei_Sun">Zhi-Wei Sun</a>, Nov 16 2017</div> <div class=sectline>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." - <a href="/wiki/User:Eric_M._Schmidt">Eric M. Schmidt</a>, Dec 16 2017</div> <div class=sectline>Number of U_{k}-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths. - <a href="/wiki/User:Sergey_Kirgizov">Sergey Kirgizov</a>, Apr 08 2018</div> <div class=sectline>If tau_1 and tau_2 are two distinct permutation patterns chosen from the set {132,231,312}, then a(n) is the number of valid hook configurations of permutations of [n+1] that avoid the patterns tau_1 and tau_2. - <a href="/wiki/User:Colin_Defant">Colin Defant</a>, Apr 28 2019</div> <div class=sectline>Number of permutations of length n that are sorted to the identity by a consecutive-321-avoiding stack followed by a classical-21-avoiding stack. - <a href="/wiki/User:Colin_Defant">Colin Defant</a>, Aug 29 2020</div> <div class=sectline>From <a href="/wiki/User:Helmut_Prodinger">Helmut Prodinger</a>, Dec 13 2020: (Start)</div> <div class=sectline>a(n) is the number of paths in the first quadrant starting at (0,0) and consisting of n steps from the infinite set {(1,1), (1,-1), (1,-2), (1,-3), ...}.</div> <div class=sectline>For example, denoting U=(1,1), D=(1,-1), D_ j=(1,-j) for j >= 2, a(4) counts UUUU, UUUD, UUUD_2, UUUD_3, UUDU, UUDD, UUD_2U, UDUU, UDUD.</div> <div class=sectline>This step set is inspired by {(1,1), (1,-1), (1,-3), (1,-5), ...}, suggested by Emeric Deutsch around 2000.</div> <div class=sectline>See Prodinger link that contains a bijection to Motzkin paths. (End)</div> <div class=sectline>Named by Donaghey (1977) after the Israeli-American mathematician Theodore Motzkin (1908-1970). In Sloane's "A Handbook of Integer Sequences" (1973) they were called "generalized ballot numbers". - <a href="/wiki/User:Amiram_Eldar">Amiram Eldar</a>, Apr 15 2021</div> <div class=sectline>Number of Motzkin n-paths a(n) is split into <a href="/A107587" title="Number of Motzkin n-paths with an even number of up steps.">A107587</a>(n), number of even Motzkin n-paths, and <a href="/A343386" title="Number of odd Motzkin n-paths, i.e., Motzkin n-paths with an odd number of up steps.">A343386</a>(n), number of odd Motzkin n-paths. The value <a href="/A107587" title="Number of Motzkin n-paths with an even number of up steps.">A107587</a>(n) - <a href="/A343386" title="Number of odd Motzkin n-paths, i.e., Motzkin n-paths with an odd number of up steps.">A343386</a>(n) can be called the "shadow" of a(n) (see <a href="/A343773" title="Excess of the number of even Motzkin n-paths (A107587) over the odd ones (A343386).">A343773</a>). - <a href="/wiki/User:Gennady_Eremin">Gennady Eremin</a>, May 17 2021</div> <div class=sectline>Conjecture: If p is a prime of the form 6m+1 (<a href="/A002476" title="Primes of the form 6m + 1.">A002476</a>), then a(p-2) is divisible by p. Currently, no counterexample exists for p < 10^7. Personal communication from <a href="/wiki/User:Robert_Gerbicz">Robert Gerbicz</a>: mod such p this is equivalent to <a href="/A066796" title="a(n) = Sum_{i=1..n} binomial(2*i,i).">A066796</a> with comment: "Every <a href="/A066796" title="a(n) = Sum_{i=1..n} binomial(2*i,i).">A066796</a>(n) from <a href="/A066796" title="a(n) = Sum_{i=1..n} binomial(2*i,i).">A066796</a>((p-1)/2) to <a href="/A066796" title="a(n) = Sum_{i=1..n} binomial(2*i,i).">A066796</a>(p-1) is divisible by prime p of form 6m+1". - <a href="/wiki/User:Serge_Batalov">Serge Batalov</a>, Feb 08 2022</div> <div class=sectline>From <a href="/wiki/User:Rob_Burns">Rob Burns</a>, Nov 11 2024: (Start)</div> <div class=sectline>The conjecture is proved in the 2017 paper by Rob Burns in the Links below. The result is contained in Tables 4 and 5 of the paper, which show that a(p-2) = 0 (mod p) when p = 1 (mod 6) and a(p-2) ‎ = -1 (mod p) when p = -1 (mod 6).</div> <div class=sectline>In fact, the 2017 paper by Burns establishes more general congruences for a(p^k - 2) where k >= 1.</div> <div class=sectline>If p = 1 (mod 6) then a(p^k - 2) ‎= 0 (mod p) for k >=1.</div> <div class=sectline>If p = -1 (mod 6) then a(p^k - 2) ‎= -1 (mod p) when k is odd and a(p^k - 2) = 0 (mod p) when k is even.</div> <div class=sectline>These are consequences of the transitions provided in Tables 4, 5 and 6 of the paper.</div> <div class=sectline>The 2024 paper by Nadav Kohen also proves the conjecture. Proposition 6 of the paper states that a prime p divides a(p-2) if and only if p = (1 mod 3). (End)</div> <div class=sectline>From <a href="/wiki/User:Peter_Bala">Peter Bala</a>, Feb 10 2022: (Start)</div> <div class=sectline>Conjectures:</div> <div class=sectline>(1) For prime p == 1 (mod 6) and n, r >= 1, a(n*p^r - 2) == -<a href="/A005717" title="Construct triangle in which n-th row is obtained by expanding (1 + x + x^2)^n and take the next-to-central column.">A005717</a>(n-1) (mod p), where we take <a href="/A005717" title="Construct triangle in which n-th row is obtained by expanding (1 + x + x^2)^n and take the next-to-central column.">A005717</a>(0) = 0 to match Batalov's conjecture above.</div> <div class=sectline>(2) For prime p == 5 (mod 6) and n >= 1, a(n*p - 2) == -<a href="/A005773" title="Number of directed animals of size n (or directed n-ominoes in standard position).">A005773</a>(n) (mod p).</div> <div class=sectline>(3) For prime p >= 3 and k >= 1, a(n + p^k) == a(n) (mod p) for 0 <= n <= (p^k - 3).</div> <div class=sectline>(4) For prime p >= 5 and k >= 2, a(n + p^k) == a(n) (mod p^2) for 0 <= n <= (p^(k-1) - 3). (End)</div> <div class=sectline>The Hankel transform of this sequence with a(0) omitted gives the period-6 sequence [1, 0, -1, -1, 0, 1, ...] which is <a href="/A010892" title="Inverse of 6th cyclotomic polynomial. A period 6 sequence.">A010892</a> with its first term omitted, while the Hankel transform of the current sequence is the all-ones sequence <a href="/A000012" title="The simplest sequence of positive numbers: the all 1's sequence.">A000012</a>, and also it is the unique sequence with this property which is similar to the unique Hankel transform property of the Catalan numbers. - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Apr 17 2022</div> <div class=sectline>The number of terms in which the exponent of any variable x_i is not greater than 2 in the expansion of Product_{j=1..n} Sum_{i=1..j} x_i. E.g.: a(4) = 9: 3*x1^2*x2^2, 4*x1^2*x2*x3, 2*x1^2*x2*x4, x1^2*x3^2, x1^2*x3*x4, 2*x1*x2^2*x3, x1*x2^2*x4, x1*x2*x3^2, x1*x2*x3*x4. - <a href="/wiki/User:Elif_Baser">Elif Baser</a>, Dec 20 2024</div> </div> </div> <div class=section> <div class=sectname>REFERENCES</div> <div class=sectbody> <div class=sectline>E. Barcucci, R. Pinzani, and R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.</div> <div class=sectline>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.</div> <div class=sectline>F. R. Bernhart, Catalan, Motzkin, and Riordan numbers, Discr. Math., 204 (1999) 73-112.</div> <div class=sectline>R. Bojicic and M. D. 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.</div> <div class=sectline>Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pp. 24, 298, 618, 912.</div> <div class=sectline>Alin Bostan, Calcul Formel pour la Combinatoire des Marches, Habilitation à Diriger des Recherches, Laboratoire d’Informatique de Paris Nord, Université Paris 13, December 2017; https://specfun.inria.fr/bostan/HDR.pdf</div> <div class=sectline>A. J. Bu, Automated counting of restricted Motzkin paths, Enumerative Combinatorics and Applications, ECA 1:2 (2021) Article S2R12.</div> <div class=sectline>Naiomi Cameron, JE McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.</div> <div class=sectline>L. Carlitz, Solution of certain recurrences, SIAM J. Appl. Math., 17 (1969), 251-259.</div> <div class=sectline>Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.</div> <div class=sectline>D. E. Davenport, L. W. Shapiro, and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33.</div> <div class=sectline>E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.</div> <div class=sectline>T. Doslic, D. Svrtan, and D. Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 67-82.</div> <div class=sectline>Tomislav Doslic and Darko Veljan, Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182-2212. MR2404544 (2009j:05019).</div> <div class=sectline>S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.</div> <div class=sectline>M. Dziemianczuk, "Enumerations of plane trees with multiple edges and Raney lattice paths." Discrete Mathematics 337 (2014): 9-24.</div> <div class=sectline>Wenjie Fang, A partial order on Motzkin paths, Discrete Math., 343 (2020), #111802.</div> <div class=sectline>I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (5.2.10).</div> <div class=sectline>N. S. S. Gu, N. Y. Li, and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.</div> <div class=sectline>Kris Hatch, Presentation of the Motzkin Monoid, Senior Thesis, Univ. Cal. Santa Barbara, 2012; http://ccs.math.ucsb.edu/senior-thesis/Kris-Hatch.pdf.</div> <div class=sectline>V. Jelinek, Toufik Mansour, and M. Shattuck, On multiple pattern avoiding set partitions, Advances in Applied Mathematics Volume 50, Issue 2, February 2013, pp. 292-326.</div> <div class=sectline>Hana Kim and R. P. Stanley, A refined enumeration of hex trees and related polynomials, http://www-math.mit.edu/~rstan/papers/hextrees.pdf, Preprint 2015.</div> <div class=sectline>S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. See p. 399 Table A.7.</div> <div class=sectline>A. Kuznetsov et al., Trees associated with the Motzkin numbers, J. Combin. Theory, A 76 (1996), 145-147.</div> <div class=sectline>T. Lengyel, On divisibility properties of some differences of Motzkin numbers, Annales Mathematicae et Informaticae, 41 (2013) pp. 121-136.</div> <div class=sectline>W. A. Lorenz, Y. Ponty, and P. Clote, Asymptotics of RNA Shapes, Journal of Computational Biology. 2008, 15(1): 31-63. doi:10.1089/cmb.2006.0153.</div> <div class=sectline>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.</div> <div class=sectline>Toufik Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76.</div> <div class=sectline>Toufik Mansour, Matthias Schork, and Mark Shattuck, Catalan numbers and pattern restricted set partitions. Discrete Math. 312(2012), no. 20, 2979-2991. MR2956089.</div> <div class=sectline>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.</div> <div class=sectline>Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.</div> <div class=sectline>J. Riordan, Enumeration of plane trees by branches and endpoints, J. Combin. Theory, A 23 (1975), 214-222.</div> <div class=sectline>A. Sapounakis et al., Ordered trees and the inorder transversal, Disc. Math., 306 (2006), 1732-1741.</div> <div class=sectline>A. Sapounakis, I. Tasoulas, and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.</div> <div class=sectline>E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.</div> <div class=sectline>L. W. Shapiro et al., The Riordan group, Discrete Applied Math., 34 (1991), 229-239.</div> <div class=sectline>Mark Shattuck, On the zeros of some polynomials with combinatorial coefficients, Annales Mathematicae et Informaticae, 42 (2013) pp. 93-101, http://ami.ektf.hu.</div> <div class=sectline>N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).</div> <div class=sectline>N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).</div> <div class=sectline>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.</div> <div class=sectline>R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.37. Also Problem 7.16(b), y_3(n).</div> <div class=sectline>P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.</div> <div class=sectline>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.</div> <div class=sectline>Chenying Wang, Piotr Miska, and István Mező, "The r-derangement numbers." Discrete Mathematics 340.7 (2017): 1681-1692.</div> <div class=sectline>Ying Wang and Guoce Xin, A Classification of Motzkin Numbers Modulo 8, Electron. J. Combin., 25(1) (2018), #P1.54.</div> <div class=sectline>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.</div> <div class=sectline>Wen-jin Woan, A Recursive Relation for Weighted Motzkin Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.6.</div> <div class=sectline>F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160.</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline>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)</div> <div class=sectline>M. Abrate, S. Barbero, U. Cerruti, and 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.</div> <div class=sectline>M. Aigner, <a href="http://dx.doi.org/10.1006/eujc.1998.0235">Motzkin Numbers</a>, Europ. J. Comb. 19 (1998), 663-675.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>Marcello Artioli, Giuseppe Dattoli, Silvia Licciardi, and Simonetta Pagnutti, <a href="https://arxiv.org/abs/1703.07262">Motzkin Numbers: an Operational Point of View</a>, arXiv:1703.07262 [math.CO], 2017.</div> <div class=sectline>Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, <a href="http://doi.org/10.1007/978-3-319-77313-1_15">Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects</a>, in International Conference on Language and Automata Theory and Applications, S. Klein, C. Martín-Vide, D. Shapira (eds), Springer, Cham, pp 195-206, 2018.</div> <div class=sectline>Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Laboratoire d'Informatique de Paris Nord (LIPN 2019).</div> <div class=sectline>Andrei Asinowski, Cyril Banderier, and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).</div> <div class=sectline>A. Asinowski and 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.</div> <div class=sectline>Axel Bacher, <a href="https://arxiv.org/abs/1802.06030">Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths</a>, arXiv:1802.06030 [cs.DS], 2018.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>Elena Barcucci, Alberto Del Lungo, Elisa Pergola, and 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).</div> <div class=sectline>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.</div> <div class=sectline>Jean-Luc Baril, <a href="https://doi.org/10.37236/665">Classical sequences revisited with permutations avoiding dotted pattern</a>, Electronic Journal of Combinatorics, 18 (2011), #P178.</div> <div class=sectline>Jean-Luc Baril, <a href="https://doi.org/10.46298/dmtcs.2158">Avoiding patterns in irreducible permutations</a>, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016).</div> <div class=sectline>Jean-Luc Baril, David Bevan, and Sergey Kirgizov, <a href="https://arxiv.org/abs/1906.11870">Bijections between directed animals, multisets and Grand-Dyck paths</a>, arXiv:1906.11870 [math.CO], 2019.</div> <div class=sectline>Jean-Luc Baril and Sergey Kirgizov, <a href="http://jl.baril.u-bourgogne.fr/Stirling.pdf">The pure descent statistic on permutations</a>, 2016.</div> <div class=sectline>Jean-Luc Baril and Sergey Kirgizov, <a href="https://doi.org/10.1016/j.disc.2017.06.005">The pure descent statistic on permutations</a>, Discrete Mathematics, 340(10) (2017), 2550-2558.</div> <div class=sectline>Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, <a href="http://jl.baril.u-bourgogne.fr/decreasing.pdf">Dyck paths with a first return decomposition constrained by height</a>, 2017.</div> <div class=sectline>Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, <a href="https://doi.org/10.1016/j.disc.2018.03.002">Dyck paths with a first return decomposition constrained by height</a>, Discrete Mathematics, 341(6) (2018), 1620-1628.</div> <div class=sectline>Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, <a href="https://arxiv.org/abs/1804.01293">Enumeration of Łukasiewicz paths modulo some patterns</a>, arXiv:1804.01293 [math.CO], 2018.</div> <div class=sectline>Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, <a href="http://math.colgate.edu/~integers/t46/t46.Abstract.html">Motzkin paths with a restricted first return decomposition</a>, Integers (2019) Vol. 19, A46.</div> <div class=sectline>Jean-Luc Baril, Sergey Kirgizov, José L. Ramírez, and Diego Villamizar, <a href="https://arxiv.org/abs/2401.06228">The Combinatorics of Motzkin Polyominoes</a>, arXiv:2401.06228 [math.CO], 2024. See pages 1 and 7.</div> <div class=sectline>Jean-Luc Baril, Toufik Mansour, and A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/equival.pdf">Equivalence classes of permutations modulo excedances</a>, 2014.</div> <div class=sectline>Jean-Luc Baril and J.-M. Pallo, <a href="http://jl.baril.u-bourgogne.fr/Motzkin.pdf">Motzkin subposet and Motzkin geodesics in Tamari lattices</a>, 2013.</div> <div class=sectline>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.</div> <div class=sectline>Jean-Luc Baril and A. Petrossian, <a href="http://jl.baril.u-bourgogne.fr/Dyck.pdf">Equivalence classes of Dyck paths modulo some statistics</a>, 2004.</div> <div class=sectline>Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Barnabei/barnabei5.html">Motzkin and Catalan Tunnel Polynomials</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.</div> <div class=sectline>Marilena Barnabei, Flavio Bonetti, and Matteo Silimbani, <a href="https://doi.org/10.1016/j.aam.2010.05.002">Restricted involutions and Motzkin paths</a>, Advances in Applied Mathematics 47 (2011), 102-115.</div> <div class=sectline>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, 8 (2005), #05.4.5.</div> <div class=sectline>Paul 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</div> <div class=sectline>Paul 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.</div> <div class=sectline>Paul Barry, <a href="http://arxiv.org/abs/1205.2565">On sequences with {-1, 0, 1} Hankel transforms</a>, arXiv:1205.2565 [math.CO], 2012.</div> <div class=sectline>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, 15 (2012), #12.8.2.</div> <div class=sectline>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, 15 (2012), #12.8.7.</div> <div class=sectline>Paul Barry, <a href="https://doi.org/10.1016/j.laa.2015.10.032">Riordan arrays, generalized Narayana triangles, and series reversion</a>, Linear Algebra and its Applications, 491 (2016) 343-385.</div> <div class=sectline>Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.</div> <div class=sectline>Paul Barry, <a href="https://arxiv.org/abs/1802.03443">On a transformation of Riordan moment sequences</a>, arXiv:1802.03443 [math.CO], 2018.</div> <div class=sectline>Paul Barry, <a href="https://www.emis.de/journals/JIS/VOL22/Barry3/barry422.html">Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles</a>, J. Int. Seq., 22 (2019), #19.5.8.</div> <div class=sectline>Paul Barry, <a href="https://arxiv.org/abs/2001.08799">Characterizations of the Borel triangle and Borel polynomials</a>, arXiv:2001.08799 [math.CO], 2020.</div> <div class=sectline>A. M. Baxter and L. K. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf">Ascent sequences avoiding pairs of patterns</a>, preprint, 2014.</div> <div class=sectline>A. M. Baxter and L. K. Pudwell, <a href="https://doi.org/10.37236/4479">Ascent sequences avoiding pairs of patterns</a>, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.58.</div> <div class=sectline>Christian Bean, <a href="https://hdl.handle.net/20.500.11815/1184">Finding structure in permutation sets</a>, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.</div> <div class=sectline>Christian Bean, A. Claesson, and H. Ulfarsson, <a href="http://arxiv.org/abs/1512.03226">Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3</a>, arXiv:1512.03226 [math.CO], 2015.</div> <div class=sectline>Jan Bok, <a href="https://arxiv.org/abs/1801.05498">Graph-indexed random walks on special classes of graphs</a>, arXiv:1801.05498 [math.CO], 2018.</div> <div class=sectline>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.</div> <div class=sectline>Alin 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.</div> <div class=sectline>Alin Bostan, <a href="https://specfun.inria.fr/bostan/HDR.pdf">Calcul Formel pour la Combinatoire des Marches [The text is in English]</a>, Habilitation à Diriger des Recherches, Laboratoire d’Informatique de Paris Nord, Université Paris 13, December 2017.</div> <div class=sectline>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.</div> <div class=sectline>Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, <a href="https://arxiv.org/abs/2001.00393">Stieltjes moment sequences for pattern-avoiding permutations</a>, arXiv:2001.00393 [math.CO], 2020.</div> <div class=sectline>Henry Bottomley, <a href="/A001006/a001006.2.gif">Illustration of initial terms</a>.</div> <div class=sectline>Rob Burns, <a href="https://arxiv.org/abs/1703.00826">Structure and asymptotics for Motzkin numbers modulo primes using automata</a>, arXiv:1703.00826 [math.NT], 2017.</div> <div class=sectline>Alexander Burstein and J. Pantone, <a href="http://arxiv.org/abs/1402.3842">Two examples of unbalanced Wilf-equivalence</a>, arXiv:1402.3842 [math.CO], 2014.</div> <div class=sectline>Alexander Burstein and Louis W. Shapiro, <a href="https://arxiv.org/abs/2112.11595">Pseudo-involutions in the Riordan group</a>, arXiv:2112.11595 [math.CO], 2021.</div> <div class=sectline>N. T. Cameron, <a href="https://www.math.hmc.edu/~cameron/dissertation.pdf">Random walks, trees and extensions of Riordan group techniques</a>, Dissertation, Howard University, 2002.</div> <div class=sectline>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, 8 (2005), #05.3.7.</div> <div class=sectline>Giulio Cerbai, Anders Claesson, Luca Ferrari, and Einar Steingrímsson, <a href="https://arxiv.org/abs/2006.05692">Sorting with pattern-avoiding stacks: the 132-machine</a>, arXiv:2006.05692 [math.CO], 2020.</div> <div class=sectline>Gi-Sang Cheon, S.-T. Jin, and L. W. Shapiro, <a href="https://doi.org/10.1016/j.laa.2015.03.015">A combinatorial equivalence relation for formal power series</a>, Linear Algebra and its Applications, Volume 491, 15 February 2016, Pages 123-137.</div> <div class=sectline>J. Cigler, <a href="http://arxiv.org/abs/1109.1449">Some nice Hankel determinants</a>. arXiv:1109.1449 [math.CO], 2011.</div> <div class=sectline>Johann Cigler and Christian Krattenthaler, <a href="https://arxiv.org/abs/2003.01676">Hankel determinants of linear combinations of moments of orthogonal polynomials</a>, arXiv:2003.01676 [math.CO], 2020.</div> <div class=sectline>J. B. Cosgrave, <a href="/A103772/a103772.txt">The Gauss-Factorial Motzkin connection</a> (Maple worksheet, change suffix to .mw).</div> <div class=sectline>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:1310.2449 [cs.DM], 2013.</div> <div class=sectline>J. Cigler, <a href="http://homepage.univie.ac.at/johann.cigler/preprints/hankel.pdf ">Hankel determinants of some polynomial sequences</a>, preprint, 2012.</div> <div class=sectline>Colin Defant, <a href="http://arxiv.org/abs/1904.10451">Motzkin intervals and valid hook configurations</a>, arXiv:1904.10451 [math.CO], 2019.</div> <div class=sectline>Colin Defant, <a href="https://arxiv.org/abs/2004.11367">Troupes, Cumulants, and Stack-Sorting</a>, arXiv:2004.11367 [math.CO], 2020.</div> <div class=sectline>C. Defant and K. Zheng, <a href="https://arxiv.org/abs/2008.12297">Stack-Sorting with Consecutive-Pattern-Avoiding Stacks</a>, arXiv:2008.12297 [math.CO], 2020.</div> <div class=sectline>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.</div> <div class=sectline>R. M. Dickau, <a href="http://mathforum.org/advanced/robertd/delannoy.html">Delannoy and Motzkin Numbers</a>.</div> <div class=sectline>R. M. Dickau, <a href="/A001006/a001006.4.gif">The 9 paths in a 4 X 4 grid</a>.</div> <div class=sectline>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.</div> <div class=sectline>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:1210.6908 [math.CO], 2012.</div> <div class=sectline>I. Dolinka, J. East, A. Evangelou, D. FitzGerald, and N. Ham, <a href="http://arxiv.org/abs/1507.04838">Idempotent Statistics of the Motzkin and Jones Monoids</a>, arXiv:1507.04838 [math.CO], 2015.</div> <div class=sectline>I. Dolinka, J. East, and R. D. Gray, <a href="http://arxiv.org/abs/1512.02279">Motzkin monoids and partial Brauer monoids</a>, arXiv:1512.02279 [math.GR], 2015.</div> <div class=sectline>Robert Donaghey, <a href="https://doi.org/10.1016/0095-8956(77)90003-X">Restricted plane tree representations for four Motzkin-Catalan equations</a>, J. Combin. Theory, Series B, Vol. 22, No. 2 (1977), pp. 114-121.</div> <div class=sectline>Robert Donaghey, <a href="https://doi.org/10.1016/0095-8956(80)90045-3">Automorphisms on Catalan trees and bracketings</a>, Journal of Combinatorial Theory, Series B, Vol. 29, No. 1 (August 1980), pp. 75-90.</div> <div class=sectline>Robert Donaghey and Louis W. Shapiro, <a href="https://doi.org/10.1016/0097-3165(77)90020-6">Motzkin numbers</a>, J. Combin. Theory, Series A, Vol. 23, No. 3 (1977), pp. 291-301.</div> <div class=sectline>Robert W. Donley Jr, <a href="https://arxiv.org/abs/1905.01525">Binomial arrays and generalized Vandermonde identities</a>, arXiv:1905.01525 [math.CO], 2019.</div> <div class=sectline>Ivana Đurđev, Igor Dolinka, and James East, <a href="https://arxiv.org/abs/1910.10286">Sandwich semigroups in diagram categories</a>, arXiv:1910.10286 [math.GR], 2019.</div> <div class=sectline>E. S. Egge, <a href="http://arXiv.org/abs/math.CO/0307050">Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations</a>, arXiv:math/0307050 [math.CO], 2003, sec. 8.</div> <div class=sectline>S. B. Ekhad and 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.</div> <div class=sectline>Gennady Eremin, <a href="https://arxiv.org/abs/2002.08067">Generating function for Naturalized Series: The case of Ordered Motzkin Words</a>, arXiv:2002.08067 [math.CO], 2020.</div> <div class=sectline>Gennady Eremin, <a href="https://arxiv.org/abs/2004.09866">Naturalized bracket row and Motzkin triangle</a>, arXiv:2004.09866 [math.CO], 2020.</div> <div class=sectline>Gennady Eremin, <a href="https://arxiv.org/abs/2108.10676">Walking in the OEIS: From Motzkin numbers to Fibonacci numbers. The "shadows" of Motzkin numbers</a>, arXiv:2108.10676 [math.CO], 2021.</div> <div class=sectline>Jackson Evoniuk, Steven Klee, and Van Magnan, <a href="https://www.emis.de/journals/JIS/VOL21/Klee/klee2.html">Enumerating Minimal Length Lattice Paths</a>, J. Int. Seq., 21 (2018), #18.3.6.</div> <div class=sectline>Luca Ferrari and Emanuele Munarini, <a href="http://arxiv.org/abs/1203.6792">Enumeration of edges in some lattices of paths</a>, 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>.</div> <div class=sectline>P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see pages 68 and 81.</div> <div class=sectline>Rigoberto Flórez, Leandro Junes, and José L. Ramírez, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Florez/florez4.html">Further Results on Paths in an n-Dimensional Cubic Lattice</a>, Journal of Integer Sequences, 21 (2018), #18.1.2.</div> <div class=sectline>Juan B. Gil and Jordan O. Tirrell, <a href="https://arxiv.org/abs/1806.09065">A simple bijection for classical and enhanced k-noncrossing partitions</a>, arXiv:1806.09065 [math.CO], 2018. Also Discrete Mathematics (2019), Article 111705. doi:10.1016/j.disc.2019.111705</div> <div class=sectline>Samuele Giraudo, <a href="https://arxiv.org/abs/1903.00677">Tree series and pattern avoidance in syntax trees</a>, arXiv:1903.00677 [math.CO], 2019.</div> <div class=sectline>Samuele Giraudo, <a href="https://arxiv.org/abs/2204.03586">The combinator M and the Mockingbird lattice</a>, arXiv:2204.03586 [math.CO], 2022.</div> <div class=sectline>Taras Goy and Mark Shattuck, <a href="https://doi.org/10.26493/2590-9770.1645.d36">Determinant identities for the Catalan, Motzkin and Schröder numbers</a>, Art Discrete Appl. Math. Vol. 7 (2024), #P1.09.</div> <div class=sectline>Taras Goy and Mark Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Shattuck/sh36.html">Determinants of some Hessenberg-Toeplitz matrices with Motzkin number entries</a>, J. Integer Seq., 26 (2023), Art. 23.3.4.</div> <div class=sectline>Nils Haug, T. Prellberg, and G. Siudem, <a href="https://arxiv.org/abs/1605.09643">Scaling in area-weighted generalized Motzkin paths</a>, arXiv:1605.09643 [cond-mat.stat-mech], 2016.</div> <div class=sectline>Nickolas Hein and Jia Huang, <a href="https://arxiv.org/abs/1508.01688">Modular Catalan Numbers</a>, arXiv:1508.01688 [math.CO], 2015-2016.</div> <div class=sectline>Nickolas Hein and Jia Huang, <a href="https://arxiv.org/abs/1807.04623">Variations of the Catalan numbers from some nonassociative binary operations</a>, arXiv:1807.04623 [math.CO], 2018.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>Anders Hyllengren, <a href="/A258710/a258710.pdf">Letter to N. J. A. Sloane, Oct 04 1985</a></div> <div class=sectline>Anders Hyllengren, <a href="/A001006/a001006_5.pdf">Four integer sequences</a>, Oct 04 1985. Observes essentially that <a href="/A000984" title="Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2.">A000984</a> and <a href="/A002426" title="Central trinomial coefficients: largest coefficient of (1 + x + x^2)^n.">A002426</a> are inverse binomial transforms of each other, as are <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a> and <a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a>.</div> <div class=sectline>INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=50">Encyclopedia of Combinatorial Structures 50</a></div> <div class=sectline>Manuel Kauers and Doron Zeilberger, <a href="https://arxiv.org/abs/2006.10205">Counting Standard Young Tableaux With Restricted Runs</a>, arXiv:2006.10205 [math.CO], 2020.</div> <div class=sectline>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.</div> <div class=sectline>Nadav Kohen, <a href="https://arxiv.org/abs/2411.03681">Density and Symmetry in the Generalized Motzkin Numbers mod p</a>, arXiv:2411.03681 [math.CO], 2024.</div> <div class=sectline>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, 18 (2015), #15.4.6.</div> <div class=sectline>Marie-Louise Lackner and M. Wallner, <a href="http://dmg.tuwien.ac.at/mwallner/files/lpintro.pdf">An invitation to analytic combinatorics and lattice path counting</a>, preprint, 2015.</div> <div class=sectline>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.</div> <div class=sectline>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), 31-63.</div> <div class=sectline>K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, <a href="http://arxiv.org/abs/1510.01952">Equivalence classes of ballot paths modulo strings of length 2 and 3</a>, arXiv:1510.01952 [math.CO], 2015.</div> <div class=sectline>Toufik Mansour, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Mansour/mansour86.html">Statistics on Dyck Paths</a>, Journal of Integer Sequences, 9 (2006), #06.1.5.</div> <div class=sectline>Toufik 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.</div> <div class=sectline>Toufik Mansour and Mark Shattuck, <a href="https://math.colgate.edu/~integers/z5/z5.pdf">Enumeration of Catalan and smooth words according to capacity</a>, Integers (2025) Vol. 25, Art. No. A5. See p. 22.</div> <div class=sectline>V. Mazorchuk and B. Steinberg, <a href="http://arxiv.org/abs/1105.5313">Double Catalan monoids</a>, arXiv:1105.5313 [math.GR], 2011.</div> <div class=sectline>Peter McCalla and Asamoah Nkwanta, <a href="https://arxiv.org/abs/1901.07092">Catalan and Motzkin Integral Representations</a>, arXiv:1901.07092 [math.NT], 2019.</div> <div class=sectline>Cam McLeman and Erin McNicholas, <a href="http://arxiv.org/abs/1108.3588">Graph Invertibility</a>, arXiv:1108.3588 [math.CO], 2011.</div> <div class=sectline>Zhousheng Mei and Suijie Wang, <a href="https://arxiv.org/abs/1804.06265">Pattern Avoidance of Generalized Permutations</a>, arXiv:1804.06265 [math.CO], 2018.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>Heinrich Niederhausen, <a href="http://arxiv.org/abs/1105.3713">Inverses of Motzkin and Schroeder Paths</a>, arXiv:1105.3713 [math.CO], 2011.</div> <div class=sectline>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.</div> <div class=sectline>William P. Orrick, <a href="/A001006/a001006.txt">Remark on parentheses patterns of fully parenthesized expressions</a>, 2024.</div> <div class=sectline>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.</div> <div class=sectline>Ran Pan, Dun Qiu, and Jeffrey Remmel, <a href="https://arxiv.org/abs/1809.01384">Counting Consecutive Pattern Matches in S_n(132) and S_n(123)</a>, arXiv:1809.01384 [math.CO], 2018.</div> <div class=sectline>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, 21(4) (2014), #P4.7.</div> <div class=sectline>Simon Plouffe, <a href="http://plouffe.fr/OEIS/b001006.txt">The first 4431 terms</a>.</div> <div class=sectline>Helmut Prodinger, <a href="https://arxiv.org/abs/2003.01918">Deutsch paths and their enumeration</a>, arXiv:2003.01918 [math.CO], 2020.</div> <div class=sectline>Helmut Prodinger, <a href="https://arxiv.org/abs/2501.13645">Cornerless, peakless, valleyless Motzkin paths (regular and skew) and applications to bargraphs</a>, arXiv:2501.13645 [math.CO], 2025. See p. 8.</div> <div class=sectline>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.</div> <div class=sectline>L. Pudwell, A. Baxter, <a href="http://faculty.valpo.edu/lpudwell/slides/pp2014_pudwell.pdf">Ascent sequences avoiding pairs of patterns</a>, 2014</div> <div class=sectline>L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf">Pattern-avoiding ascent sequences</a>, Slides from a talk, 2015</div> <div class=sectline>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.</div> <div class=sectline>J. L. Ramírez and 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.</div> <div class=sectline>Alon Regev, Amitai Regev, and Doron Zeilberger, <a href="http://arxiv.org/abs/1507.03499">Identities in character tables of S_n</a>, arXiv:1507.03499 [math.CO], 2015.</div> <div class=sectline>John Riordan, <a href="/A001006/a001006_1.pdf">Letter to N. J. A. Sloane</a>, 1974.</div> <div class=sectline>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., 6 (2003).</div> <div class=sectline>E. Rowland and R. Yassawi, <a href="http://arxiv.org/abs/1310.8635">Automatic congruences for diagonals of rational functions</a>, arXiv:1310.8635 [math.NT], 2013.</div> <div class=sectline>E. Rowland and 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:1311.4776 [math.CO], 2013.</div> <div class=sectline>E. Royer, <a href="https://royer.perso.math.cnrs.fr/publication/mr-2013928/mr-2013928.pdf">Interprétation combinatoire des moments négatifs des valeurs de fonctions L au bord de la bande critique</a>, Ann. Sci. Ecole Norm. Sup. (4) 36 (2003), no. 4, 601-620.</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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, 7 (2004), #04.2.5.</div> <div class=sectline>E. Schröder, <a href="/A000108/a000108_9.pdf">Vier combinatorische Probleme</a>, Z. f. Math. Phys., 15 (1870), 361-376. [Annotated scanned copy]</div> <div class=sectline>Paolo Serafini, <a href="https://doi.org/10.1155/2018/3791075">An Iterative Scheme to Compute Size Probabilities in Random Graphs and Branching Processes</a>, Scientific Programming (2018), Article ID 3791075.</div> <div class=sectline>N. J. A. Sloane, <a href="/A001006/a001006.gif">Illustration of initial terms</a>.</div> <div class=sectline>N. J. A. Sloane, <a href="/classic.html#MOTZKIN">Classic Sequences</a>.</div> <div class=sectline>N. J. A. Sloane, <a href="/A001006/a001006_Vg.jpg">An Application of the OEIS</a> (Vugraph from a talk about the OEIS).</div> <div class=sectline>N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, pp. 1, 3.</div> <div class=sectline>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]</div> <div class=sectline>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, 3 (2000), #00.1.</div> <div class=sectline>Hua Sun and 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</div> <div class=sectline>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:1305.2015 [math.CO], 2013.</div> <div class=sectline>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.</div> <div class=sectline>L. Takacs, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/18_1_1.pdf">Enumeration of rooted trees and forests</a>, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).</div> <div class=sectline>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.</div> <div class=sectline>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.</div> <div class=sectline>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:1507.06944 [cs.LO], 2015.</div> <div class=sectline>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.</div> <div class=sectline>Jonas Wahl, <a href="https://arxiv.org/abs/2006.07312">Traces On Diagram Algebras I: Free Partition Quantum Groups, Random Lattice Paths And Random Walks On Trees</a>, arXiv:2006.07312 [math.PR], 2020.</div> <div class=sectline>Chen Wang and Zhi-Wei Sun, <a href="https://arxiv.org/abs/1910.06850">Congruences involving central trinomial coefficients</a>, arXiv:1910.06850 [math.NT], 2019.</div> <div class=sectline>Y. Wang and Z.-H. Zhang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Wang/wang21.html">Combinatorics of Generalized Motzkin Numbers</a>, J. Int. Seq. 18 (2015), #15.2.4.</div> <div class=sectline>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.</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MotzkinNumber.html">Motzkin Number</a>.</div> <div class=sectline>Wikipedia, <a href="https://www.wikipedia.org/wiki/Motzkin_number">Motzkin number</a>.</div> <div class=sectline>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.</div> <div class=sectline>J. Y. X. Yang, M. X. X. Zhong, and 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:1406.2583 [math.CO], 2014.</div> <div class=sectline>Huan Xiong, <a href="http://arxiv.org/abs/1409.7038">The number of simultaneous core partitions</a>, arXiv:1409.7038 [math.CO], 2014.</div> <div class=sectline>Yan X. Zhang, <a href="http://arxiv.org/abs/1508.00318">Four Variations on Graded Posets</a>, arXiv:1508.00318 [math.CO], 2015.</div> <div class=sectline>Yan Zhuang, <a href="https://arxiv.org/abs/1508.02793">A generalized Goulden-Jackson cluster method and lattice path enumeration</a>, arXiv:1508.02793 [math.CO], 2015-2018; Discrete Mathematics 341.2 (2018): 358-379.</div> <div class=sectline><a href="/index/Cor#core">Index entries for "core" sequences</a></div> </div> </div> <div class=section> <div class=sectname>FORMULA</div> <div class=sectbody> <div class=sectline>G.f.: A(x) = ( 1 - x - (1-2*x-3*x^2)^(1/2) ) / (2*x^2).</div> <div class=sectline>G.f. A(x) satisfies A(x) = 1 + x*A(x) + x^2*A(x)^2.</div> <div class=sectline>G.f.: F(x)/x where F(x) is the reversion of x/(1+x+x^2). - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Oct 23 2012</div> <div class=sectline>a(n) = (-1/2) Sum_{i+j = n+2, i >= 0, j >= 0} (-3)^i*C(1/2, i)*C(1/2, j).</div> <div class=sectline>a(n) = (3/2)^(n+2) * Sum_{k >= 1} 3^(-k) * Catalan(k-1) * binomial(k, n+2-k). [Doslic et al.]</div> <div class=sectline>a(n) ~ 3^(n+1)*sqrt(3)*(1 + 1/(16*n))/((2*n+3)*sqrt((n+2)*Pi)). [Barcucci, Pinzani and Sprugnoli]</div> <div class=sectline>Limit_{n->infinity} a(n)/a(n-1) = 3. [Aigner]</div> <div class=sectline>a(n+2) - a(n+1) = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0). [Bernhart]</div> <div class=sectline>a(n) = (1/(n+1)) * Sum_{i} (n+1)!/(i!*(i+1)!*(n-2*i)!). [Bernhart]</div> <div class=sectline>From <a href="/wiki/User:Len_Smiley">Len Smiley</a>: (Start)</div> <div class=sectline>a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*<a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>(k+1), inv. Binomial Transform of <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>.</div> <div class=sectline>a(n) = (1/(n+1))*Sum_{k=0..ceiling((n+1)/2)} binomial(n+1, k)*binomial(n+1-k, k-1);</div> <div class=sectline>D-finite with recurrence: (n+2)*a(n) = (2*n+1)*a(n-1) + (3*n-3)*a(n-2). (End)</div> <div class=sectline>a(n) = Sum_{k=0..n} C(n, 2k)*<a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>(k). - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Jul 18 2003</div> <div class=sectline>E.g.f.: exp(x)*BesselI(1, 2*x)/x. - <a href="/wiki/User:Vladeta_Jovovic">Vladeta Jovovic</a>, Aug 20 2003</div> <div class=sectline>a(n) = <a href="/A005043" title="Riordan numbers: a(n) = (n-1)*(2*a(n-1) + 3*a(n-2))/(n+1).">A005043</a>(n) + <a href="/A005043" title="Riordan numbers: a(n) = (n-1)*(2*a(n-1) + 3*a(n-2))/(n+1).">A005043</a>(n+1).</div> <div class=sectline>The Hankel transform of this sequence gives <a href="/A000012" title="The simplest sequence of positive numbers: the all 1's sequence.">A000012</a> = [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. - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Feb 23 2004</div> <div class=sectline>a(m+n) = Sum_{k>=0} <a href="/A064189" title="Triangle T(n,k), 0 <= k <= n, read by rows, defined by: T(0,0)=1, T(n,k)=0 if n < k, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,...">A064189</a>(m, k)*<a href="/A064189" title="Triangle T(n,k), 0 <= k <= n, read by rows, defined by: T(0,0)=1, T(n,k)=0 if n < k, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,...">A064189</a>(n, k). - <a href="/wiki/User:Philippe_Deléham">Philippe Deléham</a>, Mar 05 2004</div> <div class=sectline>a(n) = (1/(n+1))*Sum_{j=0..floor(n/3)} (-1)^j*binomial(n+1, j)*binomial(2*n-3*j, n). - <a href="/wiki/User:Emeric_Deutsch">Emeric Deutsch</a>, Mar 13 2004</div> <div class=sectline>a(n) = <a href="/A086615" title="Antidiagonal sums of triangle A086614.">A086615</a>(n) - <a href="/A086615" title="Antidiagonal sums of triangle A086614.">A086615</a>(n-1) (n >= 1). - <a href="/wiki/User:Emeric_Deutsch">Emeric Deutsch</a>, Jul 12 2004</div> <div class=sectline>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.]. - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Feb 22 2005</div> <div class=sectline>G.f.: c(x^2/(1-x)^2)/(1-x), c(x) the g.f. of <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>. - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, May 31 2006</div> <div class=sectline>Asymptotic formula: a(n) ~ sqrt(3/4/Pi)*3^(n+1)/n^(3/2). - <a href="/wiki/User:Benoit_Cloitre">Benoit Cloitre</a>, Jan 25 2007</div> <div class=sectline>a(n) = <a href="/A007971" title="INVERTi transform of central trinomial coefficients (A002426).">A007971</a>(n+2)/2. - <a href="/wiki/User:Zerinvary_Lajos">Zerinvary Lajos</a>, Feb 28 2007</div> <div class=sectline>a(n) = (1/(2*Pi))*Integral_{x=-1..3} x^n*sqrt((3-x)*(1+x)) is the moment representation. - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Sep 10 2007</div> <div class=sectline>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 <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>. The present sequence is Phi([0,1,1]), see the 6th formula. - <a href="/wiki/User:Gary_W._Adamson">Gary W. Adamson</a>, Oct 27 2008</div> <div class=sectline>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). - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Dec 06 2008</div> <div class=sectline>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). - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Feb 08 2009</div> <div class=sectline>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)). - <a href="/wiki/User:Mark_van_Hoeij">Mark van Hoeij</a>, Nov 12 2009</div> <div class=sectline>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). - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Mar 02 2010</div> <div class=sectline>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). - <a href="/wiki/User:Paul_Barry">Paul Barry</a>, Jan 26 2011 [Adds apparently a third '1' in front. - <a href="/wiki/User:R._J._Mathar">R. J. Mathar</a>, Jan 29 2011]</div> <div class=sectline>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 (<a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>). - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Mar 18 2011</div> <div class=sectline>a(n) = (2/Pi)*Integral_{x=-1..1} (1+2*x)^n*sqrt(1-x^2). - <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, Sep 11 2011</div> <div class=sectline>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). - <a href="/wiki/User:Sergei_N._Gladkovskii">Sergei N. Gladkovskii</a>, Dec 01 2011</div> <div class=sectline>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). - <a href="/wiki/User:Sergei_N._Gladkovskii">Sergei N. Gladkovskii</a>, Dec 11 2011</div> <div class=sectline>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. - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Mar 23 2012</div> <div class=sectline>a(n) = (-1)^n*hypergeometric([-n,3/2],[3],4). - <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, Aug 15 2012</div> <div class=sectline>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. - <a href="/wiki/User:Karol_A._Penson">Karol A. Penson</a>, Jun 24 2013</div> <div class=sectline>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). - <a href="/wiki/User:Sergei_N._Gladkovskii">Sergei N. Gladkovskii</a>, May 14 2013</div> <div class=sectline>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. - <a href="/wiki/User:Doron_Zeilberger">Doron Zeilberger</a>, Mar 12, 2015</div> <div class=sectline>G.f. A(x) with offset 1 satisfies: A(x)^2 = A( x^2/(1-2*x) ). - <a href="/wiki/User:Paul_D._Hanna">Paul D. Hanna</a>, Nov 08 2015</div> <div class=sectline>a(n) = GegenbauerPoly(n,-n-1,-1/2)/(n+1). - <a href="/wiki/User:Emanuele_Munarini">Emanuele Munarini</a>, Oct 20 2016</div> <div class=sectline>a(n) = a(n-1) + <a href="/A002026" title="Generalized ballot numbers (first differences of Motzkin numbers).">A002026</a>(n-1). Number of Motzkin paths that start with an F step plus number of Motzkin paths that start with an U step. - <a href="/wiki/User:R._J._Mathar">R. J. Mathar</a>, Jul 25 2017</div> <div class=sectline>G.f. A(x) satisfies A(x)*A(-x) = F(x^2), where F(x) is the g.f. of <a href="/A168592" title="G.f.: exp( Sum_{n>=1} A082758(n)*x^n/n ), where A082758(n) = sum of the squares of the trinomial coefficients in row n of tr...">A168592</a>. - <a href="/wiki/User:Alexander_Burstein">Alexander Burstein</a>, Oct 04 2017</div> <div class=sectline>G.f.: A(x) = exp(int((E(x)-1)/x dx)), where E(x) is the g.f. of <a href="/A002426" title="Central trinomial coefficients: largest coefficient of (1 + x + x^2)^n.">A002426</a>. Equivalently, E(x) = 1 + x*A'(x)/A(x). - <a href="/wiki/User:Alexander_Burstein">Alexander Burstein</a>, Oct 05 2017</div> <div class=sectline>G.f. A(x) satisfies: A(x) = Sum_{j>=0} x^j * Sum_{k=0..j} binomial(j,k)*x^k*A(x)^k. - <a href="/wiki/User:Ilya_Gutkovskiy">Ilya Gutkovskiy</a>, Apr 11 2019</div> <div class=sectline>From <a href="/wiki/User:Gennady_Eremin">Gennady Eremin</a>, May 08 2021: (Start)</div> <div class=sectline>G.f.: 2/(1 - x + sqrt(1-2*x-3*x^2)).</div> <div class=sectline>a(n) = <a href="/A107587" title="Number of Motzkin n-paths with an even number of up steps.">A107587</a>(n) + <a href="/A343386" title="Number of odd Motzkin n-paths, i.e., Motzkin n-paths with an odd number of up steps.">A343386</a>(n) = 2*<a href="/A107587" title="Number of Motzkin n-paths with an even number of up steps.">A107587</a>(n) - <a href="/A343773" title="Excess of the number of even Motzkin n-paths (A107587) over the odd ones (A343386).">A343773</a>(n) = 2*<a href="/A343386" title="Number of odd Motzkin n-paths, i.e., Motzkin n-paths with an odd number of up steps.">A343386</a>(n) + <a href="/A343773" title="Excess of the number of even Motzkin n-paths (A107587) over the odd ones (A343386).">A343773</a>(n). (End)</div> <div class=sectline>Revert transform of <a href="/A049347" title="Period 3: repeat [1, -1, 0].">A049347</a> (after Michael Somos). - <a href="/wiki/User:Gennady_Eremin">Gennady Eremin</a>, Jun 11 2021</div> <div class=sectline>Sum_{n>=0} 1/a(n) = 2.941237337631025604300320152921013604885956025483079699366681494505960039781389<wbr>... - <a href="/wiki/User:Vaclav_Kotesovec">Vaclav Kotesovec</a>, Jun 17 2021</div> <div class=sectline>Let a(-1) = (1 - sqrt(-3))/2 and a(n) = a(-3-n)*(-3)^(n+3/2) for all n in Z. Then a(n) satisfies my previous formula relation from Mar 23 2012 now for all n in Z. - <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Apr 17 2022</div> <div class=sectline>Let b(n) = 1 for n <= 1, otherwise b(n) = Sum_{k=2..n} b(k-1) * b(n-k), then a(n) = b(n+1) (conjecture). - <a href="/wiki/User:Joerg_Arndt">Joerg Arndt</a>, Jan 16 2023</div> <div class=sectline>From <a href="/wiki/User:Peter_Bala">Peter Bala</a>, Feb 03 2024: (Start)</div> <div class=sectline>G.f.: A(x) = 1/(1 + x)*c(x/(1 + x))^2 = 1 + x/(1 + x)*c(x/(1 + x))^3, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>.</div> <div class=sectline>A(x) = 1/(1 - 3*x)*c(-x/(1 -3*x))^2.</div> <div class=sectline>a(n+1) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n, k)*<a href="/A000245" title="a(n) = 3*(2*n)!/((n+2)!*(n-1)!).">A000245</a>(k+1).</div> <div class=sectline>a(n) = 3^n * Sum_{k = 0..n} (-3)^(-k)*binomial(n, k)*Catalan(k+1).</div> <div class=sectline>a(n) = 3^n * hypergeom([3/2, -n], [3], 4/3). (End)</div> <div class=sectline>G.f. A(x) satisfies A(x) = exp( x*A(x) + Integral x*A(x)/(1 - x^2*A(x)) dx ). - <a href="/wiki/User:Paul_D._Hanna">Paul D. Hanna</a>, Mar 04 2024</div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>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 + ...</div> <div class=sectline>.</div> <div class=sectline>The 21 Motzkin-paths of length 5: UUDDF, UUDFD, UUFDD, UDUDF, UDUFD, UDFUD, UDFFF, UFUDD, UFDUD, UFDFF, UFFDF, UFFFD, FUUDD, FUDUD, FUDFF, FUFDF, FUFFD, FFUDF, FFUFD, FFFUD, FFFFF.</div> </div> </div> <div class=section> <div class=sectname>MAPLE</div> <div class=sectbody> <div class=sectline># Three different Maple scripts for this sequence:</div> <div class=sectline><a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a> := proc(n)</div> <div class=sectline> add(binomial(n, 2*k)*<a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>(k), k=0..floor(n/2)) ;</div> <div class=sectline>end proc:</div> <div class=sectline><a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a> := 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); end if; end proc:</div> <div class=sectline># n -> [a(0), a(1), .., a(n)]</div> <div class=sectline><a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a>_list := proc(n) local w, m, j, i; w := proc(i, j, n) option remember;</div> <div class=sectline>if min(i, j, n) < 0 or max(i, j) > n then 0</div> <div class=sectline>elif n = 0 then if i = 0 and j = 0 then 1 else 0 fi else</div> <div class=sectline>w(i, j + 1, n - 1) + w(i - 1, j, n - 1) + w(i + 1, j - 1, n - 1) fi end:</div> <div class=sectline>[seq( add( add( w(i, j, m), i = 0..m), j = 0..m), m = 0..n)] end:</div> <div class=sectline><a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a>_list(29); # <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, May 21 2011</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>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]</div> <div class=sectline>(* Second program: *)</div> <div class=sectline>CoefficientList[Series[(1 - x - (1 - 2x - 3x^2)^(1/2))/(2x^2), {x, 0, 29}], x] (* <a href="/wiki/User:Jean-François_Alcover">Jean-François Alcover</a>, Nov 29 2011 *)</div> <div class=sectline>Table[Hypergeometric2F1[(1-n)/2, -n/2, 2, 4], {n, 0, 29}] (* <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, May 15 2016 *)</div> <div class=sectline>Table[GegenbauerC[n, -n-1, -1/2]/(n+1), {n, 0, 100}] (* <a href="/wiki/User:Emanuele_Munarini">Emanuele Munarini</a>, Oct 20 2016 *)</div> <div class=sectline>MotzkinNumber = DifferenceRoot[Function[{y, n}, {(-3n-3)*y[n] + (-2n-5)*y[n+1] + (n+4)*y[n+2] == 0, y[0] == 1, y[1] == 1}]];</div> <div class=sectline>Table[MotzkinNumber[n], {n, 0, 29}] (* <a href="/wiki/User:Jean-François_Alcover">Jean-François Alcover</a>, Oct 27 2021 *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(PARI) {a(n) = polcoeff( ( 1 - x - sqrt((1 - x)^2 - 4 * x^2 + x^3 * O(x^n))) / (2 * x^2), n)}; /* <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Sep 25 2003 */</div> <div class=sectline>(PARI) {a(n) = if( n<0, 0, n++; polcoeff( serreverse( x / (1 + x + x^2) + x * O(x^n)), n))}; /* <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Sep 25 2003 */</div> <div class=sectline>(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp(x + x * O(x^n)) * besseli(1, 2 * x + x * O(x^n)), n))}; /* <a href="/wiki/User:Michael_Somos">Michael Somos</a>, Sep 25 2003 */</div> <div class=sectline>(Maxima) a[0]:1$</div> <div class=sectline>a[1]:1$</div> <div class=sectline>a[n]:=((2*n+1)*a[n-1]+(3*n-3)*a[n-2])/(n+2)$</div> <div class=sectline>makelist(a[n], n, 0, 12); /* <a href="/wiki/User:Emanuele_Munarini">Emanuele Munarini</a>, Mar 02 2011 */</div> <div class=sectline>(Maxima)</div> <div class=sectline>M(n) := coeff(expand((1+x+x^2)^(n+1)), x^n)/(n+1);</div> <div class=sectline>makelist(M(n), n, 0, 60); /* <a href="/wiki/User:Emanuele_Munarini">Emanuele Munarini</a>, Apr 04 2012 */</div> <div class=sectline>(Maxima) makelist(ultraspherical(n, -n-1, -1/2)/(n+1), n, 0, 12); /* <a href="/wiki/User:Emanuele_Munarini">Emanuele Munarini</a>, Oct 20 2016 */</div> <div class=sectline>(Haskell)</div> <div class=sectline>a001006 n = a001006_list !! n</div> <div class=sectline>a001006_list = zipWith (+) a005043_list $ tail a005043_list</div> <div class=sectline>-- <a href="/wiki/User:Reinhard_Zumkeller">Reinhard Zumkeller</a>, Jan 31 2012</div> <div class=sectline>(Python)</div> <div class=sectline>from gmpy2 import divexact</div> <div class=sectline><a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a> = [1, 1]</div> <div class=sectline>for n in range(2, 10**3):</div> <div class=sectline> <a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a>.append(divexact(<a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a>[-1]*(2*n+1)+(3*n-3)*<a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a>[-2], n+2))</div> <div class=sectline># <a href="/wiki/User:Chai_Wah_Wu">Chai Wah Wu</a>, Sep 01 2014</div> <div class=sectline>(Python)</div> <div class=sectline>def mot():</div> <div class=sectline> a, b, n = 0, 1, 1</div> <div class=sectline> while True:</div> <div class=sectline> yield b//n</div> <div class=sectline> n += 1</div> <div class=sectline> a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)//((n+1)*(n-1))</div> <div class=sectline><a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a> = mot()</div> <div class=sectline>print([next(<a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a>) for n in range(30)]) # <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, May 16 2016</div> <div class=sectline>(Python)</div> <div class=sectline># A simple generator of Motzkin-paths (see the first comment of <a href="/wiki/User:David_Callan">David Callan</a>).</div> <div class=sectline>C = str.count</div> <div class=sectline>def aGen(n: int):</div> <div class=sectline> a = [""]</div> <div class=sectline> for w in a:</div> <div class=sectline> if len(w) == n:</div> <div class=sectline> if C(w, "U") == C(w, "D"): yield w</div> <div class=sectline> else:</div> <div class=sectline> for j in "UDF":</div> <div class=sectline> u = w + j</div> <div class=sectline> if C(u, "U") >= C(u, "D"): a += [u]</div> <div class=sectline> return a</div> <div class=sectline>for n in range(6):</div> <div class=sectline> MP = [w for w in aGen(n)];</div> <div class=sectline> print(len(MP), ":", MP) # <a href="/wiki/User:Peter_Luschny">Peter Luschny</a>, Dec 03 2024</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Cf. <a href="/A026300" title="Motzkin triangle, T, read by rows; T(0,0) = T(1,0) = T(1,1) = 1; for n >= 2, T(n,0) = 1, T(n,k) = T(n-1,k-2) + T(n-1,k-1) + ...">A026300</a>, <a href="/A005717" title="Construct triangle in which n-th row is obtained by expanding (1 + x + x^2)^n and take the next-to-central column.">A005717</a>, <a href="/A020474" title="A Motzkin triangle: a(n,k), n >= 2, 2 <= k <= n, = number of complete, strictly subdiagonal staircase functions.">A020474</a>, <a href="/A001850" title="Central Delannoy numbers: a(n) = Sum_{k=0..n} C(n,k)*C(n+k,k).">A001850</a>, <a href="/A004148" title="Generalized Catalan numbers: a(n+1) = a(n) + Sum_{k=1..n-1} a(k)*a(n-1-k).">A004148</a>. First column of <a href="/A064191" title="Triangle T(n,k) (n >= 0, 0 <= k <= n) generalizing Motzkin numbers.">A064191</a>, <a href="/A064189" title="Triangle T(n,k), 0 <= k <= n, read by rows, defined by: T(0,0)=1, T(n,k)=0 if n < k, T(n,k) = T(n-1,k-1) + T(n-1,k) + T(n-1,...">A064189</a>, <a href="/A000108" title="Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).">A000108</a>, <a href="/A088615" title="Primes arising in A088614.">A088615</a>, <a href="/A007971" title="INVERTi transform of central trinomial coefficients (A002426).">A007971</a>, <a href="/A001405" title="a(n) = binomial(n, floor(n/2)).">A001405</a>, <a href="/A005817" title="a(n) = C(floor(n/2 + 1/2))*C(floor(n/2 + 1)) where C(i) = Catalan numbers A000108.">A005817</a>, <a href="/A049401" title="Number of Young tableaux of height <= 5.">A049401</a>, <a href="/A007579" title="Number of Young tableaux of height <= 6.">A007579</a>, <a href="/A007578" title="Number of Young tableaux of height <= 7.">A007578</a>, <a href="/A097862" title="Triangle read by rows: T(n,k) is the number of Motzkin paths of length n and height k (n>=0, k>=0).">A097862</a>, <a href="/A005773" title="Number of directed animals of size n (or directed n-ominoes in standard position).">A005773</a>, <a href="/A178515" title="Triangle read by rows: T(n,k) is the number of involutions of {1,2,...,n} having genus k (see first comment for definition o...">A178515</a>, <a href="/A217275" title="Expansion of 2/(1-x+sqrt(1-2*x-27*x^2)).">A217275</a>. First row of <a href="/A064645" title="Table where the entry (n,k) (n >= 0, k >= 0) gives number of Motzkin paths of the length n with the minimum peak width of k.">A064645</a>.</div> <div class=sectline>Bisections: <a href="/A026945" title="A bisection of the Motzkin numbers A001006.">A026945</a>, <a href="/A099250" title="Bisection of Motzkin numbers A001006.">A099250</a>.</div> <div class=sectline>Sequences related to chords in a circle: <a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a>, <a href="/A054726" title="Number of graphs with n nodes on a circle without crossing edges.">A054726</a>, <a href="/A006533" title="Place n equally-spaced points around a circle and join every pair of points by a chord; this divides the circle into a(n) re...">A006533</a>, <a href="/A006561" title="Number of intersections of diagonals in the interior of a regular n-gon.">A006561</a>, <a href="/A006600" title="Total number of triangles visible in regular n-gon with all diagonals drawn.">A006600</a>, <a href="/A007569" title="Number of nodes in regular n-gon with all diagonals drawn.">A007569</a>, <a href="/A007678" title="Number of regions in regular n-gon with all diagonals drawn.">A007678</a>. See also entries for chord diagrams in Index file.</div> <div class=sectline>a(n) = <a href="/A005043" title="Riordan numbers: a(n) = (n-1)*(2*a(n-1) + 3*a(n-2))/(n+1).">A005043</a>(n)+<a href="/A005043" title="Riordan numbers: a(n) = (n-1)*(2*a(n-1) + 3*a(n-2))/(n+1).">A005043</a>(n+1).</div> <div class=sectline><a href="/A086246" title="Expansion of (1 + x - sqrt(1 - 2*x - 3*x^2)) / 2 in powers of x.">A086246</a> is another version, although this is the main entry. Column k=3 of <a href="/A182172" title="Number A(n,k) of standard Young tableaux of n cells and height <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.">A182172</a>.</div> <div class=sectline>Motzkin numbers <a href="/A001006" title="Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.">A001006</a> read mod 2,3,4,5,6,7,8,11: <a href="/A039963" title="The period-doubling sequence A035263 repeated.">A039963</a>, <a href="/A039964" title="Motzkin numbers A001006 read mod 3.">A039964</a>, <a href="/A299919" title="Motzkin numbers (A001006) mod 4.">A299919</a>, <a href="/A258712" title="Motzkin numbers A001006 read mod 5.">A258712</a>, <a href="/A299920" title="Motzkin numbers (A001006) mod 6.">A299920</a>, <a href="/A258711" title="Motzkin numbers A001006 read mod 7.">A258711</a>, <a href="/A299918" title="Motzkin numbers (A001006) mod 8.">A299918</a>, <a href="/A258710" title="Motzkin numbers A001006 read mod 11.">A258710</a>.</div> <div class=sectline>Cf. <a href="/A004148" title="Generalized Catalan numbers: a(n+1) = a(n) + Sum_{k=1..n-1} a(k)*a(n-1-k).">A004148</a>, <a href="/A004149" title="Generalized Catalan numbers: a(n+1) = a(n) + Sum_{k=2..n-1} a(k)*a(n-1-k).">A004149</a>, <a href="/A023421" title="Generalized Catalan Numbers x^2*A(x)^2 -(1-x+x^2+x^3+x^4)*A(x) + 1 =0.">A023421</a>, <a href="/A023422" title="Generalized Catalan Numbers x^2*A(x)^2 -(1-x+x^2+x^3+x^4+x^5)*A(x) + 1 =0.">A023422</a>, <a href="/A023423" title="Generalized Catalan Numbers x^2*A(x)^2 -(1-x+x^2+x^3+x^4+x^5+x^6)*A(x) + 1 =0.">A023423</a>, <a href="/A290277" title="Inverse Euler Transform of the Motzkin Numbers.">A290277</a> (inv. Euler Transf.).</div> <div class=sectline>Sequence in context: <a href="/A166587" title="A signed variant of the Motzkin numbers.">A166587</a> <a href="/A292440" title="Expansion of (1 - x + sqrt(1 - 2*x - 3*x^2))/2 in powers of x.">A292440</a> <a href="/A168049" title="Expansion of (3 -x -sqrt(1-2*x-3*x^2))/2.">A168049</a> * <a href="/A086246" title="Expansion of (1 + x - sqrt(1 - 2*x - 3*x^2)) / 2 in powers of x.">A086246</a> <a href="/A247100" title="The number of ways to write an n-bit binary string and then define each run of ones as an element in an equivalence relation.">A247100</a> <a href="/A230556" title="Number of involutions avoiding the pattern 4231.">A230556</a></div> <div class=sectline>Adjacent sequences: <a href="/A001003" title="Schroeder's second problem (generalized parentheses); also called super-Catalan numbers or little Schroeder numbers.">A001003</a> <a href="/A001004" title="Number of nonequivalent dissections of an (n+2)-gon by nonintersecting diagonals up to rotation and reflection.">A001004</a> <a href="/A001005" title="Number of ways of partitioning n points on a circle into subsets only of sizes 2 and 3.">A001005</a> * <a href="/A001007" title="a(n) = ( Sum C(p,i); i=1,...,floor(2p/3) ) / p^2, where p = prime(n).">A001007</a> <a href="/A001008" title="a(n) = numerator of harmonic number H(n) = Sum_{i=1..n} 1/i.">A001008</a> <a href="/A001009" title="Triangle giving number L(n,k) of normalized k X n Latin rectangles.">A001009</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="a sequence of nonnegative numbers">nonn</span>,<span title="an important sequence">core</span>,<span title="it is very easy to produce terms of sequence">easy</span>,<span title="an exceptionally nice sequence">nice</span>,<span title="edited within the last two weeks">changed</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a></div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified February 17 13:01 EST 2025. Contains 380972 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>

CINXE.COM

A001006 - OEIS