login
Number of comparative probability orderings on all subsets of n elements that can arise by assigning a probability distribution to the individual elements.
3

%I #40 Mar 24 2023 18:08:08

%S 1,1,1,2,14,516,124187,214580603

%N Number of comparative probability orderings on all subsets of n elements that can arise by assigning a probability distribution to the individual elements.

%C Also 1/(2^n*n!) * number of regions of hyperplane arrangements with normals (0,1,-1)^n.

%C From _David W. Wilson_, Aug 15 2008: (Start)

%C Also, number of possible orderings of the set of divisors of a product of n distinct primes.

%C Let p1 < p2 < ... < p_n be primes (say p1 = p, p2 = q, p3 = r, ...) Consider the set M of divisors of p1*p2*...*p_n. How many ways can M be ordered?

%C For n = 0, we have m = { 1 }, with 1 ordering.

%C For n = 1, we have M = { 1, p }. There is 1 possible ordering, 1 < p.

%C For n = 2, we have M = { 1, p, q, pq }. Remembering p < q, there is again 1 possible ordering, 1 < p < q < pq.

%C For n = 3, we have M = { 1, p, q, r, pq, pr, qr, pqr }. There are 2 possible orderings here:

%C 1 < p < q < r < pq < pr < qr < pqr,

%C 1 < p < q < pq < r < pr < qr < pqr. (End)

%H Antoine Deza, George Manoussakis, and Shmuel Onn, <a href="https://dx.doi.org/10.1007/s00454-017-9873-z">Primitive Zonotopes</a>, Discrete & Computational Geometry, 2017, p. 1-13. (See p. 5.)

%H T. Fine and J. Gill, <a href="https://doi.org/10.1214/aop/1176996036">The enumeration of comparative probability relations</a>, Ann. Prob. 4 (1976) 667-673.

%H Shane Kepley, Konstantin Mischaikow, and Lun Zhang, <a href="https://arxiv.org/abs/2006.02622">Computing linear extensions for Boolean lattices with algebraic constraints</a>, arXiv:2006.02622 [math.CO], 2020.

%H D. Maclagan, <a href="https://arxiv.org/abs/math/9809134">Boolean Term Orders and the Root System B_n</a>, arXiv:math/9809134 [math.CO], 1998-1999. (Data in table on p.13)

%H D. Maclagan, <a href="https://doi.org/10.1023/A:1006207716298">Boolean Term Orders and the Root System B_n</a>, Order 15 (1999), 279-295. (Data in first table on p. 293.)

%F a(n) <= A005806(n) with equality iff n <= 4. - _M. F. Hasler_, Mar 17 2023

%o (PARI) apply( {A009997(n)=if(n>4, [516, 124187, 214580603][n-4], (n-=!!n)^n\/2)}, [0..7]) \\ _M. F. Hasler_, Mar 17 2023

%Y Cf. A005806, A361388.

%K nonn,hard,more,nice

%O 0,4

%A _N. J. A. Sloane_

%E a(6) and a(7) from Diane Maclagan and _Michael Kleber_

%E Edited by _N. J. A. Sloane_, Nov 26 2008

%E a(0) = 1 inserted by _M. F. Hasler_, Mar 17 2023