login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001006 Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.
(Formerly M1184 N0456)
295
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Number of 4321-, (3412,2413)-, (3412,3142)- and 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, 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, 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, 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, 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, Jun 07 2006

Also the number of standard Young tableaux of height <= 3. - Mike Zabrocki, 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. - Gary W. Adamson, 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. - Gary W. Adamson, Oct 27 2008

Equals A005773 / A005773 shifted (i.e., (1,2,5,13,35,96,...) / (1,1,2,5,13,35,96,...)). - Gary W. Adamson, Dec 21 2008

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

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

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. - Peter Luschny, May 21 2011

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

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

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 number of letters x in word z.  The a(4) = 9 words are: aaaa, aaab, aaba, abaa, aabb, abab, aabc, abac, abca. - Alois P. Heinz, May 26 2012

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

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

Number of (4231,5276143)-avoiding involutions in S_n. - Alexander Burstein, Mar 05 2014

REFERENCES

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

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

C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, [http://algo.inria.fr/banderier/Papers/DiscMath99.ps Generating Functions for Generating Trees], Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

Barcucci, Elena; Del Lungo, Alberto; Pergola, Elisa; Pinzani, Renzo. A methodology for plane tree enumeration. 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) - From N. J. A. Sloane, Jun 03 2012

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.

J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178; http://www.combinatorics.org/Volume_18/PDF/v18i1p178.pdf

J.-L. Baril, J.-M. Pallo, Motzkin subposet and Motzkin geodesics in Tamari lattices, 2013; http://jl.baril.u-bourgogne.fr/Motzkin.pdf

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.

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

J. Cigler, Hankel determinants of some polynomial sequences, http://homepage.univie.ac.at/johann.cigler/preprints/hankel.pdf, 2012. - From N. J. A. Sloane, Jan 02 2013

Dairyko, Michael; Tyner, Samantha; Pudwell, Lara; Wynn, Casey. Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From N. J. A. Sloane, Feb 01 2013

D. E. Davenport, L. W. Shapiro and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33. - From N. J. A. Sloane, May 11 2012

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.

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

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.

Doslic, Tomislav and Veljan, Darko. Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182--2212. MR2404544 (2009j:05019) - From N. J. A. Sloane, May 01 2012

S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191. [From Emeric Deutsch, May 29 2010]

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

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

Kris Hatch, Presentation of the Motzkin Monoid, Senior Thesis, Univ. Cal. Santa Barbara, 2012; http://ccs.math.ucsb.edu/senior-thesis/Kris-Hatch.pdf. - From N. J. A. Sloane, Dec 25 2012

Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011; http://repository.wit.ie/1693/1/AoifeThesis.pdf

V. Jelinek, T. Mansour and M. Shattuck, On multiple pattern avoiding set partitions, Advances in Applied Mathematics Volume 50, Issue 2, February 2013, Pages 292-326. - From N. J. A. Sloane, Jan 01 2013

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

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

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

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

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. - From N. J. A. Sloane, Oct 13 2012

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

Mansour, Toufik; Schork, Matthias; Shattuck, Mark. Catalan numbers and pattern restricted set partitions. Discrete Math. 312(2012), no. 20, 2979--2991. MR2956089. - From N. J. A. Sloane, Sep 07 2012

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.

L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), http://faculty.valpo.edu/lpudwell/slides/notredame.pdf, 2012.

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

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.

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

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

Z.-W. Sun, Conjectures involving arithmetical sequences, Number Theory: Arithmetic in Shangrila (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. - From N. J. A. Sloane, Dec 28 2012

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.

LINKS

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.

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

P. Barry, On sequences with {-1, 0, 1} Hankel transforms, Arxiv preprint arXiv:1205.2565, 2012. - From N. J. A. Sloane, Oct 18 2012

Paul Barry, Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, Vol. 15 2012, #12.8.2.  - From N. J. A. Sloane, Dec 29 2012

Paul Barry, On the Hurwitz Transform of Sequences, Journal of Integer Sequences, Vol. 15 (2012), #12.8.7.

Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003, 2013.

A. Bostan, Computer Algebra for Lattice Path Combinatorics, Seminaire de Combinatoire Ph. Flajolet, March 28 2013.

H. Bottomley, Illustration of initial terms

A. Burstein, J. Pantone, Two examples of unbalanced Wilf-equivalence, arXiv:1402.3842, 2014.

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

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.

J. Cigler, Some nice Hankel determinants. Arxiv preprint arXiv:1109.1449, 2011.

R. De Castro, A. L. Ramírez and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449, 2013

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

Yun Ding and Rosena R. X. Du, Counting Humps in Motzkin paths, Arxiv preprint arXiv:1109.2661, 2011

Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908, 2012.

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

Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, Arxiv preprint arXiv:1203.6792, 2012. - From N. J. A. Sloane, Oct 03 2012

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, Journal of Computational Biology 15:1 (2008), pp. 31-63.

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

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

V. Mazorchuk and B. Steinberg, Double Catalan monoids, Arxiv preprint arXiv:1105.5313, 2011.

Cam McLeman and Erin McNicholas, Graph Invertibility, Arxiv preprint arXiv:1108.3588, 2011

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.

Heinrich Niederhausen, Inverses of Motzkin and Schroeder Paths, Arxiv preprint arXiv:1105.3713, 2011.

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. Rowland, R. Yassawi, Automatic congruences for diagonals of rational functions, arXiv preprint arXiv:1310.8635, 2013

E. Rowland, D. Zeilberger, A Case Study in Meta-AUTOMATION: AUTOMATIC Generation of Congruence AUTOMATA For Combinatorial Sequences, arXiv preprint arXiv:1311.4776, 2013

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

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, arXiv:0711.1738. Mentions this sequence. - N. J. A. Sloane, Mar 14 2014

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.

Yidong Sun and Fei Ma, Minors of a Class of Riordan Arrays Related to Weighted Partial Motzkin Paths, arXiv preprint arXiv:1305.2015, 2013

Zhi-Wei Sun, Conjectures involving combinatorial sequences, Arxiv preprint arXiv:1208.2683, 2012. - From N. J. A. Sloane, Dec 25 2012

Yi Wang and Bao-Xuan Zhu, Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences, arXiv preprint arXiv:1303.5595, 2013

Eric Weisstein's World of Mathematics, Motzkin Number

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

Index entries for "core" sequences

FORMULA

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

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

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

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, Jul 18 2003

E.g.f.: exp(x)*BesselI(1, 2*x)/x. - Vladeta Jovovic, 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. - Philippe Deléham, Feb 23 2004

a(m+n) = Sum_{k>=0} A064189(m, k)*A064189(n, k). - Philippe Deléham, 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, Mar 13 2004

a(n) = A086615(n)-A086615(n-1) (n>=1). - Emeric Deutsch, 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-2*x-3*x^2))^2; a(n)=(3/4)*(1/2)^n*sum(k=0..2*n, 3^(n-k)*C(k)*C(k+1, n+1-k) ) + 0^n/4 [after Doslic et al.]. - Paul Barry, Feb 22 2005

