A211694 Number of partitions of [n] that contain no isolated singletons.

1, 0, 1, 1, 2, 3, 6, 11, 23, 47, 103, 226, 518, 1200, 2867, 6946, 17234, 43393, 111419, 290242, 768901, 2065172, 5630083, 15549403, 43527487, 123343911, 353864422, 1026935904, 3014535166, 8945274505, 26829206798, 81293234754, 248805520401, 768882019073, 2398686176048, 7552071250781

Offset: 0

Author

R. H. Hardin, Apr 19 2012

Keywords

• nonn

Comments

Number of nonnegative integer arrays of length n with new values introduced in order 0 upwards and every value appearing only in runs of at least 2.

Column 2 of A211700.

Examples

			All solutions for n = 7:
  0    0    0    0    0    0    0    0    0    0    0
  0    0    0    0    0    0    0    0    0    0    0
  0    0    1    0    1    0    0    0    1    1    1
  1    1    1    1    1    0    0    0    1    1    1
  1    1    2    1    1    0    1    0    0    1    1
  2    1    2    0    2    0    1    1    0    1    0
  2    1    2    0    2    0    1    1    0    1    0
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1132
• A. O. Munagi, Set partitions with isolated singletons, Am. Math. Monthly 125 (2018), 447-452.

Crossrefs

Cf. A160823, A211700.

Cf. A198648, A198655, A303587, A303588, A363181.

Programs

Maple

f:=proc(n) local j;
add(combinat:-bell(j-1)*binomial(n-j-1, j-1), j=0..floor(n/2));
end;
[seq(f(n), n=0..100)]; # N. J. A. Sloane, May 19 2018

Mathematica

a[n_] := If[n == 0, 1, Sum[BellB[j-1]*Binomial[n-j-1, j-1], {j, 1, Floor[n/2]}]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jun 17 2024, after Maple code *)

Formula

G.f.: 1+x^2/W(0), where W(k) = 1 - x - x^2/(1 - x^2*(k+1)/W(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 10 2014

Extensions

Edited by Andrey Zabolotskiy, Feb 07 2025