OFFSET
1,3
COMMENTS
a(1) = 1 by convention.
A prime index of n is a number m such that prime(m) divides n.
LINKS
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
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.
EXAMPLE
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.
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}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Sep 13 2018
STATUS
approved