A001173 Half the number of binary relations on n unlabeled points. (Formerly M4010 N1662)

1, 5, 52, 1522, 145984, 48464496, 56141454464, 229148550030864, 3333310786076963968, 174695272746749919580928, 33301710992539090379269318144, 23278728241293494533015563325552128, 60084295633556503802059558812644803074048, 576025077880237078776946730871618386151571214336

Offset

1,2

References

M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sept. 15, 1955, pp. 14-22.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=1..14.

R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.

M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]

W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.

Formula

a(n) = A000595(n)/2. - Sean A. Irvine, Mar 16 2012

Mathematica

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[2 GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/(2 n!)];
Array[a, 12] (* Jean-François Alcover, Aug 01 2019, after Andrew Howroyd in A000595 *)

Crossrefs

Cf. A000595, A001174.

Sequence in context: A322195 A216464 A279644 * A277202 A223248 A208303

Adjacent sequences: A001170 A001171 A001172 * A001174 A001175 A001176

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

More terms from Vladeta Jovovic, Apr 18 2000

a(13)-a(14) (based on A000595) from Pontus von Brömssen, Aug 04 2022

Status

approved