

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.


14



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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

Table of n, a(n) for n=1..78.
Gus Wiseman, Enumeration of paths and cycles and ecoefficients of incomparability graphs.
Wikipedia, Expressing power sums in terms of elementary symmetric polynomials


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

Different orderings with signs are A115131, A210258, A263916.
Cf. A005651, A008480, A048994, A056239, A124794, A124795, A135278, A215366, A318762, A319191, A319193, A319226.
Sequence in context: A326619 A326567 A066328 * A304037 A265144 A263275
Adjacent sequences: A319222 A319223 A319224 * A319226 A319227 A319228


KEYWORD

nonn


AUTHOR

Gus Wiseman, Sep 13 2018


STATUS

approved



