login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A046873 Number of total orders extending inclusion on P({1,...,n}). 2
1, 1, 2, 48, 1680384, 14807804035657359360, 141377911697227887117195970316200795630205476957716480 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Trivial upper bound: a(n) <= (2^n)!.

Number of linear extensions of the boolean lattice 2^n. - Mitch Harris, Dec 27 2005

The number of vertices in the representation of all linear extensions in a distributive lattice are the Dedekind numbers (A000372) and the number of edges constitutes A118077. - Oliver Wienand, Apr 11 2006

A lower bound is A051459(n) = Product_{k=0..n} binomial(n,k)! <= a(n). - Geoffrey Critzer, May 20 2018

LINKS

J. Daniel Christensen, Table of n, a(n) for n = 0..7

Graham R. Brightwell, and Prasad Tetali, The number of linear extensions of the Boolean lattice, Order, v. 20 (2003), no. 4, 333-345. (Gives asymptotics.)

Andries E. Brouwer and J. Daniel Christensen, Counterexamples to conjectures about Subset Takeaway and counting linear extensions of a Boolean lattice, arXiv:1702.03018 [math.CO], 2017. (Gives n=7 result.)

Sha, Ji Chang and Kleitman, D. J., The number of linear extensions of subset ordering, Discrete Math. 63 (1987), no. 2-3, 271-278.

EXAMPLE

a(2)=2 because either {}<{0}<{1}<{0,1} or {}<{1}<{0}<{0,1}.

CROSSREFS

Cf. A001206, A114717, A000372, A118077.

Sequence in context: A057527 A166475 A152688 * A261125 A164334 A100540

Adjacent sequences:  A046870 A046871 A046872 * A046874 A046875 A046876

KEYWORD

nonn,nice

AUTHOR

David A. Madore

EXTENSIONS

a(5) from Oliver Wienand, Apr 11 2006, using Python and an inference method for computing the set of linear extensions of arbitrary posets. Using the same method on a compute server generated a(6) on Dec 05 2010.

a(7) from J. Daniel Christensen, Feb 13 2017, based on Brouwer-Christensen work cited above, using C.

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 27 15:14 EST 2020. Contains 331295 sequences. (Running on oeis4.)