login
Number of nonempty subsets of {1, ..., n} containing no three cyclically successive elements.
5

%I #12 Jan 06 2020 16:52:38

%S 0,1,3,6,10,20,38,70,130,240,442,814,1498,2756,5070,9326,17154,31552,

%T 58034,106742,196330,361108,664182,1221622,2246914,4132720,7601258,

%U 13980894,25714874,47297028,86992798,160004702,294294530,541292032,995591266,1831177830

%N Number of nonempty subsets of {1, ..., n} containing no three cyclically successive elements.

%C Cyclically successive means 1 is a successor of n.

%C Set partitions using these subsets are counted by A323949.

%F For n >= 3 we have a(n) = A001644(n) - 1.

%F From _Chai Wah Wu_, Jan 06 2020: (Start)

%F a(n) = 2*a(n-1) - a(n-4) for n > 6.

%F G.f.: x*(x^5 + x^4 - 2*x^3 + x + 1)/(x^4 - 2*x + 1). (End)

%e The a(1) = 1 through a(5) = 20 stable subsets:

%e {1} {1} {1} {1} {1}

%e {2} {2} {2} {2}

%e {1,2} {3} {3} {3}

%e {1,2} {4} {4}

%e {1,3} {1,2} {5}

%e {2,3} {1,3} {1,2}

%e {1,4} {1,3}

%e {2,3} {1,4}

%e {2,4} {1,5}

%e {3,4} {2,3}

%e {2,4}

%e {2,5}

%e {3,4}

%e {3,5}

%e {4,5}

%e {1,2,4}

%e {1,3,4}

%e {1,3,5}

%e {2,3,5}

%e {2,4,5}

%t stabsubs[g_]:=Select[Rest[Subsets[Union@@g]],Select[g,Function[ed,UnsameQ@@ed&&Complement[ed,#]=={}]]=={}&];

%t Table[Length[stabsubs[Partition[Range[n],3,1,1]]],{n,15}]

%Y Cf. A000126, A000296, A001610, A001644, A169985, A306357, A323949, A323952, A323955.

%K nonn

%O 0,3

%A _Gus Wiseman_, Feb 10 2019