A107131 -id:A107131 - cp's OEIS frontend

A088617 Triangle read by rows: T(n,k) = C(n+k,n)*C(n,k)/(k+1), for n >= 0, k = 0..n.

1, 1, 1, 1, 3, 2, 1, 6, 10, 5, 1, 10, 30, 35, 14, 1, 15, 70, 140, 126, 42, 1, 21, 140, 420, 630, 462, 132, 1, 28, 252, 1050, 2310, 2772, 1716, 429, 1, 36, 420, 2310, 6930, 12012, 12012, 6435, 1430, 1, 45, 660, 4620, 18018, 42042, 60060, 51480, 24310, 4862

Offset: 0

N. J. A. Sloane, Nov 23 2003

Row sums: A006318 (Schroeder numbers). Essentially same as triangle A060693 transposed.
T(n,k) is number of Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1), H=(2,0) and never going below the x-axis) from (0,0) to (2n,0), having k U's. E.g., T(2,1)=3 because we have UHD, UDH and HUD. - Emeric Deutsch, Dec 06 2003
Little Schroeder numbers A001003 have a(n) = Sum_{k=0..n} A088617(n,k)*(-1)^(n-k)*2^k. - Paul Barry, May 24 2005
Conjecture: The expected number of U's in a Schroeder n-path is asymptotically Sqrt[1/2]*n for large n. - David Callan, Jul 25 2008
T(n, k) is also the number of order-preserving and order-decreasing partial transformations (of an n-chain) of width k (width(alpha) = |Dom(alpha)|). - Abdullahi Umar, Oct 02 2008
The antidiagonals of this lower triangular matrix are the rows of A055151. - Tom Copeland, Jun 17 2015

			Triangle begins:
  [0] 1;
  [1] 1,  1;
  [2] 1,  3,   2;
  [3] 1,  6,  10,    5;
  [4] 1, 10,  30,   35,    14;
  [5] 1, 15,  70,  140,   126,    42;
  [6] 1, 21, 140,  420,   630,   462,   132;
  [7] 1, 28, 252, 1050,  2310,  2772,  1716,   429;
  [8] 1, 36, 420, 2310,  6930, 12012, 12012,  6435,  1430;
  [9] 1, 45, 660, 4620, 18018, 42042, 60060, 51480, 24310, 4862;

Charles Jordan, Calculus of Finite Differences, Chelsea 1965, p. 449.

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows 0 <= n <= 150)
Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, Enumeration of multi-rooted plane trees, arXiv:2301.09765 [math.CO], 2023.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry, Continued fractions and transformations of integer sequences, JIS 12 (2009) 09.7.6.
Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
Paul Barry, On the inversion of Riordan arrays, arXiv:2101.06713 [math.CO], 2021.
Manosij Ghosh Dastidar and Michael Wallner, Bijections and congruences involving lattice paths and integer compositions, arXiv:2402.17849 [math.CO], 2024. See p. 16.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Hsien-Kuei Hwang and Satoshi Kuriki, Integrated empirical measures and generalizations of classical goodness-of-fit statistics, arXiv:2404.06040 [math.ST], 2024. See p. 11.
C. Jordan, Calculus of Finite Differences, Budapest, 1939. [Annotated scans of pages 448-450 only]
A. Kirillov, On Some Quadratic Algebras I 1/2: Combinatorics of Dunkl and Gaudin Elements, Schubert, Grothendieck, Fuss-Catalan, Universal Tutte and Reduced Polynomials, arXiv preprint arXiv:1502.00426 [math.RT], 2016.
M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.
Paul W. Lapey and Aaron Williams, A Shift Gray Code for Fixed-Content Łukasiewicz Words, Williams College, 2022.
A. Laradji and A. Umar, A. Combinatorial results for semigroups of order-preserving partial transformations, Journal of Algebra 278, (2004), 342-359.
A. Laradji and A. Umar, Combinatorial results for semigroups of order-decreasing partial transformations, J. Integer Seq. 7 (2004), 04.3.8.
Jason P. Smith, The poset of graphs ordered by induced containment, arXiv:1806.01821 [math.CO], 2018.

Diagonals give A000217, A034827, A000910, A088625, A088626, A000108, A001700, A002457, A002802, A002803.
Cf. A000108, A001003, A006318, A060693, A084938, A085478.
Cf. A033282, A055151, A123160.
Cf. A001263, A011973, A055151, A060693, A074909, A086810, A107131.

