A055151 -id:A055151 - cp's OEIS frontend

A091156 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having k long ascents (i.e., ascents of length at least 2). Rows are of length 1,1,2,2,3,3,... .

1, 1, 1, 1, 1, 4, 1, 11, 2, 1, 26, 15, 1, 57, 69, 5, 1, 120, 252, 56, 1, 247, 804, 364, 14, 1, 502, 2349, 1800, 210, 1, 1013, 6455, 7515, 1770, 42, 1, 2036, 16962, 27940, 11055, 792, 1, 4083, 43086, 95458, 57035, 8217, 132, 1, 8178, 106587, 305812, 257257

Offset: 0

Emeric Deutsch, Feb 22 2004

Also number of ordered trees with n edges, having k branch nodes (i.e., vertices of outdegree at least 2).
Also number of Łukasiewicz paths of length n having k fall steps (1,-1) that start at an odd level. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(4,2)=2 because we have U(D)U(D) and U(3)(D)D(D), where U=(1,1), D=(1,-1), U(3)=(1,3) and the fall steps that start at an odd level are shown between parentheses. Row n has 1+floor(n/2) terms. Row sums are the Catalan numbers (A000108). T(2n,n)=A000108(n). T(2n+1,n)=A001791(n+1)=binomial(2n+2,n). - Emeric Deutsch, Jan 06 2005
Also number of Dyck paths of semilength n with k UUD's - I. Tasoulas (jtas(AT)unipi.gr), Feb 19 2006
T(n,k) = number of Dyck n-paths whose decomposition into 2-step subpaths contains k UUs. For example, T(4,2)=2 counts UU|UU|DD|DD, UU|DD|UU|DD (vertical bars indicate path decomposition). - David Callan, Jun 07 2006
T(n,k) = number of binary trees on n-1 edges containing k right edges whose child vertex has no right child. Under Knuth's "natural" correspondence, such a vertex in binary (n-1)-tree ~ a vertex of outdegree >=2 in ordered n-tree. - David Callan, Sep 25 2006
T(n,k) = number of binary trees on n-1 edges containing k left edges whose child vertex has no left child. Under "natural" correspondence, such a vertex in binary (n-1)-tree ~ a leaf edge with no left neighbor edge and not incident to the root in ordered n-tree ~ a UUD in Dyck n-path. - David Callan, Sep 25 2006
T(n,k) = number of permutations of length n avoiding 321 (classically) with k descents. - Andrew Baxter, May 17 2011.

			T(4,1) = 11 because among the 14 Dyck paths of semilength 4, the paths that do not have exactly one long ascent are UDUDUDUD (no long ascent), UUDDUUDD (two long ascents) and UUDUUDDD (two long ascents). Here U=(1,1) and D=(1,-1).
Triangle begins:
  1;
  1;
  1,    1;
  1,    4;
  1,   11,    2;
  1,   26,   15;
  1,   57,   69,    5;
  1,  120,  252,   56;
  1,  247,  804,  364,   14;
  1,  502, 2349, 1800,  210;
  1, 1013, 6455, 7515, 1770, 42;
  ...

R. P. Stanley, Enumerative Combinatorics, Vol. 1, 1986; See Exercise 3.71(f).

Alois P. Heinz, Rows n = 0..200, flattened
M. Barnabei et al., The descent statistic over 123-avoiding permutations, arXiv:0910.0963 [math.CO], 2009.
A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011. See p. 88.
Michael Bukata, Ryan Kulwicki, Nicholas Lewandowski, Lara Pudwell, Jacob Roth, Teresa Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv:1812.07112 [math.CO], 2018.
Colin Defant, Stack-Sorting Preimages of Permutation Classes, arXiv:1809.03123 [math.CO], 2018.
Katie R. Gedeon, Kazhdan-Lusztig polynomials of thagomizer matroids, arXiv:1610.05349 [math.CO], 2016.
Y. Park, S. Park, Avoiding permutations and the Narayana numbers, J. Korean Math. Soc. 50 (2013), No. 3, pp. 529-541.
Lara Pudwell, On the distribution of peaks (and other statistics), 16th International Conference on Permutation Patterns, Dartmouth College, 2018.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
Chao-Jen Wang, Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords.
Philip B. Zhang and Sergey Kitaev, Descent generating polynomials for (n-3)- and (n-4)-stack-sortable (pattern-avoiding) permutations, Discrete Applied Mathematics, Volume 372, 2025, Pages 1-14.
Index entries for sequences related to Łukasiewicz

