login
Number of partial orders on {1,2,...,n} that are contained in the usual linear order (i.e., xRy => x<y).
(Formerly M1805)
9

%I M1805 #68 Apr 24 2024 13:24:57

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

%T 64824245807684

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

%C Also known as naturally labeled posets. - _David Bevan_, Nov 16 2023

%C Also the number of n X n upper triangular Boolean matrices B with all diagonal entries 1 such that B = B^2.

%C 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 N. B. Hindman, personal communication.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H 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 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 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 S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Transitive relations, topologies and partial orders</a>

%H 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 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 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 N. Hindman and N. J. A. Sloane, <a href="/A006455/a006455.pdf">Correspondence, 1981-1991</a>

%H 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 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 D. E. Knuth, <a href="https://www-cs-faculty.stanford.edu/~knuth/programs.html">POSETS</a>, program for n = 10, 11, 12.

%H 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 <a href="/index/Pos#posets">Index entries for sequences related to posets</a>

%F E.g.f.: exp(S(x)-1) where S(x)is the e.g.f. for A323502. - _Ludovic Schwob_, Mar 29 2024

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

%Y Cf. A000112, A001035, A323502.

%K hard,more,nice,nonn

%O 0,3

%A _N. J. A. Sloane_

%E Additional comments and more terms from _Don Knuth_, Dec 03 2001