cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 15 results. Next

A001006 Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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 first and last elements are 1 or 2 and the absolute difference between any 2 consecutive elements is 0 or 1. - Jon Perry, Sep 04 2003
From David Callan, Jul 15 2004: (Start)
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).
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.)
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)
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 William P. Orrick, Jun 13 2024.)
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
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 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. - 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 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
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 A245888. - Manda Riehl, Aug 07 2014
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.) - David Callan, Aug 27 2014
From Tony Foster III, Jul 28 2016: (Start)
A series created using 2*a(n) + a(n+1) has Hankel transform of F(2n), offset 3, F being the Fibonacci bisection, A001906 (empirical observation).
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, A197649 (empirical observation). (End)
Conjecture: (2/n)*Sum_{k=1..n} (2k+1)*a(k)^2 is an integer for each positive integer n. - Zhi-Wei Sun, Nov 16 2017
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." - Eric M. Schmidt, Dec 16 2017
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. - Sergey Kirgizov, Apr 08 2018
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. - Colin Defant, Apr 28 2019
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. - Colin Defant, Aug 29 2020
From Helmut Prodinger, Dec 13 2020: (Start)
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), ...}.
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.
This step set is inspired by {(1,1), (1,-1), (1,-3), (1,-5), ...}, suggested by Emeric Deutsch around 2000.
See Prodinger link that contains a bijection to Motzkin paths. (End)
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". - Amiram Eldar, Apr 15 2021
Number of Motzkin n-paths a(n) is split into A107587(n), number of even Motzkin n-paths, and A343386(n), number of odd Motzkin n-paths. The value A107587(n) - A343386(n) can be called the "shadow" of a(n) (see A343773). - Gennady Eremin, May 17 2021
Conjecture: If p is a prime of the form 6m+1 (A002476), then a(p-2) is divisible by p. Currently, no counterexample exists for p < 10^7. Personal communication from Robert Gerbicz: mod such p this is equivalent to A066796 with comment: "Every A066796(n) from A066796((p-1)/2) to A066796(p-1) is divisible by prime p of form 6m+1". - Serge Batalov, Feb 08 2022
From Rob Burns, Nov 11 2024: (Start)
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).
In fact, the 2017 paper by Burns establishes more general congruences for a(p^k - 2) where k >= 1.
If p == 1 (mod 6) then a(p^k - 2) == 0 (mod p) for k >= 1.
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.
These are consequences of the transitions provided in Tables 4, 5 and 6 of the paper.
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)
From Peter Bala, Feb 10 2022: (Start)
Conjectures:
(1) For prime p == 1 (mod 6) and n, r >= 1, a(n*p^r - 2) == -A005717(n-1) (mod p), where we take A005717(0) = 0 to match Batalov's conjecture above.
(2) For prime p == 5 (mod 6) and n >= 1, a(n*p - 2) == -A005773(n) (mod p).
(3) For prime p >= 3 and k >= 1, a(n + p^k) == a(n) (mod p) for 0 <= n <= (p^k - 3).
(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)
The Hankel transform of this sequence with a(0) omitted gives the period-6 sequence [1, 0, -1, -1, 0, 1, ...] which is A010892 with its first term omitted, while the Hankel transform of the current sequence is the all-ones sequence A000012, and also it is the unique sequence with this property which is similar to the unique Hankel transform property of the Catalan numbers. - Michael Somos, Apr 17 2022
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. - Elif Baser, Dec 20 2024

Examples

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

References

  • 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.
  • 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.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pp. 24, 298, 618, 912.
  • A. J. Bu, Automated counting of restricted Motzkin paths, Enumerative Combinatorics and Applications, ECA 1:2 (2021) Article S2R12.
  • Naiomi Cameron, JE McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.
  • L. Carlitz, Solution of certain recurrences, SIAM J. Appl. Math., 17 (1969), 251-259.
  • 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.
  • D. E. Davenport, L. W. Shapiro, and L. C. Woodson, The Double Riordan Group, The Electronic Journal of Combinatorics, 18(2) (2012), #P33.
  • E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
  • T. Doslic, D. Svrtan, and D. Veljan, Enumerative aspects of secondary structures, Discr. Math., 285 (2004), 67-82.
  • Tomislav Doslic and Darko Veljan, Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182-2212. MR2404544 (2009j:05019).
  • S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.
  • M. Dziemianczuk, "Enumerations of plane trees with multiple edges and Raney lattice paths." Discrete Mathematics 337 (2014): 9-24.
  • Wenjie Fang, A partial order on Motzkin paths, Discrete Math., 343 (2020), #111802.
  • 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.
  • 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.
  • 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.
  • 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, and 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.
  • Toufik Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76.
  • Toufik Mansour, Matthias Schork, and Mark Shattuck, Catalan numbers and pattern restricted set partitions. Discrete Math. 312(2012), no. 20, 2979-2991. MR2956089.
  • 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.
  • 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.
  • 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.
  • Mark 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).
  • P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.
  • 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.
  • Chenying Wang, Piotr Miska, and István Mező, "The r-derangement numbers." Discrete Mathematics 340.7 (2017): 1681-1692.
  • Ying Wang and Guoce Xin, A Classification of Motzkin Numbers Modulo 8, Electron. J. Combin., 25(1) (2018), #P1.54.
  • 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

Crossrefs

Cf. A026300, A005717, A020474, A001850, A004148. First column of A064191, A064189, A000108, A088615, A007971, A001405, A005817, A049401, A007579, A007578, A097862, 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.
Motzkin numbers A001006 read mod 2,3,4,5,6,7,8,11: A039963, A039964, A299919, A258712, A299920, A258711, A299918, A258710.
Cf. A004148, A004149, A023421, A023422, A023423, A290277 (inv. Euler Transf.).

Programs

  • Haskell
    a001006 n = a001006_list !! n
a001006_list = zipWith (+) a005043_list $ tail a005043_list
-- Reinhard Zumkeller, Jan 31 2012
  • Maple
    # Three different Maple scripts for this sequence:
A001006 := proc(n)
    add(binomial(n,2*k)*A000108(k),k=0..floor(n/2)) ;
end proc:
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); end if; end proc:
# 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_list(29); # 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]
(* Second program: *)
CoefficientList[Series[(1 - x - (1 - 2x - 3x^2)^(1/2))/(2x^2), {x, 0, 29}], x] (* Jean-François Alcover, Nov 29 2011 *)
Table[Hypergeometric2F1[(1-n)/2, -n/2, 2, 4], {n,0,29}] (* Peter Luschny, May 15 2016 *)
Table[GegenbauerC[n,-n-1,-1/2]/(n+1),{n,0,100}] (* Emanuele Munarini, Oct 20 2016 *)
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}]];
Table[MotzkinNumber[n], {n, 0, 29}] (* Jean-François Alcover, Oct 27 2021 *)
  • 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 */
  • Maxima
    makelist(ultraspherical(n,-n-1,-1/2)/(n+1),n,0,12); /* Emanuele Munarini, Oct 20 2016 */
  • 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 */
  • Python
    from gmpy2 import divexact
A001006 = [1, 1]
for n in range(2, 10**3):
    A001006.append(divexact(A001006[-1]*(2*n+1)+(3*n-3)*A001006[-2],n+2))
# Chai Wah Wu, Sep 01 2014
  • Python
    def mot():
    a, b, n = 0, 1, 1
    while True:
        yield b//n
        n += 1
        a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)//((n+1)*(n-1))
A001006 = mot()
print([next(A001006) for n in range(30)]) # Peter Luschny, May 16 2016
  • Python
    # A simple generator of Motzkin-paths (see the first comment of David Callan).
