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

Links

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

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.

Example

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

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

Crossrefs

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

Sequence in context: A150103 A150104 A145868 * A058122 A150105 A150106

Adjacent sequences: A376074 A376075 A376076 * A376078 A376079 A376080

Keyword

nonn

Author

Alois P. Heinz, Sep 08 2024

Status

approved