login
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.
5

%I #14 Feb 04 2017 10:36:11

%S 1,2,4,9,23,66,209,722,2697,10825,46429,211799,1023304,5217048,

%T 27974458,157310519,925326848,5680341820,36315837763,241348819913,

%U 1664484383610,11893800649953,87931422125632,671699288516773,5295185052962371,43029828113547685

%N 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.

%H Alois P. Heinz, <a href="/A261134/b261134.txt">Table of n, a(n) for n = 0..32</a>

%e a(3) = 9: {}, 1, 2, 3, 1|2, 2|3, 13, 1|3, 1|2|3.

%e 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.

%p g:= proc(n, s, t) option remember; `if`(n=0, 1, add(

%p `if`(j in s, 0, g(n-1, `if`(j=0, {}, s union {j}),

%p `if`(j=t, t+1, t))), j=0..t))

%p end:

%p a:= n-> g(n, {}, 1):

%p seq(a(n), n=0..20);

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

%Y Cf. A247100, A261041, A261489, A261492.

%K nonn

%O 0,2

%A _Alois P. Heinz_, Aug 10 2015