A247491 Number of crossing partitions of {1,2,...,n} that contain no singletons.

0, 0, 0, 0, 1, 5, 26, 126, 624, 3193, 17119, 96668, 576104, 3621982, 23980620, 166805068, 1215842905, 9263445775, 73599067250, 608471202527, 5224252803246, 46499854580107, 428369819029085, 4078345518655015, 40073659206668916, 405885206895408576, 4232705116291188276

Offset: 0

Author

Peter Luschny, Sep 25 2014

Keywords

• nonn

Comments

A partition p of the set {1,2,...,n} whose elements are arranged in their natural order, is crossing if there exist four numbers 1 <= i < k < j < l <= n such that i and j are in the same block, k and l are in the same block, but i,j and k,l belong to two different blocks.

Also the number of crossing partitions of {1,2,...,n} that contain no cyclical adjacencies. e.g., a(5) = 5, [13|24|5, 13|25|4, 14|25|3, 14|2|35, 1|24|35]. - Yuchun Ji, Nov 13 2020

Examples

			The crossing partitions of {1,2,3,4,5} that contain no singletons are: [13|245], [14|235], [24,135], [25|134], [35|124].
		

Links

• Indranil Ghosh, Table of n, a(n) for n = 0..163
• Peter Luschny, Set partitions

Crossrefs

Cf. A016098, A005043, A000110, A000296, A247494.

Programs

Maple

A247491 := n -> (-1)^n-add((-1)^(n-k)*combinat:-bell(k), k = 0..n-1) - (-1)^n*hypergeom([-n, 1/2], [2], 4); seq(round(evalf(A247491(n), 100)), n=0..27);

Mathematica

Table[Sum[(-1)^(n-k)*Binomial[n,k]*(BellB[k]-CatalanNumber[k]), {k,0,n}], {n, 0, 26}] (* Indranil Ghosh, Mar 04 2017 *)

PARI

B(n) = sum(k=0, n, stirling(n,k,2));
a(n) = sum(k=0, n, (-1)^(n-k)*binomial(n,k)*(B(k)-binomial(2*k,k)/(k+1))); \\ Indranil Ghosh, Mar 04 2017

Sage

A247491 = lambda n: sum((-1)^(n-k)*binomial(n,k)*(bell_number(k) - catalan_number(k)) for k in (0..n))
[A247491(n) for n in range(27)]

Formula

a(n) = Sum_{k=0..n} (-1)^(n-k)*C(n,k)*(Bell(k)-Catalan(k)).

a(n) = A000296(n) - A005043(n).

a(n) = A016098(n) - A247494(n); i.e., remove the partitions with cyclical adjacencies from the crossing partitions. - Yuchun Ji, Nov 17 2020