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

0, 0, 0, 0, 0, 5, 45, 322, 2086, 13092, 82060, 523116, 3429481, 23279555, 164244262, 1206458632, 9228941572, 73471779239, 608000100209, 5222503739340, 46493341311706, 428345495309624, 4078254436854598, 40073317276815681, 405883920183989049, 4232700263388189325

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 number of crossing partitions of {1,2,...,n} that contain cyclical adjacencies. a(5) = 5, [124|35, 134|25, 135|24, 13|245, 14|235]. - Yuchun Ji, Nov 13 2020

Links

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

Peter Luschny, Set partitions

Formula

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

a(n) = A016098(n) - A247491(n).

a(n) = A000296(n+1) - A106640(n-1), for n>0 (i.e., remove the non-crossing partitions from the cyclical adjacencies partitions). - Yuchun Ji, Nov 11 2020

Example

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

Maple

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

Mathematica

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

Prog

(Sage)
A247494 = lambda n: sum((-1)^(n-k+1)*binomial(n, k)*(bell_number(k)-catalan_number(k)) for k in (0..n-1))
[A247494(n) for n in range(26)]
(PARI)
B(n) = sum(k=0, n, stirling(n, k, 2));
a(n) = sum(k=0, n-1, (-1)^(n-k+1)*binomial(n, k)*(B(k) - binomial(2*k, k)/(k+1))); \\ Indranil Ghosh, Mar 04 2017

Crossrefs

Cf. A016098, A005043, A000110, A000296, A106640, A247491.

Sequence in context: A343136 A343106 A081070 * A043025 A190540 A268219

Adjacent sequences: A247491 A247492 A247493 * A247495 A247496 A247497

Keyword

nonn

Author

Peter Luschny, Oct 02 2014

Status

approved