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,2

Comments

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

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

Formula

EULERi transform of A000666.

Example

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

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

Crossrefs

Cf. A000666. Row sums of A304311.

Sequence in context: A308112 A020098 A013081 * A192258 A052561 A181927

Adjacent sequences: A054918 A054919 A054920 * A054922 A054923 A054924

Keyword

nonn,easy

Author

N. J. A. Sloane, May 24 2000

Extensions

More terms from Vladeta Jovovic, Jul 17 2000

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

Status

approved