A294084 Number of indecomposable intervals in the Tamari lattices.

0, 1, 2, 8, 41, 240, 1528, 10312, 72647, 528992, 3954488, 30201504, 234798627, 1853076528, 14814453896, 119763949936, 977709717091, 8050816106176, 66803956281592, 558146870481760, 4692269111973668, 39669049950811328, 337082395954643168, 2877697636252004168, 24672447821197834553

Offset

0,3

Comments

This is also the number of interval-posets with connected Hasse diagram.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1031

F. Chapoton, Sur le nombre d'intervalles dans les treillis de Tamari, arXiv:math/0602368 [math.CO], 2006.

F. Chapoton, Sur le nombre d'intervalles dans les treillis de Tamari, Séminaire Lotharingien de combinatoire, vol. 55 (2006).

Alois Panholzer, Parking function varieties for combinatorial tree models, arXiv:2007.14676 [math.CO], 2020.

Formula

The generating series can be obtained by inverting the generating series of A000260.

Example

Among the 3 interval-posets of size 2 :
1 --> 2 ; 1 <-- 2 ; 1  2,
only the third (which is an antichain) is not a connected poset.

Maple

h:= proc(n) h(n):= 2*(4*n+1)!/((n+1)!*(3*n+2)!) end:
a:= proc(n) a(n):= `if`(n=0, 0, h(n)-add(a(n-i)*h(i), i=1..n-1)) end:
seq(a(n), n=0..25);  # Alois P. Heinz, Feb 28 2019

Mathematica

terms = 25;
G[_] = 0; Do[G[x_] = 1 + x G[x]^4 + O[x]^terms, terms];
F[x_] = 1 - 1/((2 - G[x]) G[x]^2);
CoefficientList[F[x], x] (* Jean-François Alcover, Feb 14 2019 *)

Prog

(Sage)
F = PowerSeriesRing(ZZ, 't')([1] + [(2 * binomial(4 * n + 1, n - 1)) // (n * (n + 1)) for n in range(1, 20)])
1 - F.inverse()
(Julia)
using Nemo
s(n) = div(Nemo.binom(4*n + 2, n + 1), (2*n + 1) * (3*n + 2))
R, z = PowerSeriesRing(ZZ, 25, "z")
F = sum(s(n)z^n for n in 0:25)
G = 1 - inv(F)
println([coeff(G, n) for n in 0:24]) # Peter Luschny, Feb 26 2018

Crossrefs

Cf. A000260.

Sequence in context: A020083 A333093 A217362 * A177340 A067119 A093935

Adjacent sequences: A294081 A294082 A294083 * A294085 A294086 A294087

Keyword

nonn

Author

F. Chapoton, Feb 26 2018

Status

approved