

A303838


Number of zforests with least common multiple n > 1.


17



0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 8, 1, 1, 2, 2, 2, 5, 1, 2, 2, 4, 1, 8, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 16, 1, 2, 3, 1, 2, 8, 1, 3, 2, 8, 1, 7, 1, 2, 3, 3, 2, 8, 1, 5, 1, 2, 1, 16, 2, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,6


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 4cycle. 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. A zforest is a finite set of pairwise indivisible positive integers greater than 1 such that all connected components are ztrees, meaning they have clutter density 1.
This is a generalization to multiset systems of the usual definition of hyperforest (viz. 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) = A134954(k).
Differs from A324837 at positions {1, 180, 210, ...}. For example, a(210) = 55, A324837(210) = 49.


LINKS

Gus Wiseman, Table of n, a(n) for n = 1..250
R. Bacher, On the enumeration of labelled hypertrees and of labelled bipartite trees, arXiv:1102.2708 [math.CO].


EXAMPLE

The a(60) = 16 zforests together with the corresponding multiset systems (see A112798, A302242) are the following.
(60): {{1,1,2,3}}
(3,20): {{2},{1,1,3}}
(4,15): {{1,1},{2,3}}
(4,30): {{1,1},{1,2,3}}
(5,12): {{3},{1,1,2}}
(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}}
(3,4,5): {{2},{1,1},{3}}
(3,4,10): {{2},{1,1},{1,3}}
(4,5,6): {{1,1},{3},{1,2}}
(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]]]], Function[s, LCM@@s==n&&And@@Table[zensity[Select[s, Divisible[m, #]&]]==1, {m, zsm[s]}]&&Select[Tuples[s, 2], UnsameQ@@#&&Divisible@@#&]=={}]]], {n, 100}]


CROSSREFS

Cf. A006126, A030019, A048143, A076078, A112798, A134954, A275307, A285572, A286518, A286520, A293993, A293994, A302242, A303837, A304118.
Sequence in context: A321747 A008480 A168324 * A324837 A285572 A179926
Adjacent sequences: A303835 A303836 A303837 * A303839 A303840 A303841


KEYWORD

nonn


AUTHOR

Gus Wiseman, May 19 2018


STATUS

approved



