A191646
Triangle read by rows: T(n,k) = number of connected multigraphs with n >= 0 edges and 1 <= k <= n+1 vertices, with no loops allowed.
Original entry on oeis.org
1, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 5, 3, 0, 1, 4, 11, 11, 6, 0, 1, 6, 22, 34, 29, 11, 0, 1, 7, 37, 85, 110, 70, 23, 0, 1, 9, 61, 193, 348, 339, 185, 47, 0, 1, 11, 95, 396, 969, 1318, 1067, 479, 106, 0, 1, 13, 141, 771, 2445, 4457, 4940, 3294, 1279, 235
Offset: 0
Triangle T(n,k) (with rows n >= 0 and columns k >= 1) begins as follows:
1;
0, 1;
0, 1, 1;
0, 1, 2, 2;
0, 1, 3, 5, 3;
0, 1, 4, 11, 11, 6;
0, 1, 6, 22, 34, 29, 11;
...
- Andrew Howroyd, Table of n, a(n) for n = 0..1274 (terms 0..119 from R. J. Mathar)
- R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO], 2017; see Section 4.
- Brendan McKay and Adolfo Piperno, nauty and Traces. [nauty and Traces are programs for computing automorphism groups of graphs and digraphs.]
- B. D. McKay and A. Piperno, Practical Graph Isomorphism, II, J. Symbolic Computation 60 (2013), 94-112.
- Gordon Royle, Small Multigraphs.
- Gus Wiseman, Illustration of the 33 connected multigraphs counted in row 5.
Cf.
A000664,
A007718,
A036250,
A050535,
A191646,
A191970,
A275421,
A317672,
A322114,
A322133,
A322152.
-
EulerT(v)={my(p=exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1); Vec(p/x,-#v)}
InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(serchop( sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i), 1))}
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,x)={sum(i=2, #v, sum(j=1, i-1, my(g=gcd(v[i],v[j])); g*x^(v[i]*v[j]/g))) + sum(i=1, #v, my(t=v[i]); ((t-1)\2)*x^t + if(t%2,0,x^(t/2)))}
G(n,m)={my(s=0); forpart(p=n, s+=permcount(p)*EulerT(Vec(edges(p,x) + O(x*x^m), -m))); s/n!}
R(n)={Mat(apply(p->Col(p+O(y^n),-n), InvEulerMT(vector(n, k, 1 + y*Ser(G(k,n-1), y)))))}
{ my(A=R(10)); for(n=1, #A, for(k=1, n, print1(A[n,k], ", "));print) } \\ Andrew Howroyd, May 14 2018
A191970
Number of connected graphs with n edges with loops allowed.
Original entry on oeis.org
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
Offset: 0
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
Cf.
A000664,
A002905,
A007718,
A050535,
A053419,
A054923,
A191646,
A191970,
A275421,
A322133,
A322151,
A322152.
-
\\ 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
A368099
Triangle read by rows where T(n,k) is the number of non-isomorphic k-element sets of finite nonempty multisets with cardinalities summing to n, or strict multiset partitions of weight n and length k.
Original entry on oeis.org
1, 0, 1, 0, 2, 1, 0, 3, 4, 1, 0, 5, 12, 5, 1, 0, 7, 28, 22, 5, 1, 0, 11, 66, 83, 31, 5, 1, 0, 15, 134, 252, 147, 34, 5, 1, 0, 22, 280, 726, 620, 203, 35, 5, 1, 0, 30, 536, 1946, 2283, 1069, 235, 35, 5, 1, 0, 42, 1043, 4982, 7890, 5019, 1469, 248, 35, 5, 1
Offset: 0
Triangle begins:
1
0 1
0 2 1
0 3 4 1
0 5 12 5 1
0 7 28 22 5 1
0 11 66 83 31 5 1
0 15 134 252 147 34 5 1
0 22 280 726 620 203 35 5 1
0 30 536 1946 2283 1069 235 35 5 1
0 42 1043 4982 7890 5019 1469 248 35 5 1
...
Row n = 4 counts the following representatives:
. {{1,1,1,1}} {{1},{1,1,1}} {{1},{2},{1,1}} {{1},{2},{3},{4}}
{{1,1,1,2}} {{1},{1,1,2}} {{1},{2},{1,2}}
{{1,1,2,2}} {{1},{1,2,2}} {{1},{2},{1,3}}
{{1,1,2,3}} {{1},{1,2,3}} {{1},{2},{3,3}}
{{1,2,3,4}} {{1},{2,2,2}} {{1},{2},{3,4}}
{{1},{2,2,3}}
{{1},{2,3,4}}
{{1,1},{1,2}}
{{1,1},{2,2}}
{{1,1},{2,3}}
{{1,2},{1,3}}
{{1,2},{3,4}}
Counting connected components instead of edges gives
A321194.
For set multipartitions we have
A334550.
Cf.
A255903,
A296122,
A302545,
A306005,
A317532,
A317775,
A317794,
A317795,
A319560,
A368094,
A368095.
-
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]&/@sps[Range[n]]],{s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
Table[Length[Union[brute /@ Select[mpm[n],UnsameQ@@#&&Length[#]==k&]]], {n,0,5},{k,0,n}]
-
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
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}
K(q, t, k)={EulerT(Vec(sum(j=1, #q, my(g=gcd(t, q[j])); g*x^(q[j]/g)) + O(x*x^k), -k))}
G(n)={my(s=0); forpart(q=n, my(p=sum(t=1, n, y^t*subst(x*Ser(K(q, t, n\t))/t, x, x^t))); s+=permcount(q)*exp(p-subst(subst(p, x, x^2), y, y^2))); s/n!}
T(n)={[Vecrev(p) | p <- Vec(G(n))]}
{ my(A=T(10)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 11 2024
Showing 1-3 of 3 results.
Comments