A344136 Number of linear intervals in the Tamari lattices.

1, 3, 12, 49, 198, 792, 3146, 12441, 49062, 193154, 759696, 2986458, 11737820, 46134090, 181350630, 713046345, 2804421510, 11033453970, 43424181240, 170965500030, 673354218420, 2652994345560, 10456457024052, 41227321016394

Offset

1,2

Comments

The description is conjectural. An interval is linear if it is isomorphic to a total order. The conjecture has been checked up to the term 49062 for n=9.

Apparently odd exactly when n is a power of 2.

Links

Michael De Vlieger, Table of n, a(n) for n = 1..1663

Clément Chenevière, Linear Intervals in the Tamari, Dyck and alt-Tamari Lattices, arXiv:2209.00418 [math.CO], 2022.

Clément Chenevière, Enumerative study of intervals in lattices of Tamari type, Ph. D. thesis, Univ. Strasbourg (France), Ruhr-Univ. Bochum (Germany), HAL tel-04255439 [math.CO], 2024. See p. 151.

Formula

a(n) = (3/2)*binomial(2*n, n)*(n^2 - n + 2)/(n + 2)/(n + 1).

a(n) = binomial(2*n, n)/(n + 1) + binomial(2*n-1, n-2) + 2*binomial(2*n-1, n-3).

a(n) ~ (3/2) * 4^n * (1 - 33/(8*n)) / sqrt(n*Pi). - Peter Luschny, May 10 2021

a(n) = a(n-1)*2*(2*n - 1)*(n^2 - n + 2)/((n + 2)*(n^2 - 3*n + 4)) for n > 1. - Chai Wah Wu, May 13 2021

Example

All 3 intervals in the lattice of cardinality 2 are linear. Among 13 intervals in the pentagon, only one is not linear.

Mathematica

Array[(3/2) Binomial[2 #, #]*(#^2 - # + 2)/(# + 2)/(# + 1) &, 24] (* Michael De Vlieger, Sep 09 2022 *)

Prog

(Sage)
[3/2*binomial(2*n, n)*(n**2-n+2)/(n+2)/(n+1) for n in range(1, 30)]

Crossrefs

Cf. A000260.

Sequence in context: A371436 A178872 A323263 * A248347 A037758 A037646

Adjacent sequences: A344133 A344134 A344135 * A344137 A344138 A344139

Keyword

nonn

Author

F. Chapoton, May 10 2021

Status

approved