cp's OEIS Frontend

A000250 Number of symmetric reflexive relations on n nodes: (1/2)*A000666.

%I A000250 M2868 N1153 #30 Jul 15 2024 10:22:56
%S A000250 1,3,10,45,272,2548,39632,1104306,56871880,5463113568,978181717680,
%T A000250 326167542296048,202701136710498400,235284321080559981952,
%U A000250 511531711735594715527360,2089424601541011618029114896,16084004145036771186002041099712,234026948449058790311618594954430848,6454432593140577452393525511509194184320
%N A000250 Number of symmetric reflexive relations on n nodes: (1/2)*A000666.
%D A000250 Harary, Frank; Palmer, Edgar M.; Robinson, Robert W.; Schwenk, Allen J.; Enumeration of graphs with signed points and lines. J. Graph Theory 1 (1977), no. 4, 295-308.
%D A000250 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 A000250 W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
%D A000250 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000250 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000250 Jean-François Alcover, <a href="/A000250/b000250.txt">Table of n, a(n) for n = 1..40</a>
%H A000250 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]
%t A000250 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 A000250 edges[v_] := Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]} ] + Sum[Quotient[v[[i]], 2] + 1, {i, 1, Length[v]}];
%t A000250 a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/(2  n!)];
%t A000250 a /@ Range[19] (* _Jean-François Alcover_, Jan 17 2020, after _Andrew Howroyd_ in A000666 *)
%o A000250 (Python)
%o A000250 from itertools import combinations
%o A000250 from math import prod, factorial, gcd
%o A000250 from fractions import Fraction
%o A000250 from sympy.utilities.iterables import partitions
%o A000250 def A000250(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum(((q>>1)+1)*r+(q*r*(r-1)>>1) for q, r in p.items())-1,prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # _Chai Wah Wu_, Jul 14 2024
%Y A000250 Cf. A000595, A001173, A001174.
%K A000250 nonn,nice
%O A000250 1,2
%A A000250 _N. J. A. Sloane_
%E A000250 More terms from _Vladeta Jovovic_, Apr 18 2000
%E A000250 More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 05 2007