A054921 -id:A054921 - 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}]

A070166 Irregular triangle read by rows giving T(n,k) = number of rooted graphs on n + 1 nodes with k edges (n >= 0, 0 <= k <= n(n-1)/2).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 6, 4, 2, 1, 1, 2, 5, 11, 17, 18, 17, 11, 5, 2, 1, 1, 2, 5, 13, 29, 52, 76, 94, 94, 76, 52, 29, 13, 5, 2, 1, 1, 2, 5, 14, 35, 83, 173, 308, 487, 666, 774, 774, 666, 487, 308, 173, 83, 35, 14, 5, 2, 1, 1, 2, 5, 14, 37, 98, 252, 585, 1239, 2396, 4135, 6340

Offset: 0

Vladeta Jovovic and Eric W. Weisstein, Apr 23 2002

T(n,k) is also the number of graphs with n nodes and k edges which may contain loops. (Delete the root node and change every edge leading to it into a loop.)

T(n,k) is also the number of symmetric relations with n points and k relations.

			Triangle begins:
1;
1, 1;
1, 2, 2, 1;
1, 2, 4, 6, 4, 2, 1;
1, 2, 5, 11, 17, 18, 17, 11, 5, 2, 1; <- gives either the numbers of rooted graphs on 5 nodes, or the numbers of graphs with loops on 4 nodes; with from 0 to 10 edges
1, 2, 5, 13, 29, 52, 76, 94, 94, 76, 52, 29, 13, 5, 2, 1;
...

E. Palmer and F. Harary, Graphical Enumeration, Academic Press, 1973.

Andrew Howroyd, Table of n, a(n) for n = 0..1560
Marko R. Riedel, Number of distinct connected digraphs
Eric Weisstein's World of Mathematics, Rooted Graphs

Row sums are A000666.

Cf. A054921, A008406, A283755, A322114, A368598, A368599.

Join[{{1},{1,1}},CoefficientList[Table[CycleIndex[Join[PairGroup[SymmetricGroup[n]],Permutations[Range[Binomial[n,2]+1,Binomial[n,2]+n]],2],s]/.Table[s[i]->1+x^i,{i,1,n^2-n}],{n,2,7}],x]]//Grid  (* Geoffrey Critzer, Oct 01 2012 *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_, t_] := Product[Product[g = GCD[v[[i]], v[[j]]]; t[v[[i]]*v[[j]]/g]^g, {j, 1, i - 1}], {i, 2, Length[v]}]*Product[c = v[[i]]; t[c]^Quotient[c + 1, 2]*If[OddQ[c], 1, t[c/2]], {i, 1, Length[v]}];
row[n_] := Module[{s = 0}, Do[s += permcount[p]*edges[p, 1 + x^# &], {p, IntegerPartitions[n]}]; s/n!] // Expand // CoefficientList[#, x] &
row /@ Range[0, 7] // Flatten (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c+1)\2)*if(c%2, 1, t(c/2)))}
G(n, A=0) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i+A)); s/n!}
{ for(n=0, 7, print(Vecrev(G(n)))) } \\ Andrew Howroyd, Oct 23 2019, updated Jan 09 2024

Offset changed by Andrew Howroyd, Oct 23 2019

A322337 Number of strict 2-edge-connected integer partitions of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 1, 1, 2, 0, 4, 0, 4, 3, 5, 0, 9, 0, 10, 5, 11, 1, 18, 3, 17, 8, 22, 3, 35, 5, 32, 17, 39, 16, 59, 14, 58, 33, 75, 28, 103, 35, 106, 71, 125, 63, 174, 81, 192, 127, 220, 130, 294, 170, 325, 237, 378, 257, 504

Offset: 1

Gus Wiseman, Dec 04 2018

nonn

An integer partition is 2-edge-connected if the hypergraph of prime factorizations of its parts is connected and cannot be disconnected by removing any single part.

			The a(24) = 18 strict 2-edge-connected integer partitions of 24:
  (15,9)   (10,8,6)   (10,8,4,2)
  (16,8)   (12,8,4)   (12,6,4,2)
  (18,6)   (12,9,3)
  (20,4)   (14,6,4)
  (21,3)   (14,8,2)
  (22,2)   (15,6,3)
  (14,10)  (16,6,2)
           (18,4,2)
           (12,10,2)

Wikipedia, k-edge-connected graph

