A344191 a(n) = Catalan(n) * (n^2 + 2) / (n + 2).

1, 1, 3, 11, 42, 162, 627, 2431, 9438, 36686, 142766, 556206, 2169268, 8469060, 33096195, 129454695, 506793270, 1985612310, 7785510810, 30548406570, 119944382220, 471241577820, 1852521913710, 7286586193926, 28675561428972, 112905199767052, 444752335104252

Offset: 0

Author

F. Chapoton, May 11 2021

Keywords

• nonn

Comments

Conjecture: These are the number of linear intervals in Pallo's comb posets. An interval is linear if it is isomorphic to a total order. The conjecture has been checked up to the term 36686 for n = 9.

Examples

			All 3 intervals in the poset of cardinality 2 are linear. All 11 intervals in the poset of cardinality 5 are linear.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..1664
• Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Dyck Paths with catastrophes modulo the positions of a given pattern, Australasian J. Comb. (2022) Vol. 84, No. 2, 398-418.
• 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. 150.
• J. M. Pallo, Right-arm rotation distance between binary trees, Inform. Process. Lett., 87(4):173-177, 2003.

Crossrefs

Cf. A000108, A002694, A127632, A344136, A121686.

Programs

Maple

a := n -> `if`(n = 0, 1, a(n-1)*(2*(2*n-1)*(n^2+2))/((n+2)*(n^2-2*n+3))):
seq(a(n), n = 0..19); # Peter Luschny, May 11 2021

Mathematica

a[n_] := CatalanNumber[n] (n^2 + 2) / (n + 2);
Table[a[n], { n, 0, 23}] (* Peter Luschny, May 11 2021 *)

PARI

a(n) = (binomial(2*n,n)/(n+1))*((n^2 + 2)/(n + 2)); \\ Michel Marcus, May 11 2021

Sage

def a(n):
    return catalan_number(n)+sum(2**(n-k)/factorial(k-2)*(n-k+4)/(n+2)*prod(n+i for i in range(2, k)) for k in range(2, n+1))

Sage

def a(n): return catalan_number(n) + binomial(2*n, n-2)
print([a(n) for n in range(24)]) # Peter Luschny, May 11 2021

Formula

a(n) = Catalan(n) + (1/(n + 2))*Sum_{k=2..n}((2^(n - k)*(n - k + 4)/(k - 2)!)* Product_{i=2..k-1}(n + i)).

From Peter Luschny, May 11 2021: (Start)

a(n) = [x^n] ((2*x + sqrt(1 - 4*x) - 1)*(3*x - 1))/(2*sqrt(1 - 4*x)*x^2).

a(n) = n! * [x^n] exp(2*x)*(BesselI(0, 2*x) - BesselI(1, 2*x) + BesselI(2, 2*x)).

a(n) = a(n-1)*(2*(2*n - 1)*(n^2 + 2))/((n + 2)*(n^2 - 2*n + 3)) for n >= 1.

a(n) = Catalan(n) + binomial(2*n, n-2) = A000108(n) + A002694(n).

a(n) ~ (2^(2*n - 3)*(8*n - 25)) / (sqrt(Pi)*n^(3/2)). (End)

a(n) = A121686(n) / 2. - Hugo Pfoertner, May 11 2021