A086246 -id:A086246 - cp's OEIS frontend

A144218 Equals product A*B, where A is an infinite lower triangular matrix with A086246 in every column and B is the diagonal matrix with A001006 as diagonal.

1, 1, 1, 1, 1, 2, 2, 1, 2, 4, 4, 2, 2, 4, 9, 9, 4, 4, 4, 9, 21, 21, 9, 8, 8, 9, 21, 51, 51, 21, 18, 16, 18, 21, 51, 127, 127, 51, 42, 36, 36, 42, 51, 127, 323, 323, 127, 102, 84, 81, 84, 102, 127, 323, 835, 835, 323, 254, 204, 189, 189, 204, 254, 323, 835, 2188

Offset: 0

Gary W. Adamson, Sep 14 2008

Right border is A001006.
Row sums give A001006 without the initial 1.
Left border is A086246 (A001006 with an additional leading 1).
Sum of n-th row terms = rightmost term of next row.

			First few rows of the triangle:
    1;
    1,   1;
    1,   1,   2;
    2,   1,   2,   4;
    4,   2,   2,   4,   9;
    9,   4,   4,   4,   9,  21;
   21,   9,   8,   8,   9,  21,  51;
   51,  21,  18,  16,  18,  21,  51, 127;
  127,  51,  42,  36,  36,  42,  51, 127, 323;
  323, 127, 102,  84,  81,  84, 102, 127, 323, 835;
  835, 323, 254, 204, 189, 189, 204, 254, 323, 835, 2188;
  ...
Row 4 = (4, 2, 2, 4, 9) = termwise products of (4, 2, 1, 1, 1) and (1, 1, 2, 4, 9) = (4*1, 2*1, 1*2, 1*4, 1*9).

Paul Barry, Invariant number triangles, eigentriangles and Somos-4 sequences, arXiv preprint arXiv:1107.5490 [math.CO], 2011.

Cf. A001006, A086246.

nmax = 10;
T[0, 0] = T[1, 0] = 1;
T[n_, 0]  := Hypergeometric2F1[3/2, 1-n, 3, 4] // Abs;
T[n_, n_] := Hypergeometric2F1[(1-n)/2, -n/2, 2, 4];
row[n_] := row[n] = Table[T[m, 0], {m, n, 0, -1}]*Table[T[m, m], {m, 0, n} ];
T[n_, k_] /; 0Jean-François Alcover, Aug 07 2018 *)

Edited by Joerg Arndt, Jan 26 2024

A348197 Composition of the g.f. of A086246 with itself.

Original entry on oeis.org

0, 1, 2, 4, 10, 28, 84, 264, 860, 2880, 9862, 34392, 121770, 436688, 1583146, 5793216, 21370806, 79391536, 296760222, 1115327844, 4212125662, 15976390684, 60833679424, 232452408632, 891060970152, 3425639505624, 13204738280326, 51024408662932, 197607503526934

Offset: 0

Alexander Burstein, Oct 06 2021

nonn

G.f.: A(x) is the pseudo-involutory Riordan companion of 2*M(x)-1, where M(x) is the g.f. of A001006.
For 1 <= n <= 7, a(n) coincides with A068875(n-1).
Conjecture: a(n) > A068875(n-1) for n > 7 (equivalently, a(n) > 2*A000108(n-1) for n > 7).

Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.

Cf. A086246, A001006.

gf:= (f-> f(f(x)))(x->(1+x-sqrt(1-2*x-3*x^2))/2):
a:= n-> coeff(series(gf,x,n+1),x,n):
seq(a(n), n=0..40);  # Alois P. Heinz, Oct 06 2021

f[x_] := (1 + x - Sqrt[1 - 2*x - 3*x^2])/2; a[n_] := SeriesCoefficient[f[f[x]], {x, 0, n}]; Array[a, 25, 0] (* Amiram Eldar, Oct 06 2021 *)

f(x) = (1+x-sqrt(1-2*x-3*x^2))/2;
my(x='x+O('x^30)); concat(0, Vec(f(f(x)))) \\ Michel Marcus, Oct 06 2021

G.f.: A(x) = F(F(x)), where F(x) is the g.f. of A086246.
Let G(x) = 2*M(x) - 1, where M(x) is the g.f. of A001006 (equivalently, x*G(x) is the g.f. of A007971). Then G(-A(x)) = 1/G(x).
A(-A(x)) = -x.
a(n) ~ ((1 + sqrt(3))^(n - 1/2) * 3^(n - 1/2)) / (sqrt(Pi) * n^(3/2) * 2^n). - Vaclav Kotesovec, Oct 07 2021

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

N. J. A. Sloane

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

			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.

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.

