OFFSET
0,3
COMMENTS
Also known as naturally labeled posets. - David Bevan, Nov 16 2023
Also the number of n X n upper triangular Boolean matrices B with all diagonal entries 1 such that B = B^2.
The asymptotic values derived by Brightwell et al. are relevant only for extremely large values of n. The average number of linear extensions (topological sorts) of a random partial order on {1,...,n} is n! S_n / N_n, where S_n is this sequence and N_n is sequence A001035
REFERENCES
N. B. Hindman, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
S. P. Avann, The lattice of natural partial orders, Aequationes Mathematicae 8 (1972), 95-102.
David Bevan, Gi-Sang Cheon and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.
Graham Brightwell, Hans Jürgen Prömel and Angelika Steger, The average number of linear extensions of a partial order, Journal of Combinatorial Theory A73 (1996), 193-206.
Gi-Sang Cheon, Hong Joon Choi, Gukwon Kwon, Hojoon Lee, and Yaling Wang, A matrix approach to the structure, enumeration, and applications of partially ordered sets, arXiv:2602.04533 [math.CO], 2026. See p. 3.
Gi-Sang Cheon and Samuele Giraudo, A matrix approach to the enumeration of naturally labeled posets, arXiv:2512.17749 [math.CO], 2025. See p. 2.
Steven R. Finch, Transitive relations, topologies and partial orders. [Archived link]
Steven R. Finch, Transitive relations, topologies and partial orders, June 5, 2003. [Cached copy, with permission of the author]
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
L. H. Harper, The Range of a Steiner Operation, arXiv preprint arXiv:1608.07747 [math.CO], 2016.
N. Hindman and N. J. A. Sloane, Correspondence, 1981-1991
Florent Hivert and Nicolas M. Thiéry, Controlling the C3 Super Class Linearization Algorithm for Large Hierarchies of Classes, Order (2022).
Adam King, A. Laubmeier, K. Orans, and A. Godbole, Universal and Overlap Cycles for Posets, Words, and Juggling Patterns, arXiv preprint arXiv:1405.5938 [math.CO], 2014.
Donald E. Knuth, POSETS, program for n = 10, 11, 12.
Jean-Gabriel Luque, Ludovic Mignot, and Florent Nicart, Some Combinatorial Operators in Language Theory, arXiv preprint arXiv:1205.3371 [cs.FL], 2012. - N. J. A. Sloane, Oct 22 2012
Andrew Sack, Lattices from Pointed Building Sets: Generalized Ornamentation Lattices, arXiv:2602.06004 [math.CO], 2026. See p. 6.
FORMULA
E.g.f.: exp(S(x)-1) where S(x)is the e.g.f. for A323502. - Ludovic Schwob, Mar 29 2024
EXAMPLE
a(3) = 7: {}, {1R2}, {1R3}, {2R3}, {1R2, 1R3}, {1R3, 2R3}, {1R2, 1R3, 2R3}.
CROSSREFS
KEYWORD
hard,more,nice,nonn
AUTHOR
EXTENSIONS
Additional comments and more terms from Don Knuth, Dec 03 2001
STATUS
approved