A324015 Number of nonempty subsets of {1, ..., n} containing no two cyclically successive elements.

0, 1, 2, 3, 6, 10, 17, 28, 46, 75, 122, 198, 321, 520, 842, 1363, 2206, 3570, 5777, 9348, 15126, 24475, 39602, 64078, 103681, 167760, 271442, 439203, 710646, 1149850, 1860497, 3010348, 4870846, 7881195, 12752042, 20633238, 33385281, 54018520, 87403802

Offset

0,3

Comments

Cyclically successive means 1 succeeds n.

After a(1) = 1, same as A001610 shifted once to the right. Also, a(n) = A169985(n) - 1.

Links

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

Formula

For n <= 3, a(n) = n. Otherwise, a(n) = a(n - 1) + a(n - 2) + 1.

Example

The a(6) = 17 stable subsets:
  {1}, {2}, {3}, {4}, {5}, {6},
  {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,6},
  {1,3,5}, {2,4,6}.

Mathematica

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

Crossrefs

Cf. A000045, A000126, A000296, A001610, A001644, A169985, A306357, A324014.

Sequence in context: A363070 A023614 A001610 * A238777 A344615 A245437

Adjacent sequences: A324012 A324013 A324014 * A324016 A324017 A324018

Keyword

nonn

Author

Gus Wiseman, Feb 12 2019

Status

approved