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

Author

Gus Wiseman, Feb 10 2019

Keywords

• nonn
• easy

Examples

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

Links

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

Crossrefs

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

Programs

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

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

Extensions

More terms from Alois P. Heinz, Feb 10 2019