Cf. A007718, A013922, A054921, A095983, A218970, A275307, A286518, A304714, A304716, A305078, A305079, A322335, A322336.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
twoedQ[sys_]:=And[Length[csm[sys]]==1,And@@Table[Length[csm[Delete[sys,i]]]==1,{i,Length[sys]}]];
Table[Length[Select[IntegerPartitions[n],And[UnsameQ@@#,twoedQ[primeMS/@#]]&]],{n,30}]

A304386 Number of unlabeled hypertrees (connected antichains with no cycles) spanning up to n vertices and allowing singleton edges.

Original entry on oeis.org

1, 2, 5, 15, 50, 200, 907, 4607, 25077, 144337, 863678, 5329994, 33697112, 217317986, 1424880997, 9474795661, 63769947778, 433751273356, 2977769238994, 20611559781972, 143720352656500, 1008765712435162, 7122806053951140, 50566532826530292, 360761703055959592

Offset: 0

Gus Wiseman, May 21 2018

nonn

			Non-isomorphic representatives of the a(3) = 15 hypertrees are the following:
  {}
  {{1}}
  {{1,2}}
  {{1,2,3}}
  {{2},{1,2}}
  {{1,3},{2,3}}
  {{3},{1,2,3}}
  {{1},{2},{1,2}}
  {{3},{1,2},{2,3}}
  {{3},{1,3},{2,3}}
  {{2},{3},{1,2,3}}
  {{1},{2},{3},{1,2,3}}
  {{2},{3},{1,2},{1,3}}
  {{2},{3},{1,3},{2,3}}
  {{1},{2},{3},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

Cf. A030019, A035053, A048143, A054921, A134954, A134955, A134957, A134959, A144959, A304386, A304717, A304867, A304911, A304912, A304968, A304970.

\\ here b(n) is A318494 as vector
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
b(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerT(EulerT(2*v)))); v}
seq(n)={my(u=2*b(n)); Vec(1 + x*Ser(EulerT(u))*(1-x*Ser(u))/(1-x))} \\ Andrew Howroyd, Aug 27 2018

Partial sums of b(1) = 1, b(n) = A134959(n) otherwise.

Terms a(7) and beyond from Andrew Howroyd, Aug 27 2018

A322635 Number of regular graphs with loops on n labeled vertices.

Original entry on oeis.org

2, 4, 4, 24, 78, 1908, 23368, 1961200, 75942758, 25703384940, 4184912454930, 4462909435830552, 2245354417775573206, 10567193418810168583576, 24001585002447984453495392, 348615956932626441906675011568, 2412972383955442904868321667433106, 162906453913051798826796439651249753404

Offset: 1

Gus Wiseman, Dec 21 2018

nonn

A graph is regular if all vertices have the same degree. A loop adds 2 to the degree of its vertex.

Wikipedia, Regular graph
Gus Wiseman, The a(4) = 24 regular graphs with loops.
Gus Wiseman, The a(5) = 78 regular graphs with loops.

Row sums of A333158.

Cf. A000666, A054921, A059441, A295193, A299353, A306017, A306021, A319189, A319190, A319612, A322659, A322661.

Table[Sum[SeriesCoefficient[Product[1+Times@@x/@s,{s,Select[Tuples[Range[n],2],OrderedQ]}],Sequence@@Table[{x[i],0,k},{i,n}]],{k,0,2n}],{n,6}]

for(n=1, 10, print1(A322635(n), ", ")) \\ See A295193 for script, Andrew Howroyd, Aug 28 2019

a(11)-a(18) from Andrew Howroyd, Aug 28 2019

A322306 Number of connected divisors of n. Number of connected submultisets of the n-th multiset multisystem (A302242).

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 1, 1, 3, 1, 2, 3, 2, 1, 2, 2, 2, 3, 2, 1, 3, 1, 1, 2, 2, 2, 3, 1, 2, 3, 2, 1, 4, 1, 2, 3, 2, 1, 2, 2, 3, 2, 2, 1, 4, 2, 2, 3, 2, 1, 3, 1, 2, 5, 1, 3, 3, 1, 2, 2, 3, 1, 3, 1, 2, 3, 2, 2, 4, 1, 2, 4, 2, 1, 4, 2, 2, 3

Offset: 1

Gus Wiseman, Dec 03 2018

nonn

A prime index of n is a number m such that prime(m) divides n. A positive integer is connected if its prime indices are connected (see A305078).

			The a(1365) = 12 divisors are 3, 5, 7, 13, 21, 39, 65, 91, 195, 273, 455, 1365. These correspond to the following connected submultisets of {{1},{2},{1,1},{1,2}}.
     3: {{1}}
     5: {{2}}
     7: {{1,1}}
    13: {{1,2}}
    21: {{1},{1,1}}
    39: {{1},{1,2}}
    65: {{2},{1,2}}
    91: {{1,1},{1,2}}
   195: {{1},{2},{1,2}}
   273: {{1},{1,1},{1,2}}
   455: {{2},{1,1},{1,2}}
  1365: {{1},{2},{1,1},{1,2}}

Cf. A003963, A054921, A112798, A286518, A290103, A301957, A302242, A304714, A304716, A305078, A316556, A322307.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
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]]]]]]]]];
Table[Length[Select[Union[Subsets[primeMS[n]]],Length[zsm[#]]==1&]],{n,50}]

A322307 Number of multisets in the swell of the n-th multiset multisystem.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 03 2018

nonn

First differs from A001221 at a(91) = 3, A001221(91) = 2.
The swell of a multiset partition is the set of possible joins of its connected submultisets, where the multiplicity of a vertex in the join of a set of multisets is the maximum multiplicity of the same vertex among the parts. For example the swell of {{1,1},{1,2},{2,2}} is:
  {1,1}
  {1,2}
  {2,2}
  {1,1,2}
  {1,2,2}
  {1,1,2,2}

Cf. A003963, A054921, A056239, A112798, A218970, A286518, A290103, A301957, A302242, A304716, A305078, A305079, A316556, A322306.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
zwell[y_]:=Union[y,Join@@Cases[Subsets[Union[y],{2}],{x_,z_}?(GCD@@#>1&):>zwell[Sort[Append[Fold[DeleteCases[#1,#2,{1},1]&,y,{x,z}],LCM[x,z]]]]]];
Table[Length[zwell[primeMS[n]]],{n,100}]

A304311 Triangle T(n,k) read by rows: number of bicolored connected graphs with n nodes and k nodes of the first color.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 3, 3, 2, 6, 11, 16, 11, 6, 21, 58, 98, 98, 58, 21, 112, 407, 879, 1087, 879, 407, 112, 853, 4306, 11260, 17578, 17578, 11260, 4306, 853, 11117, 72489, 230505, 436371, 537272, 436371, 230505, 72489, 11117

Offset: 0

R. J. Mathar, May 10 2018

			Triangle begins
      1;
      1,     1;
      1,     1,      1;
      2,     3,      3,      2;
      6,    11,     16,     11,      6;
     21,    58,     98,     98,     58,     21;
    112,   407,    879,   1087,    879,    407,    112;
    853,  4306,  11260,  17578,  17578,  11260,   4306,   853;
  11117, 72489, 230505, 436371, 537272, 436371, 230505, 72489, 11117;

Andrew Howroyd, Table of n, a(n) for n = 0..1274

Cf. A054921 (row sums), A001349 (1st column), A126100 (2nd column), A303831 (3rd column), A294783 (trees).

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
S(n,y)={my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)*prod(i=1,#p,1+y^p[i])); s/n!}
InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i) )}
{my(A=InvEulerMT(vector(10, n, S(n,y)))); for(n=0, #A, for(k=0, n, print1(polcoeff(if(n,A[n],1), k), ", ")); print)} \\ Andrew Howroyd, May 13 2018

T(n,k) = T(n,n-k).

A322391 Number of integer partitions of n with edge-connectivity 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 2, 3, 3, 9, 3, 14, 8, 17, 13, 35, 17, 49, 35, 67, 53, 114, 69

Offset: 1

Gus Wiseman, Dec 05 2018

The edge-connectivity of an integer partition is the minimum number of parts that must be removed so that the prime factorizations of the remaining parts form a disconnected (or empty) hypergraph.

			The a(20) = 8 integer partitions:
  (20),
  (12,3,3,2), (9,6,3,2), (8,6,3,3),
  (6,4,4,3,3),
  (6,4,3,3,2,2), (6,3,3,3,3,2),
  (6,3,3,2,2,2,2).

Wikipedia, k-edge-connected graph

Cf. A007718, A013922, A054921, A095983, A218970, A275307, A304716, A305078, A305079, A322335, A322336, A322387, A322390.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
edgeConn[y_]:=If[Length[csm[primeMS/@y]]!=1,0,Length[y]-Max@@Length/@Select[Union[Subsets[y]],Length[csm[primeMS/@#]]!=1&]];
Table[Length[Select[IntegerPartitions[n],edgeConn[#]==1&]],{n,20}]

A322394 Heinz numbers of integer partitions with edge-connectivity 1.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 195, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269

Offset: 1

Gus Wiseman, Dec 06 2018

nonn

The first nonprime term is 195, which is the Heinz number of (6,3,2).
The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).
An integer partition has edge-connectivity 1 if the prime factorizations of the parts form a connected hypergraph that can be disconnected (or made empty) by removing a single part.

Wikipedia, k-edge-connected graph

Cf. A007718, A013922, A054921, A056239, A095983, A112798, A218970, A304716, A305078, A305079, A322336, A322391, A322393.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
edgeConn[y_]:=If[Length[csm[primeMS/@y]]!=1,0,Length[y]-Max@@Length/@Select[Union[Subsets[y]],Length[csm[primeMS/@#]]!=1&]];
Select[Range[100],edgeConn[primeMS[#]]==1&]

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

A070166 Irregular triangle read by rows giving T(n,k) = number of rooted graphs on n + 1 nodes with k edges (n >= 0, 0 <= k <= n(n-1)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A322337 Number of strict 2-edge-connected integer partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A304386 Number of unlabeled hypertrees (connected antichains with no cycles) spanning up to n vertices and allowing singleton edges.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A322635 Number of regular graphs with loops on n labeled vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A322306 Number of connected divisors of n. Number of connected submultisets of the n-th multiset multisystem (A302242).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A322307 Number of multisets in the swell of the n-th multiset multisystem.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A304311 Triangle T(n,k) read by rows: number of bicolored connected graphs with n nodes and k nodes of the first color.

Views

Author

Keywords

Examples

Links

Crossrefs