|
|
A022493
|
|
Fishburn numbers: number of linearized chord diagrams of degree n; also number of nonisomorphic interval orders on n unlabeled points.
|
|
44
|
|
|
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
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
|
Giulio Cerbai and Anders Claesson, Fishburn trees, Univ. Iceland, 2023.
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 and Svante Linusson, n! matchings, n! posets, Proc. Amer. Math. Soc., Vol. 139 (2011), pp. 435-449.
Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, Counting Biorders, J. Integer Seq., Vol. 6 (2003), Article 03.4.3.
|
|
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
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
|
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)
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):
|
|
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));
(Sage)
# 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)]
|
|
CROSSREFS
|
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).
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
Alexander Stoimenow (stoimeno(AT)math.toronto.edu)
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|