A054921
Number of connected unlabeled symmetric relations (graphs with loops) having n nodes.
Original entry on oeis.org
1, 2, 3, 10, 50, 354, 3883, 67994, 2038236, 109141344, 10693855251, 1934271527050, 648399961915988, 404093642681273382, 469756524755173254759, 1022121472711196824292810, 4176802133456105622904206409, 32159648543645931290004658982846
Offset: 0
A000666(n) = Number of increasing sequences of pairs ((x_1,y_1),...,(x_k,y_k)) such that: Sum(x_i)=n and 1<=y_i<=a(x_i+1) for all i. For example the A000666(3)=20 sequences are {((1,1),(1,1),(1,1)), ((1,1),(1,1),(1,2)), ((1,1),(1,2),(1,2)), ((1,2),(1,2),(1,2)); ((1,1),(2,1)), ((1,1),(2,2)), ((1,1),(2,3)), ((1,2),(2,1)), ((1,2),(2,2)), ((1,2),(2,3)); ((3,1)), ((3,2)), ((3,3)), ((3,4)), ((3,5)), ((3,6)), ((3,7)), ((3,8)), ((3,9)), ((3,10))}. - _Gus Wiseman_, Jul 21 2016
- Bender, Edward A., and E. Rodney Canfield. "Enumeration of connected invariant graphs." Journal of Combinatorial Theory, Series B 34.3 (1983): 268-278. See p. 273.
- Alois P. Heinz, Table of n, a(n) for n = 0..86
- Edward A. Bender and E. Rodney Canfield, Enumeration of connected invariant graphs, Journal of Combinatorial Theory, Series B 34.3 (1983): 268-278. See p. 273.
- V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.
- Gus Wiseman, A picture of all unlabeled connected simple spanning multiclutters for a(4)=50
-
nn=8;
unlabeledSimpleMluts[n_Integer]:=unlabeledSimpleMluts[n]=Total[Power[2,PermutationCycles[Ordering[Map[Sort,Select[Tuples[Range[n],2],OrderedQ]/.Table[i->Part[#,i],{i,n}]]],Length]]&/@Permutations[Range[n]]]/n!;
multing[t_,n_]:=Array[(t+#-1)/#&,n,1,Times];
ReplaceAll[a/@Range[0,nn],Solve[Table[unlabeledSimpleMluts[n]==If[n===0,a[0],Total[Function[ptn,Times@@(multing[a[First[#]],Length[#]]&/@Split[ptn])]/@IntegerPartitions[n]]],{n,0,nn}],a/@Range[0,nn]][[1]]] (* Gus Wiseman, Jul 21 2016 *)
-
from functools import lru_cache
from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
from sympy import mobius, divisors
def A054921(n):
@lru_cache(maxsize=None)
def b(n): return int(sum(Fraction(1<>1)+1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
@lru_cache(maxsize=None)
def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
return sum(mobius(d)*c(n//d) for d in divisors(n,generator=True))//n if n else 1 # Chai Wah Wu, Jul 10 2024
A303831
Birooted graphs: number of unlabeled connected graphs with n nodes rooted at 2 indistinguishable roots.
Original entry on oeis.org
0, 1, 3, 16, 98, 879, 11260, 230505, 7949596, 483572280, 53011686200, 10589943940654, 3880959679322754, 2623201177625659987, 3286005731275218388682, 7663042204550840483139108, 33407704152242477510352455230, 273327599183687887638526170380380
Offset: 1
A294783
Number of trees with n bicolored nodes and f nodes of the first color. Triangle T(n,f) read by rows, 0<=f<=n.
Original entry on oeis.org
1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 4, 6, 4, 2, 3, 9, 15, 15, 9, 3, 6, 20, 43, 51, 43, 20, 6, 11, 48, 116, 175, 175, 116, 48, 11, 23, 115, 329, 573, 698, 573, 329, 115, 23, 47, 286, 918, 1866, 2626, 2626, 1866, 918, 286, 47, 106, 719, 2609, 5978, 9656, 11241, 9656, 5978, 2609, 719, 106, 235, 1842
Offset: 0
The triangle starts
1;
1, 1;
1, 1, 1;
1, 2, 2, 1;
2, 4, 6, 4, 2;
3, 9, 15, 15, 9, 3;
6, 20, 43, 51, 43, 20, 6;
11, 48, 116, 175, 175, 116, 48, 11;
23, 115, 329, 573, 698, 573, 329, 115, 23;
47, 286, 918, 1866, 2626, 2626, 1866, 918, 286, 47;
106, 719,2609, 5978, 9656,11241, 9656,5978,2609,719,106;
235,1842,
-
R(n, y)={my(v=vector(n)); v[1]=1; for(k=1, n-1, my(p=(1+y)*v[k]); my(q=Vec(prod(j=0, poldegree(p,y), (1/(1-x*y^j) + O(x*x^(n\k)))^polcoeff(p,j)))); v=vector(n, j, v[j] + sum(i=1, (j-1)\k, v[j-i*k] * q[i+1]))); v;}
M(n)={my(B=(1+y)*x*Ser(R(n,y))); 1 + B - (B^2 - substvec(B, [x,y], [x^2,y^2]))/2}
{ my(A=M(10)); for(n=0, #A-1, print(Vecrev(polcoeff(A, n)))) } \\ Andrew Howroyd, May 12 2018
A126100
Number of rooted connected unlabeled graphs on n nodes.
Original entry on oeis.org
0, 1, 1, 3, 11, 58, 407, 4306, 72489, 2111013, 111172234, 10798144310, 1944301471861, 650202565436890, 404697467417019634, 470133531223369393920, 1022561022228933341815171, 4177761667636803276899047351, 32163582481439081597751699343141, 468019937132164016636736323752098741
Offset: 0
For 3 nodes G is either a path (2 kinds of nodes) or a triangle (one kind of node), for a total of a(3) = 3.
For the 5-vertex graphs we have 2 * 1 orbit, 6 * 2 orbits, 8 * 3 orbits, 5 * 4 orbits for a total of 2 + 12 + 24 + 20 = 58.
-
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_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
g[n_, r_] := (s = 0; Do[s += permcount[p]*(2^(r*Length[p] + edges[p])), {p, IntegerPartitions[n]}]; s/n!);
seq[m_] := Sum[g[n-1, 1] x^(n-1), {n, 0, m}]/Sum[g[n-1, 0] x^(n-1), {n, 0, m}] + O[x]^m // CoefficientList[#, x]& // Prepend[#, 0]&;
seq[20] (* Jean-François Alcover, Jul 09 2018, after Andrew Howroyd *)
-
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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
g(n,r) = {my(s=0); forpart(p=n, s+=permcount(p)*(2^(r*#p+edges(p)))); s/n!}
seq(n)={concat([0], Vec(Ser(vector(n, n, g(n-1,1)))/Ser(vector(n, n, g(n-1,0)))))} \\ Andrew Howroyd, May 03 2018
Showing 1-4 of 4 results.
Comments