login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006455 Number of partial orders on {1,2,...,n} that are contained in the usual linear order (i.e., xRy => x<y).
(Formerly M1805)
2
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 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

Table of n, a(n) for n=0..12.

S. P. Avann, The lattice of natural partial orders, Aequationes Mathematicae 8 (1972), 95-102.

Graham Brightwell, Hans Jürgen Prömel and Angelika Steger, The average number of linear extensions of a partial order, Journal of Combinatorial Theory A73 (1996), 193-206.

S. R. Finch, Transitive relations, topologies and partial orders

Joël Gay, Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.

L. H. Harper, The Range of a Steiner Operation, arXiv preprint arXiv:1608.07747 [math.CO], 2016.

N. Hindman & N. J. A. Sloane, Correspondence, 1981-1991

Adam King, A. Laubmeier, K. Orans, A. Godbole, Universal and Overlap Cycles for Posets, Words, and Juggling Patterns, arXiv preprint arXiv:1405.5938 [math.CO], 2014.

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

J.-G. Luque, L. Mignot and F. Nicart, Some Combinatorial Operators in Language Theory, arXiv preprint arXiv:1205.3371 [cs.FL], 2012. - N. J. A. Sloane, Oct 22 2012

Index entries for sequences related to posets

CROSSREFS

Cf. A000112, A001035.

Sequence in context: A137731 A008608 A028441 * A130715 A317723 A215207

Adjacent sequences:  A006452 A006453 A006454 * A006456 A006457 A006458

KEYWORD

hard,more,nice,nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

Additional comments and more terms from Don Knuth, Dec 03 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 16:53 EST 2019. Contains 319235 sequences. (Running on oeis4.)