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

%I #57 Oct 04 2023 12:11:07

%S 1,1,2,48,1680384,14807804035657359360,

%T 141377911697227887117195970316200795630205476957716480

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

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

%C Number of linear extensions of the Boolean lattice 2^n. - _Mitch Harris_, Dec 27 2005

%C 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

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

%H J. Daniel Christensen, <a href="/A046873/b046873.txt">Table of n, a(n) for n = 0..7</a>

%H Andrew Beveridge, Ian Calaway, and Kristin Heysse, <a href="https://arxiv.org/abs/1912.12319">de Finetti Lattices and Magog Triangles</a>, arXiv:1912.12319 [math.CO], 2019.

%H Graham R. Brightwell, and Prasad Tetali, <a href="http://dx.doi.org/10.1023/B:ORDE.0000034596.50352.f7">The number of linear extensions of the Boolean lattice</a>, Order, v. 20 (2003), no. 4, 333-345. (Gives asymptotics.)

%H Andries E. Brouwer and J. Daniel Christensen, <a href="https://arxiv.org/abs/1702.03018">Counterexamples to conjectures about Subset Takeaway and counting linear extensions of a Boolean lattice</a>, arXiv:1702.03018 [math.CO], 2017. (Gives n=7 result.)

%H Sha, Ji Chang and Kleitman, D. J., <a href="http://dx.doi.org/10.1016/0012-365X(87)90016-1">The number of linear extensions of subset ordering</a>, Discrete Math. 63 (1987), no. 2-3, 271-278.

%H Jian-Zhang Wu and Gleb Beliakov, <a href="https://arxiv.org/abs/2309.15399">Generating fuzzy measures from additive measures</a>, arXiv:2309.15399 [math.GM], 2023. See p. 8.

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

%Y Cf. A001206, A114717, A000372, A118077.

%K nonn,nice

%O 0,3

%A _David A. Madore_

%E 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.

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