C = str.count
def aGen(n: int):
    a = [""]
    for w in a:
        if len(w) == n:
            if C(w, "U") == C(w, "D"): yield w
        else:
            for j in "UDF":
                u = w + j
                if C(u, "U") >= C(u, "D"): a += [u]
    return a
for n in range(6):
    MP = [w for w in aGen(n)];
    print(len(MP), ":", MP)  # Peter Luschny, Dec 03 2024

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_{i+j = n+2, i >= 0, j >= 0} (-3)^i*C(1/2, i)*C(1/2, j).
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/(16*n))/((2*n+3)*sqrt((n+2)*Pi)). [Barcucci, Pinzani and Sprugnoli]
Limit_{n->infinity} a(n)/a(n-1) = 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]
From Len Smiley: (Start)
a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*A000108(k+1), inv. Binomial Transform of A000108.
a(n) = (1/(n+1))*Sum_{k=0..ceiling((n+1)/2)} binomial(n+1, k)*binomial(n+1-k, k-1);
D-finite with recurrence: (n+2)*a(n) = (2*n+1)*a(n-1) + (3*n-3)*a(n-2). (End)
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) = (1/(n+1))*Sum_{j=0..floor(n/3)} (-1)^j*binomial(n+1, j)*binomial(2*n-3*j, n). - 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))*Integral_{x=-1..3} x^n*sqrt((3-x)*(1+x)) is the moment representation. - Paul Barry, Sep 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
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
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. - Doron Zeilberger, Mar 12 2015
G.f. A(x) with offset 1 satisfies: A(x)^2 = A( x^2/(1-2*x) ). - Paul D. Hanna, Nov 08 2015
a(n) = GegenbauerPoly(n,-n-1,-1/2)/(n+1). - Emanuele Munarini, Oct 20 2016
a(n) = a(n-1) + A002026(n-1). Number of Motzkin paths that start with an F step plus number of Motzkin paths that start with an U step. - R. J. Mathar, Jul 25 2017
G.f. A(x) satisfies A(x)*A(-x) = F(x^2), where F(x) is the g.f. of A168592. - Alexander Burstein, Oct 04 2017
G.f.: A(x) = exp(int((E(x)-1)/x dx)), where E(x) is the g.f. of A002426. Equivalently, E(x) = 1 + x*A'(x)/A(x). - Alexander Burstein, Oct 05 2017
G.f. A(x) satisfies: A(x) = Sum_{j>=0} x^j * Sum_{k=0..j} binomial(j,k)*x^k*A(x)^k. - Ilya Gutkovskiy, Apr 11 2019
From Gennady Eremin, May 08 2021: (Start)
G.f.: 2/(1 - x + sqrt(1-2*x-3*x^2)).
a(n) = A107587(n) + A343386(n) = 2*A107587(n) - A343773(n) = 2*A343386(n) + A343773(n). (End)
Revert transform of A049347 (after Michael Somos). - Gennady Eremin, Jun 11 2021
Sum_{n>=0} 1/a(n) = 2.941237337631025604300320152921013604885956025483079699366681494505960039781389... - Vaclav Kotesovec, Jun 17 2021
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. - Michael Somos, Apr 17 2022
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). - Joerg Arndt, Jan 16 2023
From Peter Bala, Feb 03 2024: (Start)
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 A000108.
A(x) = 1/(1 - 3*x)*c(-x/(1 -3*x))^2.
a(n+1) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n, k)*A000245(k+1).
a(n) = 3^n * Sum_{k = 0..n} (-3)^(-k)*binomial(n, k)*Catalan(k+1).
a(n) = 3^n * hypergeom([3/2, -n], [3], 4/3). (End)
G.f. A(x) satisfies A(x) = exp( x*A(x) + Integral x*A(x)/(1 - x^2*A(x)) dx ). - Paul D. Hanna, Mar 04 2024
a(n) = hypergeom([-n/2,1/2-n/2],[2],4). - Karol A. Penson, May 18 2025

A005043 Riordan numbers: a(n) = (n-1)*(2*a(n-1) + 3*a(n-2))/(n+1).

Original entry on oeis.org

