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,6

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

Links

Indranil Ghosh, Table of n, a(n) for n = 0..163

Peter Luschny, Set partitions

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

Example

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

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

Prog

(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)]
(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

Crossrefs

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

Sequence in context: A360311 A285905 A344218 * A339892 A244617 A003583

Adjacent sequences: A247488 A247489 A247490 * A247492 A247493 A247494

Keyword

nonn

Author

Peter Luschny, Sep 25 2014

Status

approved