cp's OEIS Frontend

A054921 Number of connected unlabeled symmetric relations (graphs with loops) having n nodes.

%I A054921 #35 Jul 10 2024 15:02:51
%S A054921 1,2,3,10,50,354,3883,67994,2038236,109141344,10693855251,
%T A054921 1934271527050,648399961915988,404093642681273382,
%U A054921 469756524755173254759,1022121472711196824292810,4176802133456105622904206409,32159648543645931290004658982846
%N A054921 Number of connected unlabeled symmetric relations (graphs with loops) having n nodes.
%C A054921 Number of non-isomorphic connected antichains of two-element multisets spanning a set of n vertices. Connected antichains are also called clutters.
%D A054921 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.
%H A054921 Alois P. Heinz, <a href="/A054921/b054921.txt">Table of n, a(n) for n = 0..86</a>
%H A054921 Edward A. Bender and E. Rodney Canfield, <a href="https://doi.org/10.1016/0095-8956(83)90040-0">Enumeration of connected invariant graphs</a>, Journal of Combinatorial Theory, Series B 34.3 (1983): 268-278. See p. 273.
%H A054921 V. A. Liskovets, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/LISK/Derseq.html">Some easily derivable sequences</a>, J. Integer Sequences, 3 (2000), #00.2.2.
%H A054921 Gus Wiseman, <a href="/A054921/a054921.png">A picture of all unlabeled connected simple spanning multiclutters for a(4)=50</a>
%F A054921 EULERi transform of A000666.
%e A054921 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
%t A054921 nn=8;
%t A054921 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!;
%t A054921 multing[t_,n_]:=Array[(t+#-1)/#&,n,1,Times];
%t A054921 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 *)
%o A054921 (Python)
%o A054921 from functools import lru_cache
%o A054921 from itertools import combinations
%o A054921 from math import prod, factorial, gcd
%o A054921 from fractions import Fraction
%o A054921 from sympy.utilities.iterables import partitions
%o A054921 from sympy import mobius, divisors
%o A054921 def A054921(n):
%o A054921     @lru_cache(maxsize=None)
%o A054921     def b(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum(((q>>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)))
%o A054921     @lru_cache(maxsize=None)
%o A054921     def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o A054921     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
%Y A054921 Cf. A000666. Row sums of A304311.
%K A054921 nonn,easy
%O A054921 0,2
%A A054921 _N. J. A. Sloane_, May 24 2000
%E A054921 More terms from _Vladeta Jovovic_, Jul 17 2000
%E A054921 Added a(0)=1 by _Gus Wiseman_, Jul 21 2016