A175579 Triangle T(n,d) read by rows: Number of ascent sequences of length n with d zeros.
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, 6, 1, 1014, 1926, 1490, 660, 195, 42, 7, 1, 5335, 10840, 9020, 4300, 1365, 315, 56, 8, 1, 31240, 67195, 59550, 30290, 10255, 2520, 476, 72, 9, 1, 201608, 455379, 426405
Offset: 1
Examples
The triangle starts: 01: 1; 02: 1, 1; 03: 2, 2, 1; 04: 5, 6, 3, 1; 05: 15, 21, 12, 4, 1; 06: 53, 84, 54, 20, 5, 1; 07: 217, 380, 270, 110, 30, 6, 1; 08: 1014, 1926, 1490, 660, 195, 42, 7, 1; 09: 5335, 10840, 9020, 4300, 1365, 315, 56, 8, 1; 10: 31240, 67195, 59550, 30290, 10255, 2520, 476, 72, 9, 1; 11: 201608, 455379, 426405, 229740, 82425, 21448, 4284, 684, 90, 10, 1; ... From _Joerg Arndt_, Mar 05 2014: (Start) The 15 ascent sequences of length 4 (dots for zeros) together with their numbers of zeros and numbers of fixed points are: 01: [ . . . . ] 4 1 02: [ . . . 1 ] 3 1 03: [ . . 1 . ] 3 1 04: [ . . 1 1 ] 2 1 05: [ . . 1 2 ] 2 1 06: [ . 1 . . ] 3 2 07: [ . 1 . 1 ] 2 2 08: [ . 1 . 2 ] 2 2 09: [ . 1 1 . ] 2 2 10: [ . 1 1 1 ] 1 2 11: [ . 1 1 2 ] 1 2 12: [ . 1 2 . ] 2 3 13: [ . 1 2 1 ] 1 3 14: [ . 1 2 2 ] 1 3 15: [ . 1 2 3 ] 1 4 Both statistics give row 4: [5, 6, 3, 1]. (End)
Links
- Joerg Arndt and Alois P. Heinz, Rows n = 1..141, flattened
- Hsien-Kuei Hwang, and Emma Yu Jin, Asymptotics and statistics on Fishburn matrices and their generalizations, arXiv:1911.06690 [math.CO], 2019.
- V. Jelinek, Catalan pairs and Fishburn triples, Adv. Appl. Math. 70 (2015) 1-31
- 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: arXiv:1004.3220 [math.CO]).
- Paul Levande, Two new interpretations of the Fishburn numbers and their refined generating functions, arXiv:1006.3013
- Don Zagier, Vassiliev invariants and a strange identity related to the Dedekind eta-function, Topology, vol.40, pp.945-960 (2001); see p.948.
Crossrefs
Cf. A022493 (number of ascent sequences), A137251 (ascent sequences with k ascents), A218577 (ascent sequences with maximal element k).
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).
T(2n,n) gives A357309.
Programs
-
Maple
b:= proc(n, i, t) option remember; `if`(n=0, 1, expand(add( `if`(j=0, x, 1) *b(n-1, j, t+`if`(j>i, 1, 0)), j=0..t+1))) end: T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, -1$2)): seq(T(n), n=1..12); # Alois P. Heinz, Mar 11 2014 -
Mathematica
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 *) -
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 */ for(n=0,10,for(d=0,n,print1(T(n,d),", "));print("")) -
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 */ for(n=0,10,for(d=0,n,print1(T(n,d),", "));print(""))
Formula
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):
(1) A(x,y) = Sum_{n>=1} Product_{k=0..n-1} (1 - (1-x)^k*(1-x*y)),
(2) A(x,y) = Sum_{n>=1} x*y/(1-x*y)^n * Product_{k=1..n-1} (1 - (1-x)^k).
Extensions
Corrected offset, Joerg Arndt, Nov 03 2012
Comments