1, 0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, 11298, 30537, 83097, 227475, 625992, 1730787, 4805595, 13393689, 37458330, 105089229, 295673994, 834086421, 2358641376, 6684761125, 18985057351, 54022715451, 154000562758, 439742222071, 1257643249140
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also called Motzkin summands or ring numbers.
The old name was "Motzkin sums", used in certain publications. The sequence has the property that Motzkin(n) = A001006(n) = a(n) + a(n+1), e.g., A001006(4) = 9 = 3 + 6 = a(4) + a(5).
Number of 'Catalan partitions', that is partitions of a set 1,2,3,...,n into parts that are not singletons and whose convex hulls are disjoint when the points are arranged on a circle (so when the parts are all pairs we get Catalan numbers). - Aart Blokhuis (aartb(AT)win.tue.nl), Jul 04 2000
Number of ordered trees with n edges and no vertices of outdegree 1. For n > 1, number of dissections of a convex polygon by nonintersecting diagonals with a total number of n+1 edges. - Emeric Deutsch, Mar 06 2002
Number of Motzkin paths of length n with no horizontal steps at level 0. - Emeric Deutsch, Nov 09 2003
Number of Dyck paths of semilength n with no peaks at odd level. Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUDUDD, where U=(1,1), D=(1,-1). Number of Dyck paths of semilength n with no ascents of length 1 (an ascent in a Dyck path is a maximal string of up steps). Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUUDDD. - Emeric Deutsch, Dec 05 2003
Arises in Schubert calculus as follows. Let P = complex projective space of dimension n+1. Take n projective subspaces of codimension 3 in P in general position. Then a(n) is the number of lines of P intersecting all these subspaces. - F. Hirzebruch, Feb 09 2004
Difference between central trinomial coefficient and its predecessor. Example: a(6) = 15 = 141 - 126 and (1 + x + x^2)^6 = ... + 126*x^5 + 141*x^6 + ... (Catalan number A000108(n) is the difference between central binomial coefficient and its predecessor.) - David Callan, Feb 07 2004
a(n) = number of 321-avoiding permutations on [n] in which each left-to-right maximum is a descent (i.e., is followed by a smaller number). For example, a(4) counts 4123, 3142, 2143. - David Callan, Jul 20 2005
The Hankel transform of this sequence give A000012 = [1, 1, 1, 1, 1, 1, 1, ...]; example: Det([1, 0, 1, 1; 0, 1, 1, 3; 1, 1, 3, 6; 1, 3, 6, 15]) = 1. - Philippe Deléham, May 28 2005
The number of projective invariants of degree 2 for n labeled points on the projective line. - Benjamin J. Howard (bhoward(AT)ima.umn.edu), Nov 24 2006
Define a random variable X=trA^2, where A is a 2 X 2 unitary symplectic matrix chosen from USp(2) with Haar measure. The n-th central moment of X is E[(X+1)^n] = a(n). - Andrew V. Sutherland, Dec 02 2007
Let V be the adjoint representation of the complex Lie algebra sl(2). The dimension of the invariant subspace of the n-th tensor power of V is a(n). - Samson Black (sblack1(AT)uoregon.edu), Aug 27 2008
Starting with offset 3 = iterates of M * [1,1,1,...], 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 08 2009
a(n) has the following standard-Young-tableaux (SYT) interpretation: binomial(n+1,k)*binomial(n-k-1,k-1)/(n+1)=f^(k,k,1^{n-2k}) where f^lambda equals the number of SYT of shape lambda. - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 02 2010
a(n) is also the sum of the numbers of standard Young tableaux of shapes (k,k,1^{n-2k}) for all 1 <= k <= floor(n/2). - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 10 2010
a(n) is the number of derangements 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(3)=1 because p=231=(123) is the only derangement of {1,2,3} with genus 0. Indeed, cp'=231*312=123=(1)(2)(3) and so g(p) = (1/2)(3+1-1-3)=0. - Emeric Deutsch, May 29 2010
Apparently: Number of Dyck 2n-paths with all ascents length 2 and no descent length 2. - David Scambler, Apr 17 2012
This is true. Proof: The mapping "insert a peak (UD) after each upstep (U)" is a bijection from all Dyck n-paths to those Dyck (2n)-paths in which each ascent is of length 2. It sends descents of length 1 in the n-path to descents of length 2 in the (2n)-path. But Dyck n-paths with no descents of length 1 are equinumerous with Riordan n-paths (Motzkin n-paths with no flatsteps at ground level) as follows. Given a Dyck n-path with no descents of length 1, split it into consecutive step pairs, then replace UU with U, DD with D, UD with a blue flatstep (F), DU with a red flatstep, and concatenate the new steps to get a colored Motzkin path. Each red F will be (immediately) preceded by a blue F or a D. In the latter case, transfer the red F so that it precedes the matching U of the D. Finally, erase colors to get the required Riordan path. For example, with lowercase f denoting a red flatstep, U^5 D^2 U D^4 U^4 D^3 U D^2 -> (U^2, U^2, UD, DU, D^2, D^2, U^2, U^2 D^2, DU, D^2) -> UUFfDDUUDfD -> UUFFDDUFUDD. - David Callan, Apr 25 2012
From Nolan Wallach, Aug 20 2014: (Start)
Let ch[part1, part2] be the value of the character of the symmetric group on n letters corresponding to the partition part1 of n on the conjucgacy class given by part2. Let A[n] be the set of (n+1) partitions of 2n with parts 1 or 2. Then deleting the first term of the sequence one has a(n) = Sum_{k=1..n+1} binomial(n,k-1)*ch[[n,n], A[n][[k]]])/2^n. This via the Frobenius Character Formula can be interpreted as the dimension of the SL(n,C) invariants in tensor^n (wedge^2 C^n).
Explanation: Let p_j denote sum (x_i)^j the sum in k variables. Then the Frobenius formula says then (p_1)^j_1 (p_2)^j_2 ... (p_r)^j_r is equal to sum(lambda, ch[lambda, 1^j_12^j_2 ... r^j_r] S_lambda) with S_lambda the Schur function corresponding to lambda. This formula implies that the coefficient of S([n,n]) in (((p_1)^1+p_2)/2)^n in its expansion in terms of Schur functions is the right hand side of our formula. If we specialize the number of variables to 2 then S[n,n](x,y)=(xy)^n. Which when restricted to y=x^(-1) is 1. That is it is 1 on SL(2).
On the other hand ((p_1)^2+p_2)/2 is the complete homogeneous symmetric function of degree 2 that is tr(S^2(X)). Thus our formula for a(n) is the same as that of Samson Black above since his V is the same as S^2(C^2) as a representation of SL(2). On the other hand, if we multiply ch(lambda) by sgn you get ch(Transpose(lambda)). So ch([n,n]) becomes ch([2,...,2]) (here there are n 2's). The formula for a(n) is now (1/2^n)*Sum_{j=0..n} ch([2,..,2], 1^(2n-2j) 2^j])*(-1)^j)*binomial(n,j), which calculates the coefficient of S_(2,...,2) in (((p_1)^2-p_2)/2)^n. But ((p_1)^2-p_2)/2 in n variables is the second elementary symmetric function which is the character of wedge^2 C^n and S_(2,...,2) is 1 on SL(n).
(End)
a(n) = number of noncrossing partitions (A000108) of [n] that contain no singletons, also number of nonnesting partitions (A000108) of [n] that contain no singletons. - David Callan, Aug 27 2014
From Tom Copeland, Nov 02 2014: (Start)
Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x)= [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).
Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)].
Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).
BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)].
Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).
Various relations among the o.g.f.s may be easily constructed, such as Fib[-Mot(-x)] = -P[P(-x)] = x/(1-2*x) a generating fct for 2^n.
Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1]. (End)
Consistent with David Callan's comment above, A249548, provides a refinement of the Motzkin sums into the individual numbers for the non-crossing partitions he describes. - Tom Copeland, Nov 09 2014
The number of lattice paths from (0,0) to (n,0) that do not cross below the x-axis and use up-step=(1,1) and down-steps=(1,-k) where k is a positive integer. For example, a(4) = 3: [(1,1)(1,1)(1,-1)(1,-1)], [(1,1)(1,-1)(1,1)(1,-1)] and [(1,1)(1,1)(1,1)(1,-3)]. - Nicholas Ham, Aug 19 2015
A series created using 2*(a(n) + a(n+1)) + (a(n+1) + a(n+2)) has Hankel transform of F(2n), offset 3, F being a Fibonacci number, A001906 (Empirical observation). - Tony Foster III, Jul 30 2016
The series a(n) + A001006(n) has Hankel transform F(2n+1), offset n=1, F being the Fibonacci bisection A001519 (empirical observation). - Tony Foster III, Sep 05 2016
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. Moreover, the number of such algebras having the double centraliser property with respect to a minimal faithful projective-injective module equals the number of Riordan paths, that is, Motzkin paths without level-steps at height zero, of length n." - Eric M. Schmidt, Dec 16 2017
A connection to the Thue-Morse sequence: (-1)^a(n) = (-1)^A010060(n) * (-1)^A010060(n+1) = A106400(n) * A106400(n+1). - Vladimir Reshetnikov, Jul 21 2019
Named by Bernhart (1999) after the American mathematician John Riordan (1903-1988). - Amiram Eldar, Apr 15 2021

Examples

			a(5)=6 because the only dissections of a polygon with a total number of 6 edges are: five pentagons with one of the five diagonals and the hexagon with no diagonals.
G.f. = 1 + x^2 + x^3 + 3*x^4 + 6*x^5 + 15*x^6 + 36*x^7 + 91*x^8 + 232*x^9 + ...
From _Gus Wiseman_, Nov 15 2022: (Start)
The a(0) = 1 through a(6) = 15 lone-child-avoiding (no vertices of outdegree 1) ordered rooted trees with n + 1 vertices (ranked by A358376):
  o  .  (oo)  (ooo)  (oooo)   (ooooo)   (oooooo)
                     ((oo)o)  ((oo)oo)  ((oo)ooo)
                     (o(oo))  ((ooo)o)  ((ooo)oo)
                              (o(oo)o)  ((oooo)o)
                              (o(ooo))  (o(oo)oo)
                              (oo(oo))  (o(ooo)o)
                                        (o(oooo))
                                        (oo(oo)o)
                                        (oo(ooo))
                                        (ooo(oo))
                                        (((oo)o)o)
                                        ((o(oo))o)
                                        ((oo)(oo))
                                        (o((oo)o))
                                        (o(o(oo)))
(End)

References

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

Links

Crossrefs

