A191646 -id:A191646 - cp's OEIS frontend

A014397 Number of loopless multigraphs with 7 nodes and n edges.

1, 1, 3, 8, 22, 60, 173, 471, 1303, 3510, 9234, 23574, 58464, 140340, 326792, 738090, 1619321, 3455129, 7180856, 14555856, 28819926, 55808840, 105834657, 196779279, 359124362, 643976482, 1135731758, 1971734302, 3372477533

Offset: 0

N. J. A. Sloane

nonn

CRC Handbook of Combinatorial Designs, 1996, p. 650.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 88, (4.1.18).

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

Row 7 of A192517.

Cf. A001399, A003082, A014395, A014396, A014398.

concat([1], G(7, 30)) \\ See A191646 for G. - Andrew Howroyd, Mar 15 2020

More terms and better description from Vladeta Jovovic, Dec 29 1999

A014398 Number of loopless multigraphs with 8 nodes and n edges.

Original entry on oeis.org

1, 1, 3, 8, 23, 64, 197, 588, 1806, 5509, 16677, 49505, 143761, 406091, 1114890, 2970964, 7685972, 19311709, 47170674, 112123118, 259662333, 586583731, 1294143065, 2791716176, 5895027869, 12198014683, 24758285639, 49339306519

Offset: 0

N. J. A. Sloane

nonn

CRC Handbook of Combinatorial Designs, 1996, p. 650.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 88, (4.1.18).

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

Row 8 of A192517.

Cf. A001399, A003082, A014395, A014396, A014397.

concat([1], G(8, 30)) \\ See A191646 for G. - Andrew Howroyd, Mar 15 2020

More terms and better description from Vladeta Jovovic, Dec 29 1999

A036250 Number of trees of nonempty sets with n points. (Each node is a set of 1 or more points.)

Original entry on oeis.org

1, 1, 2, 3, 7, 14, 35, 85, 231, 633, 1845, 5461, 16707, 51945, 164695, 529077, 1722279, 5664794, 18813369, 62996850, 212533226, 721792761, 2466135375, 8471967938, 29249059293, 101440962296, 353289339927, 1235154230060, 4333718587353, 15255879756033

Offset: 0

Christian G. Bower, Nov 15 1998

nonn

Also the number of non-isomorphic connected multigraphs with loops with n edges and multiset density -1, where the multiset density of a multiset partition is the sum of the numbers of distinct vertices in each part minus the number of parts minus the number of vertices. - Gus Wiseman, Nov 28 2018

Alois P. Heinz, Table of n, a(n) for n = 0..1717
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
Gus Wiseman, Non-isomorphic representatives of the a(1) = 2 through a(5) = 35 connected multigraphs with loops with multiset density -1.
Index entries for sequences related to trees

Essentially the same as A036251.

Cf. A000055, A007718, A007719, A038052, A191646, A303837, A321155, A321229, A321254, A321256, A322111.

