cp's OEIS Frontend

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

%I A005490 M3467 #35 Apr 24 2022 06:31:43
%S A005490 1,4,13,44,163,666,2985,14550,76497,430746,2582447,16403028,109918745,
%T A005490 774289168,5715471605,44087879136,354521950931,2965359744446,
%U A005490 25749723493073,231719153184018,2157494726318233,20753996174222510,205985762120971167,2106795754056142536
%N A005490 Number of partitions of [n] where the first k elements are marked (0 <= k <= n-1) and at least k blocks contain their own index.
%C A005490 Old name was: From expansion of falling factorials.
%D A005490 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005490 E. G. Whitehead, Jr., <a href="http://dx.doi.org/10.1016/0097-3165(78)90061-4">Stirling number identities from chromatic polynomials</a>, J. Combin. Theory, A 24 (1978), 314-317.
%F A005490 a(n) = Sum_{i=1..n} b(n, i) where b(n, 1) = n and b(n+1, i+1) = (n-i) * b(n, i) + b(n+1, i) [From Whitehead]. - _Sean A. Irvine_, Jul 01 2016
%F A005490 From _Alois P. Heinz_, Jan 05 2022: (Start)
%F A005490 a(n) = Sum_{k=0..n-1} A108087(n-k,k).
%F A005490 a(n) = A000110(n) + Sum_{k=1..n-1} A259691(n,k)/k.
%F A005490 a(n) = A347420(n) - 1.
%F A005490 a(n) mod 2 = n mod 2 = A000035(n). (End)
%e A005490 a(3) = 13 = 5 + 5 + 3: 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.
%p A005490 b:= proc(n, m) option remember;
%p A005490      `if`(n=0, 1, b(n-1, m+1)+m*b(n-1, m))
%p A005490     end:
%p A005490 a:= n-> add(b(n-k, k), k=0..n-1):
%p A005490 seq(a(n), n=1..24);  # _Alois P. Heinz_, Jan 05 2022
%t A005490 b[n_, m_] := b[n, m] = If[n == 0, 1, b[n - 1, m + 1] + m*b[n - 1, m]];
%t A005490 a[n_] := Sum[b[n - k, k], {k, 0, n - 1}];
%t A005490 Table[a[n], {n, 1, 24}] (* _Jean-François Alcover_, Apr 24 2022, after _Alois P. Heinz_ *)
%Y A005490 Cf. A000035, A000110, A108087, A259691, A347420.
%K A005490 nonn
%O A005490 1,2
%A A005490 _N. J. A. Sloane_, _Simon Plouffe_
%E A005490 More terms from _Sean A. Irvine_, Jul 01 2016
%E A005490 New name from _Alois P. Heinz_, Jan 07 2022