A288785 Number of blocks of size >= three in all set partitions of n.

1, 5, 26, 137, 750, 4307, 25996, 164825, 1096217, 7633650, 55549664, 421599778, 3331027887, 27349472297, 232967157736, 2055635993935, 18762063976810, 176896220650029, 1720762736285790, 17249873608817569, 178010337967774511, 1889129778601708612

Offset

3,2

Links

Alois P. Heinz, Table of n, a(n) for n = 3..575

Wikipedia, Partition of a set

Formula

a(n) = Bell(n+1) - Sum_{j=0..2} binomial(n,j) * Bell(n-j).

a(n) = Sum_{j=0..n-3} binomial(n,j) * Bell(j).

a(n) = Sum_{k=1..n} k * A355144(n,k). - Alois P. Heinz, Jun 20 2022

E.g.f.: (exp(x) - 1 - x - x^2/2) * exp(exp(x) - 1). - Ilya Gutkovskiy, Jun 24 2022

Example

a(4) = 5: 1234, 123|4, 124|3, 134|2, 1|234.
a(5) = 26: 12345, 1234|5, 1235|4, 123|45, 123|4|5, 1245|3, 124|35, 124|3|5, 125|34, 12|345, 125|3|4, 1345|2, 134|25, 134|2|5, 135|24, 13|245, 135|2|4, 145|23, 14|235, 15|234, 1|2345, 1|234|5, 1|235|4, 145|2|3, 1|245|3, 1|2|345.
a(6) = 137: 123456, 12345|6, 12346|5, ..., 123|456, 124|356, 125|346, 126|345, 134|256, 135|246, 136|245, 145|236, 146|235, 156|234, ..., 1|256|3|4, 1|2|356|4, 1|2|3|456.

Maple

b:= proc(n) option remember; `if`(n=0, 1, add(
      b(n-j)*binomial(n-1, j-1), j=1..n))
    end:
g:= proc(n, k) option remember; `if`(n<k, 0,
      g(n, k+1) +binomial(n, k)*b(n-k))
    end:
a:= n-> g(n, 3):
seq(a(n), n=3..30);
# second Maple program:
b:= proc(n) option remember; `if`(n=0, [1, 0], add((p-> p+[0,
     `if`(j>2, p[1], 0)])(b(n-j)*binomial(n-1, j-1)), j=1..n))
    end:
a:= n-> b(n)[2]:
seq(a(n), n=3..30);  # Alois P. Heinz, Jan 06 2022

Mathematica

b[n_] := b[n] = If[n == 0, 1, Sum[b[n-j]*Binomial[n-1, j-1], {j, 1, n}]];
g[n_, k_] := g[n, k] = If[n < k, 0, g[n, k+1] + Binomial[n, k]*b[n - k]];
a[n_] := g[n, 3];
Table[a[n], {n, 3, 30}] (* Jean-François Alcover, May 28 2018, from Maple *)

Crossrefs

Column k=3 of A283424.

Cf. A000110, A355144.

Sequence in context: A355361 A083331 A076025 * A161731 A049607 A035029

Adjacent sequences: A288782 A288783 A288784 * A288786 A288787 A288788

Keyword

nonn

Author

Alois P. Heinz, Jun 15 2017

Status

approved