A091156 -id:A091156 - cp's OEIS frontend

A243752 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=U=(1,1) and 0=D=(1,-1); triangle T(n,k), n>=0, read by rows.

1, 0, 1, 0, 1, 1, 1, 3, 1, 1, 11, 2, 9, 16, 12, 4, 1, 1, 57, 69, 5, 127, 161, 98, 35, 7, 1, 323, 927, 180, 1515, 1997, 1056, 280, 14, 4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 1, 10455, 25638, 18357, 4115, 220, 1, 20705, 68850, 77685, 34840, 5685, 246, 1

Offset: 0

Alois P. Heinz, Jun 09 2014

			Triangle T(n,k) begins:
: n\k :    0     1     2     3    4    5  ...
+-----+----------------------------------------------------------
:  0  :    1;                                 [row  0 of A131427]
:  1  :    0,    1;                           [row  1 of A131427]
:  2  :    0,    1,    1;                     [row  2 of A090181]
:  3  :    1,    3,    1;                     [row  3 of A001263]
:  4  :    1,   11,    2;                     [row  4 of A091156]
:  5  :    9,   16,   12,    4,   1;          [row  5 of A091869]
:  6  :    1,   57,   69,    5;               [row  6 of A091156]
:  7  :  127,  161,   98,   35,   7,   1;     [row  7 of A092107]
:  8  :  323,  927,  180;                     [row  8 of A091958]
:  9  : 1515, 1997, 1056,  280,  14;          [row  9 of A135306]
: 10  : 4191, 5539, 3967, 1991, 781, 244, ... [row 10 of A094507]

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

Columns k=0-10 give: A243754, A243770, A243771, A243772, A243773, A243774, A243775, A243776, A243777, A243778, A243779, or main diagonals of A243753, A243827, A243828, A243829, A243830, A243831, A243832, A243833, A243834, A243835, A243836.
Row sums give A000108.
Cf. A098978, A114463, A114848, A116424, A135305, A242450, A243366, A243838.

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

A166073 Triangle read by rows: a(n,k) = number of permutations in S_n which avoid the pattern 123 and have exactly k descents.

Original entry on oeis.org

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

Offset: 0

Matteo Silimbani (silimban(AT)dm.unibo.it), Oct 06 2009, Oct 08 2009

Also number of Dyck paths of semi-length n for which the number of valleys added to the number of triple falls is k.
Apparently deletion of zeros and row-reversal maps A166073 to A091156. - R. J. Mathar, Oct 08 2009
The trivariate o.g.f. G=G(t,s,x), where t marks triple falls, s marks valleys, and x marks semilength is given by G=1+x[1+xg+t(G-1-xg)]g, where g = s(G-1)+1. Letting t=s=y, yields the given o.g.f. - Emeric Deutsch, Nov 03 2009
Apparently a variant of A126222, zeros moved to the start of each row. [J. Gardiner, seqfan list, Aug 19 2010] [R. J. Mathar, Aug 30 2010]

			For example, for n=4 and k=1 we have the 2 permutations 3412 and 2413.
Triangle begins:
1
1
1,1
0,4,1
0,2,11,1
0,0,15,26,1
0,0,5,69,57,1
0,0,0,56,252,120,1
0,0,0,14,364,804,247,1
0,0,0,0,210,1800,2349,502,1
0,0,0,0,42,1770,7515,6455,1013,1
0,0,0,0,0,792,11055,27940,16962,2036,1
0,0,0,0,0,132,8217,57035,95458,43086,4083,1
0,0,0,0,0,0,3003,62062,257257,305812,106587,8178,1
0,0,0,0,0,0,429,37037,381381,1049685,931385,258153,16369,1
0,0,0,0,0,0,0,11440,328328,2022384,3962140,2723280,614520,32752,1
0,0,0,0,0,0,0,1430,163592,2341976,9591764,14051660,7699800,1441928,65519,1
0,0,0,0,0,0,0,0,43758,1665456,14275716,41666184,47352820,21167312,3342489, 131054,1
0,0,0,0,0,0,0,0,4862,712062,13527852,77161980,168567444,152915748,56818743, 7667883,262125,1
...

Alois P. Heinz, Rows n = 0..200, flattened
M. Barnabei, F. Bonetti and M. Silimbani, The descent statistic on 123 avoiding permutations, Séminaire Lotharingien de Combinatoire, B63a (2010), 7 pp.
Bin Han and Qiongqiong Pan, (p,q,t)-Catalan continued fractions, gamma expansions and pattern avoidances, arXiv:2211.10893 [math.CO], 2022.
Dongsu Kim and Zhicong Lin, Refined restricted inversion sequences, arXiv:1706.07208 [math.CO], 2017.

