A052171 -id:A052171 - cp's OEIS frontend

A007717 Number of symmetric polynomial functions of degree n of a symmetric matrix (of indefinitely large size) under joint row and column permutations. Also number of multigraphs with n edges (allowing loops) on an infinite set of nodes.

1, 2, 7, 23, 79, 274, 1003, 3763, 14723, 59663, 250738, 1090608, 4905430, 22777420, 109040012, 537401702, 2723210617, 14170838544, 75639280146, 413692111521, 2316122210804, 13261980807830, 77598959094772, 463626704130058, 2826406013488180, 17569700716557737

Offset: 0

Colin Mallows

nonn

Euler transform of A007719.
Also the number of non-isomorphic multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}. - Gus Wiseman, Jul 18 2018
Number of distinct n X 2n matrices with integer entries and rows sums 2, up to row and column permutations. - Andrew Howroyd, Sep 06 2018
a(n) is the number of unlabeled loopless multigraphs with n edges rooted at one vertex. - Andrew Howroyd, Nov 22 2020

			a(2) = 7 (here - denotes an edge, = denotes a pair of parallel edges and o is a loop):
  oo
  o o
  o-
  o -
  =
  --
  - -
From _Gus Wiseman_, Jul 18 2018: (Start)
Non-isomorphic representatives of the a(2) = 7 multiset partitions of {1, 1, 2, 2}:
  (1122),
  (1)(122), (11)(22), (12)(12),
  (1)(1)(22), (1)(2)(12),
  (1)(1)(2)(2).
(End)
From _Gus Wiseman_, Jan 08 2024: (Start)
Non-isomorphic representatives of the a(1) = 1 through a(3) = 7 rooted loopless multigraphs (root shown as singleton):
  {{1}}  {{1},{1,2}}  {{1},{1,2},{1,2}}
         {{1},{2,3}}  {{1},{1,2},{1,3}}
                      {{1},{1,2},{2,3}}
                      {{1},{1,2},{3,4}}
                      {{1},{2,3},{2,3}}
                      {{1},{2,3},{2,4}}
                      {{1},{2,3},{4,5}}
(End)

Huaien Li and David C. Torney, Enumerations of Multigraphs, 2002.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Mateo Díaz, Dmitriy Drusvyatskiy, Jack Kendrick, and Rekha R. Thomas, Invariant Kernels: Rank Stabilization and Generalization Across Dimensions, arXiv:2502.01886 [math.OC], 2025. See p. 43.
Huaien Li and David C. Torney, Enumeration of unlabelled multigraphs, Ars Combin. 75 (2005) 171-188. MR2133219.
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO] (2017) table 67.

Row n=2 of A331485.

Cf. A000664, A002620, A007716, A007719, A020555, A050531, A050532, A050535, A052171, A053418, A053419, A094574, A316972, A316974, A318951, A339065.

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!];
a[n_] := RowSumMats[n, 2n, 2];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 25}] (* Jean-François Alcover, Oct 27 2018, after Andrew Howroyd *)

\\ See A318951 for RowSumMats
a(n)=RowSumMats(n, 2*n, 2); \\ Andrew Howroyd, Sep 06 2018

\\ See A339065 for G.
seq(n)={my(A=O(x*x^n)); Vec(G(2*n, x+A, [1]))} \\ Andrew Howroyd, Nov 22 2020

More terms from Vladeta Jovovic, Jan 26 2000

a(0)=1 prepended and a(16)-a(25) added by Max Alekseyev, Jun 21 2011

A138107 Infinite square array: T(n,k) = number of directed multigraphs with loops with n arcs and k vertices; read by falling antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 2, 6, 1, 0, 1, 2, 10, 10, 1, 0, 1, 2, 11, 31, 19, 1, 0, 1, 2, 11, 47, 90, 28, 1, 0, 1, 2, 11, 51, 198, 222, 44, 1, 0, 1, 2, 11, 52, 269, 713, 520, 60, 1, 0, 1, 2, 11, 52, 291, 1270, 2423, 1090, 85, 1, 0, 1, 2, 11, 52, 295, 1596, 5776, 7388, 2180, 110, 1, 0

Offset: 0

Benoit Jubin, May 03 2008

Partial sums of the rows of A136564.

			The array begins:
   1, 1,   1,    1,     1,     1,     1,     1,     1, ...
   0, 1,   2,    2,     2,     2,     2,     2,     2, ...
   0, 1,   6,   10,    11,    11,    11,    11,    11, ...
   0, 1,  10,   31,    47,    51,    52,    52,    52, ...
   0, 1,  19,   90,   198,   269,   291,   295,   296,  296, ...
   0, 1,  28,  222,   713,  1270,  1596,  1697,  1719, 1723, ...
   0, 1,  44,  520,  2423,  5776,  8838, 10425, 10922, ...
   0, 1,  60, 1090,  7388, 24032, 46384, ...
   0, 1,  85, 2180, 21003, 93067, ...
   0, 1, 110, 4090, ...
   ...

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

