A280891 Number of certain noncrossing set partitions.

1, 4, 12, 37, 118, 387, 1298, 4433, 15366, 53924, 191216, 684114, 2466428, 8951945, 32683230, 119949945, 442281030, 1637618400, 6086481720, 22699003830, 84918443220, 318593346630, 1198421583684, 4518886787802, 17077448924828, 64671604514552, 245380598678208, 932708665735364, 3551238550341944, 13542393822575541

Offset

1,2

Comments

Let X_n be the set of all noncrossing set partitions of an n-element set that do not contain {n-1, n} as a block, and also do not contain the block {n} whenever 1 and n-1 are in the same block. a(n) is the number of elements of X_{n+2} in which n-2 and n-1 lie in the same block.

Equivalently, a(n) is the number of noncrossing set partitions of {1, 2, ..., n+2} such that n and n+1 belong to the same block, and if 1 also belongs to this block then n+2 does as well. This leads to the formula a(n) = C(n + 1) - C(n - 1), where C(n) is the n-th Catalan number (A000108): there are C(n + 1) noncrossing set partitions with n and n + 1 in the same block, and C(n - 1) noncrossing set partitions with {n + 2} a singleton block and 1, n, and n + 1 in the same block. - Joel B. Lewis, Apr 19 2017

Links

Andrew Howroyd, Table of n, a(n) for n = 1..500

H. Mühle, Two Posets of Noncrossing Partitions Coming From Undesired Parking Spaces, arXiv:1701.02109 [math.CO], 2017.

Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Qi Wang, Tau-tilting finite simply connected algebras, arXiv:1910.01937 [math.RT], 2019.

Formula

a(n) = C(n + 1) - C(n - 1) where C(n) is the n-th Catalan number (A000108). - Joel B. Lewis, Apr 19 2017

G.f.: (1 + x)*(1 - 3*x - (1 - x)*sqrt(1 - 4*x))/(2*x^2). - Ilya Gutkovskiy, Apr 20 2017

Example

X_4 has the following 10 elements: 1|2|3|4, 12|3|4, 1|23|4, 1|24|3, 14|2|3, 1|234, 124|3, 14|23, 134|2, 1234. The a(2)=4 elements in which 2 and 3 are in the same block are 1|23|4, 1|234, 14|23, 1234.

Mathematica

CoefficientList[Series[(1 + x) (1 - 3 x - (1 - x) Sqrt[1 - 4 x])/(2 x^2), {x, 0, 30}], x] (* Michael De Vlieger, Jan 03 2020 *)

Prog

(PARI) C(n)=binomial(2*n, n)/(n+1);
vector(66, n, C(n + 1) - C(n - 1)) \\ Joerg Arndt, Apr 19 2017

Crossrefs

Cf. A000108, A071718.

Sequence in context: A019480 A192907 A047088 * A362886 A149319 A149320

Adjacent sequences: A280888 A280889 A280890 * A280892 A280893 A280894

Keyword

nonn

Author

Henri Mühle, Jan 10 2017

Status

approved