Row sums of triangle A020474, first differences of A082395.
First diagonal of triangular array in A059346.
Binomial transform of A126930. - Philippe Deléham, Nov 26 2009
The Hankel transform of a(n+1) is A128834. The Hankel transform of a(n+2) is floor((2*n+4)/3) = A004523(n+2). - Paul Barry, Mar 08 2011
The Kn11 triangle sums of triangle A175136 lead to A005043(n+2), while the Kn12(n) = A005043(n+4)-2^(n+1), Kn13(n) = A005043(n+6)-(n^2+9*n+56)*2^(n-2) and the Kn4(n) = A005043(2*n+2) = A099251(n+1) triangle sums are related to the sequence given above. For the definitions of these triangle sums see A180662. - Johannes W. Meijer, May 06 2011
Cf. A187306 (self-convolution), A348210 (column 1).
Cf. A000045, A000108, A000957, A001006, A005717, A005773, A007317, A057078, A091867, A104597, A126120, A178514, A249548, A309303.
Bisections: A099251, A099252.

Programs

  • Haskell
    a005043 n = a005043_list !! n
a005043_list = 1 : 0 : zipWith div
   (zipWith (*) [1..] (zipWith (+)
       (map (* 2) $ tail a005043_list) (map (* 3) a005043_list))) [3..]
-- Reinhard Zumkeller, Jan 31 2012
  • Maple
    A005043 := proc(n) option remember; if n <= 1 then 1-n else (n-1)*(2*A005043(n-1)+3*A005043(n-2))/(n+1); fi; end;
Order := 20: solve(series((x-x^2)/(1-x+x^2),x)=y,x); # outputs g.f.
  • Mathematica
    a[0]=1; a[1]=0; a[n_]:= a[n] = (n-1)*(2*a[n-1] + 3*a[n-2])/(n+1); Table[ a[n], {n, 0, 30}] (* Robert G. Wilson v, Jun 14 2005 *)
Table[(-3)^(1/2)/6 * (-1)^n*(3*Hypergeometric2F1[1/2,n+1,1,4/3]+ Hypergeometric2F1[1/2,n+2,1,4/3]), {n,0,32}] (* cf. Mark van Hoeij in A001006 *) (* Wouter Meeussen, Jan 23 2010 *)
RecurrenceTable[{a[0]==1,a[1]==0,a[n]==(n-1) (2a[n-1]+3a[n-2])/(n+1)},a,{n,30}] (* Harvey P. Dale, Sep 27 2013 *)
a[ n_]:= SeriesCoefficient[2/(1+x +Sqrt[1-2x-3x^2]), {x, 0, n}]; (* Michael Somos, Aug 21 2014 *)
a[ n_]:= If[n<0, 0, 3^(n+3/2) Hypergeometric2F1[3/2, n+2, 2, 4]/I]; (* Michael Somos, Aug 21 2014 *)
Table[3^(n+3/2) CatalanNumber[n] (4(5+2n)Hypergeometric2F1[3/2, 3/2, 1/2-n, 1/4] -9 Hypergeometric2F1[3/2, 5/2, 1/2 -n, 1/4])/(4^(n+3) (n+1)), {n, 0, 31}] (* Vladimir Reshetnikov, Jul 21 2019 *)
Table[Sqrt[27]/8 (3/4)^n CatalanNumber[n] Hypergeometric2F1[1/2, 3/2, 1/2 - n, 1/4], {n, 0, 31}] (* Jan Mangaldan, Sep 12 2021 *)
  • Maxima
    a[0]:1$
a[1]:0$
a[n]:=(n-1)*(2*a[n-1]+3*a[n-2])/(n+1)$
makelist(a[n],n,0,12); /* Emanuele Munarini, Mar 02 2011 */
  • PARI
    {a(n) = if( n<0, 0, n++; polcoeff( serreverse( (x - x^3) / (1 + x^3) + x * O(x^n)), n))}; /* Michael Somos, May 31 2005 */
  • PARI
    my(N=66); Vec(serreverse(x/(1+x*sum(k=1,N,x^k))+O(x^N))) \\ Joerg Arndt, Aug 19 2012
  • Python
    from functools import cache
@cache
def A005043(n: int) -> int:
    if n <= 1: return 1 - n
    return (n - 1) * (2 * A005043(n - 1) + 3 * A005043(n - 2)) // (n + 1)
print([A005043(n) for n in range(32)]) # Peter Luschny, Nov 20 2022
  • Sage
    A005043 = lambda n: (-1)^n*jacobi_P(n,1,-n-3/2,-7)/(n+1)
[simplify(A005043(n)) for n in (0..29)]
# Peter Luschny, Sep 23 2014
  • Sage
    def ms():
    a, b, c, d, n = 0, 1, 1, -1, 1
    yield 1
    while True:
        yield -b + (-1)^n*d
        n += 1
        a, b = b, (3*(n-1)*n*a+(2*n-1)*n*b)/((n+1)*(n-1))
        c, d = d, (3*(n-1)*c-(2*n-1)*d)/n
A005043 = ms()
print([next(A005043) for  in range(32)]) # _Peter Luschny, May 16 2016

Formula