Cf. A000108, A001791, A243752.

T(n,k) are rational multiples of A055151.

a := (n,k)->binomial(n+1,k)* add(binomial(k+j-1,k-1)*binomial(n+1-k, n-2*k-j), j=0..n-2*k)/(n+1); seq(seq(a(n,k), k=0..floor(n/2)),n=0..15);
seq(seq(simplify(n!*(1+k)/((n-2*k)!*(1+k)!^2)*hypergeom([k,2*k-n],[k+2],-1)),k=0.. floor(n/2)),n=0..15); # Peter Luschny, Oct 16 2015
# alternative Maple program:
b:= proc(x, y) option remember; `if`(y>x or y<0, 0,
      `if`(x=0, 1, expand(b(x-1, y)*`if`(y=0, 1, 2)*z+
       b(x-1, y+1) +b(x-1, y-1))))
    end:
T:= n-> (p-> seq(coeff(p, z, n-2*i), i=0..n/2))(b(n, 0)):
seq(T(n), n=0..15);  # Alois P. Heinz, Aug 07 2018

T[n_, k_] := Binomial[n+1, k]*Sum[Binomial[k+j-1, k-1]*Binomial[n+1-k, n- 2*k-j], {j, 0, n-2*k}]/(n+1); Table[T[n, k], {n, 0, 15}, {k, 0, Floor[n/2 ]}] // Flatten (* Jean-François Alcover, Jan 31 2016 *)

tabf(nn) = {for(n=-1, nn, for(k=0, floor(n/2), if(binomial(n+1,k) * sum(j=0, n-2*k, binomial(k+j-1,k-1) * binomial(n+1-k,n-2*k-j))/(n+1)==0,print1("1, "), print1(binomial(n+1,k) * sum(j=0, n-2*k, binomial(k+j-1,k-1) * binomial(n+1-k,n-2*k-j))/(n+1),", "));); print();); };
tabf(16); \\ Indranil Ghosh, Mar 05 2017

T(n,k) = (1/(n+1)) * binomial(n+1, k) * Sum_{j=0..n-2k} binomial(k+j-1, k-1)*binomial(n+1-k, n-2k-j).
G.f. G(t, z) satisfies z*(1-z+t*z)*G^2 - G + 1 = 0.
T(n,k) = n!*(1+k)/((n-2*k)!*(1+k)!^2)*hypergeom([k,2*k-n], [k+2], -1). - Peter Luschny, Oct 16 2015
T(n,k) = A055151(n,k)*hypergeom([k,2*k-n],[k+2],-1). - Peter Luschny, Oct 16 2015

Edited by Andrew Baxter, May 17 2011

A101280 Triangle T(n,k) (n >= 1, 0 <= k <= floor((n-1)/2)) read by rows, where T(n,k) = (k+1)T(n-1,k) + (2n-4k)T(n-1,k-1).

Original entry on oeis.org

1, 1, 1, 2, 1, 8, 1, 22, 16, 1, 52, 136, 1, 114, 720, 272, 1, 240, 3072, 3968, 1, 494, 11616, 34304, 7936, 1, 1004, 40776, 230144, 176896, 1, 2026, 136384, 1328336, 2265344, 353792, 1, 4072, 441568, 6949952, 21953408, 11184128, 1, 8166, 1398000, 33981760

Offset: 1

Don Knuth, Jan 28 2005

Row n has ceiling(n/2) terms.
The paper by Shapiro et al. explains why T(n,k) is the number of permutations of n elements having k peaks and with the further property that every rise (ascent) is immediately followed by a peak. [That is, the permutation p_1 ... p_n has the further property that (j > 1 and p_{j-1} < p_j) implies (j < n and p_j > p_{j+1}).] For example, the T(4,1)=8 permutations in the case n=4, k=1 are 1423, 2143, 2431, 3142, 3241, 3421, 4231, 4132.
A more elegant way to state this property: T(n,k) is the number of permutations of n objects with k descents such that every descent is a peak. The eight examples for n=4 and k=1 are now 1243, 1324, 1342, 1423, 2314, 2341, 2413, 3412.
The rows of this triangle are the gamma vectors of the n-dimensional (type A) permutohedra (Postnikov et al., p. 31). Cf. A055151 and A089627. - Peter Bala, Oct 28 2008

			Triangle begins:
  1;
  1,
  1,   2;
  1,   8,
  1,  22,  16;
  1,  52, 136,
  1, 114, 720, 272;
  ...
