cp's OEIS Frontend

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

%I A006455 M1805 #68 Apr 24 2024 13:24:57
%S A006455 1,1,2,7,40,357,4824,96428,2800472,116473461,6855780268,565505147444,
%T A006455 64824245807684
%N A006455 Number of partial orders on {1,2,...,n} that are contained in the usual linear order (i.e., xRy => x<y).
%C A006455 Also known as naturally labeled posets. - _David Bevan_, Nov 16 2023
%C A006455 Also the number of n X n upper triangular Boolean matrices B with all diagonal entries 1 such that B = B^2.
%C A006455 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
%D A006455 N. B. Hindman, personal communication.
%D A006455 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006455 S. P. Avann, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002026236">The lattice of natural partial orders</a>, Aequationes Mathematicae 8 (1972), 95-102.
%H A006455 David Bevan, Gi-Sang Cheon and Sergey Kitaev, <a href="https://arxiv.org/abs/2311.08023">On naturally labelled posets and permutations avoiding 12-34</a>, arXiv:2311.08023 [math.CO], 2023.
%H A006455 Graham Brightwell, Hans Jürgen Prömel and Angelika Steger, <a href="https://doi.org/10.1016/S0097-3165(96)80001-X">The average number of linear extensions of a partial order</a>, Journal of Combinatorial Theory A73 (1996), 193-206.
%H A006455 S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Transitive relations, topologies and partial orders</a>
%H A006455 S. R. Finch, <a href="/A000798/a000798_12.pdf">Transitive relations, topologies and partial orders</a>, June 5, 2003. [Cached copy, with permission of the author]
%H A006455 Joël Gay and Vincent Pilaud, <a href="https://arxiv.org/abs/1804.06572">The weak order on Weyl posets</a>, arXiv:1804.06572 [math.CO], 2018.
%H A006455 L. H. Harper, <a href="https://arxiv.org/abs/1608.07747">The Range of a Steiner Operation</a>, arXiv preprint arXiv:1608.07747 [math.CO], 2016.
%H A006455 N. Hindman and N. J. A. Sloane, <a href="/A006455/a006455.pdf">Correspondence, 1981-1991</a>
%H A006455 Florent Hivert and Nicolas M. Thiéry, <a href="https://doi.org/10.1007/s11083-022-09607-5">Controlling the C3 Super Class Linearization Algorithm for Large Hierarchies of Classes</a>, Order (2022).
%H A006455 Adam King, A. Laubmeier, K. Orans, and A. Godbole, <a href="http://arxiv.org/abs/1405.5938">Universal and Overlap Cycles for Posets, Words, and Juggling Patterns</a>, arXiv preprint arXiv:1405.5938 [math.CO], 2014.
%H A006455 D. E. Knuth, <a href="https://www-cs-faculty.stanford.edu/~knuth/programs.html">POSETS</a>, program for n = 10, 11, 12.
%H A006455 J.-G. Luque, L. Mignot and F. Nicart, <a href="http://arxiv.org/abs/1205.3371">Some Combinatorial Operators in Language Theory</a>, arXiv preprint arXiv:1205.3371 [cs.FL], 2012. - _N. J. A. Sloane_, Oct 22 2012
%H A006455 <a href="/index/Pos#posets">Index entries for sequences related to posets</a>
%F A006455 E.g.f.: exp(S(x)-1) where S(x)is the e.g.f. for A323502. - _Ludovic Schwob_, Mar 29 2024
%e A006455 a(3) = 7: {}, {1R2}, {1R3}, {2R3}, {1R2, 1R3}, {1R3, 2R3}, {1R2, 1R3, 2R3}.
%Y A006455 Cf. A000112, A001035, A323502.
%K A006455 hard,more,nice,nonn
%O A006455 0,3
%A A006455 _N. J. A. Sloane_
%E A006455 Additional comments and more terms from _Don Knuth_, Dec 03 2001