A350589 Sum over all partitions of [n] of the number of blocks containing their own index.

0, 1, 3, 9, 30, 112, 464, 2109, 10411, 55351, 314772, 1903878, 12189432, 82274309, 583389847, 4332513061, 33607736990, 271657081128, 2283282938288, 19916981288017, 179994994948647, 1682624910161483, 16247280435775188, 161833756265886822, 1660836884761337248

Offset: 0

Author

Alois P. Heinz, Jan 07 2022

Keywords

• nonn

Comments

Also the number of partitions of [n] where the first k elements are marked (1 <= k <= n) and at least k blocks contain their own index: a(3) = 9 = 5 + 3 + 1: 1'23, 1'2|3, 1'3|2, 1'|23, 1'|2|3, 1'3|2', 1'|2'3, 1'|2'|3, 1'|2'|3'.

Examples

			a(3) = 9 = 1 + 1 + 2 + 2 + 3: 123, 12|3, 13|2, 1|23, 1|2|3.
		

Links

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

Crossrefs

Cf. A000110, A005490, A088911, A108087, A259691, A347420, A350648.

Programs

Maple

b:= proc(n, m) option remember;
     `if`(n=0, 1, b(n-1, m+1)+m*b(n-1, m))
    end:
a:= n-> add(b(n-i, i), i=1..n):
seq(a(n), n=0..25);

Mathematica

b[n_, m_] := b[n, m] = If[n == 0, 1, b[n - 1, m + 1] + m*b[n - 1, m]];
a[n_] := Sum[b[n - i, i], {i, 1, n}];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jan 11 2022, after Alois P. Heinz *)

Formula

a(n) = Sum_{k=1..n} A108087(n-k,k).

a(n) = Sum_{k=1..n} k * A259691(n-1,k).

a(n) = Sum_{k=1..n} A259691(n,k)/k.

a(n) = A347420(n) - A000110(n).

a(n) = 1 + A005490(n) - A000110(n).

a(n) mod 2 = A088911(n+5).