a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*A000108(k). a(n) = (1/(n+1)) * Sum_{k=0..ceiling(n/2)} binomial(n+1, k)*binomial(n-k-1, k-1), for n > 1. - Len Smiley. [Comment from Amitai Regev (amitai.regev(AT)weizmann.ac.il), Mar 02 2010: the latter sum should be over the range k=1..floor(n/2).]
G.f.: (1 + x - sqrt(1-2*x-3*x^2))/(2*x*(1+x)).
G.f.: 2/(1+x+sqrt(1-2*x-3*x^2)). - Paul Peart (ppeart(AT)fac.howard.edu), May 27 2000
a(n+1) + (-1)^n = a(0)*a(n) + a(1)*a(n-1) + ... + a(n)*a(0). - Bernhart
a(n) = (1/(n+1)) * Sum_{i} (-1)^i*binomial(n+1, i)*binomial(2*n-2*i, n-i). - Bernhart
G.f. A(x) satisfies A = 1/(1+x) + x*A^2.
E.g.f.: exp(x)*(BesselI(0, 2*x) - BesselI(1, 2*x)). - Vladeta Jovovic, Apr 28 2003
a(n) = A001006(n-1) - a(n-1).
a(n+1) = Sum_{k=0..n} (-1)^k*A026300(n, k), where A026300 is the Motzkin triangle.
a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*binomial(k, floor(k/2)). - Paul Barry, Jan 27 2005
a(n) = Sum_{k>=0} A086810(n-k, k). - Philippe Deléham, May 30 2005
a(n+2) = Sum_{k>=0} A064189(n-k, k). - Philippe Deléham, May 31 2005
Moment representation: a(n) = (1/(2*Pi))*Int(x^n*sqrt((1+x)(3-x))/(1+x),x,-1,3). - Paul Barry, Jul 09 2006
Inverse binomial transform of A000108 (Catalan numbers). - Philippe Deléham, Oct 20 2006
a(n) = (2/Pi)* Integral_{x=0..Pi} (4*cos(x)^2-1)^n*sin(x)^2 dx. - Andrew V. Sutherland, Dec 02 2007
G.f.: 1/(1-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-... (continued fraction). - Paul Barry, Jan 22 2009
G.f.: 1/(1+x-x/(1-x/(1+x-x/(1-x/(1+x-x/(1-... (continued fraction). - Paul Barry, May 16 2009
G.f.: 1/(1-x^2/(1-x/(1-x/(1-x^2/(1-x/(1-x/(1-x^2/(1-x/(1-... (continued fraction). - Paul Barry, Mar 02 2010
a(n) = -(-1)^n * hypergeom([1/2, n+2],[2],4/3) / sqrt(-3). - Mark van Hoeij, Jul 02 2010
a(n) = (-1)^n*hypergeometric([-n,1/2],[2],4). - Peter Luschny, Aug 15 2012
Let A(x) be the g.f., then x*A(x) is the reversion of x/(1 + x^2*Sum_{k>=0} x^k); see A215340 for the correspondence to Dyck paths without length-1 ascents. - Joerg Arndt, Aug 19 2012 and Apr 16 2013
a(n) ~ 3^(n+3/2)/(8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 02 2012
G.f.: 2/(1+x+1/G(0)), where G(k) = 1 + x*(2+3*x)*(4*k+1)/( 4*k+2 - x*(2+3*x)*(4*k+2)*(4*k+3)/(x*(2+3*x)*(4*k+3) + 4*(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 05 2013
D-finite (an alternative): (n+1)*a(n) = 3*(n-2)*a(n-3) + (5*n-7)*a(n-2) + (n-2)*a(n-1), n >= 3. - Fung Lam, Mar 22 2014
Asymptotics: a(n) = (3^(n+2)/(sqrt(3*n*Pi)*(8*n)))*(1-21/(16*n) + O(1/n^2)) (with contribution by Vaclav Kotesovec). - Fung Lam, Mar 22 2014
a(n) = T(2*n-1,n)/n, where T(n,k) = triangle of A180177. - Vladimir Kruchinin, Sep 23 2014
a(n) = (-1)^n*JacobiP(n,1,-n-3/2,-7)/(n+1). - Peter Luschny, Sep 23 2014
a(n) = Sum_{k=0..n} C(n,k)*(C(k,n-k)-C(k,n-k-1)). - Peter Luschny, Oct 01 2014
Conjecture: a(n) = A002426(n) - A005717(n), n > 0. - Mikhail Kurkov, Feb 24 2019 [The conjecture is true. - Amiram Eldar, May 17 2024]
a(n) = A309303(n) + A309303(n+1). - Vladimir Reshetnikov, Jul 22 2019
From Peter Bala, Feb 11 2022: (Start)
a(n) = A005773(n+1) - 2*A005717(n) for n >= 1.
Conjectures: for n >= 1, n divides a(2*n+1) and 2*n-1 divides a(2*n). (End)

Extensions

Thanks to Laura L. M. Yang (yanglm(AT)hotmail.com) for a correction, Aug 29 2004
Name changed to Riordan numbers following a suggestion from Ira M. Gessel. - N. J. A. Sloane, Jul 24 2020

A026300 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) + T(n-1,k) for k = 1,2,...,n-1 and T(n,n) = T(n-1,n-2) + T(n-1,n-1).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 5, 4, 1, 4, 9, 12, 9, 1, 5, 14, 25, 30, 21, 1, 6, 20, 44, 69, 76, 51, 1, 7, 27, 70, 133, 189, 196, 127, 1, 8, 35, 104, 230, 392, 518, 512, 323, 1, 9, 44, 147, 369, 726, 1140, 1422, 1353, 835, 1, 10, 54, 200, 560, 1242, 2235, 3288, 3915, 3610, 2188
Offset: 0

Views

Author

Clark Kimberling

Keywords

Comments

Right-hand columns have g.f. M^k, where M is g.f. of Motzkin numbers.
Consider a semi-infinite chessboard with squares labeled (n,k), ranks or rows n >= 0, files or columns k >= 0; number of king-paths of length n from (0,0) to (n,k), 0 <= k <= n, is T(n,n-k). - Harrie Grondijs, May 27 2005. Cf. A114929, A111808, A114972.

Examples

			Triangle starts:
  [0] 1;
  [1] 1, 1;
  [2] 1, 2,  2;
  [3] 1, 3,  5,   4;
  [4] 1, 4,  9,  12,   9;
  [5] 1, 5, 14,  25,  30,  21;
  [6] 1, 6, 20,  44,  69,  76,   51;
  [7] 1, 7, 27,  70, 133, 189,  196,  127;
  [8] 1, 8, 35, 104, 230, 392,  518,  512,  323;
  [9] 1, 9, 44, 147, 369, 726, 1140, 1422, 1353, 835.

References

  • Harrie Grondijs, Neverending Quest of Type C, Volume B - the endgame study-as-struggle.
  • A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.

Links

Crossrefs

Reflected version is in A064189.
Row sums are in A005773.
T(n,n) are Motzkin numbers A001006.
Other columns of T include A002026, A005322, A005323.
Cf. A099323, A097357, A005043, A059738, A027907, A020474, A059738.

Programs

  • Haskell
    a026300 n k = a026300_tabl !! n !! k
a026300_row n = a026300_tabl !! n
a026300_tabl = iterate (\row -> zipWith (+) ([0,0] ++ row) $
                                zipWith (+) ([0] ++ row) (row ++ [0])) [1]
-- Reinhard Zumkeller, Oct 09 2013
  • Maple
    A026300 := proc(n,k)
   add(binomial(n,2*i+n-k)*(binomial(2*i+n-k,i) -binomial(2*i+n-k,i-1)), i=0..floor(k/2));
end proc: # R. J. Mathar, Jun 30 2013
  • Mathematica
    t[n_, k_] := Sum[ Binomial[n, 2i + n - k] (Binomial[2i + n - k, i] - Binomial[2i + n - k, i - 1]), {i, 0, Floor[k/2]}]; Table[ t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Robert G. Wilson v, Jan 03 2011 *)
t[, 0] = 1; t[n, 1] := n; t[n_, k_] /; k>n || k<0 = 0; t[n_, n_] := t[n, n] = t[n-1, n-2]+t[n-1, n-1]; t[n_, k_] := t[n, k] = t[n-1, k-2]+t[n-1, k-1]+t[n-1, k]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 18 2014 *)
T[n_, k_] := Binomial[n, k] Hypergeometric2F1[1/2 - k/2, -k/2, n - k + 2, 4];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Peter Luschny, Mar 21 2018 *)
  • PARI
    tabl(nn) = {for (n=0, nn, for (k=0, n, print1(sum(i=0, k\2, binomial(n, 2*i+n-k)*(binomial(2*i+n-k, i)-binomial(2*i+n-k, i-1))), ", ");); print(););} \\ Michel Marcus, Jul 25 2015

Formula

T(n,k) = Sum_{i=0..floor(k/2)} binomial(n, 2i+n-k)*(binomial(2i+n-k, i) - binomial(2i+n-k, i-1)). - Herbert Kociemba, May 27 2004
T(n,k) = A027907(n,k) - A027907(n,k-2), k<=n.
Sum_{k=0..n} (-1)^k*T(n,k) = A099323(n+1). - Philippe Deléham, Mar 19 2007
Sum_{k=0..n} (T(n,k) mod 2) = A097357(n+1). - Philippe Deléham, Apr 28 2007
Sum_{k=0..n} T(n,k)*x^(n-k) = A005043(n), A001006(n), A005773(n+1), A059738(n) for x = -1, 0, 1, 2 respectively. - Philippe Deléham, Nov 28 2009
T(n,k) = binomial(n, k)*hypergeom([1/2 - k/2, -k/2], [n - k + 2], 4). - Peter Luschny, Mar 21 2018
T(n,k) = [t^(n-k)] [x^n] 2/(1 - (2*t + 1)*x + sqrt((1 + x)*(1 - 3*x))). - Peter Luschny, Oct 24 2018
The n-th row polynomial R(n,x) equals the n-th degree Taylor polynomial of the function (1 - x^2)*(1 + x + x^2)^n expanded about the point x = 0. - Peter Bala, Feb 26 2023

Extensions

Corrected and edited by Johannes W. Meijer, Oct 05 2010

A002026 Generalized ballot numbers (first differences of Motzkin numbers).

Original entry on oeis.org

0, 1, 2, 5, 12, 30, 76, 196, 512, 1353, 3610, 9713, 26324, 71799, 196938, 542895, 1503312, 4179603, 11662902, 32652735, 91695540, 258215664, 728997192, 2062967382, 5850674704, 16626415975, 47337954326, 135015505407, 385719506620, 1103642686382, 3162376205180, 9073807670316, 26068895429376
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of ordered trees with n+1 edges, having root of degree 2 and nonroot nodes of outdegree at most 2.
Sequence without the initial 0 is the convolution of the sequence of Motzkin numbers (A001006) with itself.
Number of horizontal steps at level zero in all Motzkin paths of length n. Example: a(3)=5 because in the four Motzkin paths of length 3, (HHH), (H)UD, UD(H) and UHD, where H=(1,0), U=(1,1), D=(1,-1), we have altogether five horizontal steps H at level zero (shown in parentheses).
Number of peaks at level 1 in all Motzkin paths of length n+1. Example: a(3)=5 because in the nine Motzkin paths of length 4, HHHH, HH(UD), H(UD)H, HUHD, (UD)HH, (UD)(UD), UHDH, UHHD and UUDD (where H=(1,0), U=(1,1), D=(1,-1)), we have five peaks at level 1 (shown between parentheses).
a(n) = number of Motzkin paths of length n+1 that start with an up step. - David Callan, Jul 19 2004
Could be called a Motzkin transform of A130716 because the g.f. is obtained from the g.f. x*A130716(x)= x(1+x+x^2) (offset changed to 1) by the substitution x -> x*A001006(x) of the independent variable. - R. J. Mathar, Nov 08 2008
For n >= 1, a(n) is the number of length n permutations sorted to the identity by a consecutive-123-avoiding stack followed by a classical-21-avoiding stack. - Kai Zheng, Aug 28 2020

References

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

Links

Crossrefs

Cf. A001006, A026300, A026107, row sums of A348840 and of A348869.
A diagonal of triangle A020474.
See A244884 for a variant.

Programs

  • Mathematica
    CoefficientList[Series[4x/(1-x+Sqrt[1-2x-3x^2])^2,{x,0,30}],x] (* Harvey P. Dale, Jul 18 2011 *)
a[n_] := n*Hypergeometric2F1[(1-n)/2, 1-n/2, 3, 4]; Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Aug 13 2012 *)
  • PARI
    my(z='z+O('z^66)); concat(0,Vec(4*z/(1-z+sqrt(1-2*z-3*z^2))^2)) \\ Joerg Arndt, Mar 08 2016

Formula

a(n) = A001006(n+1) - A001006(n).
a(n) = Sum_{b = 1..(n+1)/2} C(n, 2b-1)*C(2b, b)/(b+1).
Number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer, s(0) = 0 = s(n), s(1) = 1, |s(i) - s(i-1)| <= 1 for i >= 2, Also T(n, n), where T is the array defined in A026105.
a(n) = Sum_{k=0..n-1} Sum_{i=0..k} C(k, 2i)*A000108(i+1). - Paul Barry, Jul 18 2003
G.f.: 4*z/(1-z+sqrt(1-2*z-3*z^2))^2. - Emeric Deutsch, Dec 27 2003
a(n) = A005043(n+2) - A005043(n). - Paul Barry, Apr 17 2005
D-finite with recurrence: (n+3)*a(n) +(-3*n-4)*a(n-1) +(-n-1)*a(n-2) +3*(n-2)*a(n-3)=0. - R. J. Mathar, Dec 03 2012
a(n) ~ 3^(n+3/2) / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Feb 01 2014
G.f.: A(z) satisfies z*A(z) = (1-z)*M(z) - 1, where M(z) is the g.f. of A001006. - Gennady Eremin, Feb 09 2021
a(0) = 0, a(1) = 1; a(n) = 2 * a(n-1) + a(n-2) + Sum_{k=0..n-3} a(k) * a(n-k-3). - Ilya Gutkovskiy, Nov 09 2021
G.f.: x*M(x)^2 where M(x) = (1 - x - sqrt(1 - 2*x - 3*x^2)) / (2*x^2) is the g.f. of the Motzkin numbers A001006. - Peter Bala, Feb 05 2024

Extensions

Additional comments from Emeric Deutsch, Dec 27 2003

A005322 Column of Motzkin triangle.

Original entry on oeis.org

1, 3, 9, 25, 69, 189, 518, 1422, 3915, 10813, 29964, 83304, 232323, 649845, 1822824, 5126520, 14453451, 40843521, 115668105, 328233969, 933206967, 2657946907, 7583013474, 21668135850, 62007732605, 177696228411, 509899901553, 1464990733969, 4214045993925
Offset: 2

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of returns (i.e., down steps hitting the x-axis) in all Motzkin paths of length n. E.g., a(4)=9 because in the nine Motzkin paths of length 4, HHHH, HHU(D), HU(D)H, HUH(D), U(D)HH, U(D)U(D), UH(D)H, UHH(D) and UUD(D), where H=(1,0), U=(1,1), D=(1,-1), we have altogether nine down steps D hitting the x-axis (shown in parentheses). - Emeric Deutsch, Dec 26 2003
Number of nonnegative H,U,D paths of length n that end at height 2. Bijection to the Deutsch manifestation above: turn the last U carrying the path up to height 2 into a D. This gives a Motzkin n-path with a marked return D. - David Callan, Jun 07 2006
Number of Motzkin paths of length n+2, starting with a (1,1) step, ending with a (1,-1) step and touching the x-axis at least three times. Example: a(3)=3 because we have UDHUD, UDUHD and UHDUD, where H=(1,0), U=(1,1), D=(1,-1). - Emeric Deutsch, Jul 27 2006

References

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

Links

Crossrefs

Cf. A026300, A001006.
A diagonal of triangle A020474.

Programs

  • Maple
    M:=(1-z-sqrt(1-2*z-3*z^2))/2/z^2: ser:=series(z^2*M^3,z=0,35): seq(coeff(ser,z,n),n=2..28); # Emeric Deutsch, Jul 27 2006
  • Mathematica
    CoefficientList[Series[2*(1 - x - Sqrt[1 - 2*x - 3*x^2])/(1 - x + Sqrt[1 - 2*x - 3*x^2])^2, {x,0,50}], x] (* G. C. Greubel, Mar 03 2017 *)
  • Maxima
    a(n):=sum((k-2)*k*sum(binomial(-k+2*j-1,j-1)*(-1)^(n+2-j)*binomial(n+2,j),j,k,n+2),k,1,n+2)/(n+2); /* Vladimir Kruchinin, Sep 26 2011 */
  • PARI
    x='x+O('x^50); Vec(2*(1 - x - sqrt(1 - 2*x - 3*x^2))/(1 - x + sqrt(1 - 2*x - 3*x^2))^2) \\ G. C. Greubel, Mar 03 2017

Formula

a(n) = number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer and |s(i) - s(i-1)| <= 1 for i = 1, 2, ..., n, s(0) = 0, s(n) = 2.
G.f.: 2(1-z-q)/(1-z+q)^2, where q=sqrt(1-2z-3z^2). - Emeric Deutsch, Dec 26 2003
G.f.: z^2*M^3, where M=1+zM+z^2*M^2 is the g.f. of the Motzkin numbers (A001006). - Emeric Deutsch, Jul 27 2006
a(n) = -sqrt(-3)*(-1)^n*(3*n*(13*n+27)*hypergeom([1/2, n],[1],4/3) -hypergeom([1/2, n+1],[1],4/3)*(41*n^2+115*n+60))/(2*(n+3)*(n+5)*(n+6)). - Mark van Hoeij, Nov 12 2009
a(n) = sum(k=1..n+2, (k-2)*k*sum(j=k..n+2, C(-k+2*j-1,j-1)*(-1)^(n+2-j) * C(n+2,j)))/(n+2). - Vladimir Kruchinin, Sep 26 2011
D-finite with recurrence a(n)*(4+n) = (9 + 4*n) a(n-1) - (n-1)*a(n-2) - 6*(n-1)*a(n-3). - Simon Plouffe, Feb 09 2012, corrected for offset Aug 17 2022
a(n) ~ 3^(n + 5/2) / (2*sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 17 2019
D-finite with recurrence -(n+4)*(n-2)*a(n) +n*(2*n+1)*a(n-1) +3*n*(n-1)*a(n-2)=0. - R. J. Mathar, Aug 17 2022

A005323 Column of Motzkin triangle.

Original entry on oeis.org

1, 4, 14, 44, 133, 392, 1140, 3288, 9438, 27016, 77220, 220584, 630084, 1800384, 5147328, 14727168, 42171849, 120870324, 346757334, 995742748, 2862099185, 8234447672, 23713180780, 68350541480, 197188167735, 569371325796
Offset: 3

Views

Author

N. J. A. Sloane

Keywords

References

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

Links

Crossrefs

Cf. A026300.
A diagonal of triangle A020474.

Programs

  • Maple
    A005323 := proc(n)
    if n <= 5 then
        op(n-2,[1,4,14]) ;
    else
        n*(2*n+1)*procname(n-1)+3*n*(n-1)*procname(n-2) ;
        %/(n+5)/(n-3) ;
    end if;
end proc:
seq(A005323(n),n=3..20) ; # R. J. Mathar, Aug 17 2022
  • Mathematica
    a[3] = 1; a[4] = 4;
a[n_] := a[n] = (n(3(n-1) a[n-2] + (2n+1) a[n-1])) / ((n-3)(n+5));
Table[a[n], {n, 3, 30}] (* Jean-François Alcover, Jul 27 2018 *)
  • Maxima
    a(n):=(4*sum(binomial(j,2*j-n+3)*binomial(n+1,j),j,ceiling((n-3)/2),n+1))/(n+1); /* Vladimir Kruchinin, Mar 18 2014 */

Formula

a(n) = number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer and |s(i) - s(i-1)| <= 1 for i = 1, 2, ..., n, s(0) = 0, s(n) = 3.
G.f.: z^3*M^4, where M is g.f. of Motzkin numbers (A001006).
a(n) = 4*(-3)^(1/2)*(-1)^n*n*((-3*n^3-9*n^2-6*n-9)*hypergeom([1/2, n],[1],4/3)+(2*n^3+n^2-17*n-13)*hypergeom([1/2, n+1],[1],4/3))/(3*(n+1)*(n+2)*(n+3)*(n+4)*(n+5)) (for n >= 3). - Mark van Hoeij, Nov 12 2009
(n + 5) (n - 3) a(n) = n (2 n + 1) a(n - 1) + 3 n (n - 1) a(n - 2). - Simon Plouffe, Feb 09 2012, corrected for offset Aug 17 2022
a(n) = 4*sum(j=ceiling((n-3)/2)..n+1, C(j,2*j-n+3)*C(n+1,j))/(n+1). - Vladimir Kruchinin, Mar 17 2014
a(n) ~ 2 * 3^(n + 3/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 17 2019

Extensions

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003

A062105 Square array read by antidiagonals: number of ways a pawn-like piece (with the initial 2-step move forbidden and starting from any square on the back rank) can end at various squares on an infinite chessboard.

Original entry on oeis.org

1, 1, 2, 1, 3, 5, 1, 3, 8, 13, 1, 3, 9, 22, 35, 1, 3, 9, 26, 61, 96, 1, 3, 9, 27, 75, 171, 267, 1, 3, 9, 27, 80, 216, 483, 750, 1, 3, 9, 27, 81, 236, 623, 1373, 2123, 1, 3, 9, 27, 81, 242, 694, 1800, 3923, 6046, 1, 3, 9, 27, 81, 243, 721, 2038, 5211, 11257, 17303, 1, 3, 9, 27
Offset: 0

Views

Author

Antti Karttunen, May 30 2001

Keywords

Comments

Table formatted as a square array shows the top-left corner of the infinite board.
The same array can also be constructed by the method used for constructing A217536, except with a top row consisting entirely of 1's instead of the natural numbers. - WG Zeist, Aug 25 2024

Examples

			Array begins:
 1       1       1       1       1       1       1       1       1       1       1
 2       3       3       3       3       3       3       3       3       3       3
 5       8       9       9       9       9       9       9       9       9 ...
 13      22      26      27      27      27      27      27      27 ...
 35      61      75      80      81      81      81 ...
 96      171     216     236     242     243 ...
 267     483     623     694     721 ...
 750     1373    1800    2038 ...
 2123    3923    5211 ...
 6046    11257 ...
 17303  ...
 ...
Formatted as a triangle:
 1,
 1, 2,
 1, 3, 5,
 1, 3, 8, 13,
 1, 3, 9, 22, 35,
 1, 3, 9, 26, 61, 96,
 1, 3, 9, 27, 75, 171, 267,
 1, 3, 9, 27, 80, 216, 483, 750,
 1, 3, 9, 27, 81, 236, 623, 1373, 2123,
 1, 3, 9, 27, 81, 242, 694, 1800, 3923, 6046,
 1, 3, 9, 27, 81, 243, 721, 2038, 5211, 11257, 17303,
 ...

Links

Crossrefs

A005773 gives the left column of the table. A000244 (powers of 3) gives the diagonal of the table. Variant of A062104. Cf. also A062103, A020474, A217536.

Programs

  • Maple
    [seq(CPTVSeq(j),j=0..91)]; CPTVSeq := n -> ChessPawnTriangleV( (2+(n-((trinv(n)*(trinv(n)-1))/2))), ((((trinv(n)-1)*(((1/2)*trinv(n))+1))-n)+1) );
ChessPawnTriangleV := proc(r,c) option remember; if(r < 2) then RETURN(0); fi; if(c < 1) then RETURN(0); fi; if(2 = r) then RETURN(1); fi; RETURN(ChessPawnTriangleV(r-1,c-1)+ChessPawnTriangleV(r-1,c)+ChessPawnTriangleV(r-1,c+1)); end;
M:=12; T:=Array(0..M,0..M,0);
T[0,0]:=1; T[1,1]:=1;
for i from 1 to M do T[i,0]:=0; od:
for n from 2 to M do for k from 1 to n do
T[n,k]:= T[n,k-1]+T[n-1,k-1]+T[n-2,k-1];
od: od;
rh:=n->[seq(T[n,k],k=0..n)];
for n from 0 to M do lprint(rh(n)); od: # N. J. A. Sloane, Apr 11 2020
  • Mathematica
    T[n_, k_] := T[n, k] = If[n < 1 || k < 1, 0, If[n == 1, 1, T[n - 1, k - 1] + T[n - 1, k] + T[n - 1, k + 1]]]; Table[T[n - k + 1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Mar 04 2016, adapted from PARI *)
  • PARI
    T(n,k)=if(n<1 || k<1,0,if(n==1,1,T(n-1,k-1)+T(n-1,k)+T(n-1,k+1)))

Extensions

Edited by N. J. A. Sloane, May 22 2014

A005324 Column of Motzkin triangle A026300.

Original entry on oeis.org

1, 5, 20, 70, 230, 726, 2235, 6765, 20240, 60060, 177177, 520455, 1524120, 4453320, 12991230, 37854954, 110218905, 320751445, 933149470, 2714401580, 7895719634, 22969224850, 66829893650, 194486929650, 566141346225, 1648500576021
Offset: 4

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) = number of (s(0), s(1), ..., s(n)) such that s(i) is a nonnegative integer and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 0, s(n) = 4. - Clark Kimberling
a(n) = T(n,n-4), where T is the array in A026300.

References

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

Links

Crossrefs

Cf. A026300.
A diagonal of triangle A020474.

Programs

  • Maple
    A005324 := proc(n)
    if n <= 6 then
        op(n-3,[1,5,20]) ;
    else
        n*(2*n+1)*procname(n-1)+3*n*(n-1)*procname(n-2) ;
        %/(n+6)/(n-4) ;
    end if;
end proc:
seq(A005324(n),n=4..20) ; # R. J. Mathar, Aug 17 2022
  • Mathematica
    T[n_, k_] := Sum[m = 2j+n-k; Binomial[n, m] (Binomial[m, j] - Binomial[m, j-1]), {j, 0, k/2}];
a[n_] := T[n, n-4];
Table[a[n], {n, 4, 30}] (* Jean-François Alcover, Jul 27 2018 *)
  • Maxima
    a(n) := 5*sum(binomial(j,2*j-n+4)*binomial(n+1,j),j,ceiling((n-4)/2),(n+1))/(n+1); /* Vladimir Kruchinin, Mar 18 2014 */

Formula

G.f.: z^4*M^5, where M is g.f. of Motzkin numbers (A001006).
a(n) = (-5*I*(-1)^n*(n^4-6*n^3-43*n^2-24*n+36)*3^(1/2)*hypergeom([1/2, n+2],[1],4/3)+15*I*(-1)^n*(n^4+6*n^3+17*n^2+24*n-12)*3^(1/2)*hypergeom([1/2, n+1],[1],4/3))/(6*(n+3)*(n+2)*(n+4)*(n+5)*(n+6)). - Mark van Hoeij, Oct 29 2011
a(n) (n + 6) (n - 4) = n (2 n + 1) a(n - 1) + 3 n (n - 1) a(n - 2). - Simon Plouffe, Feb 09 2012, corrected for offset Aug 17 2022
a(n) = 5*sum(j=ceiling((n-4)/2)..(n+1), binomial(j,2*j-n+4)*binomial(n+1,j))/(n+1). - Vladimir Kruchinin, Mar 17 2014
a(n) = A026300(n,n-4). - R. J. Mathar, Aug 17 2022

A005325 Column of Motzkin triangle.

Original entry on oeis.org

1, 6, 27, 104, 369, 1242, 4037, 12804, 39897, 122694, 373581, 1128816, 3390582, 10136556, 30192102, 89662216, 265640691, 785509362, 2319218869, 6839057544, 20147488020, 59306494520, 174466248840, 512987904000, 1507780192035, 4430417492826, 13015498076181
Offset: 5

Views

Author

N. J. A. Sloane

Keywords

References

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

Links

Crossrefs

Cf. A026300, A026126, A001006.
A diagonal of triangle A020474.

Programs

  • Mathematica
    RecurrenceTable[{3(-1+n)*n*a[-2+n]+n*(1+2n)*a[-1+n]-(-5+n)*(7+n)*a[n]==0, a[5]==1,a[6]==6}, a,{n,5,20}] (* Vaclav Kotesovec, Oct 05 2012 *)
a = DifferenceRoot[Function[{b, n}, {(-2n^2 - 25n - 78)b[n+1] - 3(n+5)(n+6) b[n] + (n+1)(n+13)b[n+2] == 0, b[1] == 1, b[2] == 6}]][# - 4]&;
Table[a[n], {n, 5, 31}] (* Jean-François Alcover, Jan 24 2019 *)
  • Maxima
    a(n) := 6*sum(binomial(j,2*j-n+5)*binomial(n+1,j),j,ceiling((n-5)/2),(n+1))/(n+1);
/* Vladimir Kruchinin, Mar 18 2014 */

Formula

G.f.: z^5*M^6, where M=1+z*M+z^2*M^2 is the g.f. for the Motzkin numbers (A001006). - Emeric Deutsch, Aug 13 2004
a(n) = (sqrt(-3)/81)*((-1)^n*n*(4*n^3-15*n^2-55*n+102)/(n+7)/(n+3)/(n+2)*hypergeom([1/2, n+7],[3],4/3)-(-1)^n*(4*n^4-17*n^3+23*n^2+ 242*n-288)/(n+7)/(n+3)/(n+2)*hypergeom([1/2, n+6],[3],4/3)). - Mark van Hoeij, Oct 29 2011.
a(n) (n + 11) (n - 1) = (n + 4) (3 n + 9) a(n - 2) + (n + 4) (2 n + 9) a(n - 1). - Simon Plouffe, Feb 09 2012
a(n) ~ 3^(n+5/2)/(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Oct 05 2012
a(n) = 6*sum(j=ceiling((n-5)/2)..(n+1), C(j,2*j-n+5)*C(n+1,j))/(n+1). - Vladimir Kruchinin, Mar 17 2014

Extensions

More terms from Vincenzo Librandi, May 03 2013

A342912 a(n) = [x^n] (1 - 2*x - sqrt((1 - 3*x)/(1 + x)))/(2*x^3).

Original entry on oeis.org

1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, 11298, 30537, 83097, 227475, 625992, 1730787, 4805595, 13393689, 37458330, 105089229, 295673994, 834086421, 2358641376, 6684761125, 18985057351, 54022715451, 154000562758, 439742222071, 1257643249140, 3602118427251
Offset: 0

Views

Author

Peter Luschny, Apr 18 2021

Keywords

Crossrefs

The diagonal sums of the Motzkin triangle A064189 (with the Motzkin numbers A001006 as first column), the row sums of A020474, and a shifted version of the Riordan numbers A005043.

Programs

  • Maple
    gf := (1 - 2*x - sqrt((1 - 3*x)/(1 + x)))/(2*x^3): ser := series(gf, x, 36):
seq(coeff(ser, x, n), n = 0..30);
a := proc(n) option remember; `if`(n < 3, [1, 1, 3][n + 1],
((2*a(n - 1) + 3*a(n - 2))*(n + 1))/(n + 3)) end: seq(a(n), n=0..30);
  • Mathematica
    a[n_] := (-1)^n*HypergeometricPFQ[{1/2, -2 - n}, {2}, 4]
Table[a[n], {n, 0, 30}]
  • Python
    def rnum():
    a, b, n = 1, 3, 3
    yield 1
    yield 1
    while True:
        yield b
        n += 1
        a, b = b, (n*(3*a + 2*b))//(n + 2)
A342912 = rnum()
print([next(A342912) for _ in range(31)])

Formula

D-finite with recurrence a(n) = (2*a(n - 1) + 3*a(n - 2))*(n + 1)/(n + 3) for n >= 3.
a(n) = (-1)^n*hypergeom([1/2, -2 - n], [2], 4).
a(n) ~ (3^(n + 7/2)*(16*n + 11))/(128*sqrt(Pi)*(n + 2)^(5/2)).
G.f.: (M(x) - 1) / (x + x^2) where M(x) is the g.f. of A001006. - Werner Schulte, Jan 05 2025
Showing 1-10 of 15 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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