A191646 -id:A191646 - cp's OEIS frontend

A290776 Triangle T(n,k) read by rows: the number of connected, loopless, non-oriented, vertex-labeled graphs with n >= 0 edges and k >= 1 vertices, allowing multi-edges.

1, 0, 1, 0, 1, 3, 0, 1, 7, 16, 0, 1, 12, 63, 125, 0, 1, 18, 162, 722, 1296, 0, 1, 25, 341, 2565, 10140, 16807, 0, 1, 33, 636, 7180, 47100, 169137, 262144, 0, 1, 42, 1092, 17335, 168285, 987567, 3271576, 4782969, 0, 1, 52, 1764, 37750, 509545, 4364017, 23315936, 72043092, 100000000

Offset: 0

R. J. Mathar, Aug 10 2017

This is the vertex-labeled companion to A191646.

			The triangle starts in row n=0 with 1 <= k <= n+1 vertices as
  1;
  0, 1;
  0, 1,  3;
  0, 1,  7,   16;
  0, 1, 12,   63,   125;
  0, 1, 18,  162,   722,   1296;
  0, 1, 25,  341,  2565,  10140,   16807;
  0, 1, 33,  636,  7180,  47100,  169137,   262144;
  0, 1, 42, 1092, 17355, 168285,  987567,  3271576,  4782969;
  0, 1, 52, 1764, 37750, 509545, 4364017, 23315936, 72043092, 100000000;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO] (2017), Table 62.

Cf. A055998 (k=3), A000272 (diagonal), A060091 (k=4?), A060093 (k=5?).

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];
A = R[10];
Table[A[[n, k]], {n, 1, Length[A]}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 13 2018, after Andrew Howroyd *)

\\ here S(m,n) is m nodes with n edges, not necessarily connected
S(m,n)={ binomial(binomial(m,2) + n - 1, n) }
R(N)={ my(C=matrix(N,N)); C[1,1]=1; for(m=1, N, for(n=1, N-1, C[m,n+1] = S(m,n) - S(m-1,n) - sum(i=2, m-1, sum(j=1, n, binomial(m-1, i-1)*C[i,j+1]*S(m-i, n-j))))); C~; }
{ my(A=R(10)); for(n=1, #A, for(k=1, n, print1(A[n,k],", ")); print) } \\ Andrew Howroyd, May 13 2018

Terms a(34) and beyond from Andrew Howroyd, May 13 2018

A290778 Number of connected undirected unlabeled loopless multigraphs with 4 vertices and n edges.

Original entry on oeis.org

0, 0, 0, 2, 5, 11, 22, 37, 61, 95, 141, 203, 288, 393, 531, 704, 918, 1180, 1504, 1887, 2351, 2900, 3546, 4301, 5187, 6202, 7379, 8726, 10262, 12005, 13987, 16209, 18716, 21521, 24652, 28135, 32013, 36291, 41028, 46244, 51977, 58262, 65155, 72667, 80872, 89798

Offset: 0

R. J. Mathar, Aug 10 2017

There are 6 basic underlying simple graphs on 4 vertices: the linear chain with 3 edges (a tree), the star graph with 3 edges (a tree), the 4-cycle (quadrangle) with 4 edges, the triangle extended with one edge protruding to a vertex of degree 1 (4 edges), the complete graph on 4 vertices with 6 edges, a graph with 5 edges (removing one from the complete graph).

			There are a(3) = 2 connected graphs of 3 edges and 4 vertices, the A000055(4) = 2 trees on 4 vertices.
There are a(4)=5 connected graphs of 4 edges and 4 vertices: duplicate either the middle or a sided edge of the linear chain, duplicate an edge of the star graph, or take any of the two underlying simple graphs with 4 edges.

R. J. Mathar, Connected multigraphs with 4 vertices (A290778)
R. J. Mathar,Statistics on Small Graphs, arXiv:1709.09000 (2017) Eq. (20).
Index entries for linear recurrences with constant coefficients, signature (2, 0, 0, -2, -2, 3, 0, 3, -2, -2, 0, 0, 2, -1).

Column 4 of A191646.

G.f.: -x^3*(x^10-x^9-2*x^7+x^6-x^5+3*x^4-x^2-x-2)/( (x-1)^6 *(1+x)^2 *(1+x^2) *(1+x+x^2)^2 ). - R. J. Mathar, Aug 11 2017

A309936 Irregular triangle read by rows: T(n,k) is the number of unlabeled loopless multigraphs with n edges covering k vertices, n >= 1, 1 <= k <= 2*n.

Original entry on oeis.org

0, 1, 0, 1, 1, 1, 0, 1, 2, 3, 1, 1, 0, 1, 3, 7, 6, 4, 1, 1, 0, 1, 4, 13, 17, 17, 8, 4, 1, 1, 0, 1, 6, 25, 44, 56, 41, 24, 9, 4, 1, 1, 0, 1, 7, 40, 101, 164, 158, 117, 57, 26, 9, 4, 1, 1, 0, 1, 9, 65, 216, 450, 562, 503, 315, 162, 64, 27, 9, 4, 1, 1

Offset: 1

Andrew Howroyd, Oct 23 2019

Covering k vertices means there are no vertices of degree zero.

			Triangle begins:
  0, 1;
  0, 1, 1,  1;
  0, 1, 2,  3,   1,   1;
  0, 1, 3,  7,   6,   4,   1,   1;
  0, 1, 4, 13,  17,  17,   8,   4,  1,  1;
  0, 1, 6, 25,  44,  56,  41,  24,  9,  4, 1, 1;
  0, 1, 7, 40, 101, 164, 158, 117, 57, 26, 9, 4, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..650 (rows 1..25)

Row sums are A050535.
Columns k=3..4 are A253186, A328652.
Cf. A191646, A192517, A327615.

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)))}
C(n,m)={my(s=O(x*x^m)); forpart(p=n, s+=permcount(p)/edges(p, i->1-x^i+O(x*x^m))); Col(s/n!)}
T(m) = {my(n=2*m, A=Mat(vector(n+1, n, C(n-1,m)))); A[2..m+1, 2..n+1]-A[2..m+1, 1..n]}
{ my(A=T(8)); for(n=1, matsize(A)[1], print(A[n, 1..2*n])) }