From _Peter Bala_, Jun 26 2012: (Start)
n = 4: the 9 weighted plane increasing 0-1-2 trees on 4 vertices are
..................................................................
..4...............................................................
..|...............................................................
..3..........4...4...............4...4...............3...3........
..|........./.....\............./.....\............./.....\.......
..2....2...3.......3...2...3...2.......2...3...4...2.......2...4..
..|.....\./.........\./.....\./.........\./.....\./.........\./...
..1...(t)1........(t)1....(t)1........(t)1....(t)1........(t)1....
..................................................................
..3...4...4...3...................................................
...\./.....\./....................................................
.(t)2....(t)2.....................................................
....|.......|.....................................................
....1.......1.....................................................
Hence R(4,t) = 1 + 8*t.
(End)

D. Foata and V. Strehl, "Euler numbers and variations of permutations", in Colloquio Internazionale sulle Teorie Combinatorie, Rome, September 1973, (Atti dei Convegni Lincei 17, Rome, 1976), 129.
Guoniu Han, Frédéric Jouhet, Jiang Zeng, Two new triangles of q-integers via q-Eulerian polynomials of type A and B, Ramanujan J (2013) 31:115-127, DOI 10.1007/s11139-012-9389-3
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Chapter 4.

Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.
François Bergeron, Philippe Flajolet and Bruno Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
Leonard Carlitz and Richard Scoville, Generalized Eulerian numbers: combinatorial applications, Journal für die reine und angewandte Mathematik 265 (1974), 111.
Colin Defant, Troupes, Cumulants, and Stack-Sorting, arXiv:2004.11367 [math.CO], 2020.
Diego Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions, arXiv:math/0501052 [math.CA], 2005.
Dominique Foata and Marcel-Paul Schützenberger, Théorie géometrique des polynômes eulériens, arXiv:math/0508232 [math.CO], 2005; Lecture Notes in Math. 138 (1970), 81-83.
Shi-Mei Ma, On gamma-vectors and the derivatives of the tangent and secant functions, arXiv:1304.6654 [math.CO], 2013.
Shi-Mei Ma, Jun Ma, and Yeong-Nan Yeh, On certain combinatorial expansions of descent polynomials and the change of grammars, arXiv:1802.02861 [math.CO], 2018.
Shi-Mei Ma, Jianfeng Wang, Guiying Yan, Jean Yeh, and Yeong-Nan Yeh, Symmetric decompositions and Euler-Stirling statistics on Stirling permutations, arXiv:2507.17667 [math.CO], 2025. See p. 5.
Shi-Mei Ma and Yeong-Nan Yeh, The alternating run polynomials of permutations, arXiv:1904.11437 [math.CO], 2019. See p. 4.
Alexander Postnikov, Victor Reiner, and Lauren Williams, Faces of generalized permutohedra, arXiv:math/0609184 [math.CO], 2006-2007. [_Peter Bala_, Oct 28 2008]
Louis W. Shapiro, Wen-Jin Woan, and Seyoum Getu, Runs, slides and moments, SIAM J. Alg. Discrete Methods, 4 (1983), 459-466.
Andrei K. Svinin, Somos-4 equation and related equations, arXiv:2307.05866 [math.CA], 2023. See p. 16.

The numbers 2^{n-1-k} T(n, k) form the array shown in A008303.
Cf. A055151, A089627. - Peter Bala, Oct 28 2008
Cf. A008292, A094503, A080635 (row sums).

T:=proc(n,k) if k<0 then 0 elif n=1 and k=0 then 1 elif k>floor((n-1)/2) then 0 else (k+1)*T(n-1,k)+(2*n-4*k)*T(n-1,k-1) fi end: for n from 1 to 13 do seq(T(n,k),k=0..floor((n-1)/2)) od; # yields sequence in triangular form # Emeric Deutsch, Aug 06 2005

t[, k?Negative] = 0; t[1, 0] = 1; t[n_, k_] /; k > (n-1)/2 = 0; t[n_, k_] := t[n, k] = (k+1)*t[n-1, k] + (2*n-4*k)*t[n-1, k-1]; Table[t[n, k], {n, 1, 13}, {k, 0, (n-1)/2}] // Flatten (* Jean-François Alcover, Nov 22 2012 *)

