A007717 - OEIS

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

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

OFFSET

0,2

COMMENTS

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

REFERENCES

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

LINKS

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

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.

EXAMPLE

a(2) = 7 (here - denotes an edge, = denotes a pair of parallel edges and o is a loop):

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)

MATHEMATICA

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 *)

PROG

(PARI) \\ See A318951 for RowSumMats

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

(PARI) \\ See A339065 for G.

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

CROSSREFS

Row n=2 of A331485.