cp's OEIS Frontend

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

%I A001173 M4010 N1662 #51 Jul 05 2024 16:12:42
%S A001173 1,5,52,1522,145984,48464496,56141454464,229148550030864,
%T A001173 3333310786076963968,174695272746749919580928,
%U A001173 33301710992539090379269318144,23278728241293494533015563325552128,60084295633556503802059558812644803074048,576025077880237078776946730871618386151571214336
%N A001173 Half the number of binary relations on n unlabeled points.
%D A001173 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.
%D A001173 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001173 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001173 Chai Wah Wu, <a href="/A001173/b001173.txt">Table of n, a(n) for n = 1..59</a>
%H A001173 R. L. Davis, <a href="https://dx.doi.org/10.1090/S0002-9939-1953-0055294-2">The number of structures of finite relations</a>, Proc. Amer. Math. Soc. 4 (1953), 486-495.
%H A001173 M. D. McIlroy, <a href="/A000088/a000088.pdf">Calculation of numbers of structures of relations on finite sets</a>, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]
%H A001173 W. Oberschelp, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002298732">Kombinatorische Anzahlbestimmungen in Relationen</a>, Math. Ann., 174 (1967), 53-78.
%F A001173 a(n) = A000595(n)/2. - _Sean A. Irvine_, Mar 16 2012
%t A001173 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];
%t A001173 edges[v_] := Sum[2 GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];
%t A001173 a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/(2 n!)];
%t A001173 Array[a, 12] (* _Jean-François Alcover_, Aug 01 2019, after _Andrew Howroyd_ in A000595 *)
%o A001173 (Python)
%o A001173 from itertools import product
%o A001173 from math import prod, factorial, gcd
%o A001173 from fractions import Fraction
%o A001173 from sympy.utilities.iterables import partitions
%o A001173 def A001173(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r,s) for r,s in product(p.keys(),repeat=2)),prod(q**p[q]*factorial(p[q]) for q in p)) for p in partitions(n)))>>1 # _Chai Wah Wu_, Jul 02 2024
%Y A001173 Cf. A000595, A001174.
%K A001173 nonn,nice
%O A001173 1,2
%A A001173 _N. J. A. Sloane_
%E A001173 More terms from _Vladeta Jovovic_, Apr 18 2000
%E A001173 a(13)-a(14) (based on A000595) from _Pontus von Brömssen_, Aug 04 2022