cp's OEIS Frontend

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

%I A350589 #31 Jan 11 2022 19:18:39
%S A350589 0,1,3,9,30,112,464,2109,10411,55351,314772,1903878,12189432,82274309,
%T A350589 583389847,4332513061,33607736990,271657081128,2283282938288,
%U A350589 19916981288017,179994994948647,1682624910161483,16247280435775188,161833756265886822,1660836884761337248
%N A350589 Sum over all partitions of [n] of the number of blocks containing their own index.
%C A350589 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'.
%H A350589 Alois P. Heinz, <a href="/A350589/b350589.txt">Table of n, a(n) for n = 0..575</a>
%H A350589 Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>
%F A350589 a(n) = Sum_{k=1..n} A108087(n-k,k).
%F A350589 a(n) = Sum_{k=1..n} k * A259691(n-1,k).
%F A350589 a(n) = Sum_{k=1..n} A259691(n,k)/k.
%F A350589 a(n) = A347420(n) - A000110(n).
%F A350589 a(n) = 1 + A005490(n) - A000110(n).
%F A350589 a(n) mod 2 = A088911(n+5).
%e A350589 a(3) = 9 = 1 + 1 + 2 + 2 + 3: 123, 12|3, 13|2, 1|23, 1|2|3.
%p A350589 b:= proc(n, m) option remember;
%p A350589      `if`(n=0, 1, b(n-1, m+1)+m*b(n-1, m))
%p A350589     end:
%p A350589 a:= n-> add(b(n-i, i), i=1..n):
%p A350589 seq(a(n), n=0..25);
%t A350589 b[n_, m_] := b[n, m] = If[n == 0, 1, b[n - 1, m + 1] + m*b[n - 1, m]];
%t A350589 a[n_] := Sum[b[n - i, i], {i, 1, n}];
%t A350589 Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Jan 11 2022, after _Alois P. Heinz_ *)
%Y A350589 Cf. A000110, A005490, A088911, A108087, A259691, A347420, A350648.
%K A350589 nonn
%O A350589 0,3
%A A350589 _Alois P. Heinz_, Jan 07 2022