login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A305194
Number of z-forests summing to n. Number of strict integer partitions of n with pairwise indivisible parts and all connected components having clutter density -1.
2
1, 1, 1, 1, 2, 1, 3, 2, 3, 4, 5, 4, 6, 7, 7, 9, 11, 12, 13, 15, 17, 20, 23, 25, 27, 32, 35, 40, 45, 49, 54, 58, 67, 78, 82, 95, 99, 111, 123, 135, 150, 164, 177, 194, 214, 236, 260, 282, 309, 330
OFFSET
1,5
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-forest is a strict integer partition with pairwise indivisible parts greater than 1 such that all connected components have clutter density -1.
EXAMPLE
The a(17) = 11 z-forests together with the corresponding multiset systems:
(17): {{7}}
(15,2): {{2,3},{1}}
(14,3): {{1,4},{2}}
(13,4): {{6},{1,1}}
(12,5): {{1,1,2},{3}}
(11,6): {{5},{1,2}}
(10,7): {{1,3},{4}}
(9,8): {{2,2},{1,1,1}}
(10,4,3): {{1,3},{1,1},{2}}
(7,6,4): {{4},{1,2},{1,1}}
(7,5,3,2): {{4},{3},{2},{1}}
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];
zreeQ[s_]:=And[Length[s]>=2, zensity[s]==-1];
Table[Length[Select[IntegerPartitions[n], Function[s, UnsameQ@@s&&And@@(Length[#]==1||zreeQ[#]&)/@Table[Select[s, Divisible[m, #]&], {m, zsm[s]}]&&Select[Tuples[s, 2], UnsameQ@@#&&Divisible@@#&]=={}]]], {n, 50}]
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 27 2018
STATUS
approved