A046873 Number of total orders extending inclusion on P({1,...,n}).

1, 1, 2, 48, 1680384, 14807804035657359360, 141377911697227887117195970316200795630205476957716480

Offset: 0

Author

David A. Madore

Keywords

• nonn
• nice

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

Examples

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

Links

• J. Daniel Christensen, Table of n, a(n) for n = 0..7
• Andrew Beveridge, Ian Calaway, and Kristin Heysse, de Finetti Lattices and Magog Triangles, arXiv:1912.12319 [math.CO], 2019.
• 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.
• Jian-Zhang Wu and Gleb Beliakov, Generating fuzzy measures from additive measures, arXiv:2309.15399 [math.GM], 2023. See p. 8.

Crossrefs

Cf. A001206, A114717, A000372, A118077.

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.