Cf. A001263. Row sums given by A000108.

Cf. A091156, A126222.

G := (-1+2*x*y+2*x^2*y-2*x*y^2-4*x^2*y^2+2*x^2*y^3+sqrt(1-4*x*y-4*x^2*y+4*x^2*y^2))/ (2*x*y^2*(x*y-1-x)): Gser := simplify(series(G, x = 0, 17)): for n from 0 to 12 do P[n] := sort(expand(coeff(Gser, x, n))) end do: for n from 0 to 12 do seq(coeff(P[n], y, k), k = 0 .. n-1) end do; # yields sequence in triangular form # Emeric Deutsch, Oct 30 2009
# second 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-> `if`(n=0, 1, (p-> seq(coeff(p, z, 2*i-n+2), i=0..n-1))(b(n, 0))):
seq(T(n), n=0..15);  # Alois P. Heinz, Aug 07 2018

m = maxExponent = 13;
CoefficientList[# + O[y]^m, y]& /@ CoefficientList[(-1 + 2*x*y + 2*x^2*y - 2*x*y^2 - 4*x^2*y^2 + 2*x^2*y^3 + Sqrt[1 - 4*x*y - 4*x^2*y + 4*x^2*y^2])/ (2*x*y^2*(x*y-1-x)) + O[x]^m, x] // Flatten(* Jean-François Alcover, Aug 07 2018 *)

O.g.f.: E(x,y) = (-1+2xy+2x^2y-2xy^2-4x^2y^2+2x^2y^3+sqrt[1-4xy-4x^2y+4*x^2*y^2])/ (2xy^2(xy-1-x)).

Extended by Emeric Deutsch, Oct 30 2009

A236406 Triangle read by rows: number of (1-2-3)-avoiding permutations on n letters with k peaks.

Original entry on oeis.org

1, 1, 2, 3, 2, 4, 10, 5, 32, 5, 6, 84, 42, 7, 198, 210, 14, 8, 438, 816, 168, 9, 932, 2727, 1152, 42, 10, 1936, 8250, 5940, 660, 11, 3962, 23276, 25630, 5775, 132, 12, 8034, 62400, 97812, 37180, 2574, 13, 16200, 160953, 341224, 196625, 27456, 429, 14, 32556, 402906, 1111656, 905086, 212212, 10010

Offset: 0

N. J. A. Sloane, Jan 31 2014

This is a convolution of A091156 with itself (see the Pudwell link below).

			Triangle begins:
   1;
   1;
   2;
   3,    2;
   4,   10;
   5,   32,    5;
   6,   84,   42;
   7,  198,  210,   14;
   8,  438,  816,  168;
   9,  932, 2727, 1152,  42;
  10, 1936, 8250, 5940, 660;
  ...

Alois P. Heinz, Rows n = 0..120, flattened
A. M. Baxter, Refining enumeration schemes to count according to permutation statistics, arXiv preprint arXiv:1401.0337 [math.CO], 2014.
M. Bukata, R. Kulwicki, N. Lewandowski, L. Pudwell, J. Roth, and T. Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv preprint arXiv:1812.07112 [math.CO], 2018.
L. Pudwell, On the distribution of peaks (and other statistics), 2018.

Row sums give A000108.

Cf. A091894, A276666.

m = maxExponent = 15;
G = -(-2 z^3 q^2 + 4z^3 q - 2z^3 - 2z^2 q + 2z^2 - 1 + Sqrt[-4z^2 q + 4z^2 - 4z + 1])/(2z (z q - z + 1)^2);
CoefficientList[# + O[q]^m, q]& /@ CoefficientList[G + O[z]^m, z]// Flatten (* Jean-François Alcover, Aug 06 2018 *)

T(2*n+2,n) = A276666(n+2) = (n+1)*A000108(n+2). - Alois P. Heinz, Apr 27 2018

G.f.: G(q,z) = - (-2z^3q^2+4z^3q-2z^3-2z^2q+2z^2-1+sqrt(-4z^2q+4z^2-4z+1))/(2z(zq-z+1)^2). (See the Pudwell link above.)

More terms from Alois P. Heinz, Apr 26 2018

cp's OEIS Frontend

A243752 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=U=(1,1) and 0=D=(1,-1); triangle T(n,k), n>=0, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

A055151 Triangular array of Motzkin polynomial coefficients.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

A166073 Triangle read by rows: a(n,k) = number of permutations in S_n which avoid the pattern 123 and have exactly k descents.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A236406 Triangle read by rows: number of (1-2-3)-avoiding permutations on n letters with k peaks.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions