A322115 -id:A322115

A007719

Number of independent polynomial invariants of symmetric matrix of order n.

+10
12

1, 2, 4, 11, 30, 95, 328, 1211, 4779, 19902, 86682, 393072, 1847264, 8965027, 44814034, 230232789, 1213534723, 6552995689, 36207886517, 204499421849, 1179555353219, 6942908667578, 41673453738272, 254918441681030, 1588256152307002, 10073760672179505

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

Also, number of connected multigraphs with n edges (allowing loops) and any number of nodes.

Also the number of non-isomorphic connected multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018

LINKS

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

R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO] (2017) Table 63.

FORMULA

Inverse Euler transform of A007717.

EXAMPLE

From Gus Wiseman, Jul 18 2018: (Start)

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

(112233),

(1)(12233), (12)(1233), (112)(233), (123)(123),

(1)(2)(1233), (1)(12)(233), (1)(23)(123), (12)(13)(23),

(1)(2)(3)(123), (1)(2)(13)(23).

(End)

MATHEMATICA

mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];

EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++,

c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {};

For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];

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];

Kq[q_, t_, k_] := SeriesCoefficient[1/Product[g = GCD[t, q[[j]]]; (1 - x^(q[[j]]/g))^g, {j, 1, Length[q]}], {x, 0, k}];

RowSumMats[n_, m_, k_] := Module[{s = 0}, Do[s += permcount[q]* SeriesCoefficient[ Exp[Sum[Kq[q, t, k]/t x^t, {t, 1, n}]], {x, 0, n}], {q, IntegerPartitions[m]}]; s/m!];

A007717 = Table[Print[n]; RowSumMats[n, 2 n, 2], {n, 0, 20}];

Join[{1}, EULERi[Rest[A007717]]] (* Jean-François Alcover, Oct 29 2018, using Andrew Howroyd's code for A007717 *)

CROSSREFS

Row sums of A322115.

Cf. A002905, A007716, A007717, A007719, A020555, A050535, A053419, A076864, A191970, A316972, A316974.

KEYWORD

nonn,nice

AUTHOR

Colin Mallows

EXTENSIONS

a(0)=1 added by Alberto Tacchella, Jun 20 2011

a(7)-a(25) from Franklin T. Adams-Watters, Jun 21 2011

STATUS

approved

A333397

Array read by antidiagonals: T(n,k) is the number of connected k-regular multigraphs on n unlabeled nodes, loops allowed, n >= 0, k >= 0.

+10
9

1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 2, 1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 1, 1, 3, 4, 5, 1, 0, 0, 1, 0, 3, 0, 10, 0, 1, 0, 0, 1, 1, 4, 9, 26, 28, 17, 1, 0, 0, 1, 0, 4, 0, 47, 0, 97, 0, 1, 0, 0, 1, 1, 5, 17, 91, 291, 639, 359, 71, 1, 0, 0, 1, 0, 5, 0, 149, 0, 2789, 0, 1635, 0, 1, 0, 0

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,18

COMMENTS

This sequence can be derived from A167625 by inverse Euler transform.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..405 (first 28 antidiagonals)

FORMULA

Column k is the inverse Euler transform of column k of A167625.

EXAMPLE

Array begins:

=========================================================

n\k | 0 1 2 3 4 5 6 7 8

----+----------------------------------------------------

0 | 1 1 1 1 1 1 1 1 1 ...

1 | 1 0 1 0 1 0 1 0 1 ...

2 | 0 1 1 2 2 3 3 4 4 ...

3 | 0 0 1 0 4 0 9 0 17 ...

4 | 0 0 1 5 10 26 47 91 149 ...

5 | 0 0 1 0 28 0 291 0 1934 ...

6 | 0 0 1 17 97 639 2789 12398 44821 ...

7 | 0 0 1 0 359 0 35646 0 1631629 ...

8 | 0 0 1 71 1635 40264 622457 8530044 89057367 ...

9 | 0 0 1 0 8296 0 14019433 0 6849428873 ...

...

CROSSREFS

Columns k=3..8 (with interspersed 0's for odd k) are: A005967, A085549, A129430, A129432, A129434, A129436.

Cf. A167625 (not necessarily connected), A322115 (not necessarily regular), A328682 (loopless), A333330.

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Mar 18 2020

STATUS

approved

A322137

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

+10
8

1, 1, 3, 17, 140, 1524, 20673, 336259, 6382302, 138525780, 3384988809, 91976158434, 2751122721402, 89833276321440, 3179852538140115, 121287919647418118, 4959343701136929850, 216406753768138678671, 10037782414506891597734, 493175891246093032826160

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

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

P. S. Kolesnikov and B. K. Sartayev, On the special identities of Gelfand--Dorfman algebras, arXiv:2105.13815 [math.RA], 2021.

Gus Wiseman, The a(4) = 140 labeled connected graphs with 4 edges.

MATHEMATICA

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

PROG

(PARI)

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

CROSSREFS

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

KEYWORD

nonn

AUTHOR

Gus Wiseman, Nov 27 2018

EXTENSIONS

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

STATUS

approved

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.

+10
6

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,5

LINKS

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

EXAMPLE

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

MATHEMATICA

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}]

PROG

(PARI)

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

CROSSREFS

Row sums are A322151. Last column is A000272.

Column sums are A062740.

Cf. A000664, A007718, A007719, A054923, A191646, A275421, A321254, A322114, A322115, A322137.

KEYWORD

nonn,tabl

AUTHOR

Gus Wiseman, Nov 28 2018

EXTENSIONS

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

STATUS

approved

A322151

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

