|
|
A323950
|
|
Number of ways to split an n-cycle into connected subgraphs, none having exactly two vertices.
|
|
9
|
|
|
1, 1, 1, 2, 6, 12, 23, 44, 82, 149, 267, 475, 841, 1484, 2613, 4595, 8074, 14180, 24896, 43702, 76705, 134622, 236260, 414623, 727629, 1276917, 2240851, 3932438, 6900967, 12110373, 21252244, 37295110, 65448378, 114853920, 201554603, 353703696, 620706742
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (x^7-3*x^6+3*x^5-2*x^4+x^3-3*x^2+3*x-1)/((x^3-x^2+2*x-1)*(x-1)^2). - Alois P. Heinz, Feb 10 2019
|
|
EXAMPLE
|
The a(1) = 1 through a(5) = 12 partitions:
{{1}} {{1}{2}} {{123}} {{1234}} {{12345}}
{{1}{2}{3}} {{1}{234}} {{1}{2345}}
{{123}{4}} {{1234}{5}}
{{124}{3}} {{1235}{4}}
{{134}{2}} {{1245}{3}}
{{1}{2}{3}{4}} {{1345}{2}}
{{1}{2}{345}}
{{1}{234}{5}}
{{123}{4}{5}}
{{125}{3}{4}}
{{145}{2}{3}}
{{1}{2}{3}{4}{5}}
|
|
MATHEMATICA
|
cyceds[n_, k_]:=Union[Sort/@Join@@Table[1+Mod[Range[i, j]-1, n], {i, n}, {j, Prepend[Range[i+k, n+i-1], i]}]];
spsu[_, {}]:={{}}; spsu[foo_, set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@spsu[Select[foo, Complement[#, Complement[set, s]]=={}&], Complement[set, s]]]/@Cases[foo, {i, ___}];
Table[Length[spsu[cyceds[n, 2], Range[n]]], {n, 15}]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|