A323951 Number of ways to split an n-cycle into connected subgraphs, all having at least three vertices.

1, 0, 0, 1, 1, 1, 4, 8, 13, 22, 36, 56, 86, 131, 197, 294, 437, 647, 955, 1407, 2070, 3042, 4467, 6556, 9618, 14106, 20684, 30325, 44455, 65164, 95515, 139997, 205189, 300733, 440760, 645980, 946745, 1387538, 2033552, 2980332, 4367906, 6401495, 9381865, 13749810

Offset

0,7

Links

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

Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-2,1).

Formula

G.f.: (x^7-2*x^6+x^3-3*x^2+3*x-1)/((x^3+x-1)*(x-1)^2). - Alois P. Heinz, Feb 10 2019

Example

The a(3) = 1 through a(7) = 8 partitions:
  {{123}}  {{1234}}  {{12345}}  {{123456}}    {{1234567}}
                                {{123}{456}}  {{123}{4567}}
                                {{126}{345}}  {{1234}{567}}
                                {{156}{234}}  {{1237}{456}}
                                              {{1267}{345}}
                                              {{127}{3456}}
                                              {{1567}{234}}
                                              {{167}{2345}}

Mathematica

cycedsprop[n_, k_]:=Union[Sort/@Join@@Table[1+Mod[Range[i, j]-1, n], {i, n}, {j, i+k, n+i-1}]];
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[cycedsprop[n, 2], Range[n]]], {n, 15}]

Crossrefs

Cf. A000325, A001610, A001680, A005251, A066982, A306351, A323950, A323952, A323954.

Sequence in context: A007882 A265258 A009852 * A080003 A033016 A027008

Adjacent sequences: A323948 A323949 A323950 * A323952 A323953 A323954

Keyword

nonn,easy

Author

Gus Wiseman, Feb 10 2019

Extensions

More terms from Alois P. Heinz, Feb 10 2019

Status

approved