A218577 -id:A218577 - cp's OEIS frontend

A022493 Fishburn numbers: number of linearized chord diagrams of degree n; also number of nonisomorphic interval orders on n unlabeled points.

1, 1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, 1422074, 10886503, 89903100, 796713190, 7541889195, 75955177642, 810925547354, 9148832109645, 108759758865725, 1358836180945243, 17801039909762186, 243992799075850037, 3492329741309417600, 52105418376516869150, 809029109658971635142

Offset: 0

Alexander Stoimenow (stoimeno(AT)math.toronto.edu)

Claesson and Linusson calls these the Fishburn numbers, after Peter Fishburn. [Peter Clingerman Fishburn (1936-2021) was an American mathematician and a pioneer in the field of decision-making processes. - Amiram Eldar, Jun 20 2021]
Also, number of unlabeled (2+2)-free posets.
Also, number of upper triangular matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n. - Vladeta Jovovic, Mar 10 2008
Row sums of A193387.
Also number of ascent sequences of length n. - N. J. A. Sloane, Dec 10 2011
An ascent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, d(k)>=0, and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) where asc(.) counts the ascents of its argument. - Joerg Arndt, Oct 17 2012
Replacing the function asc(.) above by a function chg(.) that counts changes in the prefix gives A000522 (arrangements). - Joerg Arndt, May 10 2013
Number of restricted growth strings (RGS) [d(0), d(1), d(2), ..., d(n-1)] such that d(0)=0, 0 <= d(k) <= k, and d(j) != d(k)+1 for j < k. - Joerg Arndt, May 10 2013
Number of permutations p(1),p(2),...,p(n) having no subsequence p(i),p(j),p(k) such that i+1 = j < k and p(k)+1 = p(i) < p(j); this corresponds to the avoidance of bivincular pattern (231,{1},{1}) in the terminology of Parviainen. Also, number of permutations p(1),...,p(n) with no subsequence p(i),p(j),p(k) with i+1 = j < k, p(i)+1 = p(k) < p(j). This is the bivincular pattern (132,{1},{1}). Proved by Bousquet-Mélou et al. and by Parviainen, respectively. - Vít Jelínek, Sep 05 2014

			From _Emanuele Munarini_, Oct 16 2012: (Start)
There are a(4)=15 ascent sequences (dots for zeros):
  01:  [ . . . . ]
  02:  [ . . . 1 ]
  03:  [ . . 1 . ]
  04:  [ . . 1 1 ]
  05:  [ . . 1 2 ]
  06:  [ . 1 . . ]
  07:  [ . 1 . 1 ]
  08:  [ . 1 . 2 ]
  09:  [ . 1 1 . ]
  10:  [ . 1 1 1 ]
  11:  [ . 1 1 2 ]
  12:  [ . 1 2 . ]
  13:  [ . 1 2 1 ]
  14:  [ . 1 2 2 ]
  15:  [ . 1 2 3 ]
(End)
From _Joerg Arndt_, May 10 2013: (Start)
There are a(4)=15 RGS of length 4 such that d(0)=0, 0 <= d(k) <= k, and d(j) != d(k)+1 for j < k (dots for zeros):
  01:  [ . . . . ]
  02:  [ . . . 1 ]
  03:  [ . . . 2 ]
  04:  [ . . . 3 ]
  05:  [ . . 1 1 ]
  06:  [ . . 1 2 ]
  07:  [ . . 1 3 ]
  08:  [ . . 2 . ]
  09:  [ . . 2 2 ]
  10:  [ . . 2 3 ]
  11:  [ . 1 1 1 ]
  12:  [ . 1 1 2 ]
  13:  [ . 1 1 3 ]
  14:  [ . 1 2 2 ]
  15:  [ . 1 2 3 ]
(End)
G.f. = 1 + x + 2*x^2 + 5*x^3 + 15*x^4 + 53*x^5 + 217*x^6 + 1014*x^7 + 5335*x^8 + ...

P. C. Fishburn, Interval Graphs and Interval Orders, Wiley, New York, 1985.

