%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, <a href="b001006.txt">The first 501 Motzkin numbers:
Table of n, a(n) for n = 0..500</a>
%H A001006 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.
%H A001006 H. Bottomley, <a href="a001006.2.gif">Illustration of initial terms</
a>
%H A001006 N. T. Cameron, <a href="http://www.princeton.edu/~wmassey/NAM03/cameron.pdf">
Random walks, trees and extensions of Riordan group techniques</a>
%H A001006 E. Deutsch and B. E. Sagan, <a href="http://arxiv.org/pdf/math.CO/0407326">
Congruences for Catalan and Motzkin numbers and related sequences</
a>, J. Num. Theory 117 (2006), 191-215.
%H A001006 R. M. Dickau, <a href="http://mathforum.org/advanced/robertd/delannoy.html">
Delannoy and Motzkin Numbers</a>
%H A001006 R. M. Dickau, <a href="a001006.4.gif">The 9 paths in a 4 X 4 grid</a>
%H A001006 E. S. Egge, <a href="http://arXiv.org/abs/math.CO/0307050">Restricted
3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials
and Enumerations</a>, sec. 8
%H A001006 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
Publications/books.html">Analytic Combinatorics</a>, 2009; see page
68, 81
%H A001006 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=50">
Encyclopedia of Combinatorial Structures 50</a>
%H A001006 J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
The Hankel Transform and Some of its Properties</a>, J. Integer Sequences,
4 (2001), #01.1.5.
%H A001006 W. A. Lorenz, Y. Ponty and P. Clote, <a href="http://bioinformatics.bc.edu/
~ponty/docs/AsymptoticsRNAShapes-JCompBiol-LorenzPontyClote.pdf">
Asymptotics of RNA Shapes (preprint)</a>, To appear in Journal of
Computational Biology (2007)
%H A001006 T. Mansour, <a href="http://arXiv.org/abs/math.CO/0110039">Restricted
1-3-2 permutations and generalized patterns</a>.
%H A001006 D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, <a href="http:/
/www.dsi.unifi.it/~merlini/GenRA.ps">On some alternative characterizations
of Riordan arrays</a>, Canad. J. Math., 49 (1997), 301-320.
%H A001006 J.-C. Novelli and J.-Y. Thibon, <a href="http://arXiv.org/abs/math.CO/
0512570">Noncommutative Symmetric Functions and Lagrange Inversion</
a>
%H A001006 Simon Plouffe, <a href="http://www.lacim.uqam.ca:16080/~plouffe/OEIS/
b001006.txt">The first 4431 terms</a>
%H A001006 Dan Romik, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
Some formulas for the central trinomial and Motzkin numbers</a>,
J. Integer Seqs., Vol. 6, 2003.
%H A001006 E. Royer, <a href="http://www.carva.org/emmanuel.royer">Interpretation
combinatoire des moments negatifs des valeurs de fonctions L au bord
de la bande critique</a>
%H A001006 A. Sapounakis and P. Tsikouras, <a href="http://www.cs.uwaterloo.ca/journals/
JIS/">On k-colored Motzkin words</a>, Journal of Integer Sequences,
Vol. 7 (2004), Article 04.2.5.
%H A001006 N. J. A. Sloane, <a href="a001006.gif">Illustration of initial terms</
a>
%H A001006 N. J. A. Sloane, <a href="classic.html#MOTZKIN">Classic Sequences</a>
%H A001006 N. J. A. Sloane, <a href="a001006_Vg.jpg">An Application of the OEIS</
a> (Vugraph from a talk about the OEIS)
%H A001006 R. A. Sulanke, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
Moments of generalized Motzkin paths</a>, J. Integer Sequences, Vol.
3 (2000), #00.1.
%H A001006 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
MotzkinNumber.html">Link to a section of The World of Mathematics.</
a>
%H A001006 W.-J. Woan, <a href="http://www.cs.uwaterloo.ca/journals/JIS/index.html">
Hankel Matrices and Lattice Paths</a>, J. Integer Sequences, 4 (2001),
#01.1.2.
%H A001006 <a href="Sindx_Cor.html#core">Index entries for "core" sequences</a>
%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
|
