A376077 Number of partitions of subsets of [n] containing n > 0, where consecutive integers are required to be in different parts.

1, 1, 2, 6, 19, 68, 269, 1168, 5516, 28117, 153668, 895345, 5534292, 36137736, 248364343, 1790801964, 13508326353, 106329846806, 871423555238, 7420685528453, 65539734707912, 599363070599885, 5666859173305898, 55317197561841526, 556788566486730535

Offset: 0

Author

Alois P. Heinz, Sep 08 2024

Keywords

• nonn

Examples

			a(3) = 6: 3, 13, 1|3, 2|3, 13|2, 1|2|3.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..576

Crossrefs

Cf. A000045, A000110, A261041 (partial sums).

Programs

Maple

b:= proc(n, m, i) option remember; `if`(n=0, 1, add(
     `if`(i=j and j>0, 0, b(n-1, max(m, j), j)), j=0..m+1))
    end:
a:= n-> b(n, 0$2)-`if`(n>0, b(n-1, 0$2), 0):
seq(a(n), n=0..30);

Mathematica

b[n_, m_, i_] := b[n, m, i] = If[n == 0, 1, Sum[If[i == j && j > 0, 0, b[n-1, Max[m, j], j]], {j, 0, m+1}]];
a[n_] := b[n, 0, 0] - If[n > 0, b[n-1, 0, 0], 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Sep 18 2024, after Alois P. Heinz *)

Formula

a(0) = 1, a(n) = A261041(n) - A261041(n-1) for n>=1.

G.f.: Sum_{j>=0} A000110(j) * (x/(1-x^2))^j.