login
Number of certain noncrossing set partitions.
2

%I #44 Sep 11 2024 08:57:44

%S 1,4,12,37,118,387,1298,4433,15366,53924,191216,684114,2466428,

%T 8951945,32683230,119949945,442281030,1637618400,6086481720,

%U 22699003830,84918443220,318593346630,1198421583684,4518886787802,17077448924828,64671604514552,245380598678208,932708665735364,3551238550341944,13542393822575541

%N Number of certain noncrossing set partitions.

%C 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.

%C 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

%H Andrew Howroyd, <a href="/A280891/b280891.txt">Table of n, a(n) for n = 1..500</a>

%H H. Gao and R. Schiffler, <a href="https://doi.org/10.3842/SIGMA.2020.058">On the Number of τ-Tilting Modules over Nakayama Algebras</a>, SIGMA 16 (2020), 058.

%H H. Mühle, <a href="https://arxiv.org/abs/1701.02109">Two Posets of Noncrossing Partitions Coming From Undesired Parking Spaces</a>, arXiv:1701.02109 [math.CO], 2017.

%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016.

%H Qi Wang, <a href="https://arxiv.org/abs/1910.01937">Tau-tilting finite simply connected algebras</a>, arXiv:1910.01937 [math.RT], 2019.

%F a(n) = C(n + 1) - C(n - 1) where C(n) is the n-th Catalan number (A000108). - _Joel B. Lewis_, Apr 19 2017

%F G.f.: (1 + x)*(1 - 3*x - (1 - x)*sqrt(1 - 4*x))/(2*x^2). - _Ilya Gutkovskiy_, Apr 20 2017

%e 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.

%t 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 *)

%o (PARI) C(n)=binomial(2*n,n)/(n+1);

%o vector(66,n,C(n + 1) - C(n - 1)) \\ _Joerg Arndt_, Apr 19 2017

%Y Cf. A000108, A071718.

%K nonn

%O 1,2

%A _Henri Mühle_, Jan 10 2017