T(n,k) = A192517(k,n) - A192517(k-1,n) for k > 1.

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

A265582 Number of (unlabeled) connected loopless multigraphs such that the sum of the numbers of vertices and edges is n.

Original entry on oeis.org

1, 1, 0, 1, 1, 2, 3, 6, 10, 21, 41, 87, 187, 423, 971, 2324, 5668, 14224, 36506, 95880, 257081, 703616, 1962887, 5578529, 16137942, 47492141, 142093854, 432001458, 1333937382, 4181500703, 13301265585, 42918900353, 140423545125, 465712099790, 1565092655597

Offset: 0

Michael Joseph, Dec 10 2015

nonn

Also the number of connected skeletal 2-cliquish graphs with n vertices. See Einstein et al. link below.
a(n) can be computed from A265580 and/or A265581, and partitions of n, by taking all loopless multigraphs (V,E) with |V| + |E| = n and subtracting out the disconnected ones.
a(n) <= A265580(n) except when n=1, and a(n) < A265580(n) for n>=6.

			For n = 5, the a(5) = 2 such multigraphs are the graph with three vertices and edges from one vertex to each of the other two, and the graph with two vertices connected by three edges.

Andrew Howroyd, Table of n, a(n) for n = 0..100
D. Einstein, M. Farber, E. Gunawan, M. Joseph, M. Macauley, J. Propp and S. Rubinstein-Salzedo, Noncrossing partitions, toggles, and homomesies, arXiv:1510.06362 [math.CO], 2015.

Cf. A191646, A265580, A265581.

\\ See A191646 for G, InvEulerMT.
seq(n)={my(v=InvEulerMT(vector((n+1)\2, k, 1 + y*Ser(G(k, n-1), y)))); Vec(1 + sum(i=1, #v, v[i]*y^i) + O(y*y^n))} \\ Andrew Howroyd, Feb 01 2020

From Andrew Howroyd, Feb 01 2020: (Start)
a(n) = Sum_{k=1..ceiling(n/2)} A191646(n-k, k) for n > 0.
Inverse Euler transform of A265581. (End)

Terms a(19) and beyond from Andrew Howroyd, Feb 01 2020

A322134 Regular tetrangle where T(n,k,i) is the number of unlabeled connected multiset partitions of weight n with k vertices and i edges.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 2, 1, 1, 2, 4, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 1, 2, 2, 1, 1, 2, 7, 6, 2, 2, 6, 4, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 3, 3, 2, 1, 1, 3, 14, 17, 9, 3, 3, 17, 18, 7, 2, 9, 7, 1, 3, 1, 0, 0

Offset: 0

Gus Wiseman, Nov 27 2018

			Tetrangle begins:
  1
.
  0 0
  1
.
  0 0 0
  1 1
  1
.
  0 0 0 0
  1 1 1
  1 1
  1
.
  0 0 0 0 0
  1 2 1 1
  2 4 2
  1 2
  1
.
  0 0 0 0 0 0
  1 2 2 1 1
  2 7 6 2
  2 6 4
  1 2
  1
.
  0  0  0  0  0  0  0
  1  3  3  2  1  1
  3 14 17  9  3
  3 17 18  7
  2  9  7
  1  3
  1
.
  0  0  0  0  0  0  0  0
  1  3  4  3  2  1  1
  3 20 33 24 11  3
  4 33 59 35 10
  3 24 35 14
  2 11 10
  1  3
  1

Triangle sums are A007718.

Cf. A007716, A054923, A191646, A191970, A275421, A286520, A317533, A317672, A321155, A321254, A322114.

cp's OEIS Frontend

A290776 Triangle T(n,k) read by rows: the number of connected, loopless, non-oriented, vertex-labeled graphs with n >= 0 edges and k >= 1 vertices, allowing multi-edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A290778 Number of connected undirected unlabeled loopless multigraphs with 4 vertices and n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A309936 Irregular triangle read by rows: T(n,k) is the number of unlabeled loopless multigraphs with n edges covering k vertices, n >= 1, 1 <= k <= 2*n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

A265582 Number of (unlabeled) connected loopless multigraphs such that the sum of the numbers of vertices and edges is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A322134 Regular tetrangle where T(n,k,i) is the number of unlabeled connected multiset partitions of weight n with k vertices and i edges.

Views

Author

Keywords

Examples

Crossrefs