cp's OEIS Frontend

A303838 Number of z-forests with least common multiple n > 1.

%I A303838 #26 Feb 03 2025 09:38:28
%S A303838 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,
%T A303838 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,
%U A303838 2,8,1,7,1,2,3,3,2,8,1,5,1,2,1,16,2,2
%N A303838 Number of z-forests with least common multiple n > 1.
%C A303838 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. A z-forest is a finite set of pairwise indivisible positive integers greater than 1 such that all connected components are z-trees, meaning they have clutter density -1.
%C A303838 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).
%C A303838 If n is squarefree with k prime factors, then a(n) = A134954(k).
%C A303838 Differs from A324837 at positions {1, 180, 210, ...}. For example, a(210) = 55, A324837(210) = 49.
%H A303838 Gus Wiseman, <a href="/A303838/b303838.txt">Table of n, a(n) for n = 1..250</a>
%H A303838 Roland 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], 2011.
%e A303838 The a(60) = 16 z-forests together with the corresponding multiset systems (see A112798, A302242) are the following.
%e A303838        (60): {{1,1,2,3}}
%e A303838      (3,20): {{2},{1,1,3}}
%e A303838      (4,15): {{1,1},{2,3}}
%e A303838      (4,30): {{1,1},{1,2,3}}
%e A303838      (5,12): {{3},{1,1,2}}
%e A303838      (6,20): {{1,2},{1,1,3}}
%e A303838     (10,12): {{1,3},{1,1,2}}
%e A303838     (12,15): {{1,1,2},{2,3}}
%e A303838     (12,20): {{1,1,2},{1,1,3}}
%e A303838     (15,20): {{2,3},{1,1,3}}
%e A303838     (3,4,5): {{2},{1,1},{3}}
%e A303838    (3,4,10): {{2},{1,1},{1,3}}
%e A303838     (4,5,6): {{1,1},{3},{1,2}}
%e A303838    (4,6,10): {{1,1},{1,2},{1,3}}
%e A303838    (4,6,15): {{1,1},{1,2},{2,3}}
%e A303838   (4,10,15): {{1,1},{1,3},{2,3}}
%t A303838 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 A303838 zensity[s_]:=Total[(PrimeNu[#]-1&)/@s]-PrimeNu[LCM@@s];
%t A303838 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}]
%Y A303838 Cf. A006126, A030019, A048143, A076078, A112798, A134954, A275307, A285572, A286518, A286520, A293993, A293994, A302242, A303837, A304118.
%K A303838 nonn
%O A303838 1,6
%A A303838 _Gus Wiseman_, May 19 2018