A006455 Number of partial orders on {1,2,...,n} that are contained in the usual linear order (i.e., xRy => x

1, 1, 2, 7, 40, 357, 4824, 96428, 2800472, 116473461, 6855780268, 565505147444, 64824245807684

Offset: 0

Author

N. J. A. Sloane

Keywords

• hard
• more
• nice
• nonn

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

Examples

			a(3) = 7: {}, {1R2}, {1R3}, {2R3}, {1R2, 1R3}, {1R3, 2R3}, {1R2, 1R3, 2R3}.
		

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.
• S. R. Finch, Transitive relations, topologies and partial orders
• S. 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.
• D. E. Knuth, POSETS, program for n = 10, 11, 12.
• J.-G. Luque, L. Mignot and F. Nicart, Some Combinatorial Operators in Language Theory, arXiv preprint arXiv:1205.3371 [cs.FL], 2012. - _N. J. A. Sloane_, Oct 22 2012
• Index entries for sequences related to posets

Crossrefs

Cf. A000112, A001035, A323502.

Formula

E.g.f.: exp(S(x)-1) where S(x)is the e.g.f. for A323502. - Ludovic Schwob, Mar 29 2024

Extensions

Additional comments and more terms from Don Knuth, Dec 03 2001