A319225 Number of acyclic spanning subgraphs of a cycle graph, where the sizes of the connected components are given by the prime indices of n.

1, 1, 2, 1, 3, 3, 4, 1, 2, 4, 5, 4, 6, 5, 5, 1, 7, 5, 8, 5, 6, 6, 9, 5, 3, 7, 2, 6, 10, 12, 11, 1, 7, 8, 7, 9, 12, 9, 8, 6, 13, 14, 14, 7, 7, 10, 15, 6, 4, 7, 9, 8, 16, 7, 8, 7, 10, 11, 17, 21, 18, 12, 8, 1, 9, 16, 19, 9, 11, 16, 20, 14, 21, 13, 8, 10, 9, 18

Offset: 1

Author

Gus Wiseman, Sep 13 2018

Keywords

• nonn

Comments

a(1) = 1 by convention.

A prime index of n is a number m such that prime(m) divides n.

Examples

			Of the cycle ({1,2,3}, {(1,2),(2,3),(3,1)}) the spanning subgraphs where the sizes of connected components are (2,1) are: ({1,2,3}, {(1,2)}), ({1,2,3}, {(2,3)}), ({1,2,3}, {(3,1)}). Since the prime indices of 6 are (2,1), we conclude a(6) = 3.
		

Links

• Wikipedia, Expressing power sums in terms of elementary symmetric polynomials
• Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

Crossrefs

Different orderings with signs are A115131, A210258, A263916.

Cf. A005651, A008480, A048994, A056239, A124794, A124795, A135278, A215366, A318762, A319191, A319193, A319226.

Programs

Mathematica

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[With[{m=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]},Select[Subsets[Partition[Range[Total[m]],2,1,1],{Total[m]-PrimeOmega[n]}],Sort[Length/@csm[Union[#,List/@Range[Total[m]]]]]==m&]]],{n,30}]

Formula

a(n) = A056239(n) * (Omega(n) - 1)! / Product c_i! where c_i is the multiplicity of prime(i) in the prime factorization of n.