login
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.
(Formerly M3467)
4

%I M3467 #35 Apr 24 2022 06:31:43

%S 1,4,13,44,163,666,2985,14550,76497,430746,2582447,16403028,109918745,

%T 774289168,5715471605,44087879136,354521950931,2965359744446,

%U 25749723493073,231719153184018,2157494726318233,20753996174222510,205985762120971167,2106795754056142536

%N 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 Old name was: From expansion of falling factorials.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H 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 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 From _Alois P. Heinz_, Jan 05 2022: (Start)

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

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

%F a(n) = A347420(n) - 1.

%F a(n) mod 2 = n mod 2 = A000035(n). (End)

%e 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 b:= proc(n, m) option remember;

%p `if`(n=0, 1, b(n-1, m+1)+m*b(n-1, m))

%p end:

%p a:= n-> add(b(n-k, k), k=0..n-1):

%p seq(a(n), n=1..24); # _Alois P. Heinz_, Jan 05 2022

%t b[n_, m_] := b[n, m] = If[n == 0, 1, b[n - 1, m + 1] + m*b[n - 1, m]];

%t a[n_] := Sum[b[n - k, k], {k, 0, n - 1}];

%t Table[a[n], {n, 1, 24}] (* _Jean-François Alcover_, Apr 24 2022, after _Alois P. Heinz_ *)

%Y Cf. A000035, A000110, A108087, A259691, A347420.

%K nonn

%O 1,2

%A _N. J. A. Sloane_, _Simon Plouffe_

%E More terms from _Sean A. Irvine_, Jul 01 2016

%E New name from _Alois P. Heinz_, Jan 07 2022