|
|
A306357
|
|
Number of nonempty subsets of {1, ..., n} containing no three cyclically successive elements.
|
|
5
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Cyclically successive means 1 is a successor of n.
Set partitions using these subsets are counted by A323949.
|
|
LINKS
|
|
|
FORMULA
|
For n >= 3 we have a(n) = A001644(n) - 1.
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|