A288786 Number of blocks of size >= four in all set partitions of n.

1, 6, 37, 225, 1395, 8944, 59585, 413117, 2981310, 22380814, 174600298, 1413841252, 11868587577, 103155618776, 927141821215, 8606806236367, 82430269073469, 813600584094320, 8267450613029789, 86406853732930699, 927993270700444588, 10232636504064477996

Offset

4,2

Links

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

Wikipedia, Partition of a set

Formula

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

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

E.g.f.: (exp(x) - Sum_{k=0..3} x^k/k!) * exp(exp(x) - 1). - Ilya Gutkovskiy, Jun 25 2022

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, 4):
seq(a(n), n=4..30);
# second Maple program:
b:= proc(n) option remember; `if`(n=0, [1, 0], add((p-> p+[0,
     `if`(j>3, p[1], 0)])(b(n-j)*binomial(n-1, j-1)), j=1..n))
    end:
a:= n-> b(n)[2]:
seq(a(n), n=4..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, 4];
Table[a[n], {n, 4, 30}] (* Jean-François Alcover, May 28 2018, from Maple *)

Crossrefs

Column k=4 of A283424.

Cf. A000110.

Sequence in context: A244618 A033116 A033124 * A180032 A022035 A255119

Adjacent sequences: A288783 A288784 A288785 * A288787 A288788 A288789

Keyword

nonn

Author

Alois P. Heinz, Jun 15 2017

Status

approved