The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #280 Aug 14 2024 05:41:32
%S 1,1,2,5,15,53,217,1014,5335,31240,201608,1422074,10886503,89903100,
%T 796713190,7541889195,75955177642,810925547354,9148832109645,
%U 108759758865725,1358836180945243,17801039909762186,243992799075850037,3492329741309417600,52105418376516869150,809029109658971635142
%N Fishburn numbers: number of linearized chord diagrams of degree n; also number of nonisomorphic interval orders on n unlabeled points.
%C 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]
%C Also, number of unlabeled (2+2)-free posets.
%C 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
%C Row sums of A193387.
%C Also number of ascent sequences of length n. - _N. J. A. Sloane_, Dec 10 2011
%C 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
%C Replacing the function asc(.) above by a function chg(.) that counts changes in the prefix gives A000522 (arrangements). - _Joerg Arndt_, May 10 2013
%C 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
%C 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
%D P. C. Fishburn, Interval Graphs and Interval Orders, Wiley, New York, 1985.
%H Alois P. Heinz, <a href="/A022493/b022493.txt">Table of n, a(n) for n = 0..488</a>
%H Scott Ahlgren, Byungchan Kim and Jeremy Lovejoy, <a href="https://arxiv.org/abs/1812.02922">Dissections of strange q-series</a>, arXiv:1812.02922 [math.NT], 2018.
%H George E. Andrews and Vít Jelínek, <a href="http://dx.doi.org/10.1016/j.ejc.2014.01.003">On q-Series Identities Related to Interval Orders</a>, European Journal of Combinatorics, Volume 39, July 2014, 178-187; <a href="http://arxiv.org/abs/1309.6669">arXiv preprint</a>, arXiv:1309.6669 [math.CO], 2013.
%H George E. Andrews and James A. Sellers, <a href="http://arxiv.org/abs/1401.5345">Congruences for the Fishburn Numbers</a>, arXiv:1401.5345 [math.NT], 2014.
%H Juan S. Auli and Sergi Elizalde, <a href="https://arxiv.org/abs/2003.11533">Wilf equivalences between vincular patterns in inversion sequences</a>, arXiv:2003.11533 [math.CO], 2020.
%H Dror Bar-Natan and Sergei Duzhin, <a href="http://www.pdmi.ras.ru/~duzhin/VasBib/">Bibliography of Vassiliev Invariants</a>.
%H Andrew M. Baxter and Lara K. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf">Ascent sequences avoiding pairs of patterns</a>, 2014.
%H Colin Bijaoui, Hans U. Boden, Beckham Myers, Robert Osburn, William Rushworth, Aaron Tronsgard and Shaoyang Zhou, <a href="https://arxiv.org/abs/2002.00635">Generalized Fishburn numbers and torus knots</a>, arXiv:2002.00635 [math.NT], 2020.
%H Béla Bollobás and Oliver Riordan, <a href="https://doi.org/10.1142/S0218216500000475">Linearized chord diagrams and an upper bound for Vassiliev invariants</a>, J. Knot Theory Ramifications, Vol. 9, No. 7 (2000), pp. 847-853.
%H Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes and Sergey Kitaev, <a href="http://arxiv.org/abs/0806.0666">(2+2)-free posets, ascent sequences and pattern avoiding permutations.</a> arXiv:0806.0666 [math.CO], 2008-2009. [Mark Dukes (dukes(AT)hi.is), May 12 2009]
%H Graham Brightwell and Mitchel T. Keller, <a href="http://arxiv.org/abs/1111.6766">Asymptotic enumeration of labelled interval orders</a>, arXiv:1111.6766 [math.CO], 2011.
%H Kathrin Bringmann, Yingkun Li and Robert C. Rhoades, <a href="https://doi.org/10.1016/j.ejc.2014.04.003">Asymptotics for the number of row-Fishburn matrices</a>, European Journal of Combinatorics, Vol. 41 (October 2014), pp. 183-196; <a href="http://www.mi.uni-koeln.de/Bringmann/selfdual_rev7.pdf">preprint</a>.
%H David Callan, <a href="https://arxiv.org/abs/1911.02209">On Ascent, Repetition and Descent Sequences</a>, arXiv:1911.02209 [math.CO], 2019.
%H Giulio Cerbai, <a href="https://arxiv.org/abs/2305.10820">Modified ascent sequences and Bell numbers</a>, arXiv:2305.10820 [math.CO], 2023. See p. 1.
%H Giulio Cerbai and Anders Claesson, <a href="https://akc.is/papers/040-Fishburn-trees.pdf">Fishburn trees</a>, Univ. Iceland, 2023.
%H Giulio Cerbai, Anders Claesson, and Bruce E. Sagan, <a href="https://arxiv.org/abs/2408.06959">Self-modified difference ascent sequences</a>, arXiv:2408.06959 [math.CO], 2024.
%H William Y. C. Chen, Alvin Y. L. Dai, Theodore Dokos, Tim Dwyer and Bruce E. Sagan, <a href="https://doi.org/10.37236/2472">On 021-Avoiding Ascent Sequences</a>, The Electronic Journal of Combinatorics, Vol. 20, No. 1 (2013), #P76.
%H Anders Claesson, Mark Dukes and Sergey Kitaev, <a href="http://arxiv.org/abs/0910.1619">A direct encoding of Stoimenow's matchings as ascent sequences</a>, arXiv:0910.1619 [math.CO], 2009.
%H Anders Claesson, Mark Dukes and Martina Kubitzke, <a href="http://arxiv.org/abs/1006.1312">Partition and composition matrices</a>, arXiv:1006.1312 [math.CO], 2010-2011.
%H Anders Claesson and Svante Linusson, <a href="http://www.ams.org/journals/proc/2011-139-02/S0002-9939-2010-10678-0/home.html">n! matchings, n! posets</a>, Proc. Amer. Math. Soc., Vol. 139 (2011), pp. 435-449.
%H Dandan Chen, Sherry H. F. Yan and Robin D. P. Zhou, <a href="https://arxiv.org/abs/1808.04191">Equidistributed statistics on Fishburn matrices and permutations</a>, arXiv:1808.04191 [math.CO], 2018.
%H Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Doignon/doignon40.html">Counting Biorders</a>, J. Integer Seq., Vol. 6 (2003), Article 03.4.3.
%H CombOS - Combinatorial Object Server, <a href="http://combos.org/jump">Generate pattern-avoiding permutations</a>.
%H Matthieu Dien, Antoine Genitrini, and Frederic Peschanski, <a href="https://www.researchgate.net/publication/363253998_A_Combinatorial_Study_of_AsyncAwait_Processes">A Combinatorial Study of Async/Await Processes</a>, Conf.: 19th Int'l Colloq. Theor. Aspects of Comp. (2022), (Analytic) Combinatorics of concurrent systems.
%H Mark Dukes, Vít Jelínek and Martina Kubitzke, <a href="https://doi.org/10.37236/531">Composition Matrices, (2+2)-Free Posets and their Specializations</a>, Electronic Journal of Combinatorics, Vol. 18, No. 1 (2011), Paper #P44.
%H Mark Dukes, Sergey Kitaev, Jeffrey B. Remmel and Einar Steingrímsson, <a href="http://dx.doi.org/10.4310/JOC.2011.v2.n1.a6">Enumerating (2+2)-free posets by indistinguishable elements</a>, Journal of Combinatorics, Vol. 2, No. 1 (2011), pp. 139-163; <a href="http://arxiv.org/abs/1006.2696">arXiv preprint</a> arXiv:1006.2696 [math.CO], 2010-2011.
%H Niklas Eriksen and Jonas Sjöstrand, <a href="https://doi.org/10.37236/3981">Equidistributed Statistics on Matchings and Permutations</a>, Electronic Journal of Combinatorics, Vol. 21, No. 4 (2014), Article P4.43.
%H Peter C. Fishburn, <a href="https://www.jstor.org/stable/168680">Intransitive indifference in preference theory: a survey</a>, Operational Research, Vol. 18, No. 2 (1970), pp. 207-208.
%H Peter C. Fishburn, <a href="https://doi.org/10.1016/0022-2496(70)90062-3">Intransitive indifference with unequal indifference intervals</a>, Journal of Mathematical Psychology, Vol. 7, No. 1 (1970), pp. 144-149.
%H Shishuo Fu, Emma Yu Jin, Zhicong Lin, Sherry H. F. Yan and Robin D. P. Zhou, <a href="https://arxiv.org/abs/1909.07277">A new decomposition of ascent sequences and Euler-Stirling statistics</a>, arXiv:1909.07277 [math.CO], 2019.
%H Frank Garvan, <a href="http://arxiv.org/abs/1406.5611">Congruences and relations for r-Fishburn numbers</a>, arXiv:1406.5611 [math.NT], (21-June-2014).
%H Juan B. Gil and Michael D. Weiner, <a href="https://arxiv.org/abs/1812.01682">On pattern-avoiding Fishburn permutations</a>, arXiv:1812.01682 [math.CO], 2018.
%H Ankush Goswami, Abhash Kumar Jha, Byungchan Kim, and Robert Osburn, <a href="https://arxiv.org/abs/2204.02628">Asymptotics and sign patterns for coefficients in expansions of Habiro elements</a>, arXiv:2204.02628 [math.NT], 2022.
%H Stuart A. Hannah, <a href="http://arxiv.org/abs/1502.05340">Sieved Enumeration of Interval Orders and Other Fishburn Structures</a>, arXiv:1502.05340 [math.CO], (18-February-2015).
%H Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze and Aaron Williams, <a href="https://arxiv.org/abs/1906.06069">Combinatorial generation via permutation languages. I. Fundamentals</a>, arXiv:1906.06069 [cs.DM], 2019.
%H P. E. Haxell, J. J. McDonald and S. K. Thomason, <a href="https://doi.org/10.1007/BF00337889">Counting interval orders</a>, Order, Vol. 4 (1987), pp. 269-272.
%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 Kazuhiro Hikami and Jeremy Lovejoy, <a href="http://arxiv.org/abs/1409.6243">Torus knots and quantum modular forms</a>, arXiv preprint arXiv:1409.6243 [math.NT], 2014.
%H Soheir Mohamed Khamis, <a href="http://dx.doi.org/10.1007/s11083-011-9213-5">Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height</a>, Order (journal), published on-line, Vol. 29 (2011), pp. 443-461.
%H Vít Jelínek, <a href="http://dx.doi.org/10.1016/j.jcta.2011.11.010">Counting general and self-dual interval orders</a>, Journal of Combinatorial Theory, Series A, Vol. 119, No. 3 (April 2012), pp. 599-614; <a href="http://arxiv.org/abs/1106.2261">arXiv preprint</a> arXiv:1106.2261 [math.CO], 2011.
%H Soheir M. Khamis, <a href="https://doi.org/10.1016/S0012-365X(03)00106-7">Height counting of unlabeled interval and N-free posets</a>, Discrete Math. Vol. 275, No. 1-3 (2004), pp. 165-175.
%H Sergey Kitaev and Jeffrey Remmel, <a href="https://doi.org/10.1016/j.dam.2011.07.010">Enumerating (2+2)-free posets by the number of minimal elements and other statistics</a>, Discrete Applied Mathematics, Vol. 159, No. 17 (2011), pp. 2098-2108.
%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 [math.CO], 2010.
%H Paul Levande, <a href="https://doi.org/10.1016/j.jcta.2012.07.012">Fishburn diagrams, Fishburn numbers and their refined generating functions</a>, Journal of Combinatorial Theory, Series A, Vol. 120, No. 1 (2013), pp. 194-217. - From _N. J. A. Sloane_, Dec 23 2012
%H Zhicong Lin and Sherry H. F. Yan, <a href="https://doi.org/10.1016/j.amc.2019.124672">Vincular patterns in inversion sequences</a>, Applied Mathematics and Computation, Vol. 364 (2020), 124672.
%H Robert Parviainen, <a href="http://arxiv.org/abs/0910.5103">Wilf classification of bi-vincular permutation patterns</a>, arXiv:0910.5103 [math.CO], 2009.
%H Lara K. Pudwell, <a href="http://arxiv.org/abs/1408.6823">Ascent sequences and the binomial convolution of Catalan numbers</a>, arXiv:1408.6823 [math.CO], (28-August-2014).
%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf">Pattern-avoiding ascent sequences</a>, Slides from a talk, 2015.
%H James A. Reeds and Peter C. Fishburn, <a href="https://doi.org/10.1023/A:1011914411416">Counting split interval orders</a>, Order, Vol. 18, No. 2 (2001), pp. 129-135.
%H A. Stoimenow, <a href="https://doi.org/10.1142/S0218216598000073">Enumeration of chord diagrams and an upper bound for Vassiliev invariants</a>, J. Knot Theory Ramifications, Vol. 7, No. 1 (1998), pp. 93-114; <a href="https://citeseerx.ist.psu.edu/pdf/98a194a9b2a21d153f20e787d77b4f57b6849a6e">alternative link</a>.
%H Armin Straub, <a href="http://arxiv.org/abs/1407.7521">Congruences for Fishburn numbers modulo prime powers</a>, arXiv:1407.7521 [math.NT], (28-July-2014).
%H Sherry H. F. Yan, <a href="http://arxiv.org/abs/1006.1226">On a conjecture about enumerating (2 + 2)-free posets</a>, arXiv:1006.1226 [math.CO], 2010.
%H Don Zagier, <a href="https://core.ac.uk/download/pdf/82563174.pdf">Vassiliev invariants and a strange identity related to the Dedekind eta-function</a>, Topology, Vol. 40, No. 5 (2001), pp. 945-960.
%H Yan X. Zhang, <a href="http://arxiv.org/abs/1508.00318">Four Variations on Graded Posets</a>, arXiv preprint arXiv:1508.00318 [math.CO], 2015.
%F Zagier gives the g.f. Sum_{n>=0} Product_{i=1..n} (1-(1-x)^i).
%F 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
%F 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
%F 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
%F 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
%F 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
%F 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]
%F 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
%F From _Peter Bala_, Dec 17 2021: (Start)
%F Conjectural g.f.s:
%F A(x) = Sum_{n >= 1} n*(1 - x)^n*Product_{k = 1..n-1} (1 - (1 - x)^k).
%F x*A(x) = 1 - Sum_{n >= 1} n*(1 - x)^(2*n+1)*Product_{k = 1..n-1} (1 - (1 - x)^k). (End)
%e From _Emanuele Munarini_, Oct 16 2012: (Start)
%e There are a(4)=15 ascent sequences (dots for zeros):
%e 01: [ . . . . ]
%e 02: [ . . . 1 ]
%e 03: [ . . 1 . ]
%e 04: [ . . 1 1 ]
%e 05: [ . . 1 2 ]
%e 06: [ . 1 . . ]
%e 07: [ . 1 . 1 ]
%e 08: [ . 1 . 2 ]
%e 09: [ . 1 1 . ]
%e 10: [ . 1 1 1 ]
%e 11: [ . 1 1 2 ]
%e 12: [ . 1 2 . ]
%e 13: [ . 1 2 1 ]
%e 14: [ . 1 2 2 ]
%e 15: [ . 1 2 3 ]
%e (End)
%e From _Joerg Arndt_, May 10 2013: (Start)
%e 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):
%e 01: [ . . . . ]
%e 02: [ . . . 1 ]
%e 03: [ . . . 2 ]
%e 04: [ . . . 3 ]
%e 05: [ . . 1 1 ]
%e 06: [ . . 1 2 ]
%e 07: [ . . 1 3 ]
%e 08: [ . . 2 . ]
%e 09: [ . . 2 2 ]
%e 10: [ . . 2 3 ]
%e 11: [ . 1 1 1 ]
%e 12: [ . 1 1 2 ]
%e 13: [ . 1 1 3 ]
%e 14: [ . 1 2 2 ]
%e 15: [ . 1 2 3 ]
%e (End)
%e 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 b:= proc(n, i, t) option remember; `if`(n<1, 1,
%p add(b(n-1, j, t+`if`(j>i,1,0)), j=0..t+1))
%p end:
%p a:= n-> b(n-1, 0, 0):
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Nov 09 2012
%t 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. *)
%t 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_ *)
%o (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 */
%o (Maxima) F(x,n) := remainder(sum(product(1-(1-x)^i,i,1,k),k,0,n),x^(n+1));
%o makelist(coeff(F(x,n),x^n),n,0,20); /* _Emanuele Munarini_, Oct 16 2012 */
%o (Sage)
%o # Program adapted from _Alois P. Heinz_'s Maple code.
%o # b(n,i,t) gives the number of length-n postfixes of ascent sequences
%o # with a prefix having t ascents and last element i.
%o @CachedFunction
%o def b(n, i, t):
%o if n <= 1: return 1
%o return sum(b(n - 1, j, t + (j > i)) for j in range(t + 2))
%o def a(n): return b(n, 0, 0)
%o [a(n) for n in range(66)]
%o # _Joerg Arndt_, May 11 2013
%Y Cf. A059685, A035378.
%Y Cf. A079144 for the labeled analog, A059685, A035378.
%Y Cf. A138265.
%Y Cf. A137251 (ascent sequences with k ascents), A218577 (ascent sequences with maximal element k), A175579 (ascent sequences with k zeros).
%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 Row sums of A294219, main diagonal of A294220.
%K nonn,nice
%O 0,3
%A Alexander Stoimenow (stoimeno(AT)math.toronto.edu)
%E Edited by _N. J. A. Sloane_, Nov 05 2011