A323950 Number of ways to split an n-cycle into connected subgraphs, none having exactly two vertices.

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

Offset: 0

Author

Gus Wiseman, Feb 10 2019

Keywords

• nonn
• easy

Examples

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

Links

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

Crossrefs

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

Programs

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

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

Extensions

More terms from Alois P. Heinz, Feb 10 2019