A369614 -id:A369614

Search: a369614 -id:a369614

Displaying 1-2 of 2 results found.

page 1

A144685

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

+10
3

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

(list; graph; refs; listen; history; text; internal format)

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.

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.

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

A144686

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

+10
1

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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]

REFERENCES

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.

LINKS

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

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.

CROSSREFS

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

KEYWORD

nonn,hard,more

AUTHOR

N. J. A. Sloane, Feb 07 2009

EXTENSIONS

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

STATUS

approved

page 1

Search completed in 0.007 seconds