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,3

Comments

Cyclically successive means 1 is a successor of n.

Set partitions using these subsets are counted by A323949.

Links

Table of n, a(n) for n=0..35.

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)

Example

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}

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}]

Crossrefs

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

Sequence in context: A295719 A178850 A018171 * A365694 A122628 A343386

Adjacent sequences: A306354 A306355 A306356 * A306358 A306359 A306360

Keyword

nonn

Author

Gus Wiseman, Feb 10 2019

Status

approved