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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A055151 Triangular array of Motzkin polynomial coefficients. 19
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

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]>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

REFERENCES

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.

LINKS

Alois P. Heinz, Rows n = 0..200, flattened

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.

Marcello Artioli, Giuseppe Dattoli, Silvia Licciardi, 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.

Samuele Giraudo, Tree series and pattern avoidance in syntax trees, arXiv:1903.00677 [math.CO], 2019.

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.

A. Postnikov, V. Reiner, L. Williams, Faces of generalized permutohedra, arXiv:math/0609184 [math.CO], 2006-2007.

FORMULA

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

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

PROG

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

(PARI) {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 */

(PARI) {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 */

CROSSREFS

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.

Sequence in context: A270103 A134546 A152193 * A181187 A104573 A010467

Adjacent sequences:  A055148 A055149 A055150 * A055152 A055153 A055154

KEYWORD

nonn,tabf,easy

AUTHOR

Michael Somos, Jun 14 2000

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 04:38 EDT 2019. Contains 324318 sequences. (Running on oeis4.)