OFFSET
2,2
COMMENTS
C(n) = A000108(n).
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).
p_n(x,y) for x,y in P_n is the probability that x is less than y in the uniform random linear extension of P_n.
b(n) is the probability p_n(x<y) that is closest to 1/2 for all x,y in P_n.
LINKS
Swee Hong Chan, Table of n, a(n) for n = 2..1000
Swee Hong Chan, Igor Pak and Greta Panova, Sorting probability of Catalan posets, Advances in Applied Mathematics, 129 (2021), 102221; arXiv:2005.13686 [math.CO], 2020.
PROG
(Sage)
def a(n):
lsp=[];
chalf=[];
for y in range (1, n+1):
sum=0;
for z in range (0, y+1):
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));
sum=sum+K;
if 2*sum >= 1:
h=sum-K;
a_1=1-2*h;
a_2=2*sum-1;
if a_1< a_2:
chalf.append(h);
lsp.append(a_1);
else:
chalf.append(sum);
lsp.append(a_2);
break;
yindex=lsp.index(min(lsp));
return (chalf[yindex])*(binomial(2*n, n))/(n+1)
CROSSREFS
KEYWORD
nonn
AUTHOR
Swee Hong Chan, May 26 2020
STATUS
approved