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

1, 2, 3, 10, 50, 354, 3883, 67994, 2038236, 109141344, 10693855251, 1934271527050, 648399961915988, 404093642681273382, 469756524755173254759, 1022121472711196824292810, 4176802133456105622904206409, 32159648543645931290004658982846

Offset: 0

Author

N. J. A. Sloane, May 24 2000

Keywords

• nonn
• easy

Comments

Number of non-isomorphic connected antichains of two-element multisets spanning a set of n vertices. Connected antichains are also called clutters.

Examples

			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
		

References

• 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.

Links

• 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

Crossrefs

Cf. A000666. Row sums of A304311.

Programs

Mathematica

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 *)

Python

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

Formula

EULERi transform of A000666.

Extensions

More terms from Vladeta Jovovic, Jul 17 2000

Added a(0)=1 by Gus Wiseman, Jul 21 2016