login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 e-coefficients 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 16 10:51 EDT 2019. Contains 327095 sequences. (Running on oeis4.)