A344136 -id:A344136 - cp's OEIS frontend

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

3, 17, 84, 393, 1778, 7866, 34254, 147433, 628914, 2663934, 11219728, 47033322, 196393044, 817338580, 3391858530, 14040986985, 57998364690, 239112756630, 984126777480, 4044255577230, 16597080112860, 68027923573740

Offset: 1

F. Chapoton, May 12 2021

nonn

Conjecture: These are the number of linear intervals in the Cambrian lattices of type B_n. An interval is linear if it is isomorphic to a total order. The conjecture has been checked up to the term 34254 for n = 7.

			For B_2, among the 18 intervals in the hexagon-shaped lattice, only one is not linear.

Michael De Vlieger, Table of n, a(n) for n = 1..1658
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.

Cf. A344136 for the type A, A344191 for a similar sequence.

a := n -> 3*(2*n^3 + n - 1)*2^(2*n - 2)*binomial(n - 3/2, -1/2)/((n + 1)*n):
seq(a(n), n = 1..22);  # Peter Luschny, May 12 2021

Array[3 (2 #^3 + # - 1)*2^(2 # - 2)*Binomial[# - 3/2, -1/2]/(# (# + 1)) &, 22] (* Michael De Vlieger, Jan 17 2024 *)

def a(n):
    return binomial(2*n,n)*(2*n+1)/2+n*binomial(2*n-2,n)+(n-1)*binomial(2*n-2,n+1)

From Peter Luschny, May 12 2021: (Start)
a(n) = 3*(2*n^3 + n - 1)*2^(2*n - 2)*binomial(n - 3/2, -1/2)/((n + 1)*n).
a(n) = [x^n] (15*x - 24*x^2 + 8*x^3 - 2 + (1 - 4*x)^(3/2)*(2 - 3*x))/(2*(1 - 4*x)^(3/2)*x).
a(n) ~ 4^(n-2)*(24*n - 15)/sqrt(Pi*n). (End)
a(n) = a(n-1)*2*(2*n - 3)*(2*n^3 + n - 1)/((n + 1)*(2*n^3 - 6*n^2 + 7*n - 4)) for n > 1. - Chai Wah Wu, May 13 2021

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

Original entry on oeis.org

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

F. Chapoton, May 11 2021

nonn

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.

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

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.

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

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

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

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

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

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

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

A344321 a(n) = 2^(2n - 5)binomial(n-5/2, -1/2)(36n^4 - 78n^3 + 54n^2 - 48n + 24)/((n + 1)n*(n - 1)) for n >= 2 and otherwise 1.

Original entry on oeis.org

1, 1, 8, 49, 246, 1157, 5248, 23256, 101398, 436865, 1865136, 7906054, 33319388, 139754994, 583859968, 2430991670, 10092510630, 41794856985, 172699266480, 712220712390, 2932169392020, 12052941519030, 49475929052160, 202838118604680

Offset: 0

F. Chapoton, May 15 2021

nonn

Conjecture: These are the number of linear intervals in the Cambrian lattices of type D_n. An interval is linear if it is isomorphic to a total order. The conjecture has been checked up to the term a(8) = 101398.

The term a(3) = 49 is the same as the 49 appearing in A344136.

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. 152.
Peter Luschny, Remark regarding A344228 and A344321.

Cf. A344136 for the type A, A344228 for the type B.
Cf. also A344191, A344216 for similar sequences.
Cf. A344400 and A344401 for an alternative approach.
Cf. A007531.

a := n -> if n < 2 then 1 else 2^(2*n - 5)*binomial(n - 5/2, -1/2)*(36*n^4 - 78*n^3 + 54*n^2 - 48*n + 24)/((n + 1)*n*(n - 1)) fi;
seq(a(n), n = 0..23); # Peter Luschny, May 16 2021

def a(n):
    if n < 2: return 1
    if n == 2: return 8
    return (3*n-2)*(1/n+1/2)*binomial(2*n-2,n-1)+6*(n-2)*binomial(2*n-4,n-2)+(n-1)*(3*n-8)/2/(2*n-3)*binomial(2*n-2,n-1)+sum(2*binomial(k,n-1)*(n+1+k) for k in range(n-1,2*n-5))
print([a(n) for n in range(24)])

a(n) = (3*n-2)*(1/n+1/2)*binomial(2*n-2,n-1) + 6*(n-2)*binomial(2*n-4,n-2) + (n-1)*(3*n-8)/(2*(2*n-3))*binomial(2*n-2,n-1) + 2 Sum_{k=1..2n-6} binomial(k,n-1)*(n+1+k) for n >= 3.

a(n) = A344401(n) / A007531(n+3) for n >= 2. - Peter Luschny, May 17 2021

Better name from Peter Luschny, May 16 2021

A344216 a(n) = n!((n+1)/2 + 2Sum_{k=2..n-1}(n-k)/(k+1)).

Original entry on oeis.org

1, 3, 16, 104, 768, 6336, 57888, 581472, 6379200, 75977280, 977045760, 13499930880, 199537067520, 3142504512000, 52546707763200, 929908914278400, 17366044153651200, 341336836618444800, 7044417438363648000

Offset: 1

F. Chapoton, May 13 2021

nonn

Conjecture: a(n) is the number of linear intervals in the weak order on the symmetric group S_n. An interval is linear if it is isomorphic to a total order. The conjecture has been checked up to a(7) = 57888.

			For S_3, among the 17 intervals in the hexagon-shaped lattice, only the full lattice is not linear.

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

Cf. A344136, A344191, A344228 for similar sequences.
Cf. A007767 for all intervals in the weak order on S_n.
Cf. A001008, A002805.

a := n -> (1/2)*n!*(4*(n + 1)*harmonic(n) - 9*n + 3):
# Or:
egf := (3 - 8*x - 4*ln(1 - x))/(2*(x - 1)^2):
ser := series(egf, x, 24): a := n -> n!*coeff(ser, x, n):
seq(a(n), n=1..19); # Peter Luschny, May 13 2021

Join[{1}, RecurrenceTable[{(n - 3) a[n] == (2 n^2 - 5 n - 1) a[n - 1] - (n^3 - 3 n^2 + 2 n) a[n - 2], a[2] == 3, a[3] == 16}, a, {n, 2, 19}]] (* Peter Luschny, May 13 2021 *)

a(n) = n!*((n+1)/2+2*sum(k=2, n-1, (n-k)/(k+1))); \\ Michel Marcus, May 13 2021

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

From Peter Luschny, May 13 2021: (Start)
a(n) = (1/2) * n! * (4 * (n + 1) * H(n) - 9*n + 3), where H(n) are the harmonic numbers H(n) = A001008(n)/A002805(n).
a(n) = n! * [x^n] (3 - 8*x - 4*log(1 - x))/(2*(x - 1)^2).
a(n) = ((2*n^2 - 5*n - 1)*a(n-1) - (n^3 - 3*n^2 + 2*n)*a(n-2))/(n - 3) for n >= 4. (End)

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

Original entry on oeis.org

6, 34, 169, 791, 3576, 15807, 68783, 295867, 1261468, 5341128, 22487906, 94244294, 393439840, 1637091585, 6792664635, 28115240595, 116120791380, 478689505140, 1969993524510, 8095052323410, 33218808108720, 136148925337230, 557389537873974, 2279607910207326

Offset: 2

F. Chapoton, May 27 2021

nonn

Conjecture: These are the number of linear intervals in the tilting posets of type B_n. An interval is linear if it is isomorphic to a total order. The conjecture has been checked up to the term 295867 for n = 9.

Michael De Vlieger, Table of n, a(n) for n = 2..1658
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. 152.

For the tilting posets of type A, see A344136.
For the Cambrian lattices of types A, B and D, see A344136, A344228, A344321.
For similar sequences, see A344191, A344216.

Array[(3 # - 9/2 - 1/# + 6/(# + 1))*Binomial[2 # - 2, # - 1] &, 24, 2] (* Michael De Vlieger, Jan 17 2024, after Sage *)

def a(n):
    return (3*n-9/2-1/n+6/(n+1))*binomial(2*n-2,n-1)

A344728 a(n) = (9n/4 - 51/8 - 5/(16n-24) + 1/n + 6/(n+1))binomial(2n-2,n-1).

Original entry on oeis.org

12, 79, 419, 2036, 9435, 42449, 187187, 813592, 3497988, 14912910, 63151022, 265958200, 1114981465, 4656455685, 19383036675, 80456688240, 333146169840, 1376479675890, 5676426414810, 23369047049400, 96060414949590

Offset: 3

F. Chapoton, May 27 2021

Conjecture: a(n) is the number of linear intervals in the tilting posets of type D_n. An interval is linear if it is isomorphic to a total order. The conjecture has been checked up to the term 187187 for n = 9.

Michael De Vlieger, Table of n, a(n) for n = 3..1659
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. 152.

For the tilting posets of types A and B, see A344136, A344717.
For the Cambrian lattices of types A, B and D, see A344136, A344228, A344321.
For similar sequences, see A344191, A344216.

Array[(9/4 # - 51/8 - 5/8/(2 # - 3) + 1/# + 6/(# + 1))*Binomial[2 # - 2, # - 1] &, 21, 3] (* Michael De Vlieger, Jan 17 2024 *)

a(n) = (9*n/4-51/8-5/(16*n-24)+1/n+6/(n+1))*binomial(2*n-2,n-1) \\ Felix Fröhlich, May 27 2021

def a(n):
    return (9/4*n-51/8-5/8/(2*n-3)+1/n+6/(n+1))*binomial(2*n-2,n-1)

A384133 Triangle read by rows: T(n,k) is the number of linear intervals of height k in the Tamari lattice Tam_n (0 <= k < n).

Original entry on oeis.org

1, 2, 1, 5, 5, 2, 14, 21, 12, 2, 42, 84, 56, 14, 2, 132, 330, 240, 72, 16, 2, 429, 1287, 990, 330, 90, 18, 2, 1430, 5005, 4004, 1430, 440, 110, 20, 2, 4862, 19448, 16016, 6006, 2002, 572, 132, 22, 2, 16796, 75582, 63648, 24752, 8736, 2730, 728, 156, 24, 2

Offset: 1

Ludovic Schwob, May 20 2025

An interval is linear of height k if it is isomorphic to the total order on k+1 elements.

			Triangle begins:
   1;
   2,    1;
   5,    5,    2;
  14,   21,   12,    2;
  42,   84,   56,   14,    2;
 132,  330,  240,   72,   16,    2;
 ...

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

Cf. A000108, A000260, A344136.

T[n_,k_]:=If[k==0, Binomial[2*n,n]/(n+1), If[k==1, Binomial[2*n-1,n-2], 2*Binomial[2*n-k,n-k-1]]]; Table[T[n,k],{n,10},{k,0,n-1}]//Flatten (* Stefano Spezia, May 26 2025 *)

Row sums give A344136.

T(n,0) = C(2*n,n)/(n+1), T(n,1) = C(2*n-1,n-2) and T(n,k) = 2*C(2*n-k,n-k-1) if k>1.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Sage

Formula

A344321 a(n) = 2^(2*n - 5)*binomial(n-5/2, -1/2)*(36*n^4 - 78*n^3 + 54*n^2 - 48*n + 24)/((n + 1)*n*(n - 1)) for n >= 2 and otherwise 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Sage

Formula

Extensions

A344216 a(n) = n!*((n+1)/2 + 2*Sum_{k=2..n-1}(n-k)/(k+1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Sage

A344728 a(n) = (9*n/4 - 51/8 - 5/(16*n-24) + 1/n + 6/(n+1))*binomial(2*n-2,n-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Sage

A384133 Triangle read by rows: T(n,k) is the number of linear intervals of height k in the Tamari lattice Tam_n (0 <= k < n).

Views

Author

Keywords

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

A344321 a(n) = 2^(2n - 5)binomial(n-5/2, -1/2)(36n^4 - 78n^3 + 54n^2 - 48n + 24)/((n + 1)n*(n - 1)) for n >= 2 and otherwise 1.

A344216 a(n) = n!((n+1)/2 + 2Sum_{k=2..n-1}(n-k)/(k+1)).

A344728 a(n) = (9n/4 - 51/8 - 5/(16n-24) + 1/n + 6/(n+1))binomial(2n-2,n-1).