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

Author

Alois P. Heinz, Aug 10 2015

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Cf. A247100, A261041, A261489, A261492.

Programs

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