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,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.

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.

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: A066328 A330417 A330415 * A333627 A304037 A265144

Adjacent sequences: A319222 A319223 A319224 * A319226 A319227 A319228

Keyword

nonn

Author

Gus Wiseman, Sep 13 2018

Status

approved