A261134 Number of partitions of subsets s of {1,...,n}, where all integers belonging to a run of consecutive members of s are required to be in different parts.

1, 2, 4, 9, 23, 66, 209, 722, 2697, 10825, 46429, 211799, 1023304, 5217048, 27974458, 157310519, 925326848, 5680341820, 36315837763, 241348819913, 1664484383610, 11893800649953, 87931422125632, 671699288516773, 5295185052962371, 43029828113547685

Offset

0,2

Links

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

Example

a(3) = 9: {}, 1, 2, 3, 1|2, 2|3, 13, 1|3, 1|2|3.
a(4) = 23: {}, 1, 2, 3, 4, 1|2, 1|3, 13, 1|4, 14, 2|3, 2|4, 24, 3|4, 1|2|3, 1|2|4, 1|24, 14|2, 1|3|4, 13|4, 14|3, 2|3|4, 1|2|3|4.

Maple

g:= proc(n, s, t) option remember; `if`(n=0, 1, add(
      `if`(j in s, 0, g(n-1, `if`(j=0, {}, s union {j}),
      `if`(j=t, t+1, t))), j=0..t))
    end:
a:= n-> g(n, {}, 1):
seq(a(n), n=0..20);

Mathematica

g[n_, s_List, t_] := g[n, s, t] = If[n == 0, 1, Sum[If[MemberQ[s, j], 0, g[n-1, If[j == 0, {}, s ~Union~ {j}], If[j == t, t+1, t]]], {j, 0, t}]]; a[n_] := g[n, {}, 1]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Feb 04 2017, translated from Maple *)

Crossrefs

Cf. A247100, A261041, A261489, A261492.

Sequence in context: A272301 A359032 A129698 * A117419 A124461 A026898

Adjacent sequences: A261131 A261132 A261133 * A261135 A261136 A261137

Keyword

nonn

Author

Alois P. Heinz, Aug 10 2015

Status

approved