%I #22 May 21 2018 03:25:46
%S 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,
%T 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,
%U 4,1,6,1,1,2,2,1,4,1,4,1,1,1,10,1,1,1
%N Number of z-trees with least common multiple n > 1.
%C 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.
%C 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).
%C If n is squarefree with k prime factors, then a(n) = A030019(k).
%H R. Bacher, <a href="https://arxiv.org/abs/1102.2708">On the enumeration of labelled hypertrees and of labelled bipartite trees</a>, arXiv:1102.2708 [math.CO].
%e The a(72) = 6 z-trees together with the corresponding multiset systems (see A112798, A302242) are the following.
%e (72): {{1,1,1,2,2}}
%e (8,18): {{1,1,1},{1,2,2}}
%e (8,36): {{1,1,1},{1,1,2,2}}
%e (9,24): {{2,2},{1,1,1,2}}
%e (6,8,9): {{1,2},{1,1,1},{2,2}}
%e (8,9,12): {{1,1,1},{2,2},{1,1,2}}
%e The a(60) = 10 z-trees together with the corresponding multiset systems are the following.
%e (60): {{1,1,2,3}}
%e (4,30): {{1,1},{1,2,3}}
%e (6,20): {{1,2},{1,1,3}}
%e (10,12): {{1,3},{1,1,2}}
%e (12,15): {{1,1,2},{2,3}}
%e (12,20): {{1,1,2},{1,1,3}}
%e (15,20): {{2,3},{1,1,3}}
%e (4,6,10): {{1,1},{1,2},{1,3}}
%e (4,6,15): {{1,1},{1,2},{2,3}}
%e (4,10,15): {{1,1},{1,3},{2,3}}
%t 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]]]]]]]]];
%t zensity[s_]:=Total[(PrimeNu[#]-1&)/@s]-PrimeNu[LCM@@s];
%t Table[Length[Select[Rest[Subsets[Rest[Divisors[n]]]],And[zensity[#]==-1,zsm[#]=={n},Select[Tuples[#,2],UnsameQ@@#&&Divisible@@#&]=={}]&]],{n,2,50}]
%Y Cf. A006126, A030019, A048143, A076078, A112798, A275307, A285572, A286518, A286520, A293993, A293994, A302242, A303838, A304118.
%K nonn
%O 1,11
%A _Gus Wiseman_, May 19 2018
|