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,2

Links

Table of n, a(n) for n=1..33.

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.

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

Prog

(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

Crossrefs

Cf. A369614.

Sequence in context: A208738 A144686 A108469 * A085584 A369614 A080019

Adjacent sequences: A144682 A144683 A144684 * A144686 A144687 A144688

Keyword

nonn,easy

Author

N. J. A. Sloane, Feb 07 2009

Extensions

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

Status

approved