|
| |
|
|
A022493
|
|
Number of linearized chord diagrams of degree n; also number of nonisomorphic interval orders on n unlabeled points.
|
|
13
| |
|
|
1, 1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, 1422074, 10886503, 89903100, 796713190, 7541889195, 75955177642, 810925547354, 9148832109645, 108759758865725, 1358836180945243, 17801039909762186, 243992799075850037
(list; graph; refs; listen; history; 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 (vladeta(AT)eunet.rs), Mar 10 2008
Also number of ascent sequences of length n. - N. J. A. Sloane, Dec 10 2011
|
|
|
REFERENCES
| 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.
Mireille Bousquet-Melou, 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 14 2009]
GRAHAM BRIGHTWELL AND MITCHEL T. KELLER, ASYMPTOTIC ENUMERATION OF LABELLED INTERVAL ORDERS, arXiv 1111.6766
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; http://www.ams.org/journals/proc/2011-139-02/S0002-9939-2010-10678-0/home.html.
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.
Soheir Mohamed Khamis, Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height, Order (journal), published on-line, 2011; DOI: 10.1007/s11083-011-9213-5.
Paul Levande, Two New Interpretations of the Fishburn Numbers and their Refined Generating Functions, arXiv:1006.3013v1.
J. A. Reeds and P. C. Fishburn, Counting split interval orders, Order, Vol. 18, No. 2, 2001, pp. 129-135.
Sherry H. F. Yan. On a conjecture about enumerating (2 + 2)-free posets, 2010, arXiv:1006.1226.
D. Zagier, Vassiliev invariants and a strange identity related to the Dedekind eta-function, Topology 40(5) (2001), 945-960.
|
|
|
LINKS
| D. Bar-Natan, Bibliography of Vassiliev Invariants
Mireille Bousquet-Melou, 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]
Julie Christophe, Jean-Paul Doignon and Samuel Fiorini, Counting Biorders, J. Integer Seqs., Vol. 6, 2003.
A. Stoimenow, Enumeration of chord diagrams and an upper bound for Vassiliev invariants, J. Knot Theory Ramifications, 7 (1998), no. 1, 93-114.
|
|
|
FORMULA
| Zagier gives the g.f. Sum_{n>=0} Prod_{i=1..n} (1-(1-x)^i).
Coefficients in expansion of Sum_{k=0..inf} Prod_{j=1..k} (1-x^j) about x=1 give (-1)^n*a(n) - R. W. Gosper Aug 08, 2001
|
|
|
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] (* From Jean-François Alcover, Dec 27 2011, after g.f. *)
|
|
|
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 */
|
|
|
CROSSREFS
| Cf. A059685, A035378.
Cf. A079144 for the labeled analogue, A059685, A035378.
Cf. A138265.
Row sums of A193387.
Sequence in context: A007548 A120567 A125280 * A006966 A056841 A107112
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
|
| |
|
|