Seiichi Manyama, Table of n, a(n) for n = 0..2106 (first 501 terms from N. J. A. Sloane)
M. Abrate, S. Barbero, U. Cerruti, and N. Murru, Fixed Sequences for a Generalization of the Binomial Interpolated Operator and for some Other Operators, J. Int. Seq. 14 (2011) # 11.8.1.
M. Aigner, Motzkin Numbers, Europ. J. Comb. 19 (1998), 663-675.
M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
J. L. Arregui, Tangent and Bernoulli numbers related to Motzkin and Catalan numbers by means of numerical triangles, arXiv:math/0109108 [math.NT], 2001.
Marcello Artioli, Giuseppe Dattoli, Silvia Licciardi, and Simonetta Pagnutti, Motzkin Numbers: an Operational Point of View, arXiv:1703.07262 [math.CO], 2017.
Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects, in International Conference on Language and Automata Theory and Applications, S. Klein, C. Martín-Vide, D. Shapira (eds), Springer, Cham, pp 195-206, 2018.
Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
A. Asinowski and G. Rote, Point sets with many non-crossing matchings, arXiv preprint arXiv:1502.04925 [cs.CG], 2015.
Axel Bacher, Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths, arXiv:1802.06030 [cs.DS], 2018.
C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps, Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv preprint arXiv:1609.06473 [math.CO], 2016.
Elena Barcucci, Alberto Del Lungo, Elisa Pergola, and Renzo Pinzani, 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).
E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.
E. Barcucci, R. Pinzani and R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.
Jean-Luc Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
Jean-Luc Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016).
Jean-Luc Baril, David Bevan, and Sergey Kirgizov, Bijections between directed animals, multisets and Grand-Dyck paths, arXiv:1906.11870 [math.CO], 2019.
Jean-Luc Baril and Sergey Kirgizov, The pure descent statistic on permutations, 2016.
Jean-Luc Baril and Sergey Kirgizov, The pure descent statistic on permutations, Discrete Mathematics, 340(10) (2017), 2550-2558.
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Dyck paths with a first return decomposition constrained by height, 2017.
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Dyck paths with a first return decomposition constrained by height, Discrete Mathematics, 341(6) (2018), 1620-1628.
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Motzkin paths with a restricted first return decomposition, Integers (2019) Vol. 19, A46.
Jean-Luc Baril, Sergey Kirgizov, José L. Ramírez, and Diego Villamizar, The Combinatorics of Motzkin Polyominoes, arXiv:2401.06228 [math.CO], 2024. See pages 1 and 7.
Jean-Luc Baril, Toufik Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, 2014.
Jean-Luc Baril and J.-M. Pallo, Motzkin subposet and Motzkin geodesics in Tamari lattices, 2013.
Jean-Luc Baril, and Jean-Marcel Pallo, A Motzkin filter in the Tamari lattice, Discrete Mathematics 338(8) (2015), 1370-1378.
Jean-Luc Baril and A. Petrossian, Equivalence classes of Dyck paths modulo some statistics, 2004.
Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.
Marilena Barnabei, Flavio Bonetti, and Matteo Silimbani, Restricted involutions and Motzkin paths, Advances in Applied Mathematics 47 (2011), 102-115.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, 8 (2005), #05.4.5.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009), #09.7.6
Paul Barry, Generalized Catalan Numbers, Hankel Transforms and Somos-4 Sequences, J. Int. Seq. 13 (2010), #10.7.2.
Paul Barry, On sequences with {-1, 0, 1} Hankel transforms, arXiv:1205.2565 [math.CO], 2012.
Paul Barry, Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, 15 (2012), #12.8.2.
Paul Barry, On the Hurwitz Transform of Sequences, Journal of Integer Sequences, 15 (2012), #12.8.7.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., 22 (2019), #19.5.8.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
A. M. Baxter and L. K. Pudwell, Ascent sequences avoiding pairs of patterns, preprint, 2014.
A. M. Baxter and L. K. Pudwell, Ascent sequences avoiding pairs of patterns, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.58.
Christian Bean, Finding structure in permutation sets, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
Christian Bean, A. Claesson, and H. Ulfarsson, Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3, arXiv:1512.03226 [math.CO], 2015.
Jan Bok, Graph-indexed random walks on special classes of graphs, arXiv:1801.05498 [math.CO], 2018.
Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vince Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003 [math.CO], 2013.
Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Seminaire de Combinatoire Ph. Flajolet, Mar 28 2013.
Alin Bostan, Calcul Formel pour la Combinatoire des Marches [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017.
Alin Bostan and Manuel Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2009.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.
Henry Bottomley, Illustration of initial terms.
Rob Burns, Structure and asymptotics for Motzkin numbers modulo primes using automata, arXiv:1703.00826 [math.NT], 2017.
Alexander Burstein and J. Pantone, Two examples of unbalanced Wilf-equivalence, arXiv:1402.3842 [math.CO], 2014.
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
N. T. Cameron, Random walks, trees and extensions of Riordan group techniques, Dissertation, Howard University, 2002.
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, 8 (2005), #05.3.7.
Giulio Cerbai, Anders Claesson, Luca Ferrari, and Einar Steingrímsson, Sorting with pattern-avoiding stacks: the 132-machine, arXiv:2006.05692 [math.CO], 2020.
Gi-Sang Cheon, S.-T. Jin, and L. W. Shapiro, A combinatorial equivalence relation for formal power series, Linear Algebra and its Applications, Volume 491, 15 February 2016, Pages 123-137.
J. Cigler, Some nice Hankel determinants. arXiv:1109.1449 [math.CO], 2011.
Johann Cigler and Christian Krattenthaler, Hankel determinants of linear combinations of moments of orthogonal polynomials, arXiv:2003.01676 [math.CO], 2020.
J. B. Cosgrave, The Gauss-Factorial Motzkin connection (Maple worksheet, change suffix to .mw).
R. De Castro, A. L. Ramírez, and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv:1310.2449 [cs.DM], 2013.
J. Cigler, Hankel determinants of some polynomial sequences, preprint, 2012.
Colin Defant, Motzkin intervals and valid hook configurations, arXiv:1904.10451 [math.CO], 2019.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
C. Defant and K. Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.
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 [math.CO], 2011.
Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv:1210.6908 [math.CO], 2012.
I. Dolinka, J. East, A. Evangelou, D. FitzGerald, and N. Ham, Idempotent Statistics of the Motzkin and Jones Monoids, arXiv:1507.04838 [math.CO], 2015.
I. Dolinka, J. East, and R. D. Gray, Motzkin monoids and partial Brauer monoids, arXiv:1512.02279 [math.GR], 2015.
Robert Donaghey, Restricted plane tree representations for four Motzkin-Catalan equations, J. Combin. Theory, Series B, Vol. 22, No. 2 (1977), pp. 114-121.
Robert Donaghey, Automorphisms on Catalan trees and bracketings, Journal of Combinatorial Theory, Series B, Vol. 29, No. 1 (August 1980), pp. 75-90.
Robert Donaghey and Louis W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, Vol. 23, No. 3 (1977), pp. 291-301.
Robert W. Donley Jr, Binomial arrays and generalized Vandermonde identities, arXiv:1905.01525 [math.CO], 2019.
Ivana Đurđev, Igor Dolinka, and James East, Sandwich semigroups in diagram categories, arXiv:1910.10286 [math.GR], 2019.
E. S. Egge, Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations, arXiv:math/0307050 [math.CO], 2003, sec. 8.
S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, 2017.
Gennady Eremin, Generating function for Naturalized Series: The case of Ordered Motzkin Words, arXiv:2002.08067 [math.CO], 2020.
Gennady Eremin, Naturalized bracket row and Motzkin triangle, arXiv:2004.09866 [math.CO], 2020.
Gennady Eremin, Walking in the OEIS: From Motzkin numbers to Fibonacci numbers. The "shadows" of Motzkin numbers, arXiv:2108.10676 [math.CO], 2021.
Jackson Evoniuk, Steven Klee, and Van Magnan, Enumerating Minimal Length Lattice Paths, J. Int. Seq., 21 (2018), #18.3.6.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv:1203.6792 [math.CO], 2012 and J. Int. Seq. 17 (2014) #14.1.5.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see pages 68 and 81.
Rigoberto Flórez, Leandro Junes, and José L. Ramírez, Further Results on Paths in an n-Dimensional Cubic Lattice, Journal of Integer Sequences, 21 (2018), #18.1.2.
Juan B. Gil and Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018. Also Discrete Mathematics (2019), Article 111705. doi:10.1016/j.disc.2019.111705
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Samuele Giraudo, The combinator M and the Mockingbird lattice, arXiv:2204.03586 [math.CO], 2022.
Taras Goy and Mark Shattuck, Determinant identities for the Catalan, Motzkin and Schröder numbers, Art Discrete Appl. Math. Vol. 7 (2024), #P1.09.
Taras Goy and Mark Shattuck, Determinants of some Hessenberg-Toeplitz matrices with Motzkin number entries, J. Integer Seq., 26 (2023), Art. 23.3.4.
Nils Haug, T. Prellberg, and G. Siudem, Scaling in area-weighted generalized Motzkin paths, arXiv:1605.09643 [cond-mat.stat-mech], 2016.
Nickolas Hein and Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015-2016.
Nickolas Hein and Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
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.
Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657 [math.CO], 2014.
Anders Hyllengren, Letter to N. J. A. Sloane, Oct 04 1985
Anders Hyllengren, Four integer sequences, Oct 04 1985. Observes essentially that A000984 and A002426 are inverse binomial transforms of each other, as are A000108 and A001006.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 50
Manuel Kauers and Doron Zeilberger, Counting Standard Young Tableaux With Restricted Runs, arXiv:2006.10205 [math.CO], 2020.
D. E. Knuth, Letter to L. W. Shapiro, R. K. Guy. N. J. A. Sloane, R. P. Stanley, H. Wilf regarding A001006 and A005043, Jan 18, 1989.
Nadav Kohen, Density and Symmetry in the Generalized Motzkin Numbers mod p, arXiv:2411.03681 [math.CO], 2024.
Dmitry V. Kruchinin and Vladimir V. Kruchinin, A Generating Function for the Diagonal T_{2n,n} in Triangles, Journal of Integer Sequences, 18 (2015), #15.4.6.
Marie-Louise Lackner and M. Wallner, An invitation to analytic combinatorics and lattice path counting, preprint, 2015.
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), 31-63.
K. Manes, A. Sapounakis, I. Tasoulas, and P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.
Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, 9 (2006), #06.1.5.
Toufik Mansour, Restricted 1-3-2 permutations and generalized patterns, arXiv:math/0110039 [math.CO], 2001.
Toufik Mansour and Mark Shattuck, Enumeration of Catalan and smooth words according to capacity, Integers (2025) Vol. 25, Art. No. A5. See p. 22.
V. Mazorchuk and B. Steinberg, Double Catalan monoids, arXiv:1105.5313 [math.GR], 2011.
Peter McCalla and Asamoah Nkwanta, Catalan and Motzkin Integral Representations, arXiv:1901.07092 [math.NT], 2019.
Cam McLeman and Erin McNicholas, Graph Invertibility, arXiv:1108.3588 [math.CO], 2011.
Zhousheng Mei and Suijie Wang, Pattern Avoidance of Generalized Permutations, arXiv:1804.06265 [math.CO], 2018.
D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.
T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
Heinrich Niederhausen, Inverses of Motzkin and Schroeder Paths, arXiv:1105.3713 [math.CO], 2011.
J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion, arXiv:math/0512570 [math.CO], 2005-2006.
William P. Orrick, Remark on parentheses patterns of fully parenthesized expressions, 2024.
Roy Oste and Joris Van der Jeugt, Motzkin paths, Motzkin polynomials and recurrence relations, The Electronic Journal of Combinatorics, 22(2) (2015), #P2.8.
Ran Pan, Dun Qiu, and Jeffrey Remmel, Counting Consecutive Pattern Matches in S_n(132) and S_n(123), arXiv:1809.01384 [math.CO], 2018.
Ville H. Pettersson, Enumerating Hamiltonian Cycles, The Electronic Journal of Combinatorics, 21(4) (2014), #P4.7.
Simon Plouffe, The first 4431 terms.
Helmut Prodinger, Deutsch paths and their enumeration, arXiv:2003.01918 [math.CO], 2020.
Helmut Prodinger, Cornerless, peakless, valleyless Motzkin paths (regular and skew) and applications to bargraphs, arXiv:2501.13645 [math.CO], 2025. See p. 8.
L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012.
L. Pudwell, A. Baxter, Ascent sequences avoiding pairs of patterns, 2014
L. Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015
José L. Ramírez, The Pascal Rhombus and the Generalized Grand Motzkin Paths, arXiv:1511.04577 [math.CO], 2015.
J. L. Ramírez and V. F. Sirvent, A Generalization of the k-Bonacci Sequence from Riordan Arrays, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.
Alon Regev, Amitai Regev, and Doron Zeilberger, Identities in character tables of S_n, arXiv:1507.03499 [math.CO], 2015.
John Riordan, Letter to N. J. A. Sloane, 1974.
Dan Romik, Some formulas for the central trinomial and Motzkin numbers, J. Integer Seqs., 6 (2003).
E. Rowland and R. Yassawi, Automatic congruences for diagonals of rational functions, arXiv:1310.8635 [math.NT], 2013.
E. Rowland and D. Zeilberger, A Case Study in Meta-AUTOMATION: AUTOMATIC Generation of Congruence AUTOMATA For Combinatorial Sequences, arXiv:1311.4776 [math.CO], 2013.
E. Royer, Interprétation combinatoire des moments négatifs des valeurs de fonctions L au bord de la bande critique, Ann. Sci. Ecole Norm. Sup. (4) 36 (2003), no. 4, 601-620.
Martin Rubey and Christian Stump, Double deficiencies of Dyck paths via the Billey-Jockusch-Stanley bijection, arXiv:1708.05092 [math.CO], 2017.
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 preprint, arXiv:0711.1738 [cond-mat.stat-mech], 2007-2009. Mentions this sequence.
A. Sapounakis and P. Tsikouras, On k-colored Motzkin words, Journal of Integer Sequences, 7 (2004), #04.2.5.
E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376. [Annotated scanned copy]
Paolo Serafini, An Iterative Scheme to Compute Size Probabilities in Random Graphs and Branching Processes, Scientific Programming (2018), Article ID 3791075.
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).
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, pp. 1, 3.
P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers. [Corrected annotated scanned copy]
R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, 3 (2000), #00.1.
Hua Sun and Yi Wang, A Combinatorial Proof of the Log-Convexity of Catalan-Like Numbers, J. Int. Seq. 17 (2014), #14.5.2
Yidong Sun and Fei Ma, Minors of a Class of Riordan Arrays Related to Weighted Partial Motzkin Paths, arXiv:1305.2015 [math.CO], 2013.
Zhi-Wei Sun, Conjectures involving arithmetical sequences, in: Number Theory: Arithmetic in Shangri-La (eds., S. Kanemitsu, H. Li and J. Liu), Proc. 6th China-Japan Seminar (Shanghai, August 15-17, 2011), World Sci., Singapore, 2013, pp. 244-258.
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.
Paul Tarau, On logic programming representations of lambda terms: de Bruijn indices, compression, type inference, combinatorial generation, normalization, 2015.
P. Tarau, A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations, arXiv:1507.06944 [cs.LO], 2015.
Paul Tarau, A Hiking Trip Through the Orders of Magnitude: Deriving Efficient Generators for Closed Simply-Typed Lambda Terms and Normal Forms, arXiv preprint arXiv:1608.03912 [cs.PL], 2016.
Jonas Wahl, Traces On Diagram Algebras I: Free Partition Quantum Groups, Random Lattice Paths And Random Walks On Trees, arXiv:2006.07312 [math.PR], 2020.
Chen Wang and Zhi-Wei Sun, Congruences involving central trinomial coefficients, arXiv:1910.06850 [math.NT], 2019.
Y. Wang and Z.-H. Zhang, Combinatorics of Generalized Motzkin Numbers, J. Int. Seq. 18 (2015), #15.2.4.
Yi Wang and Bao-Xuan Zhu, Proofs of some conjectures on monotonicity of number-theoretic and combinatorial sequences, arXiv preprint arXiv:1303.5595 [math.CO], 2013.
Eric Weisstein's World of Mathematics, Motzkin Number.
Wikipedia, Motzkin number.
W.-J. Woan, Hankel Matrices and Lattice Paths, J. Integer Sequences, 4 (2001), #01.1.2.
J. Y. X. Yang, M. X. X. Zhong, and R. D. P. Zhou, On the Enumeration of (s, s+ 1, s+2)-Core Partitions, arXiv:1406.2583 [math.CO], 2014.
Huan Xiong, The number of simultaneous core partitions, arXiv:1409.7038 [math.CO], 2014.
Yan X. Zhang, Four Variations on Graded Posets, arXiv:1508.00318 [math.CO], 2015.
Yan Zhuang, A generalized Goulden-Jackson cluster method and lattice path enumeration, arXiv:1508.02793 [math.CO], 2015-2018; Discrete Mathematics 341.2 (2018): 358-379.
Index entries for "core" sequences

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