max = 30; B[] = 1; Do[B[x] = x*Exp[Sum[(B[x^k] + x^k)/k + O[x]^n, {k, 1, n}]] // Normal, {n, 1, max}]; A[x_] = B[x] - B[x]^2/2 + B[x^2]/2; CoefficientList[1 + A[x] + O[x]^max, x] (* Jean-François Alcover, Jan 28 2019 *)

G.f.: B(x) - B^2(x)/2 + B(x^2)/2, where B(x) is g.f. for A036249.

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

Original entry on oeis.org

1, 1, 1, 0, 2, 3, 0, 1, 10, 16, 0, 0, 12, 79, 125, 0, 0, 6, 162, 847, 1296, 0, 0, 1, 179, 2565, 11436, 16807, 0, 0, 0, 116, 4615, 47100, 185944, 262144, 0, 0, 0, 45, 5540, 121185, 987567, 3533720, 4782969, 0, 0, 0, 10, 4720, 220075, 3376450, 23315936, 76826061, 100000000

Offset: 0

Gus Wiseman, Nov 28 2018

			Triangle begins:
  1
  1     1
  0     2     3
  0     1    10    16
  0     0    12    79   125
  0     0     6   162   847  1296
  0     0     1   179  2565 11436 16807

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

Row sums are A322151. Last column is A000272.
Column sums are A062740.
Cf. A000664, A007718, A007719, A054923, A191646, A275421, A321254, A322114, A322115, A322137.

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[Subsets[multsubs[Range[k],2],{n}],And[Union@@#==Range[k],Length[csm[#]]==1]&]]],{n,0,6},{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 + 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

Terms a(28) and beyond from Andrew Howroyd, Nov 29 2018

A322151 Number of labeled connected graphs with loops with n edges (the vertices are {1,2,...,k} for some k).

Original entry on oeis.org

1, 2, 5, 27, 216, 2311, 30988, 499919, 9431026, 203743252, 4960335470, 134382267082, 4009794148101, 130668970606412, 4617468180528235, 175867725701333896, 7182126650899080024, 313063334893103361130, 14507460736615554141354, 712192629608088061633746

Offset: 0

Gus Wiseman, Nov 28 2018

nonn

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

Row sums of A322147. The unlabeled version is A191970.

Cf. A000664, A002905, A007718, A013922, A054923, A057500, A191646, A291842 (planar case), A321254, A322114, A322115.

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[Length[Select[Subsets[multsubs[Range[n+1],2],{n}],And[Union@@#==Range[Max@@Union@@#],Length[csm[#]]==1]&]],{n,5}]

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 + x + O(x*x^n))^binomial(j+1,2)))))} \\ Andrew Howroyd, Nov 28 2018

Terms a(7) and beyond from Andrew Howroyd, Nov 28 2018

A339160 Triangle read by rows: T(n,k) is the number of unlabeled nonseparable (or 2-connected) loopless multigraphs with n edges and k nodes (n >= 1, 2 <= k <= n + 1).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 3, 6, 3, 1, 0, 1, 4, 11, 11, 4, 1, 0, 1, 5, 22, 33, 23, 5, 1, 0, 1, 7, 38, 89, 96, 40, 7, 1, 0, 1, 8, 63, 212, 345, 234, 70, 8, 1, 0, 1, 10, 98, 463, 1083, 1146, 546, 110, 10, 1, 0, 1, 12, 151, 943, 3068, 4739, 3505, 1169, 176, 12, 1, 0

Offset: 1

Andrew Howroyd, Dec 05 2020

			Triangle T(n,k) begins (n edges >= 1, k vertices >= 2):
  1;
  1,  0;
  1,  1,   0;
  1,  1,   1,   0;
  1,  2,   2,   1,    0;
  1,  3,   6,   3,    1,    0;
  1,  4,  11,  11,    4,    1,    0;
  1,  5,  22,  33,   23,    5,    1,    0;
  1,  7,  38,  89,   96,   40,    7,    1,   0;
  1,  8,  63, 212,  345,  234,   70,    8,   1,  0;
  1, 10,  98, 463, 1083, 1146,  546,  110,  10,  1, 0;
  1, 12, 151, 943, 3068, 4739, 3505, 1169, 176, 12, 1, 0;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..210 (rows 1..20)

Column k=3 is A001399(n-3).
Row sums are A010357.
Cf. A046752, A191646, A339070.

T(n,2) = T(n,n) = 1.

A322152 Number of labeled connected multigraphs with loops with n edges (the vertices are {1,2,...,k} for some k).

Original entry on oeis.org

1, 2, 7, 39, 314, 3359, 45000, 725269, 13670256, 295099184, 7179749707, 194399095705, 5797793490859, 188855813757729, 6671188010874785, 254007814638737649, 10370334196814589256, 451923738493729293016, 20937747226064522726151, 1027666505638118490940059

Offset: 0

Gus Wiseman, Nov 28 2018

nonn

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

Row sums of A322148. The unlabeled version is A007719.

Cf. A000272, A000664, A007718, A191646, A191970, A322114, A322115, A322147, A322151.

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[Length[Select[multsubs[multsubs[Range[n+1],2],n],And[Union@@#==Range[Max@@Union@@#],Length[csm[#]]==1]&]],{n,5}]

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+1,2)))))} \\ Andrew Howroyd, Nov 28 2018

Terms a(7) and beyond from Andrew Howroyd, Nov 28 2018

A360866 Triangle read by rows: T(n,k) is the number of unlabeled connected loopless multigraphs with n edges on k nodes and degree >= 3 at each node, n >= 2, 1 <= k <= floor(2*n/3).

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 4, 7, 0, 1, 6, 19, 6, 0, 1, 8, 40, 37, 6, 0, 1, 10, 71, 135, 56, 0, 1, 12, 117, 366, 338, 35, 0, 1, 15, 184, 858, 1417, 494, 20, 0, 1, 17, 270, 1778, 4670, 3494, 492, 0, 1, 20, 387, 3413, 13125, 17355, 6047, 251

Offset: 2

Andrew Howroyd, Feb 24 2023

Terms may be computed using the tools geng, vcolg and multig in nauty with some additional processing to check the degrees of nodes.

			Triangle begins:
  0;
  0, 1;
  0, 1;
  0, 1,  1;
  0, 1,  3,   2;
  0, 1,  4,   7;
  0, 1,  6,  19,    6;
  0, 1,  8,  40,   37,     6;
  0, 1, 10,  71,  135,    56;
  0, 1, 12, 117,  366,   338,    35;
  0, 1, 15, 184,  858,  1417,   494,   20;
  0, 1, 17, 270, 1778,  4670,  3494,  492;
  0, 1, 20, 387, 3413, 13125, 17355, 6047, 251;
  ...

Brendan McKay and Adolfo Piperno, nauty and Traces.

