The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 (list; graph; refs; listen; history; text; internal format)
 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 Table of n, a(n) for n=0..12. 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 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 Cf. A000112, A001035, A323502. Sequence in context: A363004 A008608 A028441 * A130715 A317723 A340005 Adjacent sequences: A006452 A006453 A006454 * A006456 A006457 A006458 KEYWORD hard,more,nice,nonn AUTHOR N. J. A. Sloane EXTENSIONS Additional comments and more terms from Don Knuth, Dec 03 2001 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 11 01:05 EDT 2024. Contains 375059 sequences. (Running on oeis4.)