|
Search: id:A006455
|
|
|
| A006455 |
|
Number of partial orders on {1,2,...,n} that are contained in the usual linear order (i.e. xRy => x<y).
(Formerly M1805)
|
|
+0
2
|
|
| 1, 1, 2, 7, 40, 357, 4824, 96428, 2800472, 116473461, 6855780268, 565505147444, 64824245807684
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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
|
S. P. Avann, The lattice of natural partial orders. Aequationes Mathematicae 8 (1972), 95-102.
Graham Brightwell, Hans J\"urgen Pr\"omel, and Angelika Steger, The average number of linear extensions of a partial order. Journal of Combinatorial Theory A73 (1996), 193-206.
N. B. Hindman, personal communication.
|
|
LINKS
|
D. E. Knuth, POSETS, program for n = 10, 11, 12.
Index entries for sequences related to posets
S. R. Finch, Transitive relations, topologies and partial orders
|
|
CROSSREFS
|
Cf. A000112, A001035
Sequence in context: A137731 A008608 A028441 this_sequence A130715 A106871 A107376
Adjacent sequences: A006452 A006453 A006454 this_sequence A006456 A006457 A006458
|
|
KEYWORD
|
hard,nice,nonn
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
Additional comments and more terms from D. E. Knuth, Dec 03 2001
|
|
|
Search completed in 0.002 seconds
|
