

A280891


Number of certain noncrossing set partitions.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Let X_n be the set of all noncrossing set partitions of an nelement set that do not contain {n1, n} as a block, and also do not contain the block {n} whenever 1 and n1 are in the same block. a(n) is the number of elements of X_{n+2} in which n2 and n1 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 nth 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, Tautilting finite simply connected algebras, arXiv:1910.01937 [math.RT], 2019.


FORMULA

a(n) = C(n + 1)  C(n  1) where C(n) is the nth 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: 1234, 1234, 1234, 1243, 1423, 1234, 1243, 1423, 1342, 1234. The a(2)=4 elements in which 2 and 3 are in the same block are 1234, 1234, 1423, 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: A019481 A019480 A192907 * A149319 A149320 A149321
Adjacent sequences: A280888 A280889 A280890 * A280892 A280893 A280894


KEYWORD

nonn


AUTHOR

Henri Mühle, Jan 10 2017


STATUS

approved



