login
Number of nonisomorphic connected unlabeled binary relations on n nodes.
3

%I #25 Sep 11 2018 14:08:11

%S 1,2,7,86,2818,285382,96324549,112087100482,458071928280897,

%T 6665704296529088252,349377209492194571020053,

%U 66602723163954144515240479674,46557323273646194397778583902876038,120168498151800396724425973133360413846262,1152049915423012273792614840793828654424980146983

%N Number of nonisomorphic connected unlabeled binary relations on n nodes.

%H Andrew Howroyd, <a href="/A054919/b054919.txt">Table of n, a(n) for n = 0..50</a>

%H V. A. Liskovets, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/LISK/Derseq.html">Some easily derivable sequences</a>, J. Integer Sequences, 3 (2000), #00.2.2.

%F Inverse Euler transform of A000595.

%e Nonisomorphic connected relations on set {1,2} are {2r1}, {1r1,2r1}, {2r1,2r2}, {1r1,2r1,2r2}, {1r2,2r1}, {1r1,1r2,2r1}, {1r1,1r2,2r1,2r2} so a(2)=7.

%t nn=7; c=Join[{1,2}, Table[CycleIndex[Join[PairGroup[SymmetricGroup[n],Ordered], Permutations[Range[n^2-n+1,n^2]],2],s] /. Table[s[i]->2, {i,1,n^2-n}], {n,2,nn}]]; f[x_]:=Sum[a[n]x^n,{n,0,nn}]; b=Sum[c[[n+1]]x^n, {n,0,nn}]; sol=SolveAlways[b==Normal[Series[Product[1/(1-x^i)^a[i], {i,1,nn}], {x,0,nn}]], x]; Table[a[n], {n,1,nn}]/.sol (* _Geoffrey Critzer_, Mar 31 2013 *)

%Y Cf. A000595.

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_, May 24 2000

%E More terms from _Vladeta Jovovic_, Jul 16 2000

%E a(0)=1 prepended and a(13)-a(14) from _Andrew Howroyd_, Sep 10 2018