cp's OEIS Frontend

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

%I A144685 #21 Jan 30 2025 11:38:33
%S A144685 1,2,4,9,20,45,100,222,488,1069,2324,5034,10840,23266,49704,105884,
%T A144685 224720,475773,1004212,2115186,4443896,9319702,19503224,40750884,
%U A144685 84990640,177017810,368108680,764571492,1585851248,3285861924,6800042704,14059397560,29037419424
%N A144685 Size of acyclic domain of size n based on the alternating scheme.
%H A144685 A. Galambos and V. Reiner, <a href="https://www.kellogg.northwestern.edu/research/math/seminars/200405/Galambos06205.pdf">Acyclic sets of linear orders via the Bruhat order</a>, Social Choice and Welfare, 30 (No. 2, 2008), 245-264.
%H A144685 Bernard Monjardet, <a href="https://doi.org/10.1007/978-3-540-79128-7_8">Acyclic domains of linear orders: a survey</a>, 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 <a href="https://shs.hal.science/halshs-00198635">halshs-00198635</a>.
%H A144685 Bei Zhou and Søren Riis, <a href="https://doi.org/10.1007/s10288-025-00583-1">An efficient heuristic search algorithm for discovering large Condorcet domains</a>, 4OR (2025). See Sect. 4.2.
%F A144685 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]
%F A144685 a(n) ~ n*2^(n-3). - _Clayton Thomas_, Aug 19 2019
%o A144685 (SageMath)
%o A144685 def a(n):
%o A144685     return (n+3)*2^(n-3) - (binomial(n-2,n/2-1)*(n-3/2) if is_even(n)
%o A144685                        else binomial(n-1,(n-1)/2)*(n-1)/2)
%o A144685 print([a(n) for n in (1..20)]) # _Andrey Zabolotskiy_, Oct 20 2024
%Y A144685 Cf. A369614.
%K A144685 nonn,easy
%O A144685 1,2
%A A144685 _N. J. A. Sloane_ Feb 07 2009
%E A144685 More terms added, using the formula, by _Andrey Zabolotskiy_, Oct 20 2024