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

Author

N. J. A. Sloane Feb 07 2009

Keywords

• nonn
• easy

Links

• 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.

Crossrefs

Cf. A369614.

Programs

SageMath

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

Formula

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

Extensions

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