

A006455


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


9



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

D. E. Knuth, POSETS, program for n = 10, 11, 12.


FORMULA



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



