A261041 Number of partitions of subsets of {1,...,n}, where consecutive integers are required to be in different parts.

1, 2, 4, 10, 29, 97, 366, 1534, 7050, 35167, 188835, 1084180, 6618472, 42756208, 291120551, 2081922515, 15590248868, 121920095674, 993343650912, 8414029179365, 73953763887277, 673316834487162, 6340176007793060, 61657373569634586, 618445940056365121

Offset

0,2

Comments

From Gus Wiseman, Nov 25 2019: (Start)

Conjecture: Also the number of set partitions of {1, ..., n + 1} where, if x and x + 2 belong to the same block, then so does x + 1. For example, the a(0) = 1 through a(3) = 10 set partitions are:

{{1}} {{1,2}} {{1,2,3}} {{1,2,3,4}}

{{1},{2}} {{1},{2,3}} {{1},{2,3,4}}

{{1,2},{3}} {{1,2},{3,4}}

{{1},{2},{3}} {{1,2,3},{4}}

{{1,4},{2,3}}

{{1},{2},{3,4}}

{{1},{2,3},{4}}

{{1,2},{3},{4}}

{{1,4},{2},{3}}

{{1},{2},{3},{4}}

(End)

Links

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

Notamathematician et al., Generating function for A261041, MathOverflow, 2024.

Formula

From Max Alekseyev, Sep 08 2024: (Start)

a(n) = Sum_{k=0..n} A000110(k) * Sum_{j=0..[(n-k)/2]} binomial(k+j-1,j).

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

Example

For n=3 the a(3) = 10 partitions are {}, 1, 2, 3, 1|2, 13, 1|3, 2|3, 13|2, 1|2|3.
From Gus Wiseman, Nov 25 2019: (Start)
The a(0) = 1 through a(3) = 10 set partitions:
  {}  {}     {}         {}
      {{1}}  {{1}}      {{1}}
             {{2}}      {{2}}
             {{1},{2}}  {{3}}
                        {{1,3}}
                        {{1},{2}}
                        {{1},{3}}
                        {{2},{3}}
                        {{1,3},{2}}
                        {{1},{2},{3}}
(End)

Maple

g:= proc(n, l, t) option remember; `if`(n=0, 1, add(`if`(l>0
      and j=l, 0, g(n-1, j, `if`(j=t, t+1, t))), j=0..t))
    end:
a:= n-> g(n, 0, 1):
seq(a(n), n=0..30);

Mathematica

g[n_, l_, t_] := g[n, l, t] = If[n==0, 1, Sum[If[l>0 && j==l, 0, g[n-1, j, If[j==t, t+1, t]]], {j, 0, t}]]; a[n_] := g[n, 0, 1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 04 2017, translated from Maple *)
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
Table[Length[Select[Join@@sps/@Subsets[Range[n]], !MemberQ[#, {___, x_, y_, ___}/; x+1==y]&]], {n, 0, 6}] (* Gus Wiseman, Nov 25 2019 *)

Prog

(PARI) a261041(n) = sum(k=0, n, sum(j=0, k, stirling(k, j, 2)) * sum(j=0, (n-k)\2, binomial(k+j-1, j))); \\ Max Alekseyev, Sep 08 2024

Crossrefs

Cf. A000110, A003242, A114901, A247100, A261134, A261489, A261492, A273461, A274174.

Partial sums of A376077.

Sequence in context: A320903 A230957 A279552 * A047051 A271077 A365903

Adjacent sequences: A261038 A261039 A261040 * A261042 A261043 A261044

Keyword

nonn

Author

Alois P. Heinz, Aug 09 2015

Status

approved