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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A303837 Number of z-trees with least common multiple n > 1. 26
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 3, 1, 1, 1, 2, 1, 4, 1, 1, 1, 1, 1, 4, 1, 1, 1, 3, 1, 4, 1, 2, 2, 1, 1, 4, 1, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 10, 1, 1, 2, 1, 1, 4, 1, 2, 1, 4, 1, 6, 1, 1, 2, 2, 1, 4, 1, 4, 1, 1, 1, 10, 1, 1, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,11

COMMENTS

Given a finite set S of positive integers greater than 1, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices that have a common divisor greater than 1. For example, G({6,14,15,35}) is a 4-cycle. A set S is said to be connected if G(S) is a connected graph. The clutter density of S is defined to be Sum_{s in S} (omega(s) - 1) - omega(LCM(S)), where omega = A001221 and LCM is least common multiple. Then a z-tree is a finite connected set of pairwise indivisible positive integers greater than 1 with clutter density -1.

This is a generalization to multiset systems of the usual definition of hypertree (viz. connected hypergraph F such that two distinct hyperedges of F intersect in at most a common vertex and such that every cycle of F is contained in a hyperedge).

If n is squarefree with k prime factors, then a(n) = A030019(k).

LINKS

Table of n, a(n) for n=1..86.

R. Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees, arXiv:1102.2708 [math.CO].

EXAMPLE

The a(72) = 6 z-trees together with the corresponding multiset systems (see A112798, A302242) are the following.

      (72): {{1,1,1,2,2}}

    (8,18): {{1,1,1},{1,2,2}}

    (8,36): {{1,1,1},{1,1,2,2}}

    (9,24): {{2,2},{1,1,1,2}}

   (6,8,9): {{1,2},{1,1,1},{2,2}}

  (8,9,12): {{1,1,1},{2,2},{1,1,2}}

The a(60) = 10 z-trees together with the corresponding multiset systems are the following.

       (60): {{1,1,2,3}}

     (4,30): {{1,1},{1,2,3}}

     (6,20): {{1,2},{1,1,3}}

    (10,12): {{1,3},{1,1,2}}

    (12,15): {{1,1,2},{2,3}}

    (12,20): {{1,1,2},{1,1,3}}

    (15,20): {{2,3},{1,1,3}}

   (4,6,10): {{1,1},{1,2},{1,3}}

   (4,6,15): {{1,1},{1,2},{2,3}}

  (4,10,15): {{1,1},{1,3},{2,3}}

MATHEMATICA

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[Less@@#, GCD@@s[[#]]]>1&]}, If[c=={}, s, zsm[Union[Append[Delete[s, List/@c[[1]]], LCM@@s[[c[[1]]]]]]]]];

zensity[s_]:=Total[(PrimeNu[#]-1&)/@s]-PrimeNu[LCM@@s];

Table[Length[Select[Rest[Subsets[Rest[Divisors[n]]]], And[zensity[#]==-1, zsm[#]=={n}, Select[Tuples[#, 2], UnsameQ@@#&&Divisible@@#&]=={}]&]], {n, 2, 50}]

CROSSREFS

Cf. A006126, A030019, A048143, A076078, A112798, A275307, A285572, A286518, A286520, A293993, A293994, A302242, A303838, A304118.

Sequence in context: A276088 A030612 A264857 * A286520 A320105 A120698

Adjacent sequences:  A303834 A303835 A303836 * A303838 A303839 A303840

KEYWORD

nonn

AUTHOR

Gus Wiseman, May 19 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 June 19 00:55 EDT 2019. Contains 324217 sequences. (Running on oeis4.)