cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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

Original entry on oeis.org

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

Views

Author

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

Keywords

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

Examples

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

References

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

Links

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.

Programs

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

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)

Extensions

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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.