A007718 -id:A007718 - cp's OEIS frontend

A319557 Number of non-isomorphic strict connected multiset partitions of weight n.

1, 1, 2, 5, 12, 30, 91, 256, 823, 2656, 9103, 31876, 116113, 432824, 1659692, 6508521, 26112327, 106927561, 446654187, 1900858001, 8236367607, 36306790636, 162724173883, 741105774720, 3428164417401, 16099059101049, 76722208278328, 370903316203353, 1818316254655097

Offset: 0

Gus Wiseman, Sep 23 2018

nonn

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

Also the number of non-isomorphic connected T_0 multiset partitions of weight n. In a multiset partition, two vertices are equivalent if in every block the multiplicity of the first is equal to the multiplicity of the second. The T_0 condition means that there are no equivalent vertices.

			Non-isomorphic representatives of the a(4) = 12 strict connected multiset partitions:
    {{1,1,1,1}}
    {{1,1,2,2}}
    {{1,2,2,2}}
    {{1,2,3,3}}
    {{1,2,3,4}}
   {{1},{1,1,1}}
   {{1},{1,2,2}}
   {{2},{1,2,2}}
   {{3},{1,2,3}}
   {{1,2},{2,2}}
   {{1,3},{2,3}}
  {{1},{2},{1,2}}
Non-isomorphic representatives of the a(4) = 12 connected T_0 multiset partitions:
     {{1,1,1,1}}
     {{1,2,2,2}}
    {{1},{1,1,1}}
    {{1},{1,2,2}}
    {{2},{1,2,2}}
    {{1,1},{1,1}}
    {{1,2},{2,2}}
    {{1,3},{2,3}}
   {{1},{1},{1,1}}
   {{1},{2},{1,2}}
   {{2},{2},{1,2}}
  {{1},{1},{1},{1}}

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

Cf. A007716, A007718, A049311, A056156, A283877, A316980.

Cf. A319558, A319559, A319560, A319564, A319565, A319566, A319567.

Inverse Euler transform of A316980.

Terms a(11) and beyond from Andrew Howroyd, Jan 19 2023

A191646 Triangle read by rows: T(n,k) = number of connected multigraphs with n >= 0 edges and 1 <= k <= n+1 vertices, with no loops allowed.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 5, 3, 0, 1, 4, 11, 11, 6, 0, 1, 6, 22, 34, 29, 11, 0, 1, 7, 37, 85, 110, 70, 23, 0, 1, 9, 61, 193, 348, 339, 185, 47, 0, 1, 11, 95, 396, 969, 1318, 1067, 479, 106, 0, 1, 13, 141, 771, 2445, 4457, 4940, 3294, 1279, 235

Offset: 0

Alberto Tacchella, Jul 04 2011

			Triangle T(n,k) (with rows n >= 0 and columns k >= 1) begins as follows:
  1;
  0, 1;
  0, 1, 1;
  0, 1, 2,  2;
  0, 1, 3,  5,  3;
  0, 1, 4, 11, 11,  6;
  0, 1, 6, 22, 34, 29, 11;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1274 (terms 0..119 from R. J. Mathar)
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO], 2017; see Section 4.
Brendan McKay and Adolfo Piperno, nauty and Traces. [nauty and Traces are programs for computing automorphism groups of graphs and digraphs.]
B. D. McKay and A. Piperno, Practical Graph Isomorphism, II, J. Symbolic Computation 60 (2013), 94-112.
Gordon Royle, Small Multigraphs.
Gus Wiseman, Illustration of the 33 connected multigraphs counted in row 5.

Row sums give A076864. Diagonal is A000055.
Cf. A034253, A054923, A192517, A253186 (column k=3), A290778 (column k=4).
Cf. A000664, A007718, A036250, A050535, A191646, A191970, A275421, A317672, A322114, A322133, A322152.