G.f.: c(x^2/(1-x)^2)/(1-x), c(x) the g.f. of A000108. - Paul Barry, May 31 2006

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

a(n) = A007971(n+2)/2. - Zerinvary Lajos, 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, Sep 10 2007

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

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

G.f.: 1/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/.... (continued fraction). - Paul Barry, Dec 06 2008

G.f.: 1/(1-(x+x^2)/(1-x^2/(1-(x+x^2)/(1-x^2/(1-(x+x^2)/(1-x^2/(1-.... (continued fraction). - Paul Barry, Feb 08 2009

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

G.f.: 1/(1-x/(1-x/(1-x^2/(1-x/(1-x/(1-x^2/(1-x/(1-x/(1-x^2/(1-... (continued fraction). - Paul Barry, Mar 02 2010

G.f.: 1/(1-x/(1-x/(1+x-x/(1-x/(1+x-x/(1-x/(1+x-x/(1-x/(1+x-x/(1-... (continued fraction). - Paul Barry, Jan 26 2011 [Adds apparently a third '1' in front. - R. J. Mathar, Jan 29 2011]

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

a(n) = (2/Pi)*integral(x=-1..1, (1+2*x)^n*sqrt(1-x^2)). - Peter Luschny, Sep 11 2011

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

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

a(n) satisfies 0 = a(n) * (9*a(n+1) + 15*a(n+2) - 12*a(n+3)) + a(n+1) * ( -3*a(n+1) + 10*a(n+2) - 5*a(n+3)) + a(n+2) * (a(n+2) + a(n+3)) unless n=-2. - Michael Somos, Mar 23 2012

a(n) = (-1)^n*hypergeometric([-n,3/2],[3],4). - Peter Luschny, Aug 15 2012

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

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

EXAMPLE

1 + x + 2*x^2 + 4*x^3 + 9*x^4 + 21*x^5 + 51*x^6 + 127*x^7 + 323*x^8 + ...

MAPLE

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 procname(n-1) + add(procname(k)*procname(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, Feb 28 2007

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

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

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

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

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

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

A001006(29)_list; # Peter Luschny, May 21 2011

MATHEMATICA

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 ]

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

PROG

(PARI) {a(n) = polcoeff( ( 1 - x - sqrt((1 - x)^2 - 4 * x^2 + x^3 * O(x^n))) / (2 * x^2), n)} /* Michael Somos, Sep 25 2003 */

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

(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp(x + x * O(x^n)) * besseli(1, 2 * x + x * O(x^n)), n))} /* Michael Somos, Sep 25 2003 */

(Maxima) a[0]:1$

a[1]:1$

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

makelist(a[n], n, 0, 12); /* Emanuele Munarini, Mar 02 2011 */

(Maxima)

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

makelist(M(n), n, 0, 60); /* Emanuele Munarini, Apr 04 2012 */

(Haskell)

a001006 n = a001006_list !! n

a001006_list = zipWith (+) a005043_list $ tail a005043_list

-- Reinhard Zumkeller, Jan 31 2012

CROSSREFS

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

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. Column k=3 of A182172.

Sequence in context: A168051 A166587 A168049 * A086246 A230556 A027057

Adjacent sequences:  A001003 A001004 A001005 * A001007 A001008 A001009

KEYWORD

nonn,core,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from David W. Wilson

Updated a reference. - Charles R Greathouse IV, Oct 28 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 16 10:31 EDT 2014. Contains 240577 sequences.