Displaying 1-10 of 11 results found.
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.
+10
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
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.
EXTENSIONS
a(0)=1 prepended and a(16)-a(25) added by Max Alekseyev, Jun 21 2011
Number of non-isomorphic T_0 set systems of weight n.
+10
42
1, 1, 1, 2, 4, 7, 16, 35, 82, 200, 517
COMMENTS
In a set system, two vertices are equivalent if in every block the presence of the first is equivalent to the presence of the second. The T_0 condition means that there are no equivalent vertices.
The weight of a set system is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
EXAMPLE
Non-isomorphic representatives of the a(1) = 1 through a(5) = 7 set systems:
1: {{1}}
2: {{1},{2}}
3: {{2},{1,2}}
{{1},{2},{3}}
4: {{1,3},{2,3}}
{{1},{2},{1,2}}
{{1},{3},{2,3}}
{{1},{2},{3},{4}}
5: {{1},{2,4},{3,4}}
{{2},{3},{1,2,3}}
{{2},{1,3},{2,3}}
{{3},{1,3},{2,3}}
{{1},{2},{3},{2,3}}
{{1},{2},{4},{3,4}}
{{1},{2},{3},{4},{5}}
CROSSREFS
Cf. A007716, A007718, A049311, A053419, A056156, A059201, A283877, A305854, A306006, A316980, A317757.
The squarefree dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted without multiplicity. Then a(n) is the number of non-isomorphic multiset partitions of weight n whose squarefree dual is strict (no repeated blocks).
+10
33
1, 1, 3, 7, 21, 55, 169, 496, 1582, 5080, 17073
COMMENTS
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
EXAMPLE
Non-isomorphic representatives of the a(1) = 1, a(2) = 3, and a(3) = 7 multiset partitions:
1: {{1}}
2: {{1,1}}
{{1},{1}}
{{1},{2}}
3: {{1,1,1}}
{{1},{1,1}}
{{1},{2,2}}
{{2},{1,2}}
{{1},{1},{1}}
{{1},{2},{2}}
{{1},{2},{3}}
Number of non-isomorphic strict T_0 multiset partitions of weight n.
+10
17
1, 1, 2, 6, 15, 40, 121, 353, 1107, 3550, 11818
COMMENTS
In a multiset partition, two vertices are equivalent if in every block the multiplicity of the first is equal to the multiplicity of the second. The T_0 condition means that there are no equivalent vertices.
The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.
EXAMPLE
Non-isomorphic representatives of the a(1) = 1 through a(4) = 15 multiset partitions:
1: {{1}}
2: {{1,1}}
{1},{2}}
3: {{1,1,1}}
{{1,2,2}}
{{1},{1,1}}
{{1},{2,2}}
{{2},{1,2}}
{{1},{2},{3}}
4: {{1,1,1,1}}
{{1,2,2,2}}
{{1},{1,1,1}}
{{1},{1,2,2}}
{{1},{2,2,2}}
{{1},{2,3,3}}
{{2},{1,2,2}}
{{1,1},{2,2}}
{{1,2},{2,2}}
{{1,3},{2,3}}
{{1},{2},{1,2}}
{{1},{2},{2,2}}
{{1},{2},{3,3}}
{{1},{3},{2,3}}
{{1},{2},{3},{4}}
Number of connected graphs with n edges with loops allowed.
+10
15
1, 2, 2, 6, 12, 33, 93, 287, 940, 3309, 12183, 47133, 190061, 796405, 3456405, 15501183, 71681170, 341209173, 1669411182, 8384579797, 43180474608, 227797465130, 1229915324579, 6790642656907, 38311482445514, 220712337683628, 1297542216770482, 7779452884747298
COMMENTS
Inverse Euler transform of A053419. The Multiset Transform gives the number of graphs with n edges (loops allowed) and k components (0<=k<=n):
1
0 2
0 2 3
0 6 4 4
0 12 15 6 5
0 33 36 24 8 6
0 93 111 64 33 10 7
0 287 324 207 92 42 12 8
0 940 1036 633 308 120 51 14 9
0 3309 3408 2084 966 409 148 60 16 10
0 12183 11897 6959 3243 1305 510 176 69 18 11
0 47133 43137 24415 10970 4432 1644 611 204 78 20 12
0 190061 163608 88402 38763 15125 5628 1983 712 232 87 22 13
0 796405 644905 332979 140671 53732 19316 6824 2322 813 260 96 24 14
0 3456405 2639871 1299054 529179 195517 68878 23515 8020 2661 914 288 105 26 15 (End)
EXAMPLE
a(1)=2: Either one node with the edge equal to a loop, or two nodes connected by the edge. a(2)=2: Either three nodes on a chain connected by the two edges, or two nodes connected by an edge, one node with a loop. Apparently multi-loops are not allowed (?). - R. J. Mathar, Jul 25 2017
PROG
(PARI) \\ See A322114 for InvEulerMT, G. 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
CROSSREFS
Cf. A000664, A002905, A007718, A050535, A053419, A054923, A191646, A191970, A275421, A322133, A322151, A322152.
Number of non-isomorphic strict multiset partitions of {1, 1, 2, 2, 3, 3, ..., n, n}.
+10
15
1, 1, 4, 14, 49, 173, 652, 2494
COMMENTS
Also the number of unlabeled multigraphs with n edges, allowing loops, spanning an initial interval of positive integers with no equivalent vertices (two vertices are equivalent if in every edge the multiplicity of the first is equal to the multiplicity of the second). For example, non-isomorphic representatives of the a(2) = 4 multigraphs are {(1,2),(1,3)}, {(1,1),(1,2)}, {(1,1),(2,2)}, {(1,1),(1,1)}.
EXAMPLE
Non-isomorphic representatives of the a(3) = 14 strict multiset partitions:
(112233),
(1)(12233), (11)(2233), (12)(1233), (112)(233),
(1)(2)(1233), (1)(12)(233), (1)(23)(123), (2)(11)(233), (11)(22)(33), (12)(13)(23),
(1)(2)(3)(123), (1)(2)(12)(33), (1)(2)(13)(23).
CROSSREFS
Cf. A001055, A007716, A007717, A007719, A020554, A020555, A045778, A050535, A053419, A061742, A094574, A162247, A316892, A316972.
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
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
FORMULA
Inverse Euler transform of A007717.
EXAMPLE
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}];
CROSSREFS
Cf. A002905, A007716, A007717, A007719, A020555, A050535, A053419, A076864, A191970, A316972, A316974.
Number of unlabeled simple graphs with n edges rooted at two noninterchangeable vertices.
+10
9
1, 4, 13, 43, 141, 467, 1588, 5544, 19966, 74344, 286395, 1141611, 4707358, 20063872, 88312177, 400980431, 1875954361, 9032585846, 44709095467, 227245218669, 1184822316447, 6330552351751, 34630331194626, 193785391735685, 1108363501628097, 6474568765976164
EXAMPLE
The a(1) = 4 cases correspond to a single edge which can be attached to zero, one or both of the roots.
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];
edges[v_, t_] := Product[With[{g = GCD[v[[i]], v[[j]]]}, t[v[[i]]*v[[j]]/ g]^g], {i, 2, Length[v]}, {j, 1, i-1}]*Product[With[{c = v[[i]]}, t[c]^Quotient[c-1, 2]*If[OddQ[c], 1, t[c/2]]], {i, 2, Length[v]}];
G[n_, x_, r_] := Module[{s = 0}, Do[s += permcount[p]*edges[Join[r, p], 1+x^#&], {p, IntegerPartitions[n]}]; s/n!];
seq[n_] := Module[{A = O[x]^n}, G[2n, x+A, {1, 1}]//CoefficientList[#, x]&];
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)))}
G(n, x, r)={my(s=0); forpart(p=n, s+=permcount(p)*edges(concat(r, Vec(p)), i->1+x^i)); s/n!}
seq(n)={my(A=O(x*x^n)); Vec((G(2*n, x+A, [1, 1])))}
Number of unlabeled connected simple graphs with n edges rooted at one distinguished vertex.
+10
5
1, 1, 2, 5, 13, 37, 114, 367, 1248, 4446, 16526, 63914, 256642, 1067388, 4590201, 20376849, 93240065, 439190047, 2126970482, 10579017047, 53983000003, 282345671127, 1512273916781, 8287870474339, 46438619162441, 265840311066579
FORMULA
G.f.: f(x)/g(x) where f(x) is the g.f. of A053419 and g(x) is the g.f. of A000664.
PROG
seq(n)={my(A=O(x*x^n)); Vec(G(2*n, x+A, [1])/G(2*n, x+A, []))}
Number of unlabeled simple graphs with n edges rooted at two indistinguishable vertices.
+10
4
1, 3, 9, 28, 87, 276, 909, 3086, 10879, 39821, 151363, 597062, 2442044, 10342904, 45301072, 204895366, 955661003, 4590214994, 22675644514, 115068710553, 599149303234, 3197694533771, 17475917252052, 97712883807625, 558481251055893, 3260409769087068
EXAMPLE
The a(1) = 3 cases correspond to a single edge which can be attached to zero, one or both of the roots.
PROG
seq(n)={my(A=O(x*x^n)); Vec((G(2*n, x+A, [1, 1]) + G(2*n, x+A, [2]))/2)}
Search completed in 0.010 seconds
|