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.

1, 4, 13, 44, 163, 666, 2985, 14550, 76497, 430746, 2582447, 16403028, 109918745, 774289168, 5715471605, 44087879136, 354521950931, 2965359744446, 25749723493073, 231719153184018, 2157494726318233, 20753996174222510, 205985762120971167, 2106795754056142536

Offset: 1

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• nonn

Comments

Old name was: From expansion of falling factorials.

Examples

			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.
		

References

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

Links

• E. G. Whitehead, Jr., Stirling number identities from chromatic polynomials, J. Combin. Theory, A 24 (1978), 314-317.

Crossrefs

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

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(n-k, k), k=0..n-1):
seq(a(n), n=1..24);  # Alois P. Heinz, Jan 05 2022

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 - k, k], {k, 0, n - 1}];
Table[a[n], {n, 1, 24}] (* Jean-François Alcover, Apr 24 2022, after Alois P. Heinz *)

Formula

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

From Alois P. Heinz, Jan 05 2022: (Start)

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

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

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

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

Extensions

More terms from Sean A. Irvine, Jul 01 2016

New name from Alois P. Heinz, Jan 07 2022