|
%I #12 Aug 23 2023 08:43:36
%S 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,
%T 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,
%U 12,8,1,9,16,19,9,11,16,20,14,21,13,8,10,9,18
%N Number of acyclic spanning subgraphs of a cycle graph, where the sizes of the connected components are given by the prime indices of n.
%C a(1) = 1 by convention.
%C A prime index of n is a number m such that prime(m) divides n.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Newton%27s_identities#Expressing_power_sums_in_terms_of_elementary_symmetric_polynomials">Expressing power sums in terms of elementary symmetric polynomials</a>
%H Gus Wiseman, <a href="http://arxiv.org/abs/0709.0430">Enumeration of paths and cycles and e-coefficients of incomparability graphs</a>, arXiv:0709.0430 [math.CO], 2007.
%F 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.
%e 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.
%t 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]]]]]]]]];
%t 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}]
%Y Different orderings with signs are A115131, A210258, A263916.
%Y Cf. A005651, A008480, A048994, A056239, A124794, A124795, A135278, A215366, A318762, A319191, A319193, A319226.
%K nonn
%O 1,3
%A _Gus Wiseman_, Sep 13 2018
|
