login
a(n) = C(n) * d(n), where C(n) is the Catalan number and d(n) is the sorting probability of the Catalan poset P_n.
2

%I #21 Aug 01 2020 01:14:47

%S 0,1,4,8,8,9,110,572,2496,5762,3254,5020,117912,307819,420394,677350,

%T 9611700,58689330,32290388,430183260,180484980,5983159650,44850171444,

%U 120220997328,235364198128,135740049556,2107819739960,5252440129232,37484769529504,125244830989069

%N a(n) = C(n) * d(n), where C(n) is the Catalan number and d(n) is the sorting probability of the Catalan poset P_n.

%C C(n) = A000108(n) is the Catalan number binomial(2n, n)/(n+1). P_n is the Catalan poset, which is the poset product of a 2-chain and an n-chain. The number of linear extensions of P_n is the Catalan number C(n). d(n) is Min_{x,y in P_n} |p_n(x<y) - p_n(x>y)|, where p_n(x<y) is the probability that x is less than y in the uniform random linear extension of P_n. It has been proved that a(n)/C(n) = O(n^{-5/4}), see the references: Chan, Pak, and Panova. In particular, we have a(n) < C(n).

%H Swee Hong Chan, <a href="/A335212/b335212.txt">Table of n, a(n) for n = 2..1000</a>

%H S. H. Chan, I. Pak, and G. Panova, <a href="https://arxiv.org/abs/2005.13686">Sorting probability of Catalan posets</a>, preprint arXiv:2005.13686 [math.CO] (2020), 10 pp.

%o (Sage)

%o def a(n):

%o lsp=[];

%o minloc=[];

%o for y in range (1,n+1):

%o sum=0;

%o for z in range (0,y+1):

%o K=(binomial(2*y-z-1,y-1)*binomial(2*n-2*y+z,n-y+z)*(z)*(z+1)*(n+1))/(binomial(2*n,n)*(y)*(n-y+z+1));

%o sum=sum+K;

%o if 2*sum >= 1:

%o h=sum-K;

%o a_1=1-2*h;

%o a_2=2*sum-1;

%o if a_1< a_2:

%o minloc.append(x-1);

%o lsp.append((a_1)*(binomial(2*n,n)/(n+1)));

%o else:

%o minloc.append(x);

%o lsp.append((a_2)*(binomial(2*n,n))/(n+1));

%o break;

%o return min(lsp)

%Y Cf. A000108.

%K nonn

%O 2,3

%A _Swee Hong Chan_, May 26 2020