A347420 Number of partitions of [n] where the first k elements are marked (0 <= k <= n) and at least k blocks contain their own index.

1, 2, 5, 14, 45, 164, 667, 2986, 14551, 76498, 430747, 2582448, 16403029, 109918746, 774289169, 5715471606, 44087879137, 354521950932, 2965359744447, 25749723493074, 231719153184019, 2157494726318234, 20753996174222511, 205985762120971168, 2106795754056142537

Offset: 0

Author

Alois P. Heinz, Jan 05 2022

Keywords

• nonn

Examples

			a(3) = 14 = 5 + 5 + 3 + 1: 123, 12|3, 13|2, 1|23, 1|2|3, 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'.
		

Links

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

Crossrefs

Antidiagonal sums of A108087.

Cf. A000110, A005490, A059841, A259691, A350589, A361380.

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(i, n-i), i=0..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[i, n - i], {i, 0, n}];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jan 11 2022, after Alois P. Heinz *)

Formula

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

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

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

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

a(n) = A000110(n) + A350589(n).

a(n) mod 2 = A059841(n).