G.f.: Sum_{n>=1, k>=0} T(n, k) t^k z^n/n! = C(t)(2-C(t))/(exp^(-z sqrt(1-4t)) + 1 - C(t)) - C(t), where the sum on k is actually finite, running up to ceiling(n/2) - 1; here C(t) = (1 - sqrt(1-4t))/2t is the generating function for the Catalan numbers (A000108).
Sum_{k} Eulerian(n, k) x^k = Sum_{k} T(n, k) x^k (1+x)^(n-1-2k). E.g., 1 + 11x + 11x^2 + x^3 = (1+x)^3 + 8x(1+x).
From Peter Bala, Jun 26 2012: (Start)
T(n,k) = 2^k*A094503(n,k+1).
Let r(t) = sqrt(1 - 2*t) and w(t) = (1 - r(t))/(1 + r(t)). Define F(t,z) = r(t)*(1 + w(t)*exp(r(t)*z))/(1 - w(t)*exp(r(t)*z)) = 1 + t*z + t*z^2/2! + (t+t^2)*z^3/3! + (t+4*t^2)*z^4/4! + ...; F(t,z) is the e.g.f. for A094503. The e.g.f. for the present table is A(t,z) := (F(2*t,z) - 1)/(2*t) = z + z^2/2! + (1+2*t)*z^3/3! + (1+8*t)*z^4/4! + ....
The e.g.f. A(t,z) satisfies the autonomous partial differential equation dA/dz = 1 + A + t*A^2 with A(t,0) = 0. It follows that the inverse function A(t,z)^(-1) may be expressed as an integral: A(t,z)^(-1) = int {x = 0..z} 1/(1+x+t*x^2) dx.
Applying [Dominici, Theorem 4.1] to invert the integral gives the following method for calculating the row polynomials R(n,t) of the table: let f(t,x) = 1+x+t*x^2 and let D be the operator f(t,x)*d/dx. Then R(n+1,t) = D^n(f(t,x)) evaluated at x = 0.
By Bergeron et al., Theorem 1, the row polynomial R(n,t) is the generating function for rooted plane increasing 0-1-2 trees on n vertices, where the vertices of outdegree 2 have weight t and all other vertices have weight 1. An example is given below.
Row sums A080635.
(End)

More terms from Emeric Deutsch, Aug 06 2005

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)

A247495 Generalized Motzkin numbers: Square array read by descending antidiagonals, T(n, k) = k![x^k](exp(nx)* BesselI_{1}(2*x)/x), n>=0, k>=0.

Original entry on oeis.org

1, 0, 1, 1, 1, 1, 0, 2, 2, 1, 2, 4, 5, 3, 1, 0, 9, 14, 10, 4, 1, 5, 21, 42, 36, 17, 5, 1, 0, 51, 132, 137, 76, 26, 6, 1, 14, 127, 429, 543, 354, 140, 37, 7, 1, 0, 323, 1430, 2219, 1704, 777, 234, 50, 8, 1, 42, 835, 4862, 9285, 8421, 4425, 1514, 364, 65, 9, 1

Offset: 0

Peter Luschny, Dec 11 2014

This two-dimensional array of numbers can be seen as a generalization of the Motzkin numbers A001006 for two reasons: The case n=1 reduces to the Motzkin numbers and the columns are the values of the Motzkin polynomials M_{k}(x) = sum_{j=0..k} A097610(k,j)*x^j evaluated at the nonnegative integers.

			Square array starts:
[n\k][0][1] [2]  [3]   [4]   [5]    [6]     [7]      [8]
[0]   1, 0,  1,   0,    2,    0,     5,      0,      14, ...  A126120
[1]   1, 1,  2,   4,    9,   21,    51,    127,     323, ...  A001006
[2]   1, 2,  5,  14,   42,  132,   429,   1430,    4862, ...  A000108
[3]   1, 3, 10,  36,  137,  543,  2219,   9285,   39587, ...  A002212
[4]   1, 4, 17,  76,  354, 1704,  8421,  42508,  218318, ...  A005572
[5]   1, 5, 26, 140,  777, 4425, 25755, 152675,  919139, ...  A182401
[6]   1, 6, 37, 234, 1514, 9996, 67181, 458562, 3172478, ...  A025230
A000012,A001477,A002522,A079908, ...
.
Triangular array starts:
              1,
             0, 1,
           1, 1, 1,
          0, 2, 2, 1,
        2, 4, 5, 3, 1,
      0, 9, 14, 10, 4, 1,
   5, 21, 42, 36, 17, 5, 1,
