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

4, 9, 20, 45, 100, 222, 488, 1069, 2324, 5034, 10840, 23266, 49704, 105884, 224720, 475773, 1004212, 2115186

Offset

3,1

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=3..20.

A. Galambos and V. Reiner, Acyclic sets of linear orders via the Bruhat order, Social Choice and Welfare, 30 (No. 2, 2008), 245-264.

Formula

Montrachet gives the following formula, attributed to Galambos and Reiner: if n mod 2 = 0 and n > 2 then a(n) = 2^(n-3)*(n+3)-binomial(n-2,n/2-1)*(n-3/2), otherwise if n > 1 then 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

Crossrefs

Sequence in context: A019492 A020708 A345192 * A109110 A366726 A108870

Adjacent sequences: A144682 A144683 A144684 * A144686 A144687 A144688

Keyword

nonn,more

Author

N. J. A. Sloane Feb 07 2009

Status

approved