Columns k=0..4 are: A000007, A000012, A005993, A050927, A050929.
Main diagonal is A362387.
Cf. A052171, A136564, A333361.

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)^(2*g))) * prod(i=1, #v, t(v[i])^v[i])}
G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)/edges(p,i->1-x^i)); s/n!}
T(n)={Mat(vector(n+1, k, Col(O(y*y^n) + G(k-1, y + O(y*y^n)))))}
{my(A=T(10)); for(n=1, #A, print(A[n,]))} \\ Andrew Howroyd, Oct 22 2019

T(n,k) = Sum_{p=0..k} A136564(n,p).

If k >= 2n, T(n,k) = A052171(n).

More terms from Vladeta Jovovic and Benoit Jubin, Sep 10 2008

A104209 Number of labeled directed multigraphs with n arrows and no vertex of degree 0.

Original entry on oeis.org

1, 3, 39, 819, 23949, 898947, 41212155, 2232057171, 139455901101, 9873341493231, 781184921112075, 68309191570851759, 6541702440222052137, 680922615974259589527, 76544749927261960908807, 9241807764375868372683255, 1192762017796744530286451865

Offset: 0

Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Mar 13 2005

nonn

These are the dimensions of the homogeneous components of a commutative graded Hopf algebra generalizing quasi-symmetric functions.

			a(1)=3, the three graphs being (1 -> 2), (2 -> 1) and (1 -> 1).

J.-C. Novelli, J.-Y. Thibon and N. M. Thiéry, Algèbres de Hopf de graphes [Hopf algebras of graphs], C.R. Acad. Sci. Paris (Comptes Rendus Mathématique), 339 (2004), 607-610.

Cf. A052171 (counts same objects up to labeling).

Cf. A020561, A120945.

d:=proc(n) local m;sum(binomial(m^2+n-1,n)/2^(m+1),m=0..infinity);end;

f[n_] := Sum[ Binomial[m^2 + n - 1, n]/2^(m + 1), {m, 0, Infinity}]; Table[ f[n], {n, 0, 15}] (* Robert G. Wilson v, Mar 16 2005 *)
Table[Sum[Sum[(-1)^(k-j)*Binomial[k,j]*Binomial[j^2+n-1,n],{j,0,k}],{k,0,2*n}],{n,0,20}] (* Vaclav Kotesovec, May 03 2015, much faster *)

a(n) = Sum_{m >=0} binomial(m^2+n-1, n)/2^(m+1).
G.f.: Sum_{m >= 0} (1-x)^(-m^2)/2^(m+1). Row sums of A120945. - Vladeta Jovovic, Sep 25 2006
a(n) ~ c * 2^(2*n) * n! / (sqrt(n) * (log(2))^(2*n)), where c = 0.432167265869761794333243584356866417673557873163120324347... = 2^(log(2)/8 - 1) / (sqrt(Pi) * log(2)). - Vaclav Kotesovec, May 03 2015, updated Mar 21 2018

Corrected and extended by Robert G. Wilson v, Mar 16 2005

Offset corrected by Vaclav Kotesovec, May 03 2015

A136564 Array read by rows: T(n,k) is the number of directed multigraphs with loops with n arcs, k vertices, and no vertex of degree 0.

Original entry on oeis.org

1, 1, 1, 5, 4, 1, 1, 9, 21, 16, 4, 1, 1, 18, 71, 108, 71, 22, 4, 1, 1, 27, 194, 491, 557, 326, 101, 22, 4, 1, 1, 43, 476, 1903, 3353, 3062, 1587, 497, 111, 22, 4, 1, 1, 59, 1030, 6298, 16644, 22352, 17035, 7982, 2433, 555, 111, 22, 4, 1, 1, 84, 2095, 18823, 72064

Offset: 1

Benoit Jubin, Apr 14 2008

Length of the n^th row: 2n.

			1, 1;
1, 5, 4, 1;
1, 9, 21, 16, 4, 1;
1, 18, 71, 108, 71, 22, 4, 1;
1, 27, 194, 491, 557, 326, 101, 22, 4, 1;
1, 43, 476, 1903, 3353, 3062, 1587, 497, 111, 22, 4, 1;
1, 59, 1030, 6298, 16644, 22352, 17035, 7982, 2433, 555, 111, 22, 4, 1;

Row sums: A052171. Partial row sums: A138107.

Sums of the first m entries of each row: A005993 (m=2), A050927 (m=3), A050929 (m=4).

T(n,1) = 1 if n > 0.
T(n,2n) = 1 if n > 0.
T(n,2n-1) = 4 if n >= 2.
T(n,2n-k) = A144047(k) for n large enough (conjecturally, n >= 2k is enough).
T(n,2) = (n^3 + 6*n^2 + 11*n - 6)/12 + ((n+2)/4)[n even]. (the bracket means that the second term is added if and only if n is even). - Benoit Jubin, Mar 31 2012

More terms from Benoit Jubin and Vladeta Jovovic, Sep 08 2008

A137975 Row sums of A139621, number of connected directed multigraphs with loops and no vertex of degree 0, with n arcs.

Original entry on oeis.org

1, 2, 8, 32, 167, 928, 5924, 40211, 293370, 2255406, 18201706, 153176115, 1339271815, 12124484941, 113362749476, 1092329626380, 10827837622018, 110249198676581, 1151562885666429, 12324860339781102, 135026515460855978, 1512882677086123938, 17321462912397361409, 202503301170606347695, 2415733704608822524946, 29387239261415606708127

Offset: 0

Benoit Jubin, May 01 2008, May 10 2008

nonn

Inverse Euler transform of A052171.

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

Row sums of A139621.

Cf. A052171, A139627.

\\ See A139621 for G, InvEulerMT.
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

Data corrected to match A052171. - R. J. Mathar, Jul 25 2017

A139627 Number of strongly connected directed multigraphs with loops allowed and with n arcs.

Original entry on oeis.org

1, 1, 2, 4, 12, 37, 162, 738, 3928, 22436, 138716, 911529, 6339770, 46336941, 354453138, 2826472249, 23423053967, 201179882629, 1786791372857, 16377359709120, 154644691266520, 1502016160624186, 14985219655673207, 153377735526218010, 1608741204839374373

Offset: 0

Benoit Jubin, May 01 2008

nonn

The term a(0)=1 can be interpreted as either a singleton vertex or the graph with no vertices. - Andrew Howroyd, Jan 14 2022

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

Row sums of A139622.

Cf. A052171, A350489, A350752.

\\ See PARI link in A350489 for program code.
A139627seq(20) \\ Andrew Howroyd, Jan 14 2022

3 more terms from R. J. Mathar, Aug 04 2017

Terms a(7) and beyond from Andrew Howroyd, Jan 14 2022

A121137 Number of labeled directed multigraphs (without loops) with n arcs and no vertex of degree 0.

Original entry on oeis.org

1, 2, 27, 572, 16787, 631362, 28980861, 1570956872, 98212870233, 6956704585554, 550626446263423, 48163137319172436, 4613554511554200251, 480324019903607680066, 54004504167811544647161, 6521368218660772789452944, 841771274136198763040518633

Offset: 0

Vladeta Jovovic, Sep 06 2006

Nathaniel Johnston, Table of n, a(n) for n = 0..50
Math StackExchange, Marko Riedel et al., Labeled multigraphs
Marko Riedel, Proof of closed form by Egorychev method.

Cf. A052170 (unlabeled analog), A104209, A052171.

seq(sum(binomial(m*(m-1)+n-1,n)/2^(m+1),m=0..infinity),n=0..10);
# alternate program
A121137:= n -> add(add(binomial(m, q)*(-1)^(m-q)*binomial(n+q*(q-1)-1, n), q=0..m), m=0..2*n):
seq(A121137(n), n=0..20); # Marko Riedel, Jan 26 2025

a(n) = Sum_{m>=0} binomial(m*(m-1)+n-1,n)/2^(m+1).

a(n) = Sum_{m=0..2n} Sum_{q=0..m} binomial(m,q)*(-1)^(m-q)*binomial(n+q*(q-1)-1,n). - Marko Riedel, Jan 26 2025

A364088 Number of directed multigraphs with loops containing n edges and an infinite number of vertices modulo isomorphism and reversal of all edge directions.

Original entry on oeis.org

1, 2, 9, 37, 186, 985, 5953, 38689, 271492, 2016845, 15767277, 128792803, 1094819196, 9652396448, 88040449618, 829019941267, 8044691126159, 80322444793338, 824036583310711, 8675576699596604, 93627696274152013

Offset: 0

Saibal Mitra, Jul 04 2023

nonn

MathOverflow, Answer to question on counting directed graphs

Cf. A052171 (without identifying graphs obtained from each other by reversal of all edge directions).

cp's OEIS Frontend

A007717 Number of symmetric polynomial functions of degree n of a symmetric matrix (of indefinitely large size) under joint row and column permutations. Also number of multigraphs with n edges (allowing loops) on an infinite set of nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A138107 Infinite square array: T(n,k) = number of directed multigraphs with loops with n arcs and k vertices; read by falling antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A104209 Number of labeled directed multigraphs with n arrows and no vertex of degree 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A136564 Array read by rows: T(n,k) is the number of directed multigraphs with loops with n arcs, k vertices, and no vertex of degree 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A137975 Row sums of A139621, number of connected directed multigraphs with loops and no vertex of degree 0, with n arcs.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A139627 Number of strongly connected directed multigraphs with loops allowed and with n arcs.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A121137 Number of labeled directed multigraphs (without loops) with n arcs and no vertex of degree 0.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A364088 Number of directed multigraphs with loops containing n edges and an infinite number of vertices modulo isomorphism and reversal of all edge directions.

Views