a001006 n = a001006_list !! n
a001006_list = zipWith (+) a005043_list $ tail a005043_list
-- Reinhard Zumkeller, Jan 31 2012

# 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

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

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 */

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 */

makelist(ultraspherical(n,-n-1,-1/2)/(n+1),n,0,12); /* Emanuele Munarini, Oct 20 2016 */

{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 */

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

{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 */

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

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

# 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

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

A014137 Partial sums of Catalan numbers (A000108).

Original entry on oeis.org

1, 2, 4, 9, 23, 65, 197, 626, 2056, 6918, 23714, 82500, 290512, 1033412, 3707852, 13402697, 48760367, 178405157, 656043857, 2423307047, 8987427467, 33453694487, 124936258127, 467995871777, 1757900019101, 6619846420553, 24987199492705, 94520750408709, 358268702159069

Offset: 0

N. J. A. Sloane

This is also the result of applying the transformation on generating functions A -> 1/((1 - x)*(1 - x*A)) to the g.f. for the Catalan numbers.
p divides a(p) - 3 for prime p = 3 and p = {7, 13, 19, 31, 37, 43, ...} = A002476 (Primes of the form 6*n + 1). p^2 divides a(p^2) - 3 for prime p > 3. - Alexander Adamchuk, Jul 11 2006
Prime p divides a(p) for p = {2, 3, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, ...} = A045309 (Primes congruent to {0, 2} mod 3); and A045309 (Primes p such that x^3 = n (integer) has only one solution mod p). Nonprime numbers n such that n divides a(n) are listed in A128287 = {1, 8, 133, ...}. - Alexander Adamchuk, Feb 23 2007
For p prime >= 5, a(p-1) = 1 or -2 (mod p) according as p = 1 or -1 (mod 3) (see Pan and Sun link). For example, with p=5, a(p-1) = 23 = -2 (mod p). - David Callan, Nov 29 2007
Hankel transform is A010892(n+1). - Paul Barry, Apr 24 2009
Equals INVERTi transform of A000245: (1, 3, 9, 28, ...). - Gary W. Adamson, May 15 2009
The subsequence of prime partial sums of Catalan numbers begins: a(1) = 2, a(4) = 23, a(6) = 197, a(16) = 48760367; see A121852. - Jonathan Vos Post, Feb 10 2010
Number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k >= 1 including two kinds of (1,1). - Alois P. Heinz, Oct 14 2015
Binomial transform of A086246(n+1) = [1, 1, 1, 2, 4, 9, ...], or, equivalently, of A001006 (Motzkin numbers) with 1 prepended.

			G.f. = 1 + 2*x + 4*x^2 + 9*x^3 + 23*x^4 + 65*x^5 + 197*x^6 + 626*x^7 + 2056*x^8 + ...

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0 to 200 by T. D. Noe)
G. Alvarez, J. E. Bergner, and R. Lopez, Action Graphs and Catalan Numbers, J. Int. Seq. 18 (2015), 15.7.2.
M. Apagodu, D. Zeilberger, Using the Freshman's dream to prove combinatorial congruences, Am. Math. Mon. 124, No. 7, 597-608 (2017), prop. 2'
Maciej Bendkowski and Pierre Lescanne, Combinatorics of explicit substitutions, arXiv:1804.03862 [cs.LO], 2018.
W. Chammam, F. Marcellán and R. Sfaxi, Orthogonal polynomials, Catalan numbers, and a general Hankel determinant evaluation, Linear Algebra Appl. 436(7) (2012), 2105-2116.
Joel E. Cohen, Variance Functions of Asymptotically Exponentially Increasing Integer Sequences Go Beyond Taylor's Law, J. Int. Seq., Vol. 25 (2022), Article 22.9.3.
Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro, and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, 18 (2015), Article 15.5.8.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
Ângela Mestre and José Agapito, A Family of Riordan Group Automorphisms, J. Int. Seq., Vol. 22 (2019), Article 19.8.5.
I. Pak, Partition identities and geometric bijections, Proc. Amer. Math. Soc. 132 (2004), 3457-3462.
Hao Pan and Zhi-Wei Sun, A combinatorial identity with application to Catalan numbers, arXiv:math/0509648 [math.CO], 2005-2006.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.
Kevin Topley, Computationally Efficient Bounds for the Sum of Catalan Numbers, arXiv:1601.04223 [math.CO], 2016.

Cf. A000108, A000245, A000984, A001246, A002476, A002897, A006134, A033536, A045309, A079727, A082894, A094638, A094639, A128287, A358436.

[(&+[Catalan(k): k in [0..n]]): n in [0..40]]; // G. C. Greubel, Jun 30 2024

a:= proc(n) option remember; `if`(n<2, n+1,
      ((5*n-1)*a(n-1)-(4*n-2)*a(n-2))/(n+1))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, May 18 2013
A014137List := proc(m) local A, P, n; A := [1]; P := [1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-n]]);
A := [op(A), P[-1]] od; A end: A014137List(30); # Peter Luschny, Mar 26 2022

