A304382 Number of z-trees summing to n. Number of connected strict integer partitions of n with pairwise indivisible parts and clutter density -1.

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 2, 1, 3, 2, 4, 3, 5, 2, 5, 4, 6, 3, 7, 6, 8, 4, 9, 8, 13, 9, 15, 8, 14, 12, 16, 12, 20, 20, 24, 15, 27, 20, 33, 27, 35

Offset

1,10

Comments

Given a finite set S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices with a common divisor. For example, G({6,14,15,35}) is a 4-cycle. A multiset S is said to be connected if G(S) is a connected graph.

The clutter density of a multiset S of positive integers is Sum_{s in S} (omega(s) - 1) - omega(LCM(S)).

Links

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

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

Example

The a(30) = 8 z-trees together with the corresponding multiset systems are the following.
       (30): {{1,2,3}}
     (26,4): {{1,6},{1,1}}
     (22,8): {{1,5},{1,1,1}}
     (21,9): {{2,4},{2,2}}
    (16,14): {{1,1,1,1},{1,4}}
   (15,9,6): {{2,3},{2,2},{1,2}}
  (14,10,6): {{1,4},{1,3},{1,2}}
  (12,10,8): {{1,1,2},{1,3},{1,1,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];
strConnAnti[n_]:=Select[IntegerPartitions[n], UnsameQ@@#&&Length[zsm[#]]==1&&Select[Tuples[#, 2], UnsameQ@@#&&Divisible@@#&]=={}&];
Table[Length[Select[strConnAnti[n], Length[#]==1||zreeQ[#]&]], {n, 20}]

Crossrefs

Cf. A000009, A006126, A048143, A054921, A112798, A285572, A286518, A286520, A293993, A303362, A303837, A304714, A304716, A305194, A305195.

Sequence in context: A062842 A126805 A288003 * A304717 A110963 A292622

Adjacent sequences: A304379 A304380 A304381 * A304383 A304384 A304385

Keyword

nonn

Author

Gus Wiseman, May 21 2018

Status

approved