Row sums are A360867.
Diagonal sums are A360868.
Cf. A046752, A191646, A360862 (loops allowed).

A322133 Regular triangle read by rows where T(n,k) is the number of non-isomorphic connected multiset partitions of weight n with k vertices.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 3, 2, 1, 0, 5, 8, 3, 1, 0, 7, 17, 12, 3, 1, 0, 11, 46, 45, 18, 4, 1, 0, 15, 94, 141, 76, 23, 4, 1, 0, 22, 212, 432, 333, 124, 30, 5, 1, 0, 30, 416, 1231, 1254, 622, 178, 37, 5, 1, 0, 42, 848, 3346, 4601, 2914, 1058, 252, 45, 6, 1

Offset: 0

Gus Wiseman, Nov 27 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.

			Triangle begins:
    1
    0    1
    0    2    1
    0    3    2    1
    0    5    8    3    1
    0    7   17   12    3    1
    0   11   46   45   18    4    1
    0   15   94  141   76   23    4    1
    0   22  212  432  333  124   30    5    1
    0   30  416 1231 1254  622  178   37    5    1
    0   42  848 3346 4601 2914 1058  252   45    6    1
Non-isomorphic representatives of the multiset partitions counted in row 4:
  {{1,1,1,1}}        {{1,1,2,2}}      {{1,2,3,3}}    {{1,2,3,4}}
  {{1},{1,1,1}}      {{1,2,2,2}}      {{1,3},{2,3}}
  {{1,1},{1,1}}      {{1},{1,2,2}}    {{3},{1,2,3}}
  {{1},{1},{1,1}}    {{1,2},{1,2}}
  {{1},{1},{1},{1}}  {{1,2},{2,2}}
                     {{2},{1,2,2}}
                     {{1},{2},{1,2}}
                     {{2},{2},{1,2}}

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

Row sums are A007718.

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

\\ Needs G(m,n) defined in A317533 (faster PARI).
InvEulerMTS(p)={my(n=serprec(p, x)-1, q=log(p), vars=variables(p)); sum(i=1, n, moebius(i)*substvec(q + O(x*x^(n\i)), vars, apply(v->v^i, vars))/i)}
T(n)={[Vecrev(p) | p <- Vec(1 + InvEulerMTS(y^n*G(n,n) + sum(k=0, n-1, y^k*(1 - y)*G(k,n))))]}
{ my(A=T(10)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Jan 15 2024

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

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 9, 16, 29, 56, 110, 222, 465, 1003, 2226, 5101, 12010, 29062, 72200, 183886, 479544, 1279228, 3486584, 9699975, 27520936, 79563707, 234204235, 701458966, 2136296638, 6611816700, 20784932424, 66333327604, 214819211047, 705650404444, 2350231740975

Offset: 0

Michael Joseph, Dec 10 2015

nonn

Also the number of skeletal 2-cliquish graphs with n vertices. See Einstein et al. link below.

a(n) is the sum of A265580(k) as k ranges from 0 to n. This is because there is a bijection between loopless multigraphs (V,E) satisfying |V| + |E| = k with no isolated vertices and loopless multigraphs (V,E) satisfying |V| + |E| = n with exactly n-k isolated vertices.

			For n = 4, the a(4) = 3 such multigraphs are the graph with four isolated vertices, the graph with three vertices and an edge between two of them, and the graph with two vertices connected by two 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, A192517, A265580, A265582.

\\ Needs G from A191646.
seq(n)={vector(n+1,i,1) + sum(k=1, n, concat(vector(n-k+1), G(n-k, k)))} \\ Andrew Howroyd, Feb 01 2020

a(n) = Sum_{k=0..n} A265580(k).
From Andrew Howroyd, Feb 01 2020: (Start)
a(n) = Sum_{i=1..n} A192517(i, n-i) for n > 0.
Euler transform of A265582. (End)

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

cp's OEIS Frontend

A014397 Number of loopless multigraphs with 7 nodes and n edges.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

A014398 Number of loopless multigraphs with 8 nodes and n edges.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

A036250 Number of trees of nonempty sets with n points. (Each node is a set of 1 or more points.)

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A322151 Number of labeled connected graphs with loops with n edges (the vertices are {1,2,...,k} for some k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A339160 Triangle read by rows: T(n,k) is the number of unlabeled nonseparable (or 2-connected) loopless multigraphs with n edges and k nodes (n >= 1, 2 <= k <= n + 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A322152 Number of labeled connected multigraphs with loops with n edges (the vertices are {1,2,...,k} for some k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A360866 Triangle read by rows: T(n,k) is the number of unlabeled connected loopless multigraphs with n edges on k nodes and degree >= 3 at each node, n >= 2, 1 <= k <= floor(2*n/3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A322133 Regular triangle read by rows where T(n,k) is the number of non-isomorphic connected multiset partitions of weight n with k vertices.

Views