A322152 -id:A322152 - cp's OEIS frontend

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.

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

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

A322148 Regular triangle where T(n,k) is the number of labeled connected multigraphs with loops with n edges and k vertices.

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 6, 16, 16, 1, 10, 51, 127, 125, 1, 15, 126, 574, 1347, 1296, 1, 21, 266, 1939, 8050, 17916, 16807, 1, 28, 504, 5440, 35210, 135156, 286786, 262144, 1, 36, 882, 13387, 125730, 736401, 2642122, 5368728, 4782969, 1, 45, 1452, 29854, 388190, 3239491, 17424610, 58925728, 115089813, 100000000

Offset: 0

Gus Wiseman, Nov 28 2018

			Triangle begins:
  1
  1     1
  1     3     3
  1     6    16    16
  1    10    51   127   125
  1    15   126   574  1347  1296
  1    21   266  1939  8050 17916 16807

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

Row sums are A322152. Last column is A000272.

Cf. A007718, A191646, A191970, A275421, A321155, A322114, A322115, A322137, A322147.

multsubs[set_,k_]:=If[k==0,{{}},Join@@Table[Prepend[#,set[[i]]]&/@multsubs[Drop[set,i-1],k-1],{i,Length[set]}]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[If[n==0,1,Length[Select[multsubs[multsubs[Range[k],2],n],And[Union@@#==Range[k],Length[csm[#]]==1]&]]],{n,0,5},{k,1,n+1}]

Connected(v)={my(u=vector(#v)); for(n=1, #u, u[n]=v[n] - sum(k=1, n-1, binomial(n-1, k)*v[k]*u[n-k])); u}
M(n)={Mat([Col(p, -(n+1)) | p<-Connected(vector(2*n, j, 1/(1 - x + O(x*x^n) )^binomial(j+1, 2)))[1..n+1]])}
{ my(T=M(10)); for(n=1, #T, print(T[n,][1..n])) } \\ Andrew Howroyd, Nov 29 2018

Offset corrected and terms a(28) and beyond from Andrew Howroyd, Nov 29 2018

A343094 Number of connected loopless labeled multigraphs with n edges.

Original entry on oeis.org

1, 1, 4, 24, 201, 2199, 29879, 486231, 9228867, 200272157, 4892538679, 132901744486, 3974163191604, 129735825879843, 4591187990365503, 175081375829138149, 7157470516097359747, 312267811360305253384, 14481803617066951613463, 711413177916751077562759

Offset: 0

Andrew Howroyd, Apr 14 2021

nonn

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

Row sums of A290776.
The unlabeled version is A050535.
Cf. A322152.

S[m_, n_] := Binomial[Binomial[m, 2] + n - 1, n];
R[nn_] := Module[{cc = Array[0&, {nn, nn}]}, cc[[1, 1]] = 1; For[m = 1, m <= nn, m++, For[n = 1, n <= nn - 1, n++, cc[[m, n + 1]] = S[m, n] - S[m - 1, n] - Sum[Sum[Binomial[m - 1, i - 1]*cc[[i, j + 1]]*S[m - i, n - j], {j, 1, n}], {i, 2, m - 1}]]]; cc // Transpose];
Total /@ R[20] (* Jean-François Alcover, Apr 15 2021, after Andrew Howroyd's code for A290776 *)

Connected(v)={my(u=vector(#v)); for(n=1, #u, u[n]=v[n] - sum(k=1, n-1, binomial(n-1, k)*v[k]*u[n-k])); u}
seq(n)={Vec(vecsum(Connected(vector(2*n, j, 1/(1 - x + O(x*x^n))^binomial(j, 2)))))}

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A322148 Regular triangle where T(n,k) is the number of labeled connected multigraphs with loops with n edges and k vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A343094 Number of connected loopless labeled multigraphs with n edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI