|
|
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.
|
|
83
|
|
|
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
|
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
|
Huaien Li and David C. Torney, Enumeration of unlabelled multigraphs, Ars Combin. 75 (2005) 171-188. MR2133219.
|
|
EXAMPLE
|
a(2) = 7 (here - denotes an edge, = denotes a pair of parallel edges and o is a loop):
oo
o o
o-
o -
=
--
- -
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)
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];
|
|
PROG
|
(PARI) \\ See A318951 for RowSumMats
seq(n)={my(A=O(x*x^n)); Vec(G(2*n, x+A, [1]))} \\ Andrew Howroyd, Nov 22 2020
|
|
CROSSREFS
|
Cf. A000664, A002620, A007716, A007719, A020555, A050531, A050532, A050535, A052171, A053418, A053419, A094574, A316972, A316974, A318951, A339065.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(0)=1 prepended and a(16)-a(25) added by Max Alekseyev, Jun 21 2011
|
|
STATUS
|
approved
|
|
|
|