0, 51, 132, 137, 76, 26, 6, 1.

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

Main diagonal gives A247496.

Cf. A126120, A001006, A000108, A002212, A005572, A182401, A025230, A002522, A079908, A055151, A097610, A247497, A306684.

# RECURRENCE
T := proc(n,k) option remember; if k=0 then 1 elif k=1 then n else
(n*(2*k+1)*T(n,k-1)-(n-2)*(n+2)*(k-1)*T(n,k-2))/(k+2) fi end:
seq(print(seq(T(n,k),k=0..9)),n=0..6);
# OGF (row)
ogf := n -> (1-n*x-sqrt(((n-2)*x-1)*((n+2)*x-1)))/(2*x^2):
seq(print(seq(coeff(series(ogf(n),x,12),x,k),k=0..9)),n=0..6);
# EGF (row)
egf := n -> exp(n*x)*hypergeom([],[2],x^2):
seq(print(seq(k!*coeff(series(egf(n),x,k+2),x,k),k=0..9)),n=0..6);
# MOTZKIN polynomial (column)
A097610 := proc(n,k) if type(n-k,odd) then 0 else n!/(k!*((n-k)/2)!^2* ((n-k)/2+1)) fi end: M := (k,x) -> add(A097610(k,j)*x^j,j=0..k):
seq(print(seq(M(k,n),n=0..9)),k=0..6);
# OGF (column)
col := proc(n, len) local G; G := A247497_row(n); (-1)^(n+1)* add(G[k+1]/(x-1)^(k+1), k=0..n); seq(coeff(series(%, x, len+1),x,j), j=0..len) end: seq(print(col(n,8)), n=0..6); # Peter Luschny, Dec 14 2014

T[0, k_] := If[EvenQ[k], CatalanNumber[k/2], 0];
T[n_, k_] := n^k*Hypergeometric2F1[(1 - k)/2, -k/2, 2, 4/n^2];
Table[T[n - k, k], {n, 0, 10}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Nov 03 2017 *)

