0,3

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

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

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

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

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

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

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

Also the number of standard tableaux of height less than or equal to 3. - Mike Zabrocki (zabrocki(AT)mathstat.yorku.ca), Mar 24 2007

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

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]

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]

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]

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]

M. Aigner, Motzkin Numbers, Europ. J. Comb. 19 (1998), 663-675.

M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.

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

E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.

Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.

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.

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

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.

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

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

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

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

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

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

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

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.

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

Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.

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.

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.

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

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.

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

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

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

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

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

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

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.

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

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

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.

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

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

N. J. A. Sloane, The first 501 Motzkin numbers: Table of n, a(n) for n = 0..500

J. L. Arregui, Tangent and Bernoulli numbers related to Motzkin and Catalan numbers by means of numerical triangles.

H. Bottomley, Illustration of initial terms

N. T. Cameron, Random walks, trees and extensions of Riordan group techniques

E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.

R. M. Dickau, Delannoy and Motzkin Numbers

R. M. Dickau, The 9 paths in a 4 X 4 grid

E. S. Egge, Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations, sec. 8

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 68, 81

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 50

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

W. A. Lorenz, Y. Ponty and P. Clote, Asymptotics of RNA Shapes (preprint), To appear in Journal of Computational Biology (2007)

T. Mansour, Restricted 1-3-2 permutations and generalized patterns.

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.

J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion

Simon Plouffe, The first 4431 terms

Dan Romik, Some formulas for the central trinomial and Motzkin numbers, J. Integer Seqs., Vol. 6, 2003.

E. Royer, Interpretation combinatoire des moments negatifs des valeurs de fonctions L au bord de la bande critique

A. Sapounakis and P. Tsikouras, On k-colored Motzkin words, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.5.

N. J. A. Sloane, Illustration of initial terms

N. J. A. Sloane, Classic Sequences

N. J. A. Sloane, An Application of the OEIS (Vugraph from a talk about the OEIS)

R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), #00.1.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

W.-J. Woan, Hankel Matrices and Lattice Paths, J. Integer Sequences, 4 (2001), #01.1.2.

Index entries for "core" sequences

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.

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

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

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

lim(a(n)/a(n-1), n->infinity) = 3. [Aigner]

a(n+2) - a(n+1) = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0) - Bernhart.

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

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)

a(n)=sum{ k=0..n, C(n, 2k)*A000108(k) } - Paul Barry (pbarry(AT)wit.ie), Jul 18 2003

E.g.f.: exp(x)*BesselI(1, 2*x)/x. - Vladeta Jovovic (vladeta(AT)eunet.rs), Aug 20 2003

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

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

a(m+n) = Sum_{k>=0} A064189(m, k)*A064189(n, k) . - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Mar 05 2004

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

a(n)=A086615(n)-A086615(n-1) (n>=1). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jul 12 2004

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

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

Asymptotic formula : a(n) ~ sqrt(3/4/Pi)*3^(n+1)/n^(3/2) - Benoit Cloitre (benoit7848c(AT)orange.fr), Jan 25 2007

Equals A007971/2. - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Feb 28 2007

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

Equals inverse binomial transform of A000108 starting (1, 2, 5, 14, 42,...). - Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 10 2007

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]).

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]

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]

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]

Three different Maple scripts for this sequence:

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

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;

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

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

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 ]

(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)

(PARI) a(n)=if(n<0, 0, n++; polcoeff(serreverse(x/(1+x+x^2)+x*O(x^n)), n)) (from Michael Somos)

(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)

Cf. A026300, A005717, A020474, A001850, A004148. First column of A064191, A026300, A064189. First row of A064645.

Cf. A000108, A005717, A088615. Bisections: A026945, A099250.

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

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

A086246 is another version, although this is the main entry.

Cf. A007971.

Cf. A001405, A005817, A049401, A007579, A007578.

A144218 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 14 2008]

A005773 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 21 2008]

Sequence in context: A094288 A166587 A086246 this_sequence A027057 A148071 A000636

Adjacent sequences: A001003 A001004 A001005 this_sequence A001007 A001008 A001009

nonn,core,easy,nice,new

N. J. A. Sloane (njas(AT)research.att.com).

More terms from David W. Wilson (davidwwilson(AT)comcast.net)

Updated a reference. - Charles R Greathouse IV (charles.greathouse(AT)case.edu), Oct 28 2009

0,5

A variant of the Motzkin numbers: see A001006 for the main entry.

Equals row sums of triangle A144218 starting with "1". [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 14 2008]

Starting (1, 1, 1,...) = inverse binomial transform of A014137: (1, 2, 4, 9, 23, 65,...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 02 2009]

Series reversion of g.f. A(x) is -A(-x).

a(n)+a(n-1)=a(0)*a(n)+a(1)*a(n-1)+...+a(n)*a(0), n>2.

G.f. A(x) satisfies 0=f(x, A(x)) where f(x, y)=x-y-x*y+x^2+y^2.

G.f. A(x) satisfies 0=f(x, A(x)) where f(x, y)=(y^2-y^3)-(x^2+x^3).

G.f.: (1+x-sqrt(1-2x-3x^2))/2.

G.f. A(x) satisfies A(x) = x+C(xA(x)) where C(x) is g.f. for Catalan numbers A000108 (offset 1).

(PARI) a(n)=polcoeff((1+x-sqrt(1-2*x-3*x^2+x*O(x^n)))/2, n)

a(n+2)=A001006(n).

Cf. A144218 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 14 2008]

A014137 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 02 2009]

Sequence in context: A094287 A094288 A166587 this_sequence A001006 A027057 A148071

Adjacent sequences: A086243 A086244 A086245 this_sequence A086247 A086248 A086249

nonn

Michael Somos, Jul 13 2003

0,5

A variant of the Motzkin numbers A001006. Hankel transform is A168050.

Cf. A168051.

easy,nonn,new

Paul Barry (pbarry(AT)wit.ie), Nov 17 2009

0,5

A signed variant of the Motzkin numbers A001006. Hankel transform is A168052.

Cf. A168049.

easy,sign,new

Paul Barry (pbarry(AT)wit.ie), Nov 17 2009

0,4

Hankel transform is A131713. Binomial transform is A166588.

G.f.: (1+3x-sqrt(1+2x-3x^2))/(2x); (1+3x)/(1+2x-x^2/(1+x-x^2/(1+x-x^2/(1+x-x^2/(1+... (continued fraction).

a(n)=0^n+sum{k=0..n, C(n-1,k-1)*(-3)^(n-k)*A000108(k)}.

Sequence in context: A094286 A094287 A094288 this_sequence A086246 A001006 A027057

Adjacent sequences: A166584 A166585 A166586 this_sequence A166588 A166589 A166590

easy,sign

Paul Barry (pbarry(AT)wit.ie), Oct 17 2009