A285572 -id:A285572 - cp's OEIS frontend

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

Gus Wiseman, May 21 2018

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)).

			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}}

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

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

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}]

A305150 Number of factorizations of n into distinct, pairwise indivisible factors greater than 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 3, 1, 2, 1, 2, 1, 5, 1, 1, 2, 2, 2, 2, 1, 2, 2, 3, 1, 5, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 3, 2, 3, 2, 2, 1, 6, 1, 2, 2, 1, 2, 5, 1, 2, 2, 5, 1, 3, 1, 2, 2, 2, 2, 5, 1, 3, 1, 2, 1, 6, 2, 2, 2, 3, 1, 6, 2, 2, 2, 2, 2, 4, 1, 2, 2, 2, 1, 5, 1, 3, 5

Offset: 1

Gus Wiseman, May 26 2018

nonn

			The a(60) = 6 factorizations are (3 * 4 * 5), (3 * 20), (4 * 15), (5 * 12), (6 * 10), (60). Missing from this list are (2 * 3 * 10), (2 * 5 * 6), (2 * 30).

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Cf. A001055, A001970, A007716, A045778, A162247, A259936, A275024, A285572, A281113, A281116, A303386, A303431, A305001, A305148, A305149, A305253.

facs[n_] := If[n <= 1, {{}}, Join@@Table[Map[Prepend[#, d] &, Select[facs[n/d], Min@@ # >= d &]], {d, Rest[Divisors[n]]}]]; Table[Length[Select[facs[n], UnsameQ@@ # && Select[Tuples[Union[#], 2], UnsameQ@@ # && Divisible@@ # &] == {} &]], {n, 100}]

A305150(n, m=n, facs=List([])) = if(1==n, 1, my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m)&&factorback(apply(x -> (x%d),Vec(facs))), newfacs = List(facs); listput(newfacs,d); s += A305150(n/d, d-1, newfacs))); (s)); \\ Antti Karttunen, Dec 06 2018

a(n) <= A045778(n) <= A001055(n). - Antti Karttunen, Dec 06 2018

More terms from Antti Karttunen, Dec 06 2018

A326077 Number of maximal primitive subsets of {1..n}.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 4, 4, 6, 7, 11, 11, 13, 13, 23, 24, 36, 36, 48, 48, 64, 66, 126, 126, 150, 151, 295, 363, 507, 507, 595, 595, 895, 903, 1787, 1788, 2076, 2076, 4132, 4148, 5396, 5396, 6644, 6644, 9740, 11172, 22300, 22300, 26140, 26141, 40733, 40773, 60333, 60333, 80781, 80783

Offset: 0

Gus Wiseman, Jun 05 2019

nonn

a(n) is the number of maximal primitive subsets of {1, ..., n}. Here primitive means that no element of the subset divides any other and maximal means that no element can be added to the subset while maintaining the property of being pairwise indivisible. - Nathan McNew, Aug 10 2020

			The a(0) = 1 through a(9) = 7 sets:
  {}  {1}  {1}  {1}   {1}   {1}    {1}    {1}     {1}     {1}
           {2}  {23}  {23}  {235}  {235}  {2357}  {2357}  {2357}
                      {34}  {345}  {345}  {3457}  {3457}  {2579}
                                   {456}  {4567}  {3578}  {3457}
                                                  {4567}  {3578}
                                                  {5678}  {45679}
                                                          {56789}

Nathan McNew, Table of n, a(n) for n = 0..300

Cf. A001055, A051026 (all primitive subsets), A067992, A096827, A143824, A285572, A285573, A303362, A305148, A305149, A316476, A325861, A326023, A326082.

stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[Subsets[Range[n]],stableQ[#,Divisible]&]]],{n,0,10}]

divset(n)={sumdiv(n, d, if(dif(k>#p, ismax(b), my(f=!bitand(p[k], b)); if(!f || bittest(d, k), self()(k+1, b)) + if(f, self()(k+1, b+(1<Andrew Howroyd, Aug 30 2019

Terms a(19) to a(55) from Andrew Howroyd, Aug 30 2019

Name edited by Nathan McNew, Aug 10 2020

A316468 Matula-Goebel numbers of locally stable rooted trees, meaning no branch is a submultiset of any other branch of the same root.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 15, 16, 17, 19, 23, 25, 27, 31, 32, 33, 35, 45, 47, 49, 51, 53, 55, 59, 64, 67, 69, 75, 77, 81, 83, 85, 93, 95, 97, 99, 103, 119, 121, 125, 127, 128, 131, 135, 137, 141, 149, 153, 155, 161, 165, 175, 177, 187, 197, 201, 207, 209

Offset: 1

Gus Wiseman, Jul 04 2018

nonn

A prime index of n is a number m such that prime(m) divides n. A number is in the sequence iff its distinct prime indices are pairwise indivisible and already belong to the sequence.

			Sequence of locally stable rooted trees preceded by their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   7: ((oo))
   8: (ooo)
   9: ((o)(o))
  11: ((((o))))
  15: ((o)((o)))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  23: (((o)(o)))
  25: (((o))((o)))
  27: ((o)(o)(o))
  31: (((((o)))))

Cf. A000081, A004111, A007097, A112798, A277098, A285572, A285573, A303362, A304713, A316467, A316470, A316473, A316475, A316476, A316495.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Or[#==1,And[Select[Tuples[primeMS[#],2],UnsameQ@@#&&Divisible@@#&]=={},And@@#0/@primeMS[#]]]&]

A316467 Matula-Goebel numbers of locally stable rooted identity trees, meaning no branch is a subset of any other branch of the same root.

Original entry on oeis.org

1, 2, 3, 5, 11, 15, 31, 33, 47, 55, 93, 127, 137, 141, 155, 165, 211, 257, 341, 381, 411, 465, 487, 633, 635, 709, 771, 773, 811, 907, 977, 1023, 1055, 1285, 1297, 1397, 1457, 1461, 1507, 1621, 1705, 1905, 2127, 2293, 2319, 2321, 2433, 2621, 2721, 2833, 2931

Offset: 1

Gus Wiseman, Jul 04 2018

nonn

A prime index of n is a number m such that prime(m) divides n. A number belongs to this sequence iff it is squarefree, its distinct prime indices are pairwise indivisible, and its prime indices also belong to this sequence.

			165 = prime(2)*prime(3)*prime(5) belongs to the sequence because it is squarefree, the indices {2,3,5} are pairwise indivisible, and each of them already belongs to the sequence.
Sequence of locally stable rooted identity trees preceded by their Matula-Goebel numbers begins:
    1: o
    2: (o)
    3: ((o))
    5: (((o)))
   11: ((((o))))
   15: ((o)((o)))
   31: (((((o)))))
   33: ((o)(((o))))
   47: (((o)((o))))
   55: (((o))(((o))))
   93: ((o)((((o)))))
  127: ((((((o))))))
  137: (((o)(((o)))))
  141: ((o)((o)((o))))
  155: (((o))((((o)))))
  165: ((o)((o))(((o))))

Cf. A000081, A004111, A007097, A276625, A277098, A285572, A285573, A302796, A303362, A304713, A316468, A316469, A316471, A316474, A316476, A316494.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
ain[n_]:=And[Select[Tuples[primeMS[n],2],UnsameQ@@#&&Divisible@@#&]=={},SquareFreeQ[n],And@@ain/@primeMS[n]];
Select[Range[100],ain]

A316474 Number of locally stable rooted identity trees with n nodes, meaning no branch is a subset of any other branch of the same root.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 5, 8, 14, 23, 42, 73, 133, 241, 442, 812, 1508, 2802, 5247, 9842, 18554, 35045, 66453, 126249

Offset: 1

Gus Wiseman, Jul 04 2018

			The a(9) = 8 locally stable rooted identity trees:
((((((((o))))))))
(((((o)((o))))))
((((o)(((o))))))
(((o)((((o))))))
((((o))(((o)))))
((o)(((((o))))))
((o)((o)((o))))
(((o))((((o)))))

Gus Wiseman, The a(10) = 14 locally stable rooted identity trees with 10 nodes.

Cf. A000081, A004111, A276625, A277098, A285572, A285573, A303362, A304713, A316467, A316471, A316471, A316475.

strut[n_]:=strut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[strut/@c]]]/@IntegerPartitions[n-1],UnsameQ@@#&&Select[Tuples[#,2],UnsameQ@@#&&Complement@@#=={}&]=={}&]];
Table[Length[strut[n]],{n,20}]

A317073 Number of antichains of multisets with multiset-join a normal multiset of size n.

Original entry on oeis.org

1, 1, 3, 16, 198, 9890, 8592538

Offset: 0

Gus Wiseman, Jul 20 2018

An antichain of multisets is a finite set of finite nonempty multisets, none of which is a submultiset of any other. A multiset is normal if it spans an initial interval of positive integers. The multiset-join of a set of multisets has the same vertices with multiplicities equal to the maxima of the multiplicities in the edges.

			The a(3) = 16 antichains of multisets:
  (111),
  (122), (12)(22), (1)(22),
  (112), (11)(12), (2)(11),
  (123), (13)(23), (12)(23), (12)(13), (12)(13)(23), (3)(12), (2)(13), (1)(23), (1)(2)(3).

Goran Kilibarda and Vladeta Jovovic, Antichains of Multisets, Journal of Integer Sequences, Vol. 7 (2004).

Cf. A048143, A255906, A285572, A303837, A303838, A304998, A305001.

Cf. A317074, A317075, A317077, A317079.

stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
multijoin[mss__]:=Join@@Table[Table[x,{Max[Count[#,x]&/@{mss}]}],{x,Union[mss]}]
submultisetQ[M_,N_]:=Or[Length[M]==0,MatchQ[{Sort[List@@M],Sort[List@@N]},{{x_,Z___},{_,x_,W___}}/;submultisetQ[{Z},{W}]]];
allnorm[n_]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
auu[m_]:=Select[stableSets[Union[Rest[Subsets[m]]],submultisetQ],multijoin@@#==m&];
Table[Length[Join@@Table[auu[m],{m,allnorm[n]}]],{n,5}]

a(6) from Robert Price, Jun 21 2021

A321679 Number of non-isomorphic weight-n antichains (not necessarily strict) of sets.

Original entry on oeis.org

1, 1, 3, 5, 12, 19, 45, 75, 170, 314, 713

Offset: 0

Gus Wiseman, Nov 16 2018

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(1) = 1 through a(5) = 19 antichains:
  {{1}}  {{1,2}}    {{1,2,3}}      {{1,2,3,4}}        {{1,2,3,4,5}}
         {{1},{1}}  {{1},{2,3}}    {{1,2},{1,2}}      {{1},{2,3,4,5}}
         {{1},{2}}  {{1},{1},{1}}  {{1},{2,3,4}}      {{1,2},{3,4,5}}
                    {{1},{2},{2}}  {{1,2},{3,4}}      {{1,4},{2,3,4}}
                    {{1},{2},{3}}  {{1,3},{2,3}}      {{1},{1},{2,3,4}}
                                   {{1},{1},{2,3}}    {{1},{2,3},{2,3}}
                                   {{1},{2},{3,4}}    {{1},{2},{3,4,5}}
                                   {{1},{1},{1},{1}}  {{1},{2,3},{4,5}}
                                   {{1},{1},{2},{2}}  {{1},{2,4},{3,4}}
                                   {{1},{2},{2},{2}}  {{1},{1},{1},{2,3}}
                                   {{1},{2},{3},{3}}  {{1},{2},{2},{3,4}}
                                   {{1},{2},{3},{4}}  {{1},{2},{3},{4,5}}
                                                      {{1},{1},{1},{1},{1}}
                                                      {{1},{1},{2},{2},{2}}
                                                      {{1},{2},{2},{2},{2}}
                                                      {{1},{2},{2},{3},{3}}
                                                      {{1},{2},{3},{3},{3}}
                                                      {{1},{2},{3},{4},{4}}
                                                      {{1},{2},{3},{4},{5}}

Cf. A006126, A049311, A096827, A285572, A293993, A293994, A318099, A319719, A319721, A320799, A321678.

A322437 Number of unordered pairs of factorizations of n into factors > 1 where no factor of one divides any factor of the other.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2

Offset: 1

Gus Wiseman, Dec 08 2018

nonn

First differs from A322438 at a(144) = 3, A322438(144) = 4.
From Antti Karttunen, Dec 11 2020: (Start)
Zeros occur on numbers that are either of the form p^k, or q * p^k, or p*q*r, for some primes p, q, r, and exponent k >= 0. [Note also that in all these cases, when x > 1, A307408(x) = 2+A307409(x) = 2 + (A001222(x) - 1)*A001221(x) = A000005(x)].
Proof:
  It is easy to see that for such numbers it is not possible to obtain two such distinct factorizations, that no factor of the other would not divide some factor of the other.
  Conversely, the complement set of above is formed of such composites n that have at least one unitary divisor that is either of the form
  (1) p^x * q^y, with x, y >= 2,
  or
  (2) p^x * q^y * r^z, with x >= 2, and y, z >= 1,
  or
  (3) p^x * q^y * r^z * s^w, with x, y, z, w >= 1,
  where p, q, r, s are distinct primes. Let's indicate with C the remaining portion of k coprime to p, q, r and s (which could be also 1). Then in case (1) we can construct two factorizations, the first having factors (p*q*C) and (p^(x-1) * q^(y-1)), and the second having factors (p^x * C) and (q^y) that are guaranteed to satisfy the condition that no factor in the other factorization divides any of the factors of the other factorization. For case (2) pairs like {(p * q^y * C), (p^(x-1) * r^z)} and {(p^x * C), (q^y * r^z)}, and for case (3) pairs like {(p^x * q^y * C), (r^z * s^w)} and {(p^x * r^z * C), (q^y * s^w)} offer similar examples, therefore a(n) > 0 for all such cases.
(End)

			The a(120) = 2 pairs of such factorizations:
   (6*20)|(8*15)
   (8*15)|(10*12)
The a(144) = 3 pairs of factorizations:
   (6*24)|(9,16)
   (8*18)|(12*12)
   (9*16)|(12*12)
The a(210) = 3 pairs of factorizations:
   (6*35)|(10*21)
   (6*35)|(14*15)
  (10*21)|(14*15)
[Note that 210 is the first squarefree number obtaining nonzero value]
The a(240) = 4 pairs of factorizations:
   (6*40)|(15*16)
   (8*30)|(12*20)
  (10*24)|(15*16)
  (12*20)|(15*16)
The a(1728) = 14 pairs of factorizations:
    (6*6*48)|(27*64)
   (6*12*24)|(27*64)
     (6*288)|(27*64)
    (8*8*27)|(12*12*12)
  (12*12*12)|(27*64)
  (12*12*12)|(32*54)
    (12*144)|(27*64)
    (12*144)|(32*54)
    (16*108)|(24*72)
     (18*96)|(27*64)
     (24*72)|(27*64)
     (24*72)|(32*54)
     (27*64)|(36*48)
     (32*54)|(36*48)

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences computed from exponents in factorization of n

Cf. A000688, A001055, A285572, A285573, A294068, A303362, A304713, A305149, A305150, A305193, A316476, A317144, A322435, A322436, A322441, A322442, A339626.

Cf. also comments A307408 and A307409.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[Subsets[facs[n],{2}],And[!Or@@Divisible@@@Tuples[#],!Or@@Divisible@@@Reverse/@Tuples[#]]&]],{n,100}]

factorizations(n, m=n, f=List([]), z=List([])) = if(1==n, listput(z,Vec(f)); z, my(newf); fordiv(n, d, if((d>1)&&(d<=m), newf = List(f); listput(newf,d); z = factorizations(n/d, d, newf, z))); (z));
is_ndf_pair(fac1,fac2) = { for(i=1,#fac1,for(j=1,#fac2,if(!(fac1[i]%fac2[j])||!(fac2[j]%fac1[i]),return(0)))); (1); };
number_of_ndfpairs(z) = sum(i=1,#z,sum(j=i+1,#z,is_ndf_pair(z[i],z[j])));
A322437(n) = number_of_ndfpairs(Vec(factorizations(n))); \\ Antti Karttunen, Dec 10 2020

For n > 0, a(A002110(n)) = A322441(n)/2 = A339626(n). - Antti Karttunen, Dec 10 2020

Data section extended up to a(120) and more examples added by Antti Karttunen, Dec 10 2020

A316433 Number of integer partitions of n whose length is equal to the LCM of all parts.

Original entry on oeis.org

1, 0, 1, 1, 1, 0, 2, 1, 4, 3, 4, 4, 8, 5, 7, 8, 10, 8, 13, 13, 20, 18, 25, 25, 36, 34, 48, 52, 64, 64, 85, 85, 108, 106, 129, 133, 160, 158, 189, 194, 229, 228, 276, 279, 332, 336, 394, 402, 476, 489, 572, 599, 699, 728, 845, 889, 1032, 1094, 1251, 1332, 1523

Offset: 1

Gus Wiseman, Jul 02 2018

nonn

			The a(13) = 8 partitions are (4441), (55111), (322222), (332221), (333211), (622111), (631111), (7111111).

Cf. A067538, A074761, A143773, A285572, A289508, A290103, A305566, A316429, A316430, A316431, A316432.

Table[Length[Select[IntegerPartitions[n],LCM@@#==Length[#]&]],{n,30}]

a(n) = {my(nb = 0); forpart(p=n, if (lcm(Vec(p))==#p, nb++);); nb;} \\ Michel Marcus, Jul 03 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A305150 Number of factorizations of n into distinct, pairwise indivisible factors greater than 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326077 Number of maximal primitive subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A316468 Matula-Goebel numbers of locally stable rooted trees, meaning no branch is a submultiset of any other branch of the same root.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A316467 Matula-Goebel numbers of locally stable rooted identity trees, meaning no branch is a subset of any other branch of the same root.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A316474 Number of locally stable rooted identity trees with n nodes, meaning no branch is a subset of any other branch of the same root.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A317073 Number of antichains of multisets with multiset-join a normal multiset of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A321679 Number of non-isomorphic weight-n antichains (not necessarily strict) of sets.

Views

Author

Keywords

Comments

Examples

Crossrefs