def A247495(n,k):
    if n==0: return(k//2+1)*factorial(k)/factorial(k//2+1)^2 if is_even(k) else 0
    return n^k*hypergeometric([(1-k)/2,-k/2],[2],4/n^2).simplify()
for n in (0..7): print([A247495(n,k) for k in range(11)])

T(n,k) = (n*(2*k+1)*T(n,k-1)-(n-2)*(n+2)*(k-1)*T(n,k-2))/(k+2) for k>=2.
T(n,k) = Sum_{j=0..floor(k/2)} n^(k-2*j)*binomial(k,2*j)*binomial(2*j,j)/(j+1).
T(n,k) = n^k*hypergeom([(1-k)/2,-k/2], [2], 4/n^2) for n>0.
T(n,n) = A247496(n).
O.g.f. for row n: (1-n*x-sqrt(((n-2)*x-1)*((n+2)*x-1)))/(2*x^2).
O.g.f. for row n: R(x)/x where R(x) is series reversion of x/(1+n*x+x^2).
E.g.f. for row n: exp(n*x)*hypergeom([],[2],x^2).
O.g.f. for column k: the k-th column consists of the values of the k-th Motzkin polynomial M_{k}(x) evaluated at x = 0,1,2,...; M_{k}(x) = sum_{j=0..k} A097610(k,j)*x^j = sum_{j=0..k} (-1)^j*binomial(k,j)*A001006(j)*(x+1)^(k-j).
O.g.f. for column k: sum_{j=0..k} (-1)^(k+1)*A247497(k,j)/(x-1)^(j+1). - Peter Luschny, Dec 14 2014
O.g.f. for row n: 1/(1 - n*x - x^2/(1 - n*x - x^2/(1 - n*x - x^2/(1 - n*x - x^2/(1 - ...))))), a continued fraction. - Ilya Gutkovskiy, Sep 21 2017
T(n,k) is the coefficient of x^k in the expansion of 1/(k+1) * (1 + n*x + x^2)^(k+1). - Seiichi Manyama, May 07 2019

A080159 Triangular array of ways of drawing k non-intersecting chords between n points on a circle; i.e., Motzkin polynomial coefficients.

Original entry on oeis.org

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

Offset: 0

Henry Bottomley, Jan 31 2003

			Rows start: 1; 1,0; 1,1,0; 1,3,0,0; 1,6,2,0,0; 1,10,10,0,0,0; 1,15,30,5,0,0,0; etc.

Visible version of A055151. Row sums are A001006 (Motzkin numbers). Columns include A000012, A000217, A034827 and perhaps A000910.

For n >= 2k: T(n, k) = n!/((n-2k)!k!(k+1)!) = A007318(n, 2k)*A000108(k).

T(n,k) = A055151(n,k).

A258820 Reversed rows of A178252 presented as diagonals of an irregular triangle.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 5, 2, 1, 1, 3, 10, 1, 1, 7, 5, 5, 1, 1, 4, 7, 5, 1, 1, 9, 28, 35, 3, 1, 1, 5, 12, 14, 7, 1, 1, 11, 15, 21, 14, 7, 1, 1, 6, 55, 30, 126, 28, 1, 1, 13, 22, 165, 42, 21, 4, 1

Offset: 0

Tom Copeland, Jun 18 2015

The diagonals of T are the reversed rows of A178252. E.g., the fifth diagonal of T is (1,2,2,1,1) from the example below, which is the fifth reversed row of A178252.
Factoring out the greatest common divisor (gcd) of the coefficients of the sub-polynomials in the indeterminate q of the polynomials in s presented on p. 12 of the Alexeev et al. link and then evaluating the sub-polynomials at q=1 gives the first nine rows of T given in the example below. E.g., for k=6 (the seventh row), q*s^6 + (6*q + 9*q^2) s^4 + (15*q + 15*q^2) s^2 + 5  = q*s^6 + 3*(2*q + 3*q^2)*s^4 + 15*(q + q^2)*s^2 + 5 generates (1,2+3,1+1,1)=(1,5,2,1).
The row length sequence of this irregular triangle is A008619(n) = 1 + floor(n/2). - Wolfdieter Lang, Aug 25 2015

			The irregular triangle T(n,k) starts
n\k  0 1  2  3 4 5 ...
0:   1
1:   1
2:   1 1
3:   1 1
4:   1 3  1
5:   1 2  1
6:   1 5  2  1
7:   1 3 10  1
8:   1 7  5  5 1
9:   1 4  7  5 1
10:  1 9 28 35 3 1
... reformatted. - _Wolfdieter Lang_, Aug 25 2015

N. Alexeev, J. Andersen, R. Penner, P. Zograf, Enumeration of chord diagrams on many intervals and their non-orientable analogs, arXiv:1307.0967 [math.CO], 2013-2014.

Cf. A050169, A161642, A055151, A088617, A178252, A107711, A165661, A003989, A008619.

max = 15; coes = Table[ PadRight[ CoefficientList[ BernoulliB[n, x], x], max], {n, 0, max-1}]; inv = Inverse[coes] // Numerator; t[n_, k_] := inv[[n, k]]; t[n_, k_] /; k == n+1 = 1; Table[t[n-k+1, k], {n, 2, max+1}, {k, 2, Floor[n/2]+1}] // Flatten (* Jean-François Alcover, Jul 22 2015 *)

T(n,k) = A178252(n-k,n-2k) = A055151(n,k) / A161642(n,k) = A007318(n,2k) * A000108(k) / A161642(n,k) = n! / [(n-2k)! k! (k+1)! A161642(n,k)] = A003989(n-k+1,k+1) * (n-k)! / [ (n-2k)! (k+1)! ], where A003989(j,k) = gcd(j,k).

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.

A119021 Binomial transform of A119020.

Original entry on oeis.org

1, 2, 5, 14, 44, 152, 564, 2200, 8922, 37460, 162526, 726772, 3337360, 15676000, 75057142, 365302740, 1803191210, 9011209620, 45528658362, 232340523516, 1196799936312, 6219980254704, 32605664415000, 172351828064208

Offset: 0

Paul D. Hanna, May 09 2006

nonn

A119020 is the eigenvector of triangle A055151 of Motzkin polynomial coefficients.

Cf. A119020, A119022.

A119022 Inverse binomial transform of A119020, even-indexed terms only, since all odd-indexed terms are equal to zero.

Original entry on oeis.org

1, 1, 4, 20, 154, 1302, 12672, 129558, 1462890, 17537234, 223689128, 2959757528, 40637432332, 573938538500, 8324542177200, 123276663007740, 1861540558106490, 28613268804680010, 447616821726181800

Offset: 0

Paul D. Hanna, May 09 2006

nonn

A119020 is the eigenvector of triangle A055151 of Motzkin polynomial coefficients.

Cf. A119020, A119021, A000108 (Catalan).

a(n) = A119020(n)*C(2n,n)/(n+1) = A119020(n)*A000108(n).

A161642 Triangle (by rows): T(n,k) = A007318(n,k) / A003989(n+1,k+1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 3, 1, 1, 2, 2, 2, 1, 1, 5, 10, 10, 5, 1, 1, 3, 15, 5, 15, 3, 1, 1, 7, 7, 35, 35, 7, 7, 1, 1, 4, 28, 28, 14, 28, 28, 4, 1, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 1, 5, 15, 30, 210, 42, 210, 30, 15, 5, 1

Offset: 0

Jason Richardson-White, Jun 15 2009

Taking each row polynomial listed on p. 12 of the Alexeev et al. link and listing the GCD of each sub-polynomial in the indeterminate q gives the left half of this entry's symmetric/palindromic triangle. E.g., for k=6, q*s^6 + (6*q + 9*q^2) s^4 + (15*q + 15*q^2) s^2 + 5 = q*s^6 + 3*(2*q + 3*q^2)*s^4 + 15*(q + q^2)*s^2 + 5 generates (1,3,15,5). See also A055151. - Tom Copeland, Jun 18 2015

			The triangle T(n,k) begins:
n\k 0 1  2  3   4   5   6  7  8 9 10 ...
0:  1
1:  1 1
2:  1 1  1
3:  1 3  3  1
4:  1 2  2  2   1
5:  1 5 10 10   5   1
6:  1 3 15  5  15   3   1
7:  1 7  7 35  35   7   7  1
8:  1 4 28 28  14  28  28  4  1
9:  1 9 36 84 126 126  84 36  9 1
10: 1 5 15 30 210  42 210 30 15 5  1
... reformatted. - _Wolfdieter Lang_, Aug 24 2015

N. Alexeev, J. Andersen, R. Penner, P. Zograf, Enumeration of chord diagrams on many intervals and their non-orientable analogs, arXiv:1307.0967 [math.CO], 2013-2014 [From Tom Copeland, Jun 18 2015]

Cf. A000108, A003989, A055151, A258820, A007318.

T[n_, k_] := Binomial[n, k]/GCD[n-k+1, k+1]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 06 2015, after R. J. Mathar *)

T(2n,n) = A000108(n).
T(n,k) = binomial(n,k)/A003989(n+1,k+1), 0<=k<=n. - R. J. Mathar, Sep 04 2013
For first half (k <= floor(n/2)) of each palindromic row, T(n,k) = A055151(n,k) / A258820(n,k) = A007318(n,2k) * A000108(k) / A258820(n,k) = n! / [(n-2k)! k! (k+1)! A258820(n,k)]. - Tom Copeland, Jun 18 2015

Name changed, and R. J. Mathar's formula corrected, by Wolfdieter Lang, Aug 24 2015

cp's OEIS Frontend

A091156 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having k long ascents (i.e., ascents of length at least 2). Rows are of length 1,1,2,2,3,3,... .

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A101280 Triangle T(n,k) (n >= 1, 0 <= k <= floor((n-1)/2)) read by rows, where T(n,k) = (k+1)T(n-1,k) + (2n-4k)T(n-1,k-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

Formula

A247495 Generalized Motzkin numbers: Square array read by descending antidiagonals, T(n, k) = k!*[x^k](exp(n*x)* BesselI_{1}(2*x)/x), n>=0, k>=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A080159 Triangular array of ways of drawing k non-intersecting chords between n points on a circle; i.e., Motzkin polynomial coefficients.

Views

Author

Keywords

Examples

Crossrefs

Formula

A258820 Reversed rows of A178252 presented as diagonals of an irregular triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

A247495 Generalized Motzkin numbers: Square array read by descending antidiagonals, T(n, k) = k![x^k](exp(nx)* BesselI_{1}(2*x)/x), n>=0, k>=0.