Table[Sum[(2k)!/(k!)^2/(k+1),{k,0,n}],{n,0,30}] (* Alexander Adamchuk, Jul 11 2006 *)
Accumulate[CatalanNumber[Range[0,30]]] (* Harvey P. Dale, May 08 2012 *)
a[ n_] := SeriesCoefficient[ (1 - (1 - 4 x)^(1/2)) / (2 x (1 - x)), {x, 0, n}]; (* Michael Somos, Oct 24 2015 *)
Table[(1 + CatalanNumber[n] (3 (n + 1) Hypergeometric2F1[1, -n, 1/2 - n, 1/4] - 4 n - 2))/2, {n, 0, 20}] (* Vladimir Reshetnikov, Oct 03 2016 *)

Vec((1-(1-4*x)^(1/2))/(2*x*(1-x))+O(x^99)) \\ Charles R Greathouse IV, Feb 11 2011

sm(v)={my(s=vector(#v)); s[1]=v[1]; for(n=2, #v, s[n]=v[n]+s[n-1]); s; }
C(n)=binomial(2*n, n)/(n+1);
sm(vector(66, n, C(n-1)))
/* Joerg Arndt, May 04 2013 */

from _future_ import division
A014137_list, b, s = [], 1, 0
for n in range(10**2):
    s += b
    A014137_list.append(s)
    b = b*(4*n+2)//(n+2) # Chai Wah Wu, Jan 28 2016

def A014137():
    f, c, n = 1, 1, 1
    while True:
        yield f
        n += 1
        c = c * (4*n - 6) // n
        f = c + f
a = A014137()
print([next(a) for  in range(29)]) # _Peter Luschny, Nov 30 2016

a(n) = A014138(n-1) + 1.
G.f.: (1 - (1 - 4*x)^(1/2))/(2*x*(1 - x)).
a(n) = Sum_{k=0..n} (2k)!/(k!)^2/(k+1). - Alexander Adamchuk, Jul 11 2006
D-finite with recurrence: (n+1)*a(n) + (1-5*n)*a(n-1) + 2*(2*n-1)*a(n-2) = 0. - R. J. Mathar, Dec 14 2011
Mathar's formula reduces to 2*(2*n-1)*C(n-1) = (n+1)*C(n), which is a known recurrence of the Catalan numbers, so the conjecture is true. - Peter J. Taylor, Mar 23 2015
Let C(n+1) = binomial(2*n+2,n+1)/(n+2) and H(n) = hypergeometric([1,n+3/2],[n+3],4) then A014137(n) = -(-1)^(2/3) - C(n+1)*H(n) and A014138(n) = -I^(2/3) - C(n+1)*H(n). - Peter Luschny, Aug 09 2012
G.f. (conjecture): Q(0)/(1-x), where Q(k)= 1 + (4*k + 1)*x/(k + 1 - 2*x*(k + 1)*(4*k + 3)/(2*x*(4*k + 3) + (2*k + 3)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013
a(n) ~ 2^(2*n + 2)/(3*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Dec 10 2013
0 =  a(n)*(16*a(n+1) - 26*a(n+2) + 10*a(n+3)) + a(n+1)*(-14*a(n+1) + 23*a(n+2) - 11*a(n+3)) + a(n+2)*(a(n+2) + a(n+3)) if n >= 0. - Michael Somos, Oct 24 2015
a(n) = (1 + A000108(n)*(3*(n+1)*hypergeom([1,-n], [1/2-n], 1/4) - 4*n - 2))/2. - Vladimir Reshetnikov, Oct 03 2016
G.f. A(x) satisfies: A(x) = 1 / (1 - x) + x * (1 - x) * A(x)^2. - Ilya Gutkovskiy, Jul 25 2021
From Peter Luschny, Nov 16 2022: (Start)
a(n) = C(n)*hypergeom([1, -n - 1], [1/2 - n], 1/4) + 1/2.
a(n) = A358436(n) / C(n). (End)
E.g.f.: exp(2*x)*(BesselI(0, 2*x)/2 - BesselI(1, 2*x)) + exp(x)/2*(3*Integral_{x=-oo..oo} BesselI(0,2*x)*exp(x) dx + 1). - Mélika Tebni, Sep 01 2024

A106228 G.f. satisfies A(x) = 1 + xA(x)/(1 - xA(x)^2).

Original entry on oeis.org

1, 1, 2, 6, 21, 80, 322, 1347, 5798, 25512, 114236, 518848, 2384538, 11068567, 51817118, 244370806, 1159883685, 5536508864, 26560581688, 127993221140, 619280193640, 3007251366000, 14651743202152, 71601107803904, 350873710447210, 1723795243004223

Offset: 0

Paul D. Hanna, May 19 2005

nonn

Number of paths from (0,0) to (3n-3,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1), U=(1,2), or d=(1,-1) and have no tripledescents (ddd). Example: a(3)=6 because we have udud, Uddud, udUdd, UddUdd, uudd and Ududd (the remaining four paths contain the string ddd: uUddd, UdUddd, Uuddd and UUdddd; see A027307). - Emeric Deutsch, Jun 08 2005
a(n) = number of node-labeled ordered trees (A000108) on n vertices, each node labeled with a positive integer <= its outdegree. A node is a non-root non-leaf vertex. Example. a(3)=6 counts the 5 ordered trees on 4 vertices with all labels 1 and the tree
.|.
/ \
with its (one and only) node labeled 2. - David Callan, Jul 14 2006
a(n) = number of Schroeder (n-1)-paths with no triple descents. Example: a(4)=21 counts all 22 Schroeder 3-paths (A006318) except UUUDDD. - David Callan, Jul 14 2006
(1 + 2x + 6x^2 + ...)*(1 + x + 2x^2 + 6x^3) = (1 + 3x + 10x^2 + 37x^3 + ...), where A109081 = (1, 1, 3, 10, 37, ...). - Gary W. Adamson, Nov 15 2011
a(n) = number of Motzkin paths of length 2n-1 with no downsteps in odd position. Example: a(3)=6 counts FFFFF, FFUDF, FUFDF, UDFFF, UDUDF, UFFDF with U an upstep (1,1), F a flatstep (1,0), and D a downstep (1,-1). - David Callan, May 20 2015
Number of permutations of length n that avoid 4123, 4132, and 4213. - Jay Pantone, Oct 01 2015
Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) > e(j) and e(i) <= e(k). [Martinez and Savage, 2.21] - Eric M. Schmidt, Jul 17 2017
a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {1>3, 1>4, 4>2} of length 4. That is, the number of length n permutations having no subsequences of length 4 in which the first element is the largest and the fourth element is larger than the second element. - Sergey Kitaev, Dec 10 2020
a(n) is the number of peakless Motzkin paths of length 2n that do not start with an up edge and where every pair of matching up and down edges occupies positions of the same parity. Equivalently, the number of RNA secondary structures on 2n vertices where the leftmost vertex is not matched and only vertices of the same parity can be matched. - Alexander Burstein, May 17 2021

			A = 1 + x*A + x^2*A^3 + x^3*A^5 + x^4*A^7 + x^5*A^9 + ...
a(4) = 21 since the top row terms of Q^3 = (10, 7, 3, 1). - _Gary W. Adamson_, Nov 15 2011
G.f. = 1 + x + 2*x^2 + 6*x^3 + 21*x^4 + 80*x^5 + 322*x^6 + 1347*x^7 + ...

Jay Pantone, Table of n, a(n) for n = 0..500
Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, and Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], 2015.
Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
E. Barcucci, R. Pinzani and R. Sprugnoli, The Motzkin family, P.U.M.A. Ser. A, Vol. 2, 1991, No. 3-4, pp. 249-279.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
N. R. Beaton, M. Bouvel, V. Guerrini, and S. Rinaldi, Slicings of Parallelogram Polyominoes: Catalan, Schröder, Baxter, and Other Sequences, Electr. J. Combin. 26 (2019), P3.13. Also at arXiv:1511.04854 [math.CO], 2015-2019.
Beáta Bényi, Toufik Mansour, and José L. Ramírez, Pattern Avoidance in Weak Ascent Sequences, arXiv:2309.06518 [math.CO], 2023.
Wlodzimierz Bryc, Raouf Fakhfakh, and Wojciech Mlotkowski, Cauchy-Stieltjes families with polynomial variance functions and generalized orthogonality, arXiv:1708.05343 [math.PR], 2017-2019. Also in Probability and Mathematical Statistics (2019), Vol. 39, No. 2, 237-258.
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
David Callan and Toufik Mansour, Enumeration of small Wilf classes avoiding 1342 and two other 4-letter patterns, Pure Mathematics and Applications (2018) Vol. 27, No. 1, 62-97.
Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Applied Mathematics (2019); see also author's copy
Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
JiSun Huh, Sangwook Kim, Seunghyun Seo, and Heesung Shin, Bijections on pattern avoiding inversion sequences and related objects, arXiv:2404.04091 [math.CO], 2024. See pp. 2, 22.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.

Cf. A027907, A027307, A001006, A086246, A109081, A164965, A262441.

a := proc(n) option remember; if n<2 then 1 elif n=2 then 2 else ((380*n^3-840*n^2+496*n-72)*a(n-1)+(76*n^3-282*n^2+302*n-84)*a(n-2)+(57*n^3-297*n^2+402*n-72)*a(n-3))/(76*n^3-54*n^2-46*n) fi end: seq(a(i),i=0..23); # Peter Luschny, Aug 03 2012

Flatten[{1,Table[1/n*Sum[Binomial[n,k]*Binomial[n+k,n-k-1],{k,0,n-1}],{n,1,20}]}] (* Vaclav Kotesovec, Sep 16 2013 *)
a[ n_] := If[ n < 0, 0, HypergeometricPFQ[{-n, 1 - n, n + 1}, {1, 3/2}, 1/4]]; (* Michael Somos, May 27 2014 *)

{a(n)=local(A=1+x+x*O(x^n));for(k=1,n,A=1+x*A/(1-x*A^2)); polcoeff(A,n)}

{a(n) = local(A); if( n<0, 0, n++; A = (1 + x - sqrt(1 - 2*x - 3*x^2 + x * O(x^n))) / 2; polcoeff( serreverse( x^2 / A), n))}; /* Michael Somos, Jun 18 2005 */

{a(n) = if( n<1, n==0, polcoeff( serreverse( x /  (1 + 2*x + 2*x^2 + x^3) + x * O(x^n)), n))}; /* Michael Somos, Dec 31 2014 */

from mpmath import mp
mp.dps = 32; mp.pretty = True
def A106228(n) : return int(mp.hyper([-n, 1-n, n+1], [1, 3/2], 1/4))
[A106228(n) for n in (0..23)] # Peter Luschny, Aug 02 2012

G.f.: A(x) = (1/x)*series_reversion[x/(1 + x*G001006(x))] and thus G.f. satisfies: A(x) = 1 + x*A(x)*G001006(x*A(x)) where G001006(x) is the g.f. of Motzkin numbers A001006.
G.f.: 1 + x*exp( Sum_{n>=1} A082759(n)*x^n/n ), where A082759(n) = Sum_{k=0..n} binomial(n,k)*trinomial(n,k). - Paul D. Hanna, Nov 02 2012
a(n) = (1/n)sum(binomial(n, j+1)*b(n, j), j=0..n-1), where b(n, j) are the trinomial coefficients [b(n, j)=A027907(n, j)=coefficient of x^j in (1+x+x^2)^n]. - Emeric Deutsch, Jun 08 2005
Given g.f. A(x), then B(x) = x*A(x) satisfies 0 = f(x, B(x)) where f(x, y) = y^3 - (1+y)*x*(y-x). - Michael Somos, Jun 18 2005
a(n+1) = Sum[binomial(2n-2k,n-k)*binomial(n+k,n)/(n+1),{k,0,n}]. - David Callan, Aug 16 2006
For n>0: a(n) = 1/n*sum(binomial(n,j)*sum(binomial(j,i)*binomial(n-j,2*j-n-i-1)*2^(2*n-3*j+2*i+1),i=0..n-1), j=0..n); - Vladimir Kruchinin, Dec 26 2010
a(n) = 1/(n+1)*sum(binomial(n+1,k)*binomial(n+k+1,n-k),k,0,n); - Vladimir Kruchinin, Feb 28 2010
a(n) = upper left term in M^n, M = the production matrix:
  1, 1
  1, 1, 1
  2, 2, 1, 1
  3, 3, 2, 1, 1
  4, 4, 3, 2, 1, 1
  5, 5, 4, 3, 2, 1, 1
  ...
- Gary W. Adamson, Jul 08 2011
D-finite with recurrence: 4*n*(2*n+1)*a(n) + 2*(6-5*n-10*n^2)*a(n-1) + 12*(-9*n^2+35*n-33)*a(n-2) - 2*(n-3)*(13*n-28)*a(n-3) - 15*(n-3)*(n-4)*a(n-4) = 0. - R. J. Mathar, Nov 14 2011
From Gary W. Adamson, Nov 15 2011: (Start)
a(n) is the sum of top row terms of Q^(n-1), where Q = the following infinite square production matrix:
  1, 1, 0, 0, 0, ...
  2, 1, 1, 0, 0, ...
  3, 2, 1, 1, 0, ...
  4, 3, 2, 1, 1, ...
  5, 4, 3, 2, 1, ...
  ... (End)
a(n) = 3_F_2([-n, 1-n, n+1], [1, 3/2], 1/4). - Peter Luschny, Aug 02 2012
A four-term recurrence equation is given in the Maple program. Peter Luschny, Aug 03 2012
a(n) ~ 1/228*sqrt(114)*sqrt((32129+3933*sqrt(57))^(1/3) * ((32129+3933*sqrt(57))^(2/3) + 532 + 38*(32129+3933*sqrt(57))^(1/3))) / ((32129+3933*sqrt(57))^(1/3)) * (((1261+57*sqrt(57))^(2/3) + 112 + 10*(1261+57*sqrt(57))^(1/3)) / (6*(1261+57*sqrt(57))^(1/3)))^n / (sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Sep 16 2013
G.f. satisfies x*F(x)^3 - x*F(x)^2 + (x-1)*F(x) + 1 = 0. - Jay Pantone, Oct 01 2015
G.f. satisfies A(-x*A(x)^3) = 1/A(x). - Alexander Burstein, Dec 05 2019
G.f.: A(x) = sqrt(B(x)) where B(x) is the g.f. of A262441. - Seiichi Manyama, Mar 31 2024
a(n) = Sum_{k=0..n} binomial(n,k) * binomial(n/2+3*k/2+1/2,n)/(n+3*k+1). - Seiichi Manyama, Apr 04 2024

A130777 Coefficients of first difference of Chebyshev S polynomials.

Original entry on oeis.org

1, -1, 1, -1, -1, 1, 1, -2, -1, 1, 1, 2, -3, -1, 1, -1, 3, 3, -4, -1, 1, -1, -3, 6, 4, -5, -1, 1, 1, -4, -6, 10, 5, -6, -1, 1, 1, 4, -10, -10, 15, 6, -7, -1, 1, -1, 5, 10, -20, -15, 21, 7, -8, -1, 1, -1, -5, 15, 20, -35, -21, 28, 8, -9, -1, 1, 1, -6, -15, 35, 35, -56, -28, 36, 9, -10, -1, 1

Offset: 0

Philippe Deléham, Jul 14 2007

Inverse of triangle in A061554.
Signed version of A046854.
From Paul Barry, May 21 2009: (Start)
Riordan array ((1-x)/(1+x^2),x/(1+x^2)).
This triangle is the coefficient triangle for the Hankel transforms of the family of generalized Catalan numbers that satisfy a(n;r)=r*a(n-1;r)+sum{k=1..n-2, a(k)*a(n-1-k;r)}, a(0;r)=a(1;r)=1. The Hankel transform of a(n;r) is h(n)=sum{k=0..n, T(n,k)*r^k} with g.f. (1-x)/(1-r*x+x^2). These sequences include A086246, A000108, A002212. (End)
From Wolfdieter Lang, Jun 11 2011: (Start)
The Riordan array ((1+x)/(1+x^2),x/(1+x^2)) with entries Phat(n,k)= ((-1)^(n-k))*T(n,k) and o.g.f. Phat(x,z)=(1+z)/(1-x*z+z^2) for the row polynomials Phat(n,x) is related to Chebyshev C and S polynomials as follows.
Phat(n,x) = (R(n+1,x)-R(n,x))/(x+2) = S(2*n,sqrt(2+x))
  with R(n,x)=C_n(x) in the Abramowitz and Stegun notation, p. 778, 22.5.11. See A049310 for the S polynomials. Proof from the o.g.f.s.
Recurrence for the row polynomials Phat(n,x):
  Phat(n,x) = x*Phat(n-1,x) - Phat(n-2,x) for n>=1; Phat(-1,x)=-1, Phat(0,x)=1.
The A-sequence for this Riordan array Phat (see the W. Lang link under A006232 for A- and Z-sequences for Riordan matrices) is given by 1, 0, -1, 0, -1, 0, -2, 0, -5,.., starting with 1 and interlacing the negated A000108 with zeros (o.g.f. 1/c(x^2) = 1-c(x^2)*x^2, with the o.g.f. c(x) of A000108).
The Z-sequence has o.g.f. sqrt((1-2*x)/(1+2*x)), and it is given by A063886(n)*(-1)^n.
The A-sequence of the Riordan array T(n,k) is identical with the one for the Riordan array Phat, and the Z-sequence is -A063886(n).
(End)
The row polynomials P(n,x) are the characteristic polynomials of the adjacency matrices of the graphs which look like P_n (n vertices (nodes), n-1 lines (edges)), but vertex no. 1 has a loop. - Wolfdieter Lang, Nov 17 2011
From Wolfdieter Lang, Dec 14 2013: (Start)
The zeros of P(n,x) are x(n,j) = -2*cos(2*Pi*j/(2*n+1)), j=1..n. From P(n,x) = (-1)^n*S(2*n,sqrt(2-x)) (see, e.g., the Lemma 6 of the W. Lang link).
The discriminants of the P-polynomials are given in A052750. (End)

			The triangle T(n,k) begins:
n\k  0   1   1   3    4    5    6    7    8    9  10  11  12  13 14 15 ...
0:   1
1:  -1   1
2:  -1  -1   1
3:   1  -2  -1   1
4:   1   2  -3  -1    1
5:  -1   3   3  -4   -1    1
6:  -1  -3   6   4   -5   -1    1
7:   1  -4  -6  10    5   -6   -1    1
8:   1   4 -10 -10   15    6   -7   -1    1
9:  -1   5  10 -20  -15   21    7   -8   -1    1
10: -1  -5  15  20  -35  -21   28    8   -9   -1   1
11:  1  -6 -15  35   35  -56  -28   36    9  -10  -1   1
12:  1   6 -21 -35   70   56  -84  -36   45   10 -11  -1   1
13: -1   7  21 -56  -70  126   84 -120  -45   55  11 -12  -1   1
14: -1  -7  28  56 -126 -126  210  120 -165  -55  66  12 -13  -1  1
15:  1  -8 -28  84  126 -252 -210  330  165 -220 -66  78  13 -14 -1  1
...  reformatted and extended - _Wolfdieter Lang_, Jul 31 2014.
---------------------------------------------------------------------------
From _Paul Barry_, May 21 2009: (Start)
Production matrix is
-1, 1,
-2, 0, 1,
-2, -1, 0, 1,
-4, 0, -1, 0, 1,
-6, -1, 0, -1, 0, 1,
-12, 0, -1, 0, -1, 0, 1,
-20, -2, 0, -1, 0, -1, 0, 1,
-40, 0, -2, 0, -1, 0, -1, 0, 1,
-70, -5, 0, -2, 0, -1, 0, -1, 0, 1 (End)
Row polynomials as first difference of S polynomials:
P(3,x) = S(3,x) - S(2,x) = (x^3 - 2*x) - (x^2 -1) = 1 - 2*x - x^2 +x^3.
Alternative triangle recurrence (see a comment above): T(6,2) = T(5,2) + T(5,1) = 3 + 3 = 6. T(6,3) = -T(5,3) + 0*T(5,1) = -(-4) = 4. - _Wolfdieter Lang_, Jul 31 2014

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964. Tenth printing, Wiley, 2002 (also electronically available).

Hyeong-Kwan Ju, On the sequence generated by a certain type of matrices, Honam Math. J. 39, No. 4, 665-675 (2017), Theorem 2.16.
Wolfdieter Lang, The field Q(2cos(pi/n)), its Galois group and length ratios in the regular n-gon, arXiv:1210.1018 [math.GR], 2012-2017; see Definition 1, Lemma 6 and Remark 4.
P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), p. 22-31 (formula 5).
Index entries for sequences related to Chebyshev polynomials.

Cf. A066170, A046854, A057077 (first column).

Row sums: A010892(n+1); repeat(1,0,-1,-1,0,1). Alternating row sums: A061347(n+2); repeat(1,-2,1).

A130777 := proc(n,k): (-1)^binomial(n-k+1,2)*binomial(floor((n+k)/2),k) end: seq(seq(A130777(n,k), k=0..n), n=0..11); # Johannes W. Meijer, Aug 08 2011

T[n_, k_] := (-1)^Binomial[n - k + 1, 2]*Binomial[Floor[(n + k)/2], k];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 14 2017, from Maple *)

@CachedFunction
def A130777(n,k):
    if n< 0: return 0
    if n==0: return 1 if k == 0 else 0
    h = A130777(n-1,k) if n==1 else 0
    return A130777(n-1,k-1) - A130777(n-2,k) - h
for n in (0..9): [A130777(n,k) for k in (0..n)] # Peter Luschny, Nov 20 2012

Number triangle T(n,k) = (-1)^C(n-k+1,2)*C(floor((n+k)/2),k). - Paul Barry, May 21 2009
From Wolfdieter Lang, Jun 11 2011: (Start)
Row polynomials: P(n,x) = sum(k=0..n, T(n,k)*x^k) = R(2*n+1,sqrt(2+x)) / sqrt(2+x), with Chebyshev polynomials R with coefficients given in A127672 (scaled T-polynomials).
R(n,x) is called C_n(x) in Abramowitz and Stegun's handbook, p. 778, 22.5.11.
P(n,x) = S(n,x)-S(n-1,x), n>=0, S(-1,x)=0, with the Chebyshev S-polynomials (see the coefficient triangle A049310).
O.g.f. for row polynomials: P(x,z):= sum(n>=0, P(n,x)*z^n ) = (1-z)/(1-x*z+z^2).
  (from the o.g.f. for R(2*n+1,x), n>=0, computed from the o.g.f. for the R-polynomials (2-x*z)/(1-x*z+z^2) (see A127672))
Proof of the Chebyshev connection from the o.g.f. for Riordan array property of this triangle (see the P. Barry comment above).
For the A- and Z-sequences of this Riordan array see a comment above. (End)
abs(T(n,k)) = A046854(n,k) = abs(A066170(n,k)) T(n,n-k) = A108299(n,k); abs(T(n,n-k)) = A065941(n,k). - Johannes W. Meijer, Aug 08 2011
From Wolfdieter Lang, Jul 31 2014: (Start)
Similar to the triangles A157751, A244419 and A180070 one can give for the row polynomials P(n,x) besides the usual three term recurrence another one needing only one recurrence step. This uses also a negative argument, namely P(n,x) = (-1)^(n-1)*(-1 + x/2)*P(n-1,-x) + (x/2)*P(n-1,x), n >= 1, P(0,x) = 1. Proof by computing the o.g.f. and comparing with the known one. This entails the alternative triangle recurrence T(n,k) = (-1)^(n-k)*T(n-1,k) + (1/2)*(1 + (-1)^(n-k))*T(n-1,k-1), n >= m >= 1, T(n,k) = 0 if n < k and T(n,0) = (-1)^floor((n+1)/2) = A057077(n+1). [P(n,x) recurrence corrected Aug 03 2014]
(End)

New name and Chebyshev comments by Wolfdieter Lang, Jun 11 2010

A168049 Expansion of (3 -x -sqrt(1-2x-3x^2))/2.

Original entry on oeis.org

1, 0, 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

Offset: 0

Paul Barry, Nov 17 2009

A variant of the Motzkin numbers A001006. Hankel transform is A168050.
Essentially the same as A086246. - R. J. Mathar, Dec 20 2011
Alternatively, this sequence corresponds to the number of positive walks with n steps {-1,0,1} starting at the origin, ending at altitude 1, and staying strictly above the x-axis. - David Nguyen, Dec 01 2016

			G.f. = 1 + x^2 + x^3 + 2*x^4 + 4*x^5 + 9*x^6 + 21*x^7 + 51*x^8 + ... - _Michael Somos_, Sep 26 2018

Vincenzo Librandi, Table of n, a(n) for n = 0..200
C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv:1609.06473 [math.CO], 2016.

Cf. A001006, A086246, A168050, A168051.

m:=30; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!((3 -x - Sqrt(1-2*x-3*x^2))/2)); // G. C. Greubel, Sep 25 2018

CoefficientList[Series[(3-x-Sqrt[1-2*x-3*x^2])/2, {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 12 2014 *)

Vec((3-x-sqrt(1-2*x-3*x^2))/2) \\ Charles R Greathouse IV, Dec 01 2016

D-finite with recurrence: n*a(n) +(3-2n)*a(n-1) +3(3-n)*a(n-2)=0. - R. J. Mathar, Dec 20 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)) if n>0. - Michael Somos, Jan 31 2014
a(n) ~ 3^(n+1/2) / (6*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Feb 12 2014
G.f.: 1 + x^2/(1 - x - x^2/(1 - x - x^2/(1 - x - x^2/(1 - ...)))), a continued fraction. - Ilya Gutkovskiy, Sep 23 2017

A327871 Number of self-avoiding planar walks starting at (0,0), ending at (n,n), remaining in the first quadrant and using steps (0,1), (-1,1), and (1,-1) with the restriction that (-1,1) and (1,-1) are always immediately followed by (0,1).

Original entry on oeis.org

1, 1, 3, 14, 70, 369, 2002, 11076, 62127, 352070, 2010998, 11559030, 66780155, 387444085, 2255875650, 13174629240, 77143234950, 452738296890, 2662359410158, 15683996769460, 92540962166016, 546799192200261, 3235027635603828, 19161631961190036, 113617798289197650

Offset: 0

Alois P. Heinz, Sep 28 2019

Alois P. Heinz, Table of n, a(n) for n = 0..1280
Alois P. Heinz, Animation of a(5) = 369 walks
Wikipedia, Lattice path
Wikipedia, Self-avoiding walk

Cf. A001006, A026300, A086246, A327872.

b:= proc(x, y, t) option remember; `if`(min(x, y)<0, 0,
      `if`(max(x, y)=0, 1, b(x-1, y, 1)+
      `if`(t=1, b(x-1, y+1, 0)+b(x+1, y-1, 0), 0)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..25);

b[x_, y_, t_] := b[x, y, t] = If[Min[x, y] < 0, 0, If[Max[x, y]==0, 1, b[x - 1, y, 1] + If[t==1, b[x - 1, y + 1, 0] + b[x + 1, y - 1, 0], 0]]];
a[n_] := b[n, n, 0];
a /@ Range[0, 25] (* Jean-François Alcover, May 13 2020, after Maple *)
a[n_] := Binomial[2n - 1, n - 1] Hypergeometric2F1[(2 - n)/2, (1 - n)/2, n + 2, 4];
a[0] := 1; Table[a[n], {n, 0, 24}] (* Peter Luschny, May 19 2021 *)

a(n) ~ sqrt(5 + 1/sqrt(13)) * (70 + 26*sqrt(13))^n / (2^(3/2) * sqrt(Pi*n) * 3^(3*n + 3/2)). - Vaclav Kotesovec, Oct 12 2019
From Peter Luschny, May 19 2021: (Start)
Next three formulas for n >= 1:
a(n) = A026300(2*n - 1, n - 1).
a(n) = Sum_{j=0..floor((n-1)/2)} C(2*n-1, 2*j + n)*(C(2*j + n, j) - C(2*j +n, j-1)).
a(n) = binomial(2*n - 1, n - 1)*hypergeom([(2 - n)/2, (1 - n)/2], [n + 2], 4). (End)

A091836 A triangle of Motzkin ballot numbers.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 3, 3, 1, 4, 6, 6, 4, 1, 9, 13, 13, 10, 5, 1, 21, 30, 30, 24, 15, 6, 1, 51, 72, 72, 59, 40, 21, 7, 1, 127, 178, 178, 148, 105, 62, 28, 8, 1, 323, 450, 450, 378, 276, 174, 91, 36, 9, 1, 835, 1158, 1158, 980, 730, 480, 273, 128, 45, 10, 1, 2188, 3023, 3023

Offset: 0

Emeric Deutsch, Mar 09 2004

T(n-1,k) is the number of Motzkin paths of length n that have k points on the horizontal axis (besides the first and last point). For example T(1,0)=1 counts the path UD with 2 steps and no intermediate interception with the y=0 axis, and T(1,1)=1 counts the path FF with 2 steps, staying on the y=0 axis. - R. J. Mathar, Jul 23 2017

Riordan matrix A=(g(t),t*g(t)), where g(t)=1+t*M(t)=C(t/(1-t)), where M(t) and C(t) are the g.f. of Motzkin and Catalan numbers. A is a pseudo-involution. - Emanuele Munarini, Jul 03 2024

			Triangle begins:
   1;
   1,  1;
   1,  2,  1;
   2,  3,  3,  1;
   4,  6,  6,  4,  1;
   9, 13, 13, 10,  5,  1;
  21, 30, 30, 24, 15,  6,  1;
  ...

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows n = 0..150, flattened)
M. Aigner, Motzkin Numbers, Europ. J. Comb. 19 (1998), 663-675.
Jean-Luc Baril and Paul Barry, Two kinds of partial Motzkin paths with air pockets, arXiv:2212.12404 [math.CO], 2022.
Richard J. Mathar, Motzkin Islands: a 3-dimensional Embedding of Motzkin Paths, viXra:2009.0152, 2020.
J.-C. Novelli and J.-Y. Thibon, Noncommutative Symmetric Functions and Lagrange Inversion, arXiv:math/0512570 [math.CO], 2005-2006.

Mirror image of A034929.
T(n, 0) = A086246(n+1) = A001006(n-1).
T(n, 1) = A005554(n).
Row sums are the Motzkin numbers (A001006).

T[n_, m_] := If[n == m, 1, (-1)^m (m Sum[k (-1)^(n+k) Binomial[n+k-1, n-1] Sum[Binomial[j, -n+m-k+2j] Binomial[n-m, j], {j, 0, n-m}], {k, 1, n-m}])/ (n(n-m))];
Table[T[n, m], {n, 1, 11}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jul 27 2018, after Vladimir Kruchinin *)

T(n,m):=if n=m then 1 else (-1)^m*(m*sum(k*(-1)^(n+k)*binomial(n+k-1,n-1)*sum(binomial(j,-n+m-k+2*j)*binomial(n-m,j),j,0,n-m),k,1,n-m))/(n*(n-m)); /* Vladimir Kruchinin, Aug 20 2012 */

Column k has g.f.: z^k(1+zM)^(k+1).
G.f.: (1+zM)/(1-tz(1+zM)), where M = 1 + zM+ z ^2M^2 is the g.f. of the Motzkin numbers (A001006).
T(n,m) = (m*(Sum_{k=1..n-m} k*(-1)^(n+m+k)*binomial(n+k-1,n-1) * Sum_{j=0..n-m} binomial(j,-n+m-k+2*j)*binomial(n-m,j)))/(n*(n-m)), n>m, T(n,n)=1. - Vladimir Kruchinin, Aug 20 2012
From Emanuele Munarini, Jul 03 2024: (Start)
T(n,k) = Sum_{i=0..n-k} (-1)^(n-k-i)*binomial(n-k-1,n-k-i) * binomial(2*i+k,i+k) * (k+1) / (i+k+1).
T(n,k) = Sum_{i=0..n-k} binomial(n-k-1,n-k-i)*binomial(n-i+1,i)*(k+1)/(n-i+1) for k < n.
T(n,k) = Sum_{i=0..n-k} trinomial(n-k,n-k-i)*binomial(k+1,i)*i/(n-k) for k < n, where trinomial(n,k) = A027907(n,k).
Recurrence: T(n+2,k+2) = T(n+2,k+1) + T(n+1,k+1) - T(n+1,k) - T(n,k). (End)

A292440 Expansion of (1 - x + sqrt(1 - 2x - 3x^2))/2 in powers of x.

Original entry on oeis.org

1, -1, -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

Offset: 0

Seiichi Manyama, Sep 16 2017

sign

Apart from a(1) the same as A168051. - R. J. Mathar, Sep 18 2017

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A001006, A086246.

m:=50; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!((1-x +Sqrt(1-2*x-3*x^2))/2)); // G. C. Greubel, Aug 13 2018

CoefficientList[Series[(1-x +Sqrt[1-2*x-3*x^2])/2, {x, 0, 50}], x] (* G. C. Greubel, Aug 13 2018 *)

x='x+O('x^50); Vec((1 - x + sqrt(1 - 2*x - 3*x^2))/2) \\ G. C. Greubel, Aug 13 2018

Convolution inverse of A001006.
Let f(x) = (1 - x - sqrt(1 - 2*x - 3*x^2))/(2*x^2).
G.f.: 1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(... (continued fraction).
G.f.: 1/f(x) = 1 - x - x^2*f(x).
a(n) = -A001006(n-2) for n > 1.
a(n) ~ -3^(n - 1/2) / (2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 14 2018
D-finite with recurrence: n*a(n) +(-2*n+3)*a(n-1) +3*(-n+3)*a(n-2)=0. - R. J. Mathar, Jan 23 2020

cp's OEIS Frontend

A144218 Equals product A*B, where A is an infinite lower triangular matrix with A086246 in every column and B is the diagonal matrix with A001006 as diagonal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A348197 Composition of the g.f. of A086246 with itself.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

Maxima

Maxima

PARI

PARI

PARI

Python

Python

Python

Formula

A014137 Partial sums of Catalan numbers (A000108).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Sage

Formula

A106228 G.f. satisfies A(x) = 1 + xA(x)/(1 - xA(x)^2).

A168049 Expansion of (3 -x -sqrt(1-2x-3x^2))/2.

A292440 Expansion of (1 - x + sqrt(1 - 2x - 3x^2))/2 in powers of x.