login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A022493 Fishburn numbers: number of linearized chord diagrams of degree n; also number of nonisomorphic interval orders on n unlabeled points. 43
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 (list; graph; refs; listen; history; text; internal format)
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..300

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.

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

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.

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} Prod_{i=1..n} (1-(1-x)^i).

Another formula for the g.f.: Sum_{n>=0} 1/(1-x)^(n+1) Prod_{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..inf} Prod_{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. 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.

Sequence in context: A337850 A125280 A338728 * A348580 A284729 A006966

Adjacent sequences:  A022490 A022491 A022492 * A022494 A022495 A022496

KEYWORD

nonn,nice

AUTHOR

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

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 23:47 EST 2022. Contains 350473 sequences. (Running on oeis4.)