EulerT(v)={my(p=exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1); Vec(p/x,-#v)}
InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(serchop( sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i), 1))}
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,x)={sum(i=2, #v, sum(j=1, i-1, my(g=gcd(v[i],v[j])); g*x^(v[i]*v[j]/g))) + sum(i=1, #v, my(t=v[i]); ((t-1)\2)*x^t + if(t%2,0,x^(t/2)))}
G(n,m)={my(s=0); forpart(p=n, s+=permcount(p)*EulerT(Vec(edges(p,x) + O(x*x^m), -m))); s/n!}
R(n)={Mat(apply(p->Col(p+O(y^n),-n), InvEulerMT(vector(n, k, 1 + y*Ser(G(k,n-1), y)))))}
{ my(A=R(10)); for(n=1, #A, for(k=1, n, print1(A[n,k], ", "));print) } \\ Andrew Howroyd, May 14 2018

T(n,k=3) = A253186(n) = A034253(n,k=2) for n >= 1. - Petros Hadjicostas, Oct 02 2019

A319719 Number of non-isomorphic connected antichains of multisets of weight n.

Original entry on oeis.org

1, 1, 3, 4, 10, 14, 48, 95, 305, 822, 2615

Offset: 0

Gus Wiseman, Sep 26 2018

In an antichain, no part is a proper submultiset of any other. The weight of an antichain is the sum of sizes of its parts. Weight is generally not the same as number of vertices. Connected antichains are also called clutters.

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

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

Cf. A001055, A001970, A007716, A007718, A056156, A096827, A253249, A285573, A293994, A318099, A319557, A319616-A319646, A319721.

A054923 Triangle read by rows: number of connected graphs with k >= 0 edges and n nodes (1<=n<=k+1).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 2, 3, 0, 0, 0, 1, 5, 6, 0, 0, 0, 1, 5, 13, 11, 0, 0, 0, 0, 4, 19, 33, 23, 0, 0, 0, 0, 2, 22, 67, 89, 47, 0, 0, 0, 0, 1, 20, 107, 236, 240, 106, 0, 0, 0, 0, 1, 14, 132, 486, 797, 657, 235, 0, 0, 0, 0, 0, 9, 138, 814, 2075, 2678, 1806, 551, 0, 0, 0, 0, 0, 5, 126, 1169, 4495, 8548, 8833, 5026, 1301

Offset: 0

N. J. A. Sloane

The diagonal n = k+1 is A000055(n). - Jonathan Vos Post, Aug 10 2008

			Triangle begins:
  1;
  0, 1;
  0, 0, 1;
  0, 0, 1, 2;
  0, 0, 0, 2, 3;
  0, 0, 0, 1, 5   6;
  0, 0, 0, 1, 5, 13,  11;
  0, 0, 0, 0, 4, 19,  33,  23;
  0, 0, 0, 0, 2, 22,  67,  89,  47;
  0, 0, 0, 0, 1, 20, 107, 236, 240, 106;
  ... (so with 5 edges there's 1 graph with 4 nodes, 5 with 5 nodes and 6 with 6 nodes). [Typo corrected by Anders Haglund, Jul 08 2008]

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 93, Table 4.2.2; p. 241, Table A2.

Andrew Howroyd, Table of n, a(n) for n = 0..1325
G. A. Baker et al., High-temperature expansions for the spin-1/2 Heisenberg model, Phys. Rev., 164 (1967), 800-817.
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO] (2017), Table 57.
Gordon Royle, Small graphs
Gus Wiseman, Non-isomorphic representatives of the 12 connected graphs counted in row 5.

Main diagonal is A000055.
Subsequent diagonals give the number of connected unlabeled graphs with n nodes and n+k edges for k=0..2: A001429, A001435, A001436.
Cf. A002905 (row sums), A001349 (column sums), A008406, A046751 (transpose), A054924 (transpose), A046742 (w/o left column), A343088 (labeled).
Cf. A000664, A007718, A050535, A054923, A191646, A191970, A317672, A322114, A322151.

InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(serchop( sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i), 1))}
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, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p,i->1+x^i)); s/n!}
T(n)={Mat([Col(p+O(y^n), -n) | p<-InvEulerMT(vector(n, k, G(k, y + O(y^n))))])}
{my(A=T(10)); for(n=1, #A, print(A[n,1..n]))} \\ Andrew Howroyd, Oct 23 2019

a(83)-a(89) corrected by Andrew Howroyd, Oct 24 2019

A319565 Number of non-isomorphic connected strict T_0 multiset partitions of weight n.

Original entry on oeis.org

1, 1, 1, 4, 8, 21, 62, 175, 553, 1775, 6007

Offset: 0

Gus Wiseman, Sep 23 2018

In a multiset partition, two vertices are equivalent if in every block the multiplicity of the first is equal to the multiplicity of the second. The T_0 condition means that there are no equivalent vertices.

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(4) = 8 multiset partitions:
1:      {{1}}
2:     {{1,1}}
3:    {{1,1,1}}
      {{1,2,2}}
     {{1},{1,1}}
     {{2},{1,2}}
4:   {{1,1,1,1}}
     {{1,2,2,2}}
    {{1},{1,1,1}}
    {{1},{1,2,2}}
    {{2},{1,2,2}}
    {{1,2},{2,2}}
    {{1,3},{2,3}}
   {{1},{2},{1,2}}

Cf. A007716, A007718, A049311, A056156, A059201, A283877, A316980.

Cf. A319557, A319558, A319559, A319560, A319564, A319566, A319567.

A321155 Regular triangle where T(n,k) is the number of non-isomorphic connected multiset partitions of weight n with density -1 <= k < n-2.

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 6, 6, 4, 1, 10, 14, 11, 4, 1, 22, 38, 38, 20, 6, 1, 42, 94, 111, 72, 28, 6, 1, 94, 250, 348, 278, 138, 42, 8, 1, 203, 648, 1044, 992, 596, 226, 56, 8, 1, 470, 1728, 3192, 3538, 2536, 1192, 370, 76, 10, 1

Offset: 1

Gus Wiseman, Oct 29 2018

The density of a multiset partition of weight n with e parts and v vertices is n - e - v. The weight of a multiset partition is the sum of sizes of its parts.

			Triangle begins:
    1
    2    1
    3    2    1
    6    6    4    1
   10   14   11    4    1
   22   38   38   20    6    1
   42   94  111   72   28    6    1
   94  250  348  278  138   42    8    1
  203  648 1044  992  596  226   56    8    1
  470 1728 3192 3538 2536 1192  370   76   10    1
Non-isomorphic representatives of the connected multiset partitions counted in row 5:
{1,2,3,4,5}         {1,2,3,4,4}       {1,2,2,3,3}     {1,1,2,2,2}   {1,1,1,1,1}
{1,4},{2,3,4}       {1,2},{2,3,3}     {1,2,3,3,3}     {1,2,2,2,2}
{4},{1,2,3,4}       {1,3},{2,3,3}     {1,1},{1,2,2}   {1},{1,1,1,1}
{2},{1,3},{2,3}     {2},{1,2,3,3}     {1},{1,2,2,2}   {1,1},{1,1,1}
{2},{3},{1,2,3}     {2,3},{1,2,3}     {1,2},{1,2,2}
{3},{1,3},{2,3}     {3},{1,2,3,3}     {1,2},{2,2,2}
{3},{3},{1,2,3}     {3,3},{1,2,3}     {2},{1,1,2,2}
{1},{2},{2},{1,2}   {1},{1},{1,2,2}   {2},{1,2,2,2}
{2},{2},{2},{1,2}   {1},{1,2},{2,2}   {2,2},{1,2,2}
{1},{1},{1},{1},{1} {1},{2},{1,2,2}   {1},{1},{1,1,1}
                    {2},{1,2},{1,2}   {1},{1,1},{1,1}
                    {2},{1,2},{2,2}
                    {2},{2},{1,2,2}
                    {1},{1},{1},{1,1}

First column is A125702. Row sums are A007718.

Cf. A007716, A030019, A052888, A056156, A134954, A147878, A317631, A319557, A320921.

A319560 Number of non-isomorphic strict T_0 multiset partitions of weight n.

Original entry on oeis.org

1, 1, 2, 6, 15, 40, 121, 353, 1107, 3550, 11818

Offset: 0

Gus Wiseman, Sep 23 2018

In a multiset partition, two vertices are equivalent if in every block the multiplicity of the first is equal to the multiplicity of the second. The T_0 condition means that there are no equivalent vertices.

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(4) = 15 multiset partitions:
1: {{1}}
2: {{1,1}}
   {{1},{2}}
3: {{1,1,1}}
   {{1,2,2}}
   {{1},{1,1}}
   {{1},{2,2}}
   {{2},{1,2}}
   {{1},{2},{3}}
4: {{1,1,1,1}}
   {{1,2,2,2}}
   {{1},{1,1,1}}
   {{1},{1,2,2}}
   {{1},{2,2,2}}
   {{1},{2,3,3}}
   {{2},{1,2,2}}
   {{1,1},{2,2}}
   {{1,2},{2,2}}
   {{1,3},{2,3}}
   {{1},{2},{1,2}}
   {{1},{2},{2,2}}
   {{1},{2},{3,3}}
   {{1},{3},{2,3}}
   {{1},{2},{3},{4}}

Cf. A007716, A007718, A049311, A053419, A056156, A059201, A283877, A316980.

Cf. A319557, A319558, A319559, A319564, A319565, A319566, A319567.

A322114 Regular triangle read by rows where T(n,k) is the number of unlabeled connected graphs with loops with n edges and k vertices, 1 <= k <= n+1.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 3, 2, 0, 0, 3, 6, 3, 0, 0, 2, 11, 14, 6, 0, 0, 1, 13, 35, 33, 11, 0, 0, 0, 10, 61, 112, 81, 23, 0, 0, 0, 5, 75, 262, 347, 204, 47, 0, 0, 0, 2, 68, 463, 1059, 1085, 526, 106, 0, 0, 0, 1, 49, 625, 2458, 4091, 3348, 1376, 235

Offset: 0

Gus Wiseman, Nov 26 2018

			Triangle begins:
   1
   1   1
   0   1   1
   0   1   3   2
   0   0   3   6   3
   0   0   2  11  14   6
   0   0   1  13  35  33  11
Non-isomorphic representatives of the graphs counted in row 4:
  {{2}{3}{12}{13}}   {{4}{12}{23}{34}}   {{13}{24}{35}{45}}
  {{2}{3}{13}{23}}   {{4}{13}{23}{34}}   {{14}{25}{35}{45}}
  {{3}{12}{13}{23}}  {{4}{13}{24}{34}}   {{15}{25}{35}{45}}
                     {{4}{14}{24}{34}}
                     {{12}{13}{24}{34}}
                     {{14}{23}{24}{34}}

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

Row sums are A191970. Last column is A000055.

Cf. A000664, A007716, A007718, A007719, A054923, A191646, A275421, A317533, A321254.

InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(serchop( sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i), 1))}
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, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p,i->1+x^i)); s/n!}
T(n)={Mat([Col(p+O(y^n), -n) | p<-InvEulerMT(vector(n, k, G(k, y + O(y^n))))])}
{my(A=T(10)); for(n=1, #A, print(A[n,1..n]))} \\ Andrew Howroyd, Oct 22 2019

Terms a(28) and beyond from Andrew Howroyd, Oct 22 2019

A076864 Number of connected loopless multigraphs with n edges.

Original entry on oeis.org

1, 1, 2, 5, 12, 33, 103, 333, 1183, 4442, 17576, 72810, 314595, 1410139, 6541959, 31322474, 154468852, 783240943, 4077445511, 21765312779, 118999764062, 665739100725, 3807640240209, 22246105114743, 132672322938379, 807126762251748

Offset: 0

N. J. A. Sloane, Nov 23 2002

Inverse Euler transform of A050535.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Patrick T. Komiske, Eric M. Metodiev, and Jesse Thaler, Energy flow polynomials: A complete linear basis for jet substructure, arXiv:1712.07124 [hep-ph], 2017.
Tsuyoshi Miezaki, Akihiro Munemasa, Yusaku Nishimura, Tadashi Sakuma, and Shuhei Tsujie, Universal graph series, chromatic functions, and their index theory, arXiv:2403.09985 [math.CO], 2024. See p. 23.
N. J. A. Sloane, Transforms
Gus Wiseman, Non-isomorphic representatives of the unlabeled connected multigraphs counted by the first 5 terms

Row sums of A191646.
Cf. A050535 (multisets), A076865, A076866, A076867.
Cf. A000664, A007718, A054923, A191970, A275421, A317672, A322114, A322137, A322148.

A050535 = Cases[Import["https://oeis.org/A050535/b050535.txt", "Table"], {, }][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
Join[{1}, EulerInvTransform[A050535 // Rest]] (* Jean-François Alcover, Feb 11 2020, updated Mar 17 2020 *)

More terms from Sean A. Irvine, Oct 02 2011
Name and comment swapped by Gus Wiseman, Nov 28 2018
a(0)=1 prepended by Andrew Howroyd, Oct 23 2019

A191970 Number of connected graphs with n edges with loops allowed.

Original entry on oeis.org

1, 2, 2, 6, 12, 33, 93, 287, 940, 3309, 12183, 47133, 190061, 796405, 3456405, 15501183, 71681170, 341209173, 1669411182, 8384579797, 43180474608, 227797465130, 1229915324579, 6790642656907, 38311482445514, 220712337683628, 1297542216770482, 7779452884747298

Offset: 0

Alberto Tacchella, Jun 20 2011

nonn

Inverse Euler transform of A053419.
From R. J. Mathar, Jul 25 2017: (Start)
The Multiset Transform gives the number of graphs with n edges (loops allowed) and k components (0<=k<=n):
 1
2
2 3
6 4 4
12 15 6 5
33 36 24 8 6
93 111 64 33 10 7
287 324 207 92 42 12 8
940 1036 633 308 120 51 14 9
3309 3408 2084 966 409 148 60 16 10
12183 11897 6959 3243 1305 510 176 69 18 11
47133 43137 24415 10970 4432 1644 611 204 78 20 12
190061 163608 88402 38763 15125 5628 1983 712 232 87 22 13
796405 644905 332979 140671 53732 19316 6824 2322 813 260 96 24 14
3456405 2639871 1299054 529179 195517 68878 23515 8020 2661 914 288 105 26 15 (End)

			a(1)=2: Either one node with the edge equal to a loop, or two nodes connected by the edge. a(2)=2: Either three nodes on a chain connected by the two edges, or two nodes connected by an edge, one node with a loop. Apparently multi-loops are not allowed (?). - _R. J. Mathar_, Jul 25 2017

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, Non-isomorphic representatives of the a(1) = 1 through a(4) = 12 connected graphs with loops.

Row sums of A322114.

Cf. A000664, A002905, A007718, A050535, A053419, A054923, A191646, A191970, A275421, A322133, A322151, A322152.

\\ See A322114 for InvEulerMT, G.
seq(n)={vecsum([Vec(p+O(y^n), -n) | p<-InvEulerMT(vector(n, k, G(k, y + O(y^n))))])} \\ Andrew Howroyd, Oct 22 2019

Terms a(25) and beyond from Andrew Howroyd, Oct 22 2019

cp's OEIS Frontend

A319557 Number of non-isomorphic strict connected multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A191646 Triangle read by rows: T(n,k) = number of connected multigraphs with n >= 0 edges and 1 <= k <= n+1 vertices, with no loops allowed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A319719 Number of non-isomorphic connected antichains of multisets of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A054923 Triangle read by rows: number of connected graphs with k >= 0 edges and n nodes (1<=n<=k+1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A319565 Number of non-isomorphic connected strict T_0 multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A321155 Regular triangle where T(n,k) is the number of non-isomorphic connected multiset partitions of weight n with density -1 <= k < n-2.

Views

Author

Keywords

Comments

Examples

Crossrefs

A319560 Number of non-isomorphic strict T_0 multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A322114 Regular triangle read by rows where T(n,k) is the number of unlabeled connected graphs with loops with n edges and k vertices, 1 <= k <= n+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A076864 Number of connected loopless multigraphs with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs