login
Triangle T(n,d) read by rows: Number of ascent sequences of length n with d zeros.
8

%I #48 Sep 23 2022 12:12:33

%S 1,1,1,2,2,1,5,6,3,1,15,21,12,4,1,53,84,54,20,5,1,217,380,270,110,30,

%T 6,1,1014,1926,1490,660,195,42,7,1,5335,10840,9020,4300,1365,315,56,8,

%U 1,31240,67195,59550,30290,10255,2520,476,72,9,1,201608,455379,426405

%N Triangle T(n,d) read by rows: Number of ascent sequences of length n with d zeros.

%C The first column and the row sums are both A022493.

%C Also the number of length-n ascent sequences with k fixed points. [_Joerg Arndt_, Nov 03 2012]

%H Joerg Arndt and Alois P. Heinz, <a href="/A175579/b175579.txt">Rows n = 1..141, flattened</a>

%H Hsien-Kuei Hwang, and Emma Yu Jin, <a href="https://arxiv.org/abs/1911.06690">Asymptotics and statistics on Fishburn matrices and their generalizations</a>, arXiv:1911.06690 [math.CO], 2019.

%H V. Jelinek, <a href="https://doi.org/10.1016/j.aam.2015.06.007">Catalan pairs and Fishburn triples</a>, Adv. Appl. Math. 70 (2015) 1-31

%H S. Kitaev, J. Remmel, Enumerating (2+2)-free posets by the number of minimal elements and other statistics, Discrete Applied Mathematics 159 (17) (2011), 2098-2108 (preprint: <a href="http://arxiv.org/abs/1004.3220">arXiv:1004.3220 [math.CO]</a>).

%H Paul Levande, <a href="http://arxiv.org/abs/1006.3013">Two new interpretations of the Fishburn numbers and their refined generating functions</a>, arXiv:1006.3013

%H Don Zagier, <a href="http://people.mpim-bonn.mpg.de/zagier/">Vassiliev invariants and a strange identity related to the Dedekind eta-function</a>, Topology, vol.40, pp.945-960 (2001); see p.948.

%F The bivariate g.f. A(x,y) = Sum_{n>=1, d=1..n} T(n,d)*x^(n+1)*y^(d+1) can be given in two forms (see Remmel and Kitaev, or Levande link):

%F (1) A(x,y) = Sum_{n>=1} Product_{k=0..n-1} (1 - (1-x)^k*(1-x*y)),

%F (2) A(x,y) = Sum_{n>=1} x*y/(1-x*y)^n * Product_{k=1..n-1} (1 - (1-x)^k).

%e The triangle starts:

%e 01: 1;

%e 02: 1, 1;

%e 03: 2, 2, 1;

%e 04: 5, 6, 3, 1;

%e 05: 15, 21, 12, 4, 1;

%e 06: 53, 84, 54, 20, 5, 1;

%e 07: 217, 380, 270, 110, 30, 6, 1;

%e 08: 1014, 1926, 1490, 660, 195, 42, 7, 1;

%e 09: 5335, 10840, 9020, 4300, 1365, 315, 56, 8, 1;

%e 10: 31240, 67195, 59550, 30290, 10255, 2520, 476, 72, 9, 1;

%e 11: 201608, 455379, 426405, 229740, 82425, 21448, 4284, 684, 90, 10, 1;

%e ...

%e From _Joerg Arndt_, Mar 05 2014: (Start)

%e The 15 ascent sequences of length 4 (dots for zeros) together with their numbers of zeros and numbers of fixed points are:

%e 01: [ . . . . ] 4 1

%e 02: [ . . . 1 ] 3 1

%e 03: [ . . 1 . ] 3 1

%e 04: [ . . 1 1 ] 2 1

%e 05: [ . . 1 2 ] 2 1

%e 06: [ . 1 . . ] 3 2

%e 07: [ . 1 . 1 ] 2 2

%e 08: [ . 1 . 2 ] 2 2

%e 09: [ . 1 1 . ] 2 2

%e 10: [ . 1 1 1 ] 1 2

%e 11: [ . 1 1 2 ] 1 2

%e 12: [ . 1 2 . ] 2 3

%e 13: [ . 1 2 1 ] 1 3

%e 14: [ . 1 2 2 ] 1 3

%e 15: [ . 1 2 3 ] 1 4

%e Both statistics give row 4: [5, 6, 3, 1].

%e (End)

%p b:= proc(n, i, t) option remember; `if`(n=0, 1, expand(add(

%p `if`(j=0, x, 1) *b(n-1, j, t+`if`(j>i, 1, 0)), j=0..t+1)))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, -1$2)):

%p seq(T(n), n=1..12); # _Alois P. Heinz_, Mar 11 2014

%t b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1, Expand[Sum[If[j == 0, x, 1]*b[n-1, j, t + If[j>i, 1, 0]], {j, 0, t+1}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, -1, -1]]; Table[T[n], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Mar 06 2015, after _Alois P. Heinz_ *)

%o (PARI) {T(n,d)=polcoeff(polcoeff(sum(m=0,n+1,prod(j=0,m-1,(1-(1-x)^j*(1-x*y) +x^2*y^2*O(x^n*y^d)))),n+1,x),d+1,y)} /* _Paul D. Hanna_, Feb 18 2012 */

%o for(n=0,10,for(d=0,n,print1(T(n,d),", "));print(""))

%o (PARI) {T(n,d)=polcoeff(polcoeff(sum(m=1,n+1,x*y/(1-x*y +x*y*O(x^n*y^d))^m*prod(j=1,m-1,(1-(1-x)^j))),n+1,x),d+1,y)} /* _Paul D. Hanna_, Feb 18 2012 */

%o for(n=0,10,for(d=0,n,print1(T(n,d),", "));print(""))

%Y Cf. A022493 (number of ascent sequences), A137251 (ascent sequences with k ascents), A218577 (ascent sequences with maximal element k).

%Y Cf. A218579 (ascent sequences with last zero at position k-1), A218580 (ascent sequences with first occurrence of the maximal value at position k-1), A218581 (ascent sequences with last occurrence of the maximal value at position k-1).

%Y T(2n,n) gives A357309.

%K easy,nonn,tabl

%O 1,4

%A _R. J. Mathar_, Jul 15 2010

%E Corrected offset, _Joerg Arndt_, Nov 03 2012