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,3

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'.

Links

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

Wikipedia, Partition of a set

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).

Example

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

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 *)

Crossrefs

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

Sequence in context: A339835 A134168 A124427 * A308554 A055730 A120018

Adjacent sequences: A350586 A350587 A350588 * A350590 A350591 A350592

Keyword

nonn

Author

Alois P. Heinz, Jan 07 2022

Status

approved