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,5

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.

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.

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

Example

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

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 *)

Crossrefs

Cf. A160823, A211700.

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

Sequence in context: A198620 A198648 A198655 * A303586 A130131 A338355

Adjacent sequences: A211691 A211692 A211693 * A211695 A211696 A211697

Keyword

nonn

Author

R. H. Hardin, Apr 19 2012

Extensions

Edited by Andrey Zabolotskiy, Feb 07 2025

Status

approved