Search: id:A001006 Results 1-1 of 1 results found. %I A001006 M1184 N0456 %S A001006 1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113634,310572,853467, %T A001006 2356779,6536382,18199284,50852019,142547559,400763223,1129760415, %U A001006 3192727797,9043402501,25669818476,73007772802,208023278209,593742784829 %N A001006 Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle. %C A001006 Number of (3412,2413)-, (3412,3142)- and (3412,3412)-avoiding involutions in S_n. %C A001006 Number of sequences of length n-1 consisting of positive integers such that the opening and ending elements are 1 or 2 and the absolute difference between any 2 consecutive elements is 0 or 1. - Jon Perry (perry(AT)globalnet.co.uk), Sep 04 2003 %C A001006 Also number of Motzkin n-paths: paths from (0,0) to (n,0) in an n X n grid using only steps U = (1,1), F = (1,0) and D = (1,-1). - David Callan (callan(AT)stat.wisc.edu), Jul 15 2004 %C A001006 Number of Dyck n-paths with no UUU. (Given such a Dyck n-path, change each UUD to U, then change each remaining UD to F. This is a bijection to Motzkin n-paths. Example with n=5: U U D U D U U D D D -> U F U D D.) - David Callan (callan(AT)stat.wisc.edu), Jul 15 2004 %C A001006 Number of Dyck (n+1)-paths with no UDU. (Given such a Dyck (n+1)-path, mark each U that is followed by a D and each D that is not followed by a U. Then change each unmarked U whose matching D is marked to an F. Lastly, delete all the marked steps. This is a bijection to Motzkin n-paths. Example with n=6 and marked steps in small type: U U u d D U U u d d d D u d -> U U u d D F F u d d d D u d -> U U D F F D.) - David Callan (callan(AT)stat.wisc.edu), Jul 15 2004 %C A001006 a(n) is the number of strings of length 2n from the following recursively defined set: L contains the empty string and, for any strings a and b in L, we also find (ab) in L. The first few elements of L are e, (), (()), ((())), (()()), (((()))), ((()())), ((())()), (()(())) and so on. This proves that a(n) is less than or equal to C(n), the n-th Catalan number. - Saul Schleimer (saulsch(AT)math.rutgers.edu), Feb 23 2006 %C A001006 a(n) = number of Dyck n-paths all of whose valleys have even x-coordinate (when path starts at origin). For example, T(4,2)=3 counts UDUDUUDD, UDUUDDUD, UUDDUDUD. Given such a path, split it into n subpaths of length 2 and transform UU->U, DD->D, UD->F (there will be no DUs for that would entail a valley with odd x-coordinate). This is a bijection to Motzkin n-paths. - David Callan (callan(AT)stat.wisc.edu), Jun 07 2006 %C A001006 Also the number of standard tableaux of height less than or equal to 3. - Mike Zabrocki (zabrocki(AT)mathstat.yorku.ca), Mar 24 2007 %C A001006 a(n) is the number of RNA shapes of size 2n+2. RNA Shapes are essentially Dyck words without "directly nested" motifs of the form A[[B]]C, for A, B and C Dyck words. The first RNA Shapes are [], [][], [][][], [[][]], [][][][], [][[][]], [[][][]], [[][]][] ... - Yann Ponty (ponty(AT)lri.fr), May 30 2007 %C A001006 Equals right and left borders and row sums of triangle A144218 with offset variations. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 14 2008] %C A001006 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. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 27 2008] %C A001006 Equals A005773 / A005773 shifted: (i.e. (1,2,5,13,35,96,...)/(1,1,2,5, 13,35,96,...)). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 21 2008] %C A001006 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. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 07 2009] %D A001006 M. Aigner, Motzkin Numbers, Europ. J. Comb. 19 (1998), 663-675. %D A001006 M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563. %D A001006 E. Barcucci, R. Pinzani, R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279. %D A001006 E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49. %D A001006 Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5. %D A001006 F. Bergeron, L. Favreau and D. Krob, Conjectures on the enumeration of tableaux of bounded height, Discrete Math, vol. 139, no. 1-3 (1995), 463-468. %D A001006 F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112. %D A001006 Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7. %D A001006 L. Carlitz, Solution of certain recurrences, SIAM J. Appl. Math., 17 (1969), 251-259. %D A001006 E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265. %D A001006 R. Donaghey, Restricted plane tree representations for four Motzkin-Catalan equations, J. Combin. Theory, Series B, 22 (1977), 114-121. %D A001006 R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301. %D A001006 T. Doslic, D. Svrtan and D. Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 67-82. %D A001006 N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221. %D A001006 A. Kuznetsov et al., Trees associated with the Motzkin numbers, J. Combin. Theory, A 76 (1996), 145-147. %D A001006 W. A. Lorenz, Y. Ponty, P. Clote, Asymptotics of RNA Shapes, Journal of Computational Biology. January/February 2008, 15(1): 31-63. doi:10.1089/ cmb.2006.0153. %D A001006 T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76. %D A001006 Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5. %D A001006 D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320. %D A001006 T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360. %D A001006 J. Riordan, Enumeration of plane trees by branches and endpoints, J. Combin. Theory, A 23 (1975), 214-222. %D A001006 E. Royer, Interpretation combinatoire des moments negatifs des valeurs de fonctions L au bord de la bande critique, Ann. Sci. Ecole Norm. Sup. (4) 36 (2003), no. 4, 601-620. %D A001006 A. Sapounakis et al., Ordered trees and the inorder transversal, Disc. Math., 306 (2006), 1732-1741. %D A001006 A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924. %D A001006 E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376. %D A001006 L. W. Shapiro et al., The Riordan group, Discrete Applied Math., 34 (1991), 229-239. %D A001006 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). %D A001006 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). %D A001006 Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1. %D A001006 R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.37. Also Problem 7.16(b), y_3(n). %D A001006 L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (6). %D A001006 Wen-Jin Woan, A combinatorial proof of a recursive relation of the Motzkin sequence by lattice paths. Fibonacci Quart. 40 (2002), no. 1, 3-8. %D A001006 Wen-jin Woan, A Recursive Relation for Weighted Motzkin Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.1.6. %D A001006 F. Yano and H. Yoshida, Some set partition statistics in non-crossing partitions and generating functions, Discr. Math., 307 (2007), 3147-3160. %H A001006 N. J. A. Sloane, The first 501 Motzkin numbers: Table of n, a(n) for n = 0..500 %H A001006 J. L. Arregui, Tangent and Bernoulli numbers related to Motzkin and Catalan numbers by means of numerical triangles. %H A001006 H. Bottomley, Illustration of initial terms %H A001006 N. T. Cameron, Random walks, trees and extensions of Riordan group techniques %H A001006 E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215. %H A001006 R. M. Dickau, Delannoy and Motzkin Numbers %H A001006 R. M. Dickau, The 9 paths in a 4 X 4 grid %H A001006 E. S. Egge, Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations, sec. 8 %H A001006 P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 68, 81 %H A001006 INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 50 %H A001006 J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5. %H A001006 W. A. Lorenz, Y. Ponty and P. Clote, Asymptotics of RNA Shapes (preprint), To appear in Journal of Computational Biology (2007) %H A001006 T. Mansour, Restricted 1-3-2 permutations and generalized patterns. %H A001006 D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320. %H A001006 J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion %H A001006 Simon Plouffe, The first 4431 terms %H A001006 Dan Romik, Some formulas for the central trinomial and Motzkin numbers, J. Integer Seqs., Vol. 6, 2003. %H A001006 E. Royer, Interpretation combinatoire des moments negatifs des valeurs de fonctions L au bord de la bande critique %H A001006 A. Sapounakis and P. Tsikouras, On k-colored Motzkin words, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.5. %H A001006 N. J. A. Sloane, Illustration of initial terms %H A001006 N. J. A. Sloane, Classic Sequences %H A001006 N. J. A. Sloane, An Application of the OEIS (Vugraph from a talk about the OEIS) %H A001006 R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), #00.1. %H A001006 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics. %H A001006 W.-J. Woan, Hankel Matrices and Lattice Paths, J. Integer Sequences, 4 (2001), #01.1.2. %H A001006 Index entries for "core" sequences %F A001006 G.f.: A(x) = (1 - x - (1-2*x-3*x^2)^(1/2))/(2*x^2). Satisfies A(x) = 1 + x*A(x) + x^2*A(x)^2. %F A001006 a(n) = (-1/2) Sum (-3)^i C(1/2, i) C(1/2, j); i+j=n+2, i >= 0, j >= 0. %F A001006 a(n) = (3/2)^(n+2) * Sum_{k >= 1} 3^(-k) * Catalan(k-1) * binomial(k, n+2-k) [Doslic et al.] %F A001006 a(n) ~ 3^(n+1)sqrt(3)[1+1/(16n)]/[(2n+3)sqrt((n+2)Pi)]. [Barcucci, Pinzani and Sprugnoli] %F A001006 lim(a(n)/a(n-1), n->infinity) = 3. [Aigner] %F A001006 a(n+2) - a(n+1) = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0) - Bernhart. %F A001006 a(n) = (1/(n+1)) * Sum_{i} (n+1)!/(i!*(i+1)!*(n-2*i)!) - Bernhart. %F A001006 a(n)=sum((-1)^(n-k)*binomial(n, k)*A000108(k+1), k=0..n). a(n)=sum(binomial(n+1, k)*binomial(n+1-k, k-1), k=0..ceil((n+1)/2))/(n+1); (n+2)a(n)=(2n+1)a(n-1)+(3n-3)a(n-2) - Len Smiley (smiley(AT)math.uaa.alaska.edu) %F A001006 a(n)=sum{ k=0..n, C(n, 2k)*A000108(k) } - Paul Barry (pbarry(AT)wit.ie), Jul 18 2003 %F A001006 E.g.f.: exp(x)*BesselI(1, 2*x)/x. - Vladeta Jovovic (vladeta(AT)eunet.rs), Aug 20 2003 %F A001006 a(n) = A005043(n) + A005043(n+1). %F A001006 The Hankel transform of this sequence gives A000012 = [1, 1, 1, 1, 1, 1, ...]. E;g. Det([1, 1, 2, 4; 1, 2, 4, 9; 2, 4, 9, 21; 4, 9, 21, 51]) = 1. - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Feb 23 2004 %F A001006 a(m+n) = Sum_{k>=0} A064189(m, k)*A064189(n, k) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Mar 05 2004 %F A001006 a(n)=sum((-1)^j*binomial(n+1, j)*binomial(2n-3j, n), j=0..floor(n/3))/ (n+1). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 13 2004 %F A001006 a(n)=A086615(n)-A086615(n-1) (n>=1). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 12 2004 %F A001006 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-2x-3x^2))^2; a(n)=(3/4)*(1/2)^n*sum{k=0..2n, 3^(n-k)*C(k)C(k+1, n+1-k)}+0^n/4 [after Doslic et al.] - Paul Barry (pbarry(AT)wit.ie), Feb 22 2005 %F A001006 G.f.: c(x^2/(1-x)^2)/(1-x), c(x) the g.f. of A000108; - Paul Barry (pbarry(AT)wit.ie), May 31 2006 %F A001006 Asymptotic formula : a(n) ~ sqrt(3/4/Pi)*3^(n+1)/n^(3/2) - Benoit Cloitre (benoit7848c(AT)orange.fr), Jan 25 2007 %F A001006 Equals A007971/2. - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Feb 28 2007 %F A001006 a(n)=(1/(2*pi))*int(x^n*sqrt((3-x)(1+x)),x,-1,3) is the moment representation; - Paul Barry (pbarry(AT)wit.ie), Sep 10 2007 %F A001006 Equals inverse binomial transform of A000108 starting (1, 2, 5, 14, 42, ...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 10 2007 %F A001006 Comment from Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 27 2008: Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n-1} + a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-2}*a_1 for n >= t. For example Phi([1]) is the Catalan numbers A000108. The present sequence is Phi([0,1,1]). %F A001006 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). [From Paul Barry (pbarry(AT)wit.ie), Dec 06 2008] %F A001006 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). [From Paul Barry (pbarry(AT)wit.ie), Feb 08 2009] %F A001006 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)) [From Mark van Hoeij (hoeij(AT)math.fsu.edu), Nov 12 2009] %p A001006 Three different Maple scripts for this sequence: %p A001006 [seq(add(binomial(n+1,k)*binomial(n+1-k,k-1),k=0..ceil((n+1)/2))/(n+1), n=0..50)]; %p A001006 A001006 := proc(n) option remember; local k; if n <= 1 then 1 else A001006(n-1) + add(A001006(k)*A001006(n-k-2),k=0..n-2); fi; end; %p A001006 Order := 20: solve(series(x/(1+x+x^2),x)=y,x); %p A001006 zl:=4*(1-z+sqrt(1-2*z-3*z^2))/(1-z+sqrt(1-2*z-3*z^2))^2/2: gser:=series(zl, z=0, 35): seq(coeff(gser, z, n), n=0..29); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Feb 28 2007 %t A001006 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 ] %o A001006 (PARI) a(n)=polcoeff((1-x-sqrt((1-x)^2-4*x^2+x^3*O(x^n)))/(2*x^2),n) (from Michael Somos) %o A001006 (PARI) a(n)=if(n<0,0,n++; polcoeff(serreverse(x/(1+x+x^2)+x*O(x^n)),n)) (from Michael Somos) %o A001006 (PARI) a(n)=if(n<0,0,n!*polcoeff(exp(x+x*O(x^n))*besseli(1,2*x+x*O(x^n)), n)) (from Michael Somos) %Y A001006 Cf. A026300, A005717, A020474, A001850, A004148. First column of A064191, A026300, A064189. First row of A064645. %Y A001006 Cf. A000108, A005717, A088615. Bisections: A026945, A099250. %Y A001006 Sequences related to chords in a circle: A001006, A054726, A006533, A006561, A006600, A007569, A007678. See also entries for chord diagrams in Index file. %Y A001006 a(n)=A005043(n)+A005043(n+1). %Y A001006 A086246 is another version, although this is the main entry. %Y A001006 Cf. A007971. %Y A001006 Cf. A001405, A005817, A049401, A007579, A007578. %Y A001006 A144218 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 14 2008] %Y A001006 A005773 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 21 2008] %Y A001006 Sequence in context: A094288 A166587 A086246 this_sequence A027057 A148071 A000636 %Y A001006 Adjacent sequences: A001003 A001004 A001005 this_sequence A001007 A001008 A001009 %K A001006 nonn,core,easy,nice,new %O A001006 0,3 %A A001006 N. J. A. Sloane (njas(AT)research.att.com). %E A001006 More terms from David W. Wilson (davidwwilson(AT)comcast.net) %E A001006 Updated a reference. - Charles R Greathouse IV (charles.greathouse(AT)case.edu), Oct 28 2009 Search completed in 0.006 seconds