Alois P. Heinz, Table of n, a(n) for n = 0..488
Scott Ahlgren, Byungchan Kim and Jeremy Lovejoy, Dissections of strange q-series, arXiv:1812.02922 [math.NT], 2018.
George E. Andrews and Vít Jelínek, On q-Series Identities Related to Interval Orders, European Journal of Combinatorics, Volume 39, July 2014, 178-187; arXiv preprint, arXiv:1309.6669 [math.CO], 2013.
George E. Andrews and James A. Sellers, Congruences for the Fishburn Numbers, arXiv:1401.5345 [math.NT], 2014.
Juan S. Auli and Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020.
Dror Bar-Natan and Sergei Duzhin, Bibliography of Vassiliev Invariants.
Andrew M. Baxter and Lara K. Pudwell, Ascent sequences avoiding pairs of patterns, 2014.
Colin Bijaoui, Hans U. Boden, Beckham Myers, Robert Osburn, William Rushworth, Aaron Tronsgard and Shaoyang Zhou, Generalized Fishburn numbers and torus knots, arXiv:2002.00635 [math.NT], 2020.
Béla Bollobás and Oliver Riordan, Linearized chord diagrams and an upper bound for Vassiliev invariants, J. Knot Theory Ramifications, Vol. 9, No. 7 (2000), pp. 847-853.
Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes and Sergey Kitaev, (2+2)-free posets, ascent sequences and pattern avoiding permutations. arXiv:0806.0666 [math.CO], 2008-2009. [Mark Dukes (dukes(AT)hi.is), May 12 2009]
Graham Brightwell and Mitchel T. Keller, Asymptotic enumeration of labelled interval orders, arXiv:1111.6766 [math.CO], 2011.
Kathrin Bringmann, Yingkun Li and Robert C. Rhoades, Asymptotics for the number of row-Fishburn matrices, European Journal of Combinatorics, Vol. 41 (October 2014), pp. 183-196; preprint.
David Callan, On Ascent, Repetition and Descent Sequences, arXiv:1911.02209 [math.CO], 2019.
Giulio Cerbai, Modified ascent sequences and Bell numbers, arXiv:2305.10820 [math.CO], 2023. See p. 1.
Giulio Cerbai and Anders Claesson, Fishburn trees, Univ. Iceland, 2023.
Giulio Cerbai, Anders Claesson, and Bruce E. Sagan, Self-modified difference ascent sequences, arXiv:2408.06959 [math.CO], 2024.
William Y. C. Chen, Alvin Y. L. Dai, Theodore Dokos, Tim Dwyer and Bruce E. Sagan, On 021-Avoiding Ascent Sequences, The Electronic Journal of Combinatorics, Vol. 20, No. 1 (2013), #P76.
Anders Claesson, Mark Dukes and Sergey Kitaev, A direct encoding of Stoimenow's matchings as ascent sequences, arXiv:0910.1619 [math.CO], 2009.
Anders Claesson, Mark Dukes and Martina Kubitzke, Partition and composition matrices, arXiv:1006.1312 [math.CO], 2010-2011.
Anders Claesson and Svante Linusson, n! matchings, n! posets, Proc. Amer. Math. Soc., Vol. 139 (2011), pp. 435-449.
Dandan Chen, Sherry H. F. Yan and Robin D. P. Zhou, Equidistributed statistics on Fishburn matrices and permutations, arXiv:1808.04191 [math.CO], 2018.
Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, Counting Biorders, J. Integer Seq., Vol. 6 (2003), Article 03.4.3.
CombOS - Combinatorial Object Server, Generate pattern-avoiding permutations.
Matthieu Dien, Antoine Genitrini, and Frederic Peschanski, A Combinatorial Study of Async/Await Processes, Conf.: 19th Int'l Colloq. Theor. Aspects of Comp. (2022), (Analytic) Combinatorics of concurrent systems.
Mark Dukes, Vít Jelínek and Martina Kubitzke, Composition Matrices, (2+2)-Free Posets and their Specializations, Electronic Journal of Combinatorics, Vol. 18, No. 1 (2011), Paper #P44.
Mark Dukes, Sergey Kitaev, Jeffrey B. Remmel and Einar Steingrímsson, Enumerating (2+2)-free posets by indistinguishable elements, Journal of Combinatorics, Vol. 2, No. 1 (2011), pp. 139-163; arXiv preprint arXiv:1006.2696 [math.CO], 2010-2011.
Niklas Eriksen and Jonas Sjöstrand, Equidistributed Statistics on Matchings and Permutations, Electronic Journal of Combinatorics, Vol. 21, No. 4 (2014), Article P4.43.
Peter C. Fishburn, Intransitive indifference in preference theory: a survey, Operational Research, Vol. 18, No. 2 (1970), pp. 207-208.
Peter C. Fishburn, Intransitive indifference with unequal indifference intervals, Journal of Mathematical Psychology, Vol. 7, No. 1 (1970), pp. 144-149.
Shishuo Fu, Emma Yu Jin, Zhicong Lin, Sherry H. F. Yan and Robin D. P. Zhou, A new decomposition of ascent sequences and Euler-Stirling statistics, arXiv:1909.07277 [math.CO], 2019.
Frank Garvan, Congruences and relations for r-Fishburn numbers, arXiv:1406.5611 [math.NT], (21-June-2014).
Juan B. Gil and Michael D. Weiner, On pattern-avoiding Fishburn permutations, arXiv:1812.01682 [math.CO], 2018.
Ankush Goswami, Abhash Kumar Jha, Byungchan Kim, and Robert Osburn, Asymptotics and sign patterns for coefficients in expansions of Habiro elements, arXiv:2204.02628 [math.NT], 2022.
Stuart A. Hannah, Sieved Enumeration of Interval Orders and Other Fishburn Structures, arXiv:1502.05340 [math.CO], (18-February-2015).
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
P. E. Haxell, J. J. McDonald and S. K. Thomason, Counting interval orders, Order, Vol. 4 (1987), pp. 269-272.
Hsien-Kuei Hwang and Emma Yu Jin, Asymptotics and statistics on Fishburn matrices and their generalizations, arXiv:1911.06690 [math.CO], 2019.
Kazuhiro Hikami and Jeremy Lovejoy, Torus knots and quantum modular forms, arXiv preprint arXiv:1409.6243 [math.NT], 2014.
Soheir Mohamed Khamis, Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height, Order (journal), published on-line, Vol. 29 (2011), pp. 443-461.
Vít Jelínek, Counting general and self-dual interval orders, Journal of Combinatorial Theory, Series A, Vol. 119, No. 3 (April 2012), pp. 599-614; arXiv preprint arXiv:1106.2261 [math.CO], 2011.
Soheir M. Khamis, Height counting of unlabeled interval and N-free posets, Discrete Math. Vol. 275, No. 1-3 (2004), pp. 165-175.
Sergey Kitaev and Jeffrey Remmel, Enumerating (2+2)-free posets by the number of minimal elements and other statistics, Discrete Applied Mathematics, Vol. 159, No. 17 (2011), pp. 2098-2108.
Paul Levande, Two New Interpretations of the Fishburn Numbers and their Refined Generating Functions, arXiv:1006.3013 [math.CO], 2010.
Paul Levande, Fishburn diagrams, Fishburn numbers and their refined generating functions, Journal of Combinatorial Theory, Series A, Vol. 120, No. 1 (2013), pp. 194-217. - From _N. J. A. Sloane_, Dec 23 2012
Zhicong Lin and Sherry H. F. Yan, Vincular patterns in inversion sequences, Applied Mathematics and Computation, Vol. 364 (2020), 124672.
Robert Parviainen, Wilf classification of bi-vincular permutation patterns, arXiv:0910.5103 [math.CO], 2009.
Lara K. Pudwell, Ascent sequences and the binomial convolution of Catalan numbers, arXiv:1408.6823 [math.CO], (28-August-2014).
Lara Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015.
James A. Reeds and Peter C. Fishburn, Counting split interval orders, Order, Vol. 18, No. 2 (2001), pp. 129-135.
A. Stoimenow, Enumeration of chord diagrams and an upper bound for Vassiliev invariants, J. Knot Theory Ramifications, Vol. 7, No. 1 (1998), pp. 93-114; alternative link.
Armin Straub, Congruences for Fishburn numbers modulo prime powers, arXiv:1407.7521 [math.NT], (28-July-2014).
Sherry H. F. Yan, On a conjecture about enumerating (2 + 2)-free posets, arXiv:1006.1226 [math.CO], 2010.
Don Zagier, Vassiliev invariants and a strange identity related to the Dedekind eta-function, Topology, Vol. 40, No. 5 (2001), pp. 945-960.
Yan X. Zhang, Four Variations on Graded Posets, arXiv preprint arXiv:1508.00318 [math.CO], 2015. See p. 11.
Robin D. P. Zhou, Pattern avoidance in revised ascent sequences, arXiv:2505.05171 [math.CO], 2025. See p. 2.

