OFFSET
0,3
COMMENTS
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
REFERENCES
P. C. Fishburn, Interval Graphs and Interval Orders, Wiley, New York, 1985.
LINKS
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.
FORMULA
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)
EXAMPLE
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 + ...
MAPLE
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
MATHEMATICA
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 *)
PROG
(PARI) {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 */
(Maxima) 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 */
(Sage)
# 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
CROSSREFS
Cf. A138265.
Cf. A137251 (ascent sequences with k ascents), A218577 (ascent sequences with maximal element k), A175579 (ascent sequences with k zeros).
KEYWORD
nonn,nice
AUTHOR
Alexander Stoimenow (stoimeno(AT)math.toronto.edu)
EXTENSIONS
Edited by N. J. A. Sloane, Nov 05 2011
STATUS
approved