A309980 - OEIS

%I #33 Jan 08 2021 08:46:45

%S 0,4,72,2608,272752,93847104,110518842048,454710381676032,

%T 6640565658505128832,348708024629593894001152,

%U 66538376166308068986316241408,46534722991725338264882258863095808,120139253095727581744381043433138973706240,1151909524447243687554850690730124812494959992832

%N Number of binary relations on n unlabeled nodes that are neither reflexive nor antireflexive.

%C Also the number of colored digraphs on n unlabeled nodes with nodes of exactly two colors. (Understand "(x,x) in the relation" for several nodes x as a special color!)

%H Andrew Howroyd, <a href="/A309980/b309980.txt">Table of n, a(n) for n = 1..50</a>

%F a(n) = A000595(n) - 2 * A000273(n) for n >= 1.

%e n=2: We label node 1 with (1,1) in the relation and node 2 with (2,2) not in the relation, and we have two differently labeled nodes and so a(2) = A053763(2) = 4.

%e n=3: We have exactly either one or two nodes x with (x,x) in the relation. In A328773 this labelings correspond to the color schemes [2,1] and [1,2], both represented by the column index 2. So we have a(3) = 2 * A328773(3,2) = 72.

%t 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 edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];

%t a[n_] := Module[{s = 0}, Do[t = 2^edges[p]; s += t*(1 - 2^(1 - Length[p]))* permcount[p], {p, IntegerPartitions[n]}]; s/n!];

%t Array[a, 14] (* _Jean-François Alcover_, Jan 08 2021, after _Andrew Howroyd_ *)

%o (PARI)

%o permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}

%o edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i], v[j]))) + sum(i=1, #v, v[i])}

%o a(n) = {my(s=0); forpart(p=n, my(t=2^edges(p)); s+=t*(1 - 2^(1-#p))*permcount(p)); s/n!} \\ _Andrew Howroyd_, Nov 02 2019

%Y Cf. A000595 (arbitrary binary relations), A000273 (digraphs, i.e. reflexive resp. antireflexive binary relations), A053763 (digraphs with distinguishing labeled nodes), A328773 (digraphs with given color scheme).

%K nonn

%O 1,2

%A _Peter Dolland_, Nov 02 2019