A372649 Total sum over all partitions of [n] of the number of maximal blocks.

0, 1, 3, 7, 21, 71, 293, 1268, 6107, 31123, 170745, 998966, 6212627, 40854360, 283290348, 2059884614, 15667307457, 124266461587, 1025342179759, 8784261413616, 78003593175261, 716854898767936, 6808817431686858, 66754426111124686, 674754718441688851

Offset: 0

Author

Alois P. Heinz, May 08 2024

Keywords

• nonn

Examples

			a(3) = 7 = 3 + 1 + 1 + 1 + 1: 1|2|3, 1|23, 12|3, 13|2, 123.
a(4) = 21 = 1+1+1+2+1+1+2+1+2+1+1+1+1+1+4: 1234, 123|4, 124|3, 12|34, 12|3|4, 134|2, 13|24, 13|2|4, 14|23, 1|234, 1|23|4, 14|2|3, 1|24|3, 1|2|34, 1|2|3|4.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..576
• Wikipedia, Partition of a set

Crossrefs

Cf. A000110, A097148, A372650, A372722.

Programs

Maple

b:= proc(n, m, t) option remember; `if`(n=0, t,
      add(binomial(n-1, j-1)*b(n-j, max(j, m),
     `if`(j>m, 1, `if`(j=m, t+1, t))), j=1..n))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..24);

Mathematica

b[n_, m_, t_] := b[n, m, t] = If[n == 0, t,
   Sum[Binomial[n - 1, j - 1]*b[n - j, Max[j, m],
   If[j > m, 1, If[j == m, t + 1, t]]], {j, 1, n}]];
a[n_] := b[n, 0, 0];
Table[a[n], {n, 0, 24}] (* Jean-François Alcover, May 10 2024, after Alois P. Heinz *)

Formula

a(n) = Sum_{k=0..n} k * A372722(n,k).