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

0, 1, 3, 6, 10, 20, 38, 70, 130, 240, 442, 814, 1498, 2756, 5070, 9326, 17154, 31552, 58034, 106742, 196330, 361108, 664182, 1221622, 2246914, 4132720, 7601258, 13980894, 25714874, 47297028, 86992798, 160004702, 294294530, 541292032, 995591266, 1831177830

Offset: 0

Author

Gus Wiseman, Feb 10 2019

Keywords

• nonn

Comments

Cyclically successive means 1 is a successor of n.

Set partitions using these subsets are counted by A323949.

Examples

			The a(1) = 1 through a(5) = 20 stable subsets:
  {1}  {1}    {1}    {1}    {1}
       {2}    {2}    {2}    {2}
       {1,2}  {3}    {3}    {3}
              {1,2}  {4}    {4}
              {1,3}  {1,2}  {5}
              {2,3}  {1,3}  {1,2}
                     {1,4}  {1,3}
                     {2,3}  {1,4}
                     {2,4}  {1,5}
                     {3,4}  {2,3}
                            {2,4}
                            {2,5}
                            {3,4}
                            {3,5}
                            {4,5}
                            {1,2,4}
                            {1,3,4}
                            {1,3,5}
                            {2,3,5}
                            {2,4,5}
		

Crossrefs

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

Programs

Mathematica

stabsubs[g_]:=Select[Rest[Subsets[Union@@g]],Select[g,Function[ed,UnsameQ@@ed&&Complement[ed,#]=={}]]=={}&];
Table[Length[stabsubs[Partition[Range[n],3,1,1]]],{n,15}]

Formula

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

From Chai Wah Wu, Jan 06 2020: (Start)

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

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