[[Binomial(n+k,n)*Binomial(n,k)/(k+1): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Jun 18 2015

R := n -> simplify(hypergeom([-n, n + 1], [2], -x)):
Trow := n -> seq(coeff(R(n, x), x, k), k = 0..n):
seq(print(Trow(n)), n = 0..9); # Peter Luschny, Apr 26 2022

Table[Binomial[n+k, n] Binomial[n, k]/(k+1), {n,0,10}, {k,0,n}]//Flatten (* Michael De Vlieger, Aug 10 2017 *)

{T(n, k)= if(k+1, binomial(n+k, n)*binomial(n, k)/(k+1))}

flatten([[binomial(n+k, 2*k)*catalan_number(k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 22 2022

Triangle T(n, k) read by rows; given by [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...] DELTA [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...] where DELTA is Deléham's operator defined in A084938.
T(n, k) = A085478(n, k)*A000108(k); A000108 = Catalan numbers. - Philippe Deléham, Dec 05 2003
Sum_{k=0..n} T(n, k)*x^k*(1-x)^(n-k) = A000108(n), A001003(n), A007564(n), A059231(n), A078009(n), A078018(n), A081178(n), A082147(n), A082181(n), A082148(n), A082173(n) for x = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. - Philippe Deléham, Aug 18 2005
Sum_{k=0..n} T(n,k)*x^k = (-1)^n*A107841(n), A080243(n), A000007(n), A000012(n), A006318(n), A103210(n), A103211(n), A133305(n), A133306(n), A133307(n), A133308(n), A133309(n) for x = -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8 respectively. - Philippe Deléham, Oct 18 2007
O.g.f. (with initial 1 excluded) is the series reversion with respect to x of (1-t*x)*x/(1+x). Cf. A062991 and A089434. - Peter Bala, Jul 31 2012
G.f.: 1 + (1 - x - T(0))/y, where T(k) = 1 - x*(1+y)/( 1 - x*y/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 03 2013
From Peter Bala, Jul 20 2015: (Start)
O.g.f. A(x,t) = ( 1 - x - sqrt((1 - x)^2 - 4*x*t) )/(2*x*t) = 1 + (1 + t)*x + (1 + 3*t + 2*t^2)*x^2 + ....
1 + x*(dA(x,t)/dx)/A(x,t) = 1 + (1 + t)*x + (1 + 4*t + 3*t^2)*x^2 + ... is the o.g.f. for A123160.
For n >= 1, the n-th row polynomial equals (1 + t)/(n+1)*Jacobi_P(n-1,1,1,2*t+1). Removing a factor of 1 + t from the row polynomials gives the row polynomials of A033282. (End)
From Tom Copeland, Jan 22 2016: (Start)
The o.g.f. G(x,t) = {1 - (2t+1) x - sqrt[1 - (2t+1) 2x + x^2]}/2x = (t + t^2) x + (t + 3t^2 + 2t^3) x^2 + (t + 6t^2 + 10t^3 + 5t^3) x^3 + ... generating shifted rows of this entry, excluding the first, was given in my 2008 formulas for A033282 with an o.g.f. f1(x,t) = G(x,t)/(1+t) for A033282. Simple transformations presented there of f1(x,t) are related to A060693 and A001263, the Narayana numbers. See also A086810.
The inverse of G(x,t) is essentially given in A033282 by x1, the inverse of f1(x,t): Ginv(x,t) = x [1/(t+x) - 1/(1+t+x)] = [((1+t) - t) / (t(1+t))] x - [((1+t)^2 - t^2) / (t(1+t))^2] x^2 + [((1+t)^3 - t^3) / (t(1+t))^3] x^3 - ... . The coefficients in t of Ginv(xt,t) are the o.g.f.s of the diagonals of the Pascal triangle A007318 with signed rows and an extra initial column of ones. The numerators give the row o.g.f.s of signed A074909.
Rows of A088617 are shifted columns of A107131, whose reversed rows are the Motzkin polynomials of A055151, related to A011973. The diagonals of A055151 give the rows of A088671, and the antidiagonals (top to bottom) of A088617 give the rows of A107131 and reversed rows of A055151. The diagonals of A107131 give the columns of A055151. The antidiagonals of A088617 (bottom to top) give the rows of A055151.
(End)
T(n, k) = [x^k] hypergeom([-n, 1 + n], [2], -x). - Peter Luschny, Apr 26 2022

A055151 Triangular array of Motzkin polynomial coefficients.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 6, 2, 1, 10, 10, 1, 15, 30, 5, 1, 21, 70, 35, 1, 28, 140, 140, 14, 1, 36, 252, 420, 126, 1, 45, 420, 1050, 630, 42, 1, 55, 660, 2310, 2310, 462, 1, 66, 990, 4620, 6930, 2772, 132, 1, 78, 1430, 8580, 18018, 12012, 1716, 1, 91, 2002, 15015, 42042

Offset: 0

Michael Somos, Jun 14 2000

T(n,k) = number of Motzkin paths of length n with k up steps. T(n,k)=number of 0-1-2 trees with n edges and k+1 leaves, n>0. (A 0-1-2 tree is an ordered tree in which every vertex has at most two children.) E.g., T(4,1)=6 because we have UDHH, UHDH, UHHD, HHUD, HUHD, HUDH, where U=(1,1), D(1,-1), H(1,0). - Emeric Deutsch, Nov 30 2003
Coefficients in series reversion of x/(1+H*x+U*D*x^2) corresponding to Motzkin paths with H colors for H(1,0), U colors for U(1,1) and D colors for D(1,-1). - Paul Barry, May 16 2005
Eigenvector equals A119020, so that A119020(n) = Sum_{k=0..[n/2]} T(n,k)*A119020(k). - Paul D. Hanna, May 09 2006
Row reverse of A107131. - Peter Bala, May 07 2012
Also equals the number of 231-avoiding permutations of n+1 for which descents(w) = peaks(w) = k, where descents(w) is the number of positions i such that w[i]>w[i+1], and peaks(w) is the number of positions i such that w[i-1]w[i+1]. For example, T(4,1) = 6 because 13245, 12435, 14235, 12354, 12534, 15234 are the only 231-avoiding permutations of 5 elements with descents(w) = peaks(w) = 1. - Kyle Petersen, Aug 02 2013
Apparently, a refined irregular triangle related to this triangle (and A097610) is given in the Alexeev et al. link on p. 12. This entry's triangle is also related through Barry's comment to A125181 and A134264. The diagonals of this entry are the rows of A088617. - Tom Copeland, Jun 17 2015
The row length sequence of this irregular triangle is A008619(n) = 1 + floor(n/2). - Wolfdieter Lang, Aug 24 2015

			The irregular triangle T(n,k) begins:
n\k 0  1   2    3   4  5 ...
0:  1
1:  1
2:  1  1
3:  1  3
4:  1  6   2
5:  1 10  10
6:  1 15  30    5
7:  1 21  70   35
8:  1 28 140  140  14
9:  1 36 252  420 126
10: 1 45 420 1050 630 42
... reformatted. - _Wolfdieter Lang_, Aug 24 2015

Miklos Bona, Handbook of Enumerative Combinatorics, CRC Press (2015), page 617, Corollary 10.8.2
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 4.3.

Alois P. Heinz, Rows n = 0..200, flattened
N. Alexeev, J. Andersen, R. Penner, and P. Zograf, Enumeration of chord diagrams on many intervals and their non-orientable analogs, arXiv:1307.0967 [math.CO], 2013-2014.
Marcello Artioli, Giuseppe Dattoli, Silvia Licciardi, and Simonetta Pagnutti, Motzkin Numbers: an Operational Point of View, arXiv:1703.07262 [math.CO], 2017.
Paul Barry, The Gamma-Vectors of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1804.05027 [math.CO], 2018.
Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.
Colin Defant, Postorder Preimages, arXiv preprint arXiv:1604.01723 [math.CO], 2016.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.
Thomas Grubb and Frederick Rajasekaran, Set Partition Patterns and the Dimension Index, arXiv:2009.00650 [math.CO], 2020. Mentions this sequence.
Paul W. Lapey and Aaron Williams, A Shift Gray Code for Fixed-Content Łukasiewicz Words, Williams College, 2022.
Shi-Mei Ma, On gamma-vectors and the derivatives of the tangent and secant functions, arXiv:1304.6654 [math.CO], 2013.
E. Marberg, Actions and identities on set partitions, arXiv preprint arXiv:1107.4173 [math.CO], 2011-2012.
MathOverflow, Motzkin polynomials and enumeration of chord diagrams.
Jean-Christophe Novelli and Jean-Yves Thibon, Noncommutative Symmetric Functions and Lagrange Inversion II: Noncrossing partitions and the Farahat-Higman algebra, arXiv:2106.08257 [math.CO], 2021-2022. See p. 32.
A. Postnikov, V. Reiner, and L. Williams, Faces of generalized permutohedra, arXiv:math/0609184 [math.CO], 2006-2007.
Tad White, Quota Trees, arXiv:2401.01462 [math.CO], 2024. See p. 20.
Claude Zeller and Robert Cordery, Light scattering as a Poisson process and first passage probability, arXiv:1906.11131 [cond-mat.stat-mech], 2019.

A107131 (row reversed), A080159 (with trailing zeros), A001006 = row sums, A000108(n) = T(2n, n), A001700(n) = T(2n+1, n), A119020 (eigenvector), A001263 (Narayana numbers), A089627 (gamma vectors of type B associahedra), A101280 (gamma vectors of type A permutohedra).
Cf. A125181, A134264, A088617, A161642, A258820, A003989, A008315, A091156, A011973, A097610, A126120.
Cf. A014531.

b:= proc(x, y) option remember;
      `if`(y>x or y<0, 0, `if`(x=0, 1, expand(
       b(x-1, y) +b(x-1, y+1) +b(x-1, y-1)*t)))
    end:
T:= n-> (p-> seq(coeff(p, t, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..20);  # Alois P. Heinz, Feb 05 2014

m=(1-x-(1-2x+x^2-4x^2y)^(1/2))/(2x^2 y); Map[Select[#,#>0&]&, CoefficientList[ Series[m,{x,0,15}],{x,y}]]//Grid (* Geoffrey Critzer, Feb 05 2014 *)
p[n_] := Hypergeometric2F1[(1-n)/2, -n/2, 2, 4 x]; Table[CoefficientList[p[n], x], {n, 0, 13}] // Flatten (* Peter Luschny, Jan 23 2018 *)

{T(n, k) = if( k<0 || 2*k>n, 0, n! / ((n-2*k)! * k! * (k+1)!))}

{T(n, k) = if( k<0 || 2*k>n, 0, polcoeff( polcoeff( 2 / (1 - x + sqrt((1 - x)^2 - 4*y*x^2 + x * O(x^n))), n), k))} /* Michael Somos, Feb 14 2006 */

{T(n, k) = n++; if( k<0 || 2*k>n, 0, polcoeff( polcoeff( serreverse( x / (1 + x + y*x^2) + x * O(x^n)), n), k))} /* Michael Somos, Feb 14 2006 */

T(n,k) = n!/((n-2k)! k! (k+1)!) = A007318(n, 2k)*A000108(k). - Henry Bottomley, Jan 31 2003
E.g.f. row polynomials R(n,y): exp(x)*BesselI(1, 2*x*sqrt(y))/(x*sqrt(y)). - Vladeta Jovovic, Aug 20 2003
G.f. row polynomials R(n,y): 2 / (1 - x + sqrt((1 - x)^2 - 4 *y * x^2)).
From Peter Bala, Oct 28 2008: (Start)
The rows of this triangle are the gamma vectors of the n-dimensional (type A) associahedra (Postnikov et al., p. 38). Cf. A089627 and A101280.
The row polynomials R(n,x) = Sum_{k = 0..n} T(n,k)*x^k begin R(0,x) = 1, R(1,x) = 1, R(2,x) = 1 + x, R(3,x) = 1 + 3*x. They are related to the Narayana polynomials N(n,x) := Sum_{k = 1..n} (1/n)*C(n,k)*C(n,k-1)*x^k through x*(1 + x)^n*R(n, x/(1 + x)^2) = N(n+1,x). For example, for n = 3, x*(1 + x)^3*(1 + 3*x/(1 + x)^2) = x + 6*x^2 + 6*x^3 + x^4, the 4th Narayana polynomial.
Recursion relation: (n + 2)*R(n,x) = (2*n + 1)*R(n-1,x) - (n - 1)*(1 - 4*x)*R(n-2,x), R(0,x) = 1, R(1,x) = 1. (End)
G.f.: M(x,y) satisfies: M(x,y)= 1 + x M(x,y) + y*x^2*M(x,y)^2. - Geoffrey Critzer, Feb 05 2014
T(n,k) = A161642(n,k)*A258820(n,k) = (binomial(n,k)/A003989(n+1, k+1))* A258820(n,k). - Tom Copeland, Jun 18 2015
Let T(n,k;q) = n!*(1+k)/((n-2*k)!*(1+k)!^2)*hypergeom([k,2*k-n],[k+2],q) then T(n,k;0) = A055151(n,k), T(n,k;1) = A008315(n,k) and T(n,k;-1) = A091156(n,k). - Peter Luschny, Oct 16 2015
From Tom Copeland, Jan 21 2016: (Start)
Reversed rows of A107131 are rows of this entry, and the diagonals of A107131 are the columns of this entry. The diagonals of this entry are the rows of A088617. The antidiagonals (bottom to top) of A088617 are the rows of this entry.
O.g.f.: [1-x-sqrt[(1-x)^2-4tx^2]]/(2tx^2), from the relation to A107131.
Re-indexed and signed, this triangle gives the row polynomials of the compositional inverse of the shifted o.g.f. for the Fibonacci polynomials of A011973, x / [1-x-tx^2] = x + x^2 + (1+t) x^3 + (1+2t) x^4 + ... . (End)
Row polynomials are P(n,x) = (1 + b.y)^n = Sum{k=0 to n} binomial(n,k) b(k) y^k = y^n M(n,1/y), where b(k) = A126120(k), y = sqrt(x), and M(n,y) are the Motzkin polynomials of A097610. - Tom Copeland, Jan 29 2016
Coefficients of the polynomials p(n,x) = hypergeom([(1-n)/2, -n/2], [2], 4x). - Peter Luschny, Jan 23 2018
Sum_{k=1..floor(n/2)} k * T(n,k) = A014531(n-1) for n>1. - Alois P. Heinz, Mar 29 2020

A107264 Expansion of (1 - 3x - sqrt((1-3x)^2 - 43x^2))/(23x^2).

Original entry on oeis.org

1, 3, 12, 54, 261, 1323, 6939, 37341, 205011, 1143801, 6466230, 36960300, 213243435, 1240219269, 7263473148, 42799541886, 253556163243, 1509356586897, 9023497273548, 54154973176074, 326154592965879, 1970575690572297

Offset: 0

Paul Barry, May 15 2005

Series reversion of x/(1+3x+3x^2). Transform of 3^n under the matrix A107131. A row of A107267.
Counts colored Motzkin paths, where H(1,0) and U(1,1) each have 3 colors and D(1,-1) one color. - Paul Barry, May 18 2005
Number of Motzkin paths of length n in which both the "up" and the "level" steps come in three colors. - Paul Barry, May 18 2005
Third binomial transform of 1,0,3,0,18,0,... or 3^n*C(n) (A005159) with interpolated zeros. - Paul Barry, May 24 2005
As a continued fraction, the g.f. is 1/(1-3*x-3*x^2/(1-3*x-3*x^2/(1-3*x-3*x^2/(1-3*x-3*x^2/(.... - Paul Barry, Dec 02 2008

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group and Chebyshev polynomials, arXiv:2502.13673 [math.CO], 2025.
N. Gabriel, K. Peske, L. Pudwell, and S. Tay, Pattern Avoidance in Ternary Trees, J. Int. Seq. 15 (2012) # 12.1.5.
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.
L. Pudwell, Pattern avoidance in trees, (slides from a talk, mentions many sequences), 2012. - From _N. J. A. Sloane_, Jan 03 2013

CoefficientList[Series[(1-3*x-Sqrt[1-6*x-3*x^2])/(6*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 17 2012 *)

G.f.: (1 - 3x - sqrt(1-6x-3x^2))/(6x^2);
a(n) = Sum_{k=0..n} (1/(k+1))*C(k+1, n-k+1)*C(n, k)3^k.
a(n) = Sum_{k=0..floor(n/2)} C(n, 2k)*C(k)*3^(n-k). - Paul Barry, May 18 2005
E.g.f.: exp(3x)*Bessel_I(1, sqrt(3)*2*x)/(sqrt(3)*x). - Paul Barry, May 24 2005
a(n) = (1/Pi)*Integral_{x=3-2*sqrt(3)..3+2*sqrt(3)} x^n*sqrt(-x^2 + 6*x + 3)/6. - Paul Barry, Sep 16 2006
a(n) = A156016(n+1)/3. - Philippe Deléham, Feb 04 2009
D-finite with recurrence: (n+2)*a(n) = 3*(2*n+1)*a(n-1) + 3*(n-1)*a(n-2). - Vaclav Kotesovec, Oct 17 2012
a(n) ~ (5+3*sqrt(3))*(3+2*sqrt(3))^n/(2*sqrt(2*Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 17 2012
G.f.: Let F(x) be the g.f. of A348189 with offset 1, then F(x) = x + 2*x^2*F(x)^2*A(x*F(x)). - Alexander Burstein, Feb 14 2022

A005774 Number of directed animals of size n (k=1 column of A038622); 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, where s(0) = 2; also sum of row n+1 of array T in A026323.

Original entry on oeis.org

0, 1, 3, 9, 26, 75, 216, 623, 1800, 5211, 15115, 43923, 127854, 372749, 1088283, 3181545, 9312312, 27287091, 80038449, 234988827, 690513030, 2030695569, 5976418602, 17601021837, 51869858544, 152951628725, 451271872701, 1332147482253

Offset: 0

Simon Plouffe

Number of ordered trees with n+1 edges, having root degree at least 2 and nonroot outdegrees at most 2. - Emeric Deutsch, Aug 02 2002
From Petkovsek's algorithm, this recurrence does not have any closed form solutions. So there is no hypergeometric closed form for a(n). - Herbert S. Wilf
Sum of two consecutive trinomial coefficients starting two positions before central one. Example: a(4) = 10+16 and (1 + x + x^2)^4 = ... + 10*x^2 + 16*x^3 + 19*x^4 + ... - David Callan, Feb 07 2004
Image of n (A001477) under the Motzkin related matrix A107131. Binomial transform of A037952. - Paul Barry, May 12 2005
a(n) = total number of ascents (maximal runs of consecutive upsteps) in all Motzkin (n+1)-paths. For example, the 9 Motzkin 4-paths are FFFF, FFUD, FUDF, FUFD, UDFF, UDUD, UFDF, UFFD, UUDD and they contain a total of 9 ascents and so a(3)=9 (U=upstep, D=downstep, F=flatstep). - David Callan, Aug 16 2006
Image of the sequence (0,1,2,3,3,3,...) under the array A122896. - Paul Barry, Sep 18 2006
This is some kind of Motzkin transform of A079978 because the substitution x-> x*A001006(x) in the independent variable of the g.f. A079978(x) yields 1,0 followed by this sequence here. - R. J. Mathar, Nov 08 2008

			G.f.: x + 3*x^2 + 9*x^3 + 26*x^4 + 75*x^5 + 216*x^6 + 623*x^7 + ...

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

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
P. Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
D. Gouyou-Beauchamps, G. Viennot, Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Adv. in Appl. Math. 9 (1988), no. 3, 334-357.
Christian Krattenthaler, Daniel Yaqubi, Some determinants of path generating functions, II, arXiv:1802.05990 [math.CO], 2018; Adv. Appl. Math. 101 (2018), 232-265.
Simon Plouffe, Approximations de Séries Génératrices et Quelques Conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, Une méthode pour obtenir la fonction génératrice d'une série, FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.

Cf. A038622, A098494, A026010, A005773, A005775, A066822.

a005774 0 = 0
a005774 n = a038622 n 1 -- Reinhard Zumkeller, Feb 26 2013

seq( add(binomial(i,k+1)*binomial(i-k,k), k=0..floor(i/2)), i=0..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
seq(simplify(GegenbauerC(n-2,-n,-1/2) + GegenbauerC(n-1,-n,-1/2)), n=0..27); # Peter Luschny, May 12 2016

CoefficientList[Series[(1-x-Sqrt[1-2x-3x^2])/(x(1-3x+Sqrt[1-2x-3x^2])),{x,0,30}],x] (* Harvey P. Dale, Sep 20 2011 *)
RecurrenceTable[{a[0]==0, a[1]==1,a[n]==(2n(n+1)a[n-1]+3n(n-1)a[n-2])/ ((n+2)(n-1))},a,{n,30}] (* Harvey P. Dale, Nov 09 2012 *)

s=[0,1]; {A005774(n)=k=(2*(n+2)*(n+1)*s[2]+3*(n+1)*n*s[1])/((n+3)*n); s[1]=s[2]; s[2]=k; k}

{a(n) = if( n<2, n>0, (2 * (n+1) * n *a(n-1) + 3 * (n-1) * n * a(n-2)) / (n+2) / (n-1))}; /* Michael Somos, May 01 2003 */

Inverse binomial transform of [ 0, 1, 5, 21, 84, ... ] (A002054). - John W. Layman
D-finite with recurrence (n+2)*(n-1)*a(n) = 2*n*(n+1)*a(n-1) + 3*n*(n-1)*a(n-2) for all n in Z. - Michael Somos, May 01 2003
E.g.f.: exp(x)*(BesselI(1, 2*x)+BesselI(2, 2*x)). - Vladeta Jovovic, Jan 01 2004
G.f.: (1-x-sqrt(1-2x-3x^2))/(x(1-3x+sqrt(1-2x-3x^2))); a(n)= Sum_{k=0..n} C(k+1, n-k+1)*C(n, k)*k/(k+1); a(n) = Sum_{k=0..n} C(n, k)*C(k, floor((k-1)/2)). - Paul Barry, May 12 2005
Starting (1, 3, 9, 26, ...) = binomial transform of A026010: (1, 2, 4, 7, 14, 25, 50, 91, ...). - Gary W. Adamson, Oct 22 2007
a(n)*(2+n) = (4+4*n)*a(n-1) - n*a(n-2) + (12-6*n)*a(n-3). - Simon Plouffe, Feb 09 2012
a(n) ~ 3^(n+1/2) / sqrt(Pi*n). - Vaclav Kotesovec, Mar 10 2014
0 = a(n)*(+36*a(n+1) + 18*a(n+2) - 96*a(n+3) + 30*a(n+4)) + a(n+1)*(-6*a(n+1) + 49*a(n+2) - 26*a(n+3) + 3*a(n+4)) + a(n+2)*(+15*a(n+3) - 8*a(n+4)) + a(n+3)*(a(n+4)) if n >= 0. - Michael Somos, Aug 06 2014
a(n) = GegenbauerC(n-2,-n,-1/2) + GegenbauerC(n-1,-n,-1/2). - Peter Luschny, May 12 2016

Further descriptions from Clark Kimberling

A107267 A square array of Motzkin related transforms, read by antidiagonals.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 4, 6, 3, 1, 0, 9, 20, 12, 4, 1, 0, 21, 72, 54, 20, 5, 1, 0, 51, 272, 261, 112, 30, 6, 1, 0, 127, 1064, 1323, 672, 200, 42, 7, 1, 0, 323, 4272, 6939, 4224, 1425, 324, 56, 8, 1, 0, 835, 17504, 37341, 27456, 10625, 2664, 490, 72, 9, 1

Offset: 0

Paul Barry, May 15 2005

Rows are transforms of k^n, k>=0, under the matrix A107131. As a number triangle, with T(n,k)=if(k<=n,sum{j=0..n-k, (1/(j+1))C(j+1,n-k-j+1)C(n-k,j)k^j},0), row sums are A107268 and diagonal sums are A107269. Rows are series reversions of x/(1+kx+kx^2), k>=0. Conjecture: rows count weighted Motzkin paths.

Row k counts colored Motzkin paths, where H(1,0) and U(1,1) each have k colors and D(1,-1) one color. - Paul Barry, May 16 2005

			Array begins
  1, 0,  0,   0,    0,     0,      0, ...
  1, 1,  2,   4,    9,    21,     51, ...
  1, 2,  6,  20,   72,   272,   1064, ...
  1, 3, 12,  54,  261,  1323,   6939, ...
  1, 4, 20, 112,  672,  4224,  27456, ...
  1, 5, 30, 200, 1425, 10625,  81875, ...
  1, 6, 42, 324, 2664, 22896, 203256, ...

Seiichi Manyama, Antidiagonals n = 0..139, flattened

Rows n=0..6 give A000007, A001006, A071356, A107264, A003645, A107265, A107266.
Main diagonal gives A292716.
Cf. A000108.

Number array T(n,k) = Sum_{j=0..k} n^j * binomial(k,j) * binomial(j+1,k-j+1)/(j+1).
G.f. of row k: 1/(1 - k*x - k*x^2/(1 - k*x - k*x^2/(1 - k*x - k*x^2/(1 - k*x - k*x^2/(1 - ...))))), a continued fraction. - Ilya Gutkovskiy, Sep 21 2017
From Seiichi Manyama, May 05 2019: (Start)
T(n,k) = Sum_{j=0..floor(k/2)} n^(k-j) * binomial(k,2*j) * binomial(2*j,j)/(j+1) = Sum_{j=0..floor(k/2)} n^(k-j) * binomial(k,2*j) * A000108(j).
(k+2) * T(n,k) = n * (2*k+1) * T(n,k-1) - n * (n-4) * (k-1) * T(n,k-2). (End)

A140662 Number of possible column states for self-avoiding polygons in a slit of width n.

Original entry on oeis.org

1, 3, 8, 20, 50, 126, 322, 834, 2187, 5797, 15510, 41834, 113633, 310571, 853466, 2356778, 6536381, 18199283, 50852018, 142547558, 400763222, 1129760414, 3192727796, 9043402500, 25669818475, 73007772801, 208023278208, 593742784828, 1697385471210, 4859761676390

Offset: 1

R. J. Mathar, Jul 11 2008

Number of Dyck (n+1)-paths whose maximum ascent length is 2. - David Scambler, Aug 22 2012

Number of (n+1)-Motzkin-paths with at least one up-step (see A001006 and the Python program). - Peter Luschny, Dec 03 2024

			The 20 Motzkin-paths of length 5 with at least one up-step are: UUDDF, UUDFD, UUFDD, UDUDF, UDUFD, UDFUD, UDFFF, UFUDD, UFDUD, UFDFF, UFFDF, UFFFD, FUUDD, FUDUD, FUDFF, FUFDF, FUFFD, FFUDF, FFUFD, FFFUD.

J. Alvarez, E.J. Janse van Rensburg et al. Self-avoiding walks and polygons in slits.
Xiaomei Chen, Counting humps and peaks in Motzkin paths with height k, arXiv:2412.00668 [math.CO], 2024. See p. 7.
Louis Marin, Counting Polyominoes in a Rectangle b X h, arXiv:2406.16413 [cs.DM], 2024. See p. 148.

Cf. A055151, A080159, A088617, A107131, A097610.
Cf. A001006.
Column k=2 of A203717 (shifted).

a := n -> n*(n + 1)*hypergeom([1, -n/2 + 1, 1/2 - n/2], [2, 3], 4)/2:
seq(simplify(a(n)), n = 1..30);  # Peter Luschny, Dec 03 2024

# A generator of the Motzkin-paths with at least one up-step.
C = str.count
def aGen(n: int): # -> Generator[str, Any, list[str]]
    a = [""]
    for w in a:
        if len(w) == n + 1:
            if (C(w, "U") > 0 and 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(1, 6):
    SAP = [w for w in aGen(n)]
    print(len(SAP), ":", SAP)  # Peter Luschny, Dec 03 2024

a(n) = Sum_{m=1..[(n+1)/2]} (n+1)!/((n+1-2m)!m!(m+1)!).
a(n) = A001006(n + 1) - 1. [Corrected by Peter Luschny, Dec 03 2024]
D-finite with recurrence (n+3)*a(n) + (-4*n-7)*a(n-1) + (2*n+3)*a(n-2) + (4*n-5)*a(n-3) + 3*(-n+2)*a(n-4) = 0. - R. J. Mathar, Nov 01 2021
From Peter Luschny, Dec 03 2024: (Start)
a(n) = (1/2)*n*(n + 1)*hypergeom([1, -n/2 + 1, 1/2 - n/2], [2, 3], 4).
a(n) = n!*[x^n]((exp(x)*(-x^3 + 2*(2*x - 3)*x*BesselI(0,2*x) + (x*(5*x - 4) + 6)*BesselI(1, 2* x)))/x^3). (End)

A107265 Expansion of (1-5x-sqrt((1-5x)^2-45x^2))/(25x^2).

Original entry on oeis.org

1, 5, 30, 200, 1425, 10625, 81875, 646875, 5211875, 42659375, 353725000, 2965031250, 25083859375, 213894609375, 1836516718750, 15863968750000, 137767560546875, 1202116083984375, 10534061644531250, 92664360625000000, 817975366904296875, 7243402948779296875

Offset: 0

Paul Barry, May 15 2005

Series reversion of x/(1+5x+5x^2). Transform of 5^n under the matrix A107131. A row of A107267.

Counts colored Motzkin paths, where H(1,0) and U(1,1) each have 5 colors and D(1,-1) one color. - Paul Barry, May 16 2005

Vincenzo Librandi, Table of n, a(n) for n = 0..200

CoefficientList[Series[(1-5*x-Sqrt[1-10*x+5*x^2])/(10*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 17 2012 *)

x='x+O('x^66); Vec((1-5*x-sqrt(1-10*x+5*x^2))/(10*x^2)) \\ Joerg Arndt, May 15 2013

G.f.: (1-5*x-sqrt(1-10*x+5*x^2))/(10*x^2).
a(n) = Sum_{k=0..n} (1/(k+1)) * C(k+1,n-k+1) * C(n, k) * 5^k.
E.g.f.: a(n) = n!* [x^n] exp(5*x)*BesselI(1,2*sqrt(5)*x) /(sqrt(5)*x). -Peter Luschny, Aug 25 2012
D-finite with recurrence: (n+2)*a(n) = 5*(2*n+1)*a(n-1) - 5*(n-1)*a(n-2). - Vaclav Kotesovec, Oct 17 2012
a(n) ~ sqrt(38+17*sqrt(5))*(5+2*sqrt(5))^n/(2*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 17 2012
G.f.: 1/(1 - 5*x - 5*x^2/(1 - 5*x - 5*x^2/(1 - 5*x - 5*x^2/(1 - 5*x - 5*x^2/(1 - ...))))), a continued fraction. - Ilya Gutkovskiy, Sep 21 2017

A359364 Triangle read by rows. The Motzkin triangle, the coefficients of the Motzkin polynomials. M(n, k) = binomial(n, k) * CatalanNumber(k/2) if k is even, otherwise 0.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 6, 0, 2, 1, 0, 10, 0, 10, 0, 1, 0, 15, 0, 30, 0, 5, 1, 0, 21, 0, 70, 0, 35, 0, 1, 0, 28, 0, 140, 0, 140, 0, 14, 1, 0, 36, 0, 252, 0, 420, 0, 126, 0, 1, 0, 45, 0, 420, 0, 1050, 0, 630, 0, 42, 1, 0, 55, 0, 660, 0, 2310, 0, 2310, 0, 462, 0

Offset: 0

Peter Luschny, Jan 09 2023

The generalized Motzkin numbers M(n, k) are a refinement of the Motzkin numbers M(n) (A001006) in the sense that they are coefficients of polynomials M(n, x) = Sum_{n..k} M(n, k) * x^k that take the value M(n) at x = 1. The coefficients of x^n are the aerated Catalan numbers A126120.
Variants are the irregular triangle A055151 with zeros deleted, A097610 with reversed rows, A107131 and A080159.
In the literature the name 'Motzkin triangle' is also used for the triangle A026300, which is generated from the powers of the generating function of the Motzkin numbers.

			Triangle M(n, k) starts:
[0] 1;
[1] 1, 0;
[2] 1, 0,  1;
[3] 1, 0,  3, 0;
[4] 1, 0,  6, 0,   2;
[5] 1, 0, 10, 0,  10, 0;
[6] 1, 0, 15, 0,  30, 0,   5;
[7] 1, 0, 21, 0,  70, 0,  35, 0;
[8] 1, 0, 28, 0, 140, 0, 140, 0,  14;
[9] 1, 0, 36, 0, 252, 0, 420, 0, 126, 0;

M. Artioli, G. Dattoli, S. Licciardi, and S. Pagnutti, Motzkin Numbers: an Operational Point of View, arXiv:1703.07262 [math.CO], 2017, (Table 1 on p. 3).

Variants: A055151, A080159, A097610, A107131.
Columns M(n, 2*k): A000012, A000217, A034827, A000910, A088625, A088626, A213380.
Cf. A001006 (Motzkin numbers), A026300 (Motzkin gf. triangle), A126120 (aerated Catalan), A000108 (Catalan).
Cf. A138364, A107587, A002457, A002522, A025179, A025235, A056107, A014531, A023426, A091147, A189912, A343386, A343773, A359647, A359649.

CatalanNumber := n -> binomial(2*n, n)/(n + 1):
M := (n, k) -> ifelse(irem(k, 2) = 1, 0, CatalanNumber(k/2)*binomial(n, k)):
for n from 0 to 9 do seq(M(n, k), k = 0..n) od;
# Alternative, as coefficients of polynomials:
p := n -> hypergeom([(1 - n)/2, -n/2], [2], (2*x)^2):
seq(print(seq(coeff(simplify(p(n)), x, k), k = 0..n)), n = 0..9);
# Using the exponential generating function:
egf := exp(x)*BesselI(1, 2*x*t)/(x*t): ser:= series(egf, x, 11):
seq(print(seq(coeff(simplify(n!*coeff(ser, x, n)), t, k), k = 0..n)), n = 0..9);

from functools import cache
@cache
def M(n: int, k: int) -> int:
    if k %  2: return 0
    if n <  3: return 1
    if n == k: return (2 * (n - 1) * M(n - 2, n - 2)) // (n // 2 + 1)
    return (M(n - 1, k) * n) // (n - k)
for n in range(10): print([M(n, k) for k in range(n + 1)])

Let p(n, x) = hypergeom([(1 - n)/2, -n/2], [2], (2*x)^2).
p(n, 1) = A001006(n); p(n, sqrt(2)) = A025235(n); p(n, 2) = A091147(n).
p(2, n) = A002522(n); p(3, n) = A056107(n).
p(n, n) = A359649(n); 2^n*p(n, 1/2) = A000108(n+1).
M(n, k) = [x^k] p(n, x).
M(n, k) = [t^k] (n! * [x^n] exp(x) * BesselI(1, 2*t*x) / (t*x)).
M(n, k) = [t^k][x^n] ((1 - x - sqrt((x-1)^2 - (2*t*x)^2)) / (2*(t*x)^2)).
M(n, n) = A126120(n).
M(n, n-1) = A138364(n), the number of Motzkin n-paths with exactly one flat step.
M(2*n, 2*n) = A000108(n), the number of peakless Motzkin paths having a total of n up and level steps.
M(4*n, 2*n) = A359647(n), the central terms without zeros.
M(2*n+2, 2*n) = A002457(n) = (-4)^n * binomial(-3/2, n).
Sum_{k=0..n} M(n - k, k) = A023426(n).
Sum_{k=0..n} k * M(n, k) = 2*A014531(n-1) = 2*GegenbauerC(n - 2, -n, -1/2).
Sum_{k=0..n} i^k*M(n, k) = A343773(n), (i the imaginary unit), is the excess of the number of even Motzkin n-paths (A107587) over the odd ones (A343386).
Sum_{k=0..n} Sum_{j=0..k} M(n, j) = A189912(n).
Sum_{k=0..n} Sum_{j=0..k} M(n, n-j) = modified A025179(n).
For a recursion see the Python program.

cp's OEIS Frontend

A136787 Triangle read by rows: A107131 * A000012.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A136788 Triangle read by rows: A000012 * A107131.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A088617 Triangle read by rows: T(n,k) = C(n+k,n)*C(n,k)/(k+1), for n >= 0, k = 0..n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A055151 Triangular array of Motzkin polynomial coefficients.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

A107264 Expansion of (1 - 3*x - sqrt((1-3*x)^2 - 4*3*x^2))/(2*3*x^2).

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Formula

A005774 Number of directed animals of size n (k=1 column of A038622); 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, where s(0) = 2; also sum of row n+1 of array T in A026323.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions

A107267 A square array of Motzkin related transforms, read by antidiagonals.

Views

Author

Keywords

Comments

A107264 Expansion of (1 - 3x - sqrt((1-3x)^2 - 43x^2))/(23x^2).

A107265 Expansion of (1-5x-sqrt((1-5x)^2-45x^2))/(25x^2).