+10
6

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

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

MATHEMATICA

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}]

PROG

(PARI)

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

CROSSREFS

Row sums of A322147. The unlabeled version is A191970.

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

KEYWORD

nonn

AUTHOR

Gus Wiseman, Nov 28 2018

EXTENSIONS

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

STATUS

approved

A322152

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

+10
5

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

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

MATHEMATICA

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}]

PROG

(PARI)

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

CROSSREFS

Row sums of A322148. The unlabeled version is A007719.

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

KEYWORD

nonn

AUTHOR

Gus Wiseman, Nov 28 2018

EXTENSIONS

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

STATUS

approved

A327615

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

+10
4

1, 1, 1, 3, 2, 1, 1, 5, 8, 6, 2, 1, 1, 8, 19, 25, 16, 7, 2, 1, 1, 11, 40, 73, 73, 47, 19, 7, 2, 1, 1, 15, 77, 194, 263, 232, 133, 58, 20, 7, 2, 1, 1, 19, 132, 454, 835, 951, 719, 397, 164, 61, 20, 7, 2, 1, 1, 24, 217, 984, 2385, 3507, 3365, 2306, 1177, 490, 175, 62, 20, 7, 2, 1

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

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

LINKS

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

FORMULA

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

EXAMPLE

Triangle begins:

1, 1;

1, 3, 2, 1;

1, 5, 8, 6, 2, 1;

1, 8, 19, 25, 16, 7, 2, 1;

1, 11, 40, 73, 73, 47, 19, 7, 2, 1;

1, 15, 77, 194, 263, 232, 133, 58, 20, 7, 2, 1;

1, 19, 132, 454, 835, 951, 719, 397, 164, 61, 20, 7, 2, 1;

...

PROG

(PARI)

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])) }

CROSSREFS

Row sums are A007717.

Columns k=2..3 are A024206, A327728.

Cf. A136564, A290428, A309936, A322115.

KEYWORD

nonn,tabf

AUTHOR

Andrew Howroyd, Oct 23 2019

STATUS

approved

A360862

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

+10
4

1, 1, 2, 1, 4, 1, 7, 5, 1, 10, 20, 5, 1, 14, 48, 36, 1, 18, 99, 153, 30, 1, 23, 181, 481, 277, 17, 1, 28, 303, 1239, 1451, 323, 1, 34, 479, 2811, 5572, 2946, 193, 1, 40, 726, 5805, 17607, 17343, 3806, 71, 1, 47, 1055, 11148, 48401, 77708, 36872, 3188, 1, 54, 1492, 20219, 120018, 288476, 243007, 54386, 1496

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,3

COMMENTS

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

LINKS

Table of n, a(n) for n=2..66.

Brendan McKay and Adolfo Piperno, nauty and Traces

EXAMPLE

Triangle begins:

1;

1, 2;

1, 4;

1, 7, 5;

1, 10, 20, 5;

1, 14, 48, 36;

1, 18, 99, 153, 30;

1, 23, 181, 481, 277, 17;

1, 28, 303, 1239, 1451, 323;

1, 34, 479, 2811, 5572, 2946, 193;

1, 40, 726, 5805, 17607, 17343, 3806, 71;

1, 47, 1055, 11148, 48401, 77708, 36872, 3188;

1, 54, 1492, 20219, 120018, 288476, 243007, 54386, 1496;

...

CROSSREFS

Column 2 is A014616.

Row sums are A360863.

Diagonal sums are A360864.

Cf. A322115, A327615, A360866 (loopless).

KEYWORD

nonn,tabf

AUTHOR

Andrew Howroyd, Feb 24 2023

STATUS

approved

A360870

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

+10
4

1, 1, 2, 1, 4, 1, 7, 2, 1, 10, 8, 2, 1, 14, 19, 11, 1, 18, 40, 48, 7, 1, 23, 77, 154, 70, 5, 1, 28, 132, 421, 392, 71, 1, 34, 217, 1008, 1638, 690, 35, 1, 40, 340, 2210, 5623, 4548, 767, 16, 1, 47, 510, 4477, 16745, 22657, 8594, 566, 1, 54, 742, 8557, 44698, 92844, 64716, 11247, 226

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,3

COMMENTS

Columns k >= 3 correspond to the 2-connected graphs.

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

LINKS

Table of n, a(n) for n=2..66.

Brendan McKay and Adolfo Piperno, nauty and Traces.

EXAMPLE

Triangle begins:

1;

1, 2;

1, 4;

1, 7, 2;

1, 10, 8, 2;

1, 14, 19, 11;

1, 18, 40, 48, 7;

1, 23, 77, 154, 70, 5;

1, 28, 132, 421, 392, 71;

1, 34, 217, 1008, 1638, 690, 35;

1, 40, 340, 2210, 5623, 4548, 767, 16;

1, 47, 510, 4477, 16745, 22657, 8594, 566;

1, 54, 742, 8557, 44698, 92844, 64716, 11247, 226;

...

CROSSREFS

Column 2 is A014616.

Row sums are A360882.

Row sums except first column are A360871.

Cf. A046752, A322115, A360862, A360866.

KEYWORD

nonn,tabf

AUTHOR

Andrew Howroyd, Feb 25 2023

STATUS

approved

A322148

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

+10
3

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,5

LINKS

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

EXAMPLE

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

MATHEMATICA

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}]

PROG

(PARI)

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

CROSSREFS

Row sums are A322152. Last column is A000272.

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

KEYWORD

nonn,tabl

AUTHOR

Gus Wiseman, Nov 28 2018

EXTENSIONS

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

STATUS

approved