A335212 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.

0, 1, 4, 8, 8, 9, 110, 572, 2496, 5762, 3254, 5020, 117912, 307819, 420394, 677350, 9611700, 58689330, 32290388, 430183260, 180484980, 5983159650, 44850171444, 120220997328, 235364198128, 135740049556, 2107819739960, 5252440129232, 37484769529504, 125244830989069

Offset

2,3

Comments

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).

Links

Swee Hong Chan, Table of n, a(n) for n = 2..1000

S. H. Chan, I. Pak, and G. Panova, Sorting probability of Catalan posets, preprint arXiv:2005.13686 [math.CO] (2020), 10 pp.

Prog

(Sage)
def a(n):
    lsp=[];
    minloc=[];
    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:
                    minloc.append(x-1);
                    lsp.append((a_1)*(binomial(2*n, n)/(n+1)));
                else:
                    minloc.append(x);
                    lsp.append((a_2)*(binomial(2*n, n))/(n+1));
                break;
    return min(lsp)

Crossrefs

Cf. A000108.

Sequence in context: A304651 A187768 A344984 * A141284 A272812 A273207

Adjacent sequences: A335209 A335210 A335211 * A335213 A335214 A335215

Keyword

nonn

Author

Swee Hong Chan, May 26 2020

Status

approved