Cf. A059685, A035378.
Cf. A079144 for the labeled analog, A059685, A035378.
Cf. A138265.
Cf. A137251 (ascent sequences with k ascents), A218577 (ascent sequences with maximal element k), A175579 (ascent sequences with k zeros).
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).
Row sums of A294219, main diagonal of A294220.

b:= proc(n, i, t) option remember; `if`(n<1, 1,
      add(b(n-1, j, t+`if`(j>i,1,0)), j=0..t+1))
    end:
a:= n-> b(n-1, 0, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 09 2012

max = 22; f[x_] := Sum[ Product[ 1-(1-x)^j, {j, 1, n}], {n, 0, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* Jean-François Alcover, Dec 27 2011, after g.f. *)
b[n_, i_, t_] := b[n, i, t] = If[n<1, 1, Sum[b[n-1, j, t + If[j>i, 1, 0]], {j, 0, t+1}] ]; a[n_] := b[n-1, 0, 0]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Apr 09 2015, after Alois P. Heinz *)

F(x,n) := remainder(sum(product(1-(1-x)^i,i,1,k),k,0,n),x^(n+1));
makelist(coeff(F(x,n),x^n),n,0,20); /* Emanuele Munarini, Oct 16 2012 */

{a(n) = polcoeff( sum(i=0, n, prod(j=1, i, 1 - (1-x)^j, 1 + x * O(x^n))), n)}; /* Michael Somos, Jul 21 2006 */

# Program adapted from Alois P. Heinz's Maple code.
# b(n,i,t) gives the number of length-n postfixes of ascent sequences
# with a prefix having t ascents and last element i.
@CachedFunction
def b(n, i, t):
    if n <= 1: return 1
    return sum(b(n - 1, j, t + (j > i)) for j in range(t + 2))
def a(n): return b(n, 0, 0)
[a(n) for n in range(66)]
# Joerg Arndt, May 11 2013

Zagier gives the g.f. Sum_{n>=0} Product_{i=1..n} (1-(1-x)^i).
Another formula for the g.f.: Sum_{n>=0} 1/(1-x)^(n+1) Product_{i=1..n} (1-1/(1-x)^i)^2. Proved by Andrews-Jelínek and Bringmann-Li-Rhoades. - Vít Jelínek, Sep 05 2014
Coefficients in expansion of Sum_{k>=0} Product_{j=1..k} (1-x^j) about x=1 give (-1)^n*a(n). - Bill Gosper, Aug 08 2001
G.f.: 1 + x*Q(0), where Q(k) = 1 + (1-(1-x)^(2*k+2))/(1 - (1-(1-x)^(2*k+3))/(1 -(1-x)^(2*k+3) + 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 13 2013
G.f. (conjecture): Q(0), where Q(k) = 1 + (1 - (1-x)^(2*k+1))/(1 - (1-(1-x)^(2*k+2))/(1 -(1-x)^(2*k+2) + 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 13 2013
G.f.: 1 + z(1)/( 1+0 - z(2)/( 1+z(2) - z(3)/( 1+z(3) - z(4)/( 1+z(4) - z(5)/(...))))) where z(k) = 1 - (1-x)^k; this is Euler's continued fraction for 1 + z(1) + z(1)*z(2) + z(1)*z(2)*z(3) + ... . - Joerg Arndt, Mar 11 2014
Asymptotics (proved by Zagier, 2001; see also Brightwell and Keller, 2011): a(n) ~ (12*sqrt(3)*exp(Pi^2/12)/Pi^(5/2)) * n!*sqrt(n)*(6/Pi^2)^n. - Vaclav Kotesovec, May 03 2014  [edited by Vít Jelínek, Sep 05 2014]
For any prime p that is not a quadratic residue mod 23, there is at least one value of j such that for all k and m, we have a(p^k*m - j) mod p^k = 0. E.g., for p=5 one may take j=1 and k=2, and conclude that a(25-1), a(50-1), a(75-1), a(100-1), ...  are multiples of 25. See Andrews-Sellers, Garvan, and Straub. - Vít Jelínek, Sep 05 2014
From Peter Bala, Dec 17 2021: (Start)
Conjectural g.f.s:
A(x) = Sum_{n >= 1} n*(1 - x)^n*Product_{k = 1..n-1} (1 - (1 - x)^k).
x*A(x) = 1 - Sum_{n >= 1} n*(1 - x)^(2*n+1)*Product_{k = 1..n-1} (1 - (1 - x)^k). (End)

Edited by N. J. A. Sloane, Nov 05 2011

A137251 Triangle T(n,k) read by rows: number of k X k triangular matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n, n>=1, 1<=k<=n.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 6, 7, 1, 1, 10, 26, 15, 1, 1, 15, 71, 98, 31, 1, 1, 21, 161, 425, 342, 63, 1, 1, 28, 322, 1433, 2285, 1138, 127, 1, 1, 36, 588, 4066, 11210, 11413, 3670, 255, 1, 1, 45, 1002, 10165, 44443, 79781, 54073, 11586, 511, 1, 1, 55, 1617, 23056, 150546, 434638, 528690, 246409, 36038, 1023, 1

Offset: 1

Vladeta Jovovic, Mar 11 2008

Row sums are A022493.
Number of ascent sequences of length n with k-1 ascents, see example. [Joerg Arndt, Nov 03 2012]
Number of interval orders on n elements having exactly k maximal antichains. Also, number of interval orders on n elements having an interval representation with k distinct endpoints, but not with k-1 distinct endpoints. Also, number of interval orders on n elements whose elements define k distinct strict down-sets (a strict down-set defined by an element x of a poset (P,<) is the set {y in P: yVít Jelínek, Sep 06 2014

			Triangle starts:
01:  1,
02:  1,  1,
03:  1,  3,    1,
04:  1,  6,    7,     1,
05:  1, 10,   26,    15,      1,
06:  1, 15,   71,    98,     31,       1,
07:  1, 21,  161,   425,    342,      63,       1,
08:  1, 28,  322,  1433,   2285,    1138,     127,       1,
09:  1, 36,  588,  4066,  11210,   11413,    3670,     255,       1,
10:  1, 45, 1002, 10165,  44443,   79781,   54073,   11586,     511,      1,
11:  1, 55, 1617, 23056, 150546,  434638,  528690,  246409,   36038,   1023,    1,
12:  1, 66, 2497, 48400, 451515, 1968580, 3895756, 3316193, 1090517, 110930, 2047, 1,
...
From _Joerg Arndt_, Nov 03 2012: (Start)
The 53 ascent sequences of length 5 together with their numbers of ascents are (dots for zeros):
01:  [ . . . . . ]   0      28:  [ . 1 1 . 1 ]   2
02:  [ . . . . 1 ]   1      29:  [ . 1 1 . 2 ]   2
03:  [ . . . 1 . ]   1      30:  [ . 1 1 1 . ]   1
04:  [ . . . 1 1 ]   1      31:  [ . 1 1 1 1 ]   1
05:  [ . . . 1 2 ]   2      32:  [ . 1 1 1 2 ]   2
06:  [ . . 1 . . ]   1      33:  [ . 1 1 2 . ]   2
07:  [ . . 1 . 1 ]   2      34:  [ . 1 1 2 1 ]   2
08:  [ . . 1 . 2 ]   2      35:  [ . 1 1 2 2 ]   2
09:  [ . . 1 1 . ]   1      36:  [ . 1 1 2 3 ]   3
10:  [ . . 1 1 1 ]   1      37:  [ . 1 2 . . ]   2
11:  [ . . 1 1 2 ]   2      38:  [ . 1 2 . 1 ]   3
12:  [ . . 1 2 . ]   2      39:  [ . 1 2 . 2 ]   3
13:  [ . . 1 2 1 ]   2      40:  [ . 1 2 . 3 ]   3
14:  [ . . 1 2 2 ]   2      41:  [ . 1 2 1 . ]   2
15:  [ . . 1 2 3 ]   3      42:  [ . 1 2 1 1 ]   2
16:  [ . 1 . . . ]   1      43:  [ . 1 2 1 2 ]   3
17:  [ . 1 . . 1 ]   2      44:  [ . 1 2 1 3 ]   3
18:  [ . 1 . . 2 ]   2      45:  [ . 1 2 2 . ]   2
19:  [ . 1 . 1 . ]   2      46:  [ . 1 2 2 1 ]   2
20:  [ . 1 . 1 1 ]   2      47:  [ . 1 2 2 2 ]   2
21:  [ . 1 . 1 2 ]   3      48:  [ . 1 2 2 3 ]   3
22:  [ . 1 . 1 3 ]   3      49:  [ . 1 2 3 . ]   3
23:  [ . 1 . 2 . ]   2      50:  [ . 1 2 3 1 ]   3
24:  [ . 1 . 2 1 ]   2      51:  [ . 1 2 3 2 ]   3
25:  [ . 1 . 2 2 ]   2      52:  [ . 1 2 3 3 ]   3
26:  [ . 1 . 2 3 ]   3      53:  [ . 1 2 3 4 ]   4
27:  [ . 1 1 . . ]   1
There is 1 ascent sequence with no ascent, 10 with one ascent, etc., giving the fourth row [1, 10, 26, 15, 1].
(End)

Peter C. Fishburn, Interval Orders and Interval Graphs: Study of Partially Ordered Sets, John Wiley & Sons, 1985.

Alois P. Heinz, Rows n = 1..141, flattened (Rows n = 1..15 from Joerg Arndt)
Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, and Sergey Kitaev, (2+2)-free posets, ascent sequences and pattern avoiding permutations, arXiv:0806.0666 [math.CO], 2008.
Giulio Cerbai, Modified ascent sequences and Bell numbers, arXiv:2305.10820 [math.CO], 2023. See p. 8.
William Y. C. Chen, Alvin Y.L. Dai, Theodore Dokos, Tim Dwyer and Bruce E. Sagan, On 021-Avoiding Ascent Sequences, The Electronic Journal of Combinatorics Volume 20, Issue 1 (2013), #P76.
Matthieu Dien, Antoine Genitrini, and Frederic Peschanski, A Combinatorial Study of Async/Await Processes, Conf.: 19th Int'l Colloq. Theor. Aspects of Comp. (2022), (Analytic) Combinatorics of concurrent systems.
M. Dukes, V Jelínek, and M. Kubitzke Composition Matrices, (2+2)-Free Posets and their Specializations, Electronic Journal of Combinatorics, Volume 18, Issue 1, 2011, Paper #P44.
Vít Jelínek, Counting general and self-dual interval orders, Journal of Combinatorial Theory, Series A, Volume 119, Issue 3, April 2012, pp. 599-614; arXiv preprint, arXiv:1106.2261 [math.CO], 2011.

Cf. A022493 (number of ascent sequences), A218577 (ascent sequences with maximal element k), A175579 (ascent sequences with k zeros).

T(2n,n) gives A357141.

b:= proc(n, i, t) option remember; local j; if n<1 then [0$t, 1]
      else []; for j from 0 to t+1 do zip((x, y)->x+y, %,
      b(n-1, j, t+`if`(j>i, 1, 0)), 0) od; % fi
    end:
T:= n-> b(n-1, 0, 0)[]:
seq(T(n), n=1..12);  # Alois P. Heinz, May 20 2013

zip[f_, x_List, y_List, z_] := With[{m = Max[Length[x], Length[y]]}, f[PadRight[x, m, z], PadRight[y, m, z]]]; b[n_, i_, t_] := b[n, i, t] = Module[{j, pc}, If[n<1, Append[Array[0&, t], 1], pc = {}; For[j = 0, j <= t+1, j++, pc = zip[Plus, pc, b[n-1, j, t+If[j>i, 1, 0]], 0]]; pc]]; T[n_] := b[n-1, 0, 0]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Jan 29 2014, after Alois P. Heinz *)

G.f.: Sum_{n,k>=1} T(n,k)x^n y^k = Sum_{n>=1} y^n Product_{i=1..n} (1-(1-x)^i)/(y+(1-x)^i-y*(1-x)^i). See Jelínek's paper, Corollary 2.5. - Vít Jelínek, Sep 06 2014

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

Original entry on oeis.org

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

R. J. Mathar, Jul 15 2010

The first column and the row sums are both A022493.

Also the number of length-n ascent sequences with k fixed points. [Joerg Arndt, Nov 03 2012]

			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)

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.

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.

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

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

{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(""))

{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(""))

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

Corrected offset, Joerg Arndt, Nov 03 2012

cp's OEIS Frontend

A022493 Fishburn numbers: number of linearized chord diagrams of degree n; also number of nonisomorphic interval orders on n unlabeled points.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Sage

Formula

Extensions

A137251 Triangle T(n,k) read by rows: number of k X k triangular matrices with nonnegative integer entries and without zero rows or columns such that sum of all entries is equal to n, n>=1, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A218579 Triangle read by rows: T(n,k) is the number of ascent sequences of length n with last zero at position k-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A218580 Triangle read by rows: T(n,k) is the number of ascent sequences of length n with first occurrence of the maximal value at position k-1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A218581 Triangle read by rows: T(n,k) is the number of ascent sequences of length n with last occurrence of the maximal value at position k-1.

Views

Author

Keywords

Comments

Examples

Crossrefs