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

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

Author

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

Keywords

• nonn
• tabf

Comments

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]

Examples

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

Links

• 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.

Crossrefs

Cf. A001263. Row sums given by A000108.

Cf. A091156, A126222.

Programs

Maple

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

Mathematica

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

Formula

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

Extensions

Extended by Emeric Deutsch, Oct 30 2009