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

%I #26 Nov 30 2022 11:38:35

%S 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,

%T 0,0,0,14,364,804,247,1,0,0,0,0,210,1800,2349,502,1,0,0,0,0,42,1770,

%U 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

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

%C Also number of Dyck paths of semi-length n for which the number of valleys added to the number of triple falls is k.

%C Apparently deletion of zeros and row-reversal maps A166073 to A091156. - _R. J. Mathar_, Oct 08 2009

%C 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

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

%H Alois P. Heinz, <a href="/A166073/b166073.txt">Rows n = 0..200, flattened</a>

%H M. Barnabei, F. Bonetti and M. Silimbani, <a href="http://www.kurims.kyoto-u.ac.jp/EMIS/journals/SLC/wpapers/s63barnbosi.html">The descent statistic on 123 avoiding permutations</a>, Séminaire Lotharingien de Combinatoire, B63a (2010), 7 pp.

%H Bin Han and Qiongqiong Pan, <a href="https://arxiv.org/abs/2211.10893">(p,q,t)-Catalan continued fractions, gamma expansions and pattern avoidances</a>, arXiv:2211.10893 [math.CO], 2022.

%H Dongsu Kim and Zhicong Lin, <a href="https://arxiv.org/abs/1706.07208">Refined restricted inversion sequences</a>, arXiv:1706.07208 [math.CO], 2017.

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

%e For example, for n=4 and k=1 we have the 2 permutations 3412 and 2413.

%e Triangle begins:

%e 1

%e 1

%e 1,1

%e 0,4,1

%e 0,2,11,1

%e 0,0,15,26,1

%e 0,0,5,69,57,1

%e 0,0,0,56,252,120,1

%e 0,0,0,14,364,804,247,1

%e 0,0,0,0,210,1800,2349,502,1

%e 0,0,0,0,42,1770,7515,6455,1013,1

%e 0,0,0,0,0,792,11055,27940,16962,2036,1

%e 0,0,0,0,0,132,8217,57035,95458,43086,4083,1

%e 0,0,0,0,0,0,3003,62062,257257,305812,106587,8178,1

%e 0,0,0,0,0,0,429,37037,381381,1049685,931385,258153,16369,1

%e 0,0,0,0,0,0,0,11440,328328,2022384,3962140,2723280,614520,32752,1

%e 0,0,0,0,0,0,0,1430,163592,2341976,9591764,14051660,7699800,1441928,65519,1

%e 0,0,0,0,0,0,0,0,43758,1665456,14275716,41666184,47352820,21167312,3342489, 131054,1

%e 0,0,0,0,0,0,0,0,4862,712062,13527852,77161980,168567444,152915748,56818743, 7667883,262125,1

%e ...

%p 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

%p # second Maple program:

%p b:= proc(x, y) option remember; `if`(y>x or y<0, 0, `if`(x=0, 1,

%p expand(b(x-1, y)*`if`(y=0, 1, 2)*z+b(x-1, y+1) +b(x-1, y-1))))

%p end:

%p T:= n-> `if`(n=0, 1, (p-> seq(coeff(p, z, 2*i-n+2), i=0..n-1))(b(n, 0))):

%p seq(T(n), n=0..15); # _Alois P. Heinz_, Aug 07 2018

%t m = maxExponent = 13;

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

%Y Cf. A001263. Row sums given by A000108.

%Y Cf. A091156, A126222.

%K nonn,tabf

%O 0,6

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

%E Extended by _Emeric Deutsch_, Oct 30 2009