A001173 Half the number of binary relations on n unlabeled points.

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

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice

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

• Chai Wah Wu, Table of n, a(n) for n = 1..59
• 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.

Crossrefs

Cf. A000595, A001174.

Programs

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

Python

from itertools import product
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A001173(n): return int(sum(Fraction(1<>1 # Chai Wah Wu, Jul 02 2024

Formula

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

Extensions

More terms from Vladeta Jovovic, Apr 18 2000

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