login
This site is supported by donations 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. 29
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.

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

A. M. Baxter, L. K. Pudwell, Ascent sequences avoiding pairs of patterns, 2014, http://faculty.valpo.edu/lpudwell/papers/AvoidingPairs.pdf

B. Bollobas and O. Riordan, Linearized chord diagrams and an upper bound for Vassiliev invariants. J. Knot Theory Ramifications 9 (2000), no. 7, 847-853.

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.

Niklas Eriksen, Jonas Sjöstrand, Equidistributed Statistics on Matchings and Permutations, Electronic Journal of Combinatorics. Volume 21 Issue 4, 2014.

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

P. C. Fishburn, Intransitive indifference in preference theory: a survey, Operational Research, 18 (1970) 207-208.

P. C. Fishburn, Intransitive indifference with unequal indifference intervals, Journal of Mathematical Psychology, 7 (1970) 144-149.

P. E. Haxell, J. J. McDonald and S. K. Thomason, Counting interval orders, Order, 4 (1987), 269-272.

Khamis, Soheir M., Height counting of unlabeled interval and N-free posets. Discrete Math. 275 (2004), no. 1-3, 165-175.

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.

P. Levande, Fishburn diagrams, Fishburn numbers and their refined generating functions, Journal of Combinatorial Theory, Series A 120 (2013) 194-217. - From N. J. A. Sloane, Dec 23 2012

J. A. Reeds and P. C. Fishburn, Counting split interval orders, Order, Vol. 18, No. 2, 2001, pp. 129-135.

D. Zagier, Vassiliev invariants and a strange identity related to the Dedekind eta-function, Topology 40(5) (2001), 945-960.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..300

George E. Andrews, Vít Jelínek, On q-Series Identities Related to Interval Orders, European Journal of Combinatorics, Volume 39, July 2014, 178-187; arXiv preprint.

George E. Andrews, James A. Sellers, Congruences for the Fishburn Numbers, arXiv:1401.5345 [math.NT], 2014

D. Bar-Natan, Sergei Duzhin, Bibliography of Vassiliev Invariants

Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, Sergey Kitaev, (2+2)-free posets, ascent sequences and pattern avoiding permutations. arxiv:0806.0666 [From Mark Dukes (dukes(AT)hi.is), May 12 2009]

Graham Brightwell and Mitchel T. Keller, Asymptotic enumeration of labelled interval orders, arXiv 1111.6766

Kathrin Bringmann, Yingkun Li, Robert C. Rhoades, Asymptotics for the number of row-Fishburn matrices, European Journal of Combinatorics, vol.41, pp.183-196, (October-2014); preprint.

Anders Claesson, Mark Dukes, Sergey Kitaev, A direct encoding of Stoimenow's matchings as ascent sequences, arXiv:0910.1619 [math.CO]

Anders Claesson, Mark Dukes and Martina Kubitzke, Partition and composition matrices, arXiv:1006.1312.

Anders Claesson and Svante Linusson, n! matchings, n! posets, Proc. Amer. Math. Soc. 139 (2011), 435-449

Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, Counting Biorders, J. Integer Seqs., Vol. 6, 2003.

M. Dukes, V. Jelínek, M. Kubitzke, Composition Matrices, (2+2)-Free Posets and their Specializations, Electronic Journal of Combinatorics, Volume 18, Issue 1, 2011, Paper #P44.

M. Dukes, S. Kitaev, J. Remmel, E. Steingrímsson, Enumerating (2+2)-free posets by indistinguishable elements, Journal of Combinatorics, Volume 2, Issue 1, 2011, pp. 139-163; arXiv preprint.

Frank Garvan, Congruences and relations for r-Fishburn numbers, arXiv:1406.5611 [math.NT], (21-June-2014)

Stuart A. Hannah, Sieved Enumeration of Interval Orders and Other Fishburn Structures, arXiv:1502.05340 [math.CO], (18-February-2015)

K. Hikami, J. Lovejoy, Torus knots and quantum modular forms, arXiv preprint arXiv:1409.6243, 2014

Soheir Mohamed Khamis, Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height, Order (journal), published on-line, 2011.

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.

Paul Levande, Two New Interpretations of the Fishburn Numbers and their Refined Generating Functions, arXiv:1006.3013v1.

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

L. Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015; http://faculty.valpo.edu/lpudwell/slides/ascseq.pdf.

A. Stoimenow, Enumeration of chord diagrams and an upper bound for Vassiliev invariants, J. Knot Theory Ramifications, 7 (1998), no. 1, 93-114.

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, 2010, arXiv:1006.1226.

Yan X Zhang, Four Variations on Graded Posets, arXiv preprint arXiv:1508.00318, 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

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 xrange(0, t+2) )

def a(n):  return b(n, 0, 0)

v022493=[a(n) for n in xrange(0, 66)]

print v022493

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

Sequence in context: A120567 A263779 A125280 * A284729 A006966 A277175

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 23 22:23 EDT 2017. Contains 291021 sequences.