A126222 -id:A126222 - cp's OEIS frontend

A126223 Number of level steps in all 2-Motzkin paths (i.e., Motzkin paths with blue and red level steps) of length n, without red level steps on the x-axis.

0, 1, 2, 7, 26, 98, 372, 1419, 5434, 20878, 80444, 310726, 1202852, 4665412, 18126760, 70538355, 274877370, 1072515990, 4189573740, 16383007410, 64126407180, 251226790620, 985033185240, 3865138313790, 15176957307876, 59633260964748, 234453859803352

Offset: 0

Emeric Deutsch, Dec 28 2006

nonn

a(n) is the number of increasing strict binary trees with 2n-1 nodes that avoid 213 and 321 in the classical sense. For more information about increasing strict binary trees with an associated permutation, see A245894. - Manda Riehl, Aug 07 2014

			a(3) = 7 because the 2-Motzkin paths without red level steps on the x-axis are BBB, BUD, UBD, URD and UDB, where U=(1,1), D=(1,-1), B=blue (1,0), R=red (1,0); they have a total of 3+1+1+1+1 = 7 level steps.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A126222.

G:=(1-2*z)*(1-2*z-sqrt(1-4*z))/2/z/sqrt(1-4*z): Gser:=series(G,z=0,32): seq(coeff(Gser,z,n),n=0..28);
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n,
      2*(2*n-3)*(n^2-n+1)*a(n-1)/((n+1)*(n^2-3*n+3)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, May 20 2014

CoefficientList[Series[(1-2*x)*(1-2*x-Sqrt[1-4*x])/(2*x*Sqrt[1-4*x]), {x, 0, 20}], x] (* Vaclav Kotesovec, Sep 08 2014 *)
Flatten[{0, Table[2*(1-n+n^2) * Binomial[2*n-2, n-1]/(n*(n+1)), {n, 1, 25}]}] (* Vaclav Kotesovec, Sep 08 2014 *)

a(n) = Sum_{k=0..n} k*A126222(n,k).
G.f.: (1-2z)(1-2z-sqrt(1-4*z))/(2z*sqrt(1-4z)).
a(n) = 2*(2*n-3)*(n^2-n+1)*a(n-1)/((n+1)*(n^2-3*n+3)) for n>1. - Alois P. Heinz, May 20 2014
a(n) = 2*(1-n+n^2) * C(2*n-2, n-1) / (n*(n+1)). - Vaclav Kotesovec, Sep 08 2014

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

A171150 Triangle related to T(x,2x).

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 3, 9, 7, 1, 6, 20, 28, 15, 1, 10, 50, 85, 75, 31, 1, 20, 105, 255, 294, 186, 63, 1, 35, 245, 651, 1029, 903, 441, 127, 1, 70, 504, 1736, 3108, 3612, 2568, 1016, 255, 1, 126, 1134, 4116, 9324, 12636, 11556, 6921, 2295, 511, 1, 252, 2310, 10290, 25080, 42120, 46035, 34605, 17930, 5110, 1023, 1

Offset: 0

Philippe Deléham, Dec 04 2009

Let the triangle T_(x,y)=T defined by T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0)=x*T(n-1,0)+T(n-1,1), T(n,k)=T(n-1,k-1)+y*T(n-1,k)+T(n-1,k+1) for k>=1.
This triangle gives the coefficients of Sum_{k=0..n} T(n,k) where y=2x.
T_(0,0) = A053121, T_(1,2) = A039599, T_(2,4) = A124575.
First column of T_(x,2x) is given by A126222.

			Triangle begins:
   1;
   1,  1;
   2,  3,  1;
   3,  9,  7,  1;
   6, 20, 28, 15,  1;
  10, 50, 85, 75, 31,  1;
  ...

M. Barnabei, F. Bonetti, and M. Silimbani, The Eulerian numbers on restricted centrosymmetric permutations, PU. M. A. Vol. 21 (2010), No. 2, pp. 99-118 (see Table p. 118, with additional zeros); see also, arXiv:0910.2376 [math.CO], 2009.

Cf. A000012, A000225, A058877, A126222.

Row sums give A000984.

Sum_{k=0..n} T(n,k)*x^k = A000007(n), A001405(n), A000984(n), A133158(n) for x = -1, 0, 1, 2 respectively.

More terms from Alois P. Heinz, Jan 31 2023

cp's OEIS Frontend

A126223 Number of level steps in all 2-Motzkin paths (i.e., Motzkin paths with blue and red level steps) of length n, without red level steps on the x-axis.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

A171150 Triangle related to T(x,2x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions