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