login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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: 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 31 19:11 EDT 2020. Contains 334748 sequences. (Running on oeis4.)