A369614 -id:A369614 - cp's OEIS frontend

A144685 Size of acyclic domain of size n based on the alternating scheme.

1, 2, 4, 9, 20, 45, 100, 222, 488, 1069, 2324, 5034, 10840, 23266, 49704, 105884, 224720, 475773, 1004212, 2115186, 4443896, 9319702, 19503224, 40750884, 84990640, 177017810, 368108680, 764571492, 1585851248, 3285861924, 6800042704, 14059397560, 29037419424

Offset: 1

N. J. A. Sloane Feb 07 2009

A. Galambos and V. Reiner, Acyclic sets of linear orders via the Bruhat order, Social Choice and Welfare, 30 (No. 2, 2008), 245-264.
Bernard Monjardet, Acyclic domains of linear orders: a survey, in "The Mathematics of Preference, Choice and Order: Essays in Honor of Peter Fishburn", edited by Steven Brams, William V. Gehrlein and Fred S. Roberts, Springer, 2009, pp. 139-160. Available as a preprint halshs-00198635.
Bei Zhou and Søren Riis, An efficient heuristic search algorithm for discovering large Condorcet domains, 4OR (2025). See Sect. 4.2.

Cf. A369614.

def a(n):
    return (n+3)*2^(n-3) - (binomial(n-2,n/2-1)*(n-3/2) if is_even(n)
                       else binomial(n-1,(n-1)/2)*(n-1)/2)
print([a(n) for n in (1..20)]) # Andrey Zabolotskiy, Oct 20 2024

Monjardet quotes the following formula from Galambos and Reiner: if n mod 2 = 0 then a(n) = 2^(n-3)*(n+3)-binomial(n-2,n/2-1)*(n-3/2), otherwise a(n) = 2^(n-3)*(n+3)-binomial(n-1,(n-1)/2)*(n-1)/2. [Corrected by Jan Volec (janvolec(AT)jikos.cz), Oct 26 2009]

a(n) ~ n*2^(n-3). - Clayton Thomas, Aug 19 2019

More terms added, using the formula, by Andrey Zabolotskiy, Oct 20 2024

A144686 Maximal size of a connected acyclic domain of permutations of n elements with diameter n*(n-1)/2.

Original entry on oeis.org

1, 2, 4, 9, 20, 45, 100

Offset: 1

N. J. A. Sloane, Feb 07 2009

a(n) is at most 2.487^n and at least 2.076^n for large enough n (see Felsner & Valtr). Originally conjectured to equal A144685, but in fact a(n) is asymptotically larger and exceeds A144685 at least for n >= 34 (see Karpov & Slinko). - Clayton Thomas, Aug 19 2019 [Updated by Andrey Zabolotskiy, Dec 31 2023]

B. Monjardet, Acyclic domains of linear orders: a survey, in "The Mathematics of Preference, Choice and Order: Essays in Honor of Peter Fishburn", edited by Steven Brams, William V. Gehrlein and Fred S. Roberts, Springer, 2009, pp. 139-160.

James Abello, The Weak Bruhat Order of S_Sigma, Consistent Sets, and Catalan Numbers, SIAM Journal on Discrete Mathematics, 4 (1991), 1-16; alternative link.
James Abello, The Majority Rule and Combinatorial Geometry (via the Symmetric Group), Annales Du Lamsade, 3 (2004), 1-13.
Vladimir I. Danilov, Alexander V. Karzanov, and Gleb Koshevoy, Condorcet domains of tiling type, Discrete Applied Mathematics 160.7-8 (2012), pages 933-940.
Stefan Felsner and Pavel Valtr, Coding and counting arrangements of pseudolines, Discrete & Computational Geometry 46.3 (2011), pages 405-416.
Alexander Karpov and Arkadii Slinko, Constructing large peak-pit Condorcet domains, Theory and Decision, 94 (2023), 97-120.
B. Monjardet, Acyclic domains of linear orders: a survey, in "The Mathematics of Preference, Choice and Order: Essays in Honor of Peter Fishburn", edited by Steven Brams, William V. Gehrlein and Fred S. Roberts, Springer, 2009, pp. 139-160 ⟨halshs-00198635⟩.

Cf. A090245 (has same initial terms but probably is unrelated), A144685, A144687, A369614.

a(1)-a(2) added and name edited by Andrey Zabolotskiy, Dec 31 2023

cp's OEIS Frontend

A144685 Size of acyclic domain of size n based on the alternating scheme.

Views

Author

Keywords

Links

Crossrefs

Programs

SageMath

Formula

Extensions