cp's OEIS Frontend

A186081 Number of binary relations R on {1,2,...,n} such that the transitive closure of R is the trivial relation.

%I A186081 #49 May 07 2024 08:16:14
%S A186081 1,1,4,144,25696,18082560,47025585664,450955726792704,
%T A186081 16260917603754029056,2253010420928564535951360,
%U A186081 1219004114245442237742488879104,2601909995433633381004133738019815424,22040854392120341022554569447470527813779456
%N A186081 Number of binary relations R on {1,2,...,n} such that the transitive closure of R is the trivial relation.
%C A186081 For n >= 2, a(n) is the number of strongly connected binary relations on [n]. - _Geoffrey Critzer_, Dec 04 2023
%F A186081 From _Geoffrey Critzer_, Dec 04 2023: (Start)
%F A186081 For n >= 2, a(n) = A003030(n)*2^n = A361269(n,1).
%F A186081 E.g.f.: 1 + s(2*x) - x where s(x) is the e.g.f. for A003030. (End)
%e A186081 a(2)=4 because there are four relations on {1,2} whose transitive closure is {(1,1), (1,2), (2,1), (2,2)}. They are the three nontransitive relations,{(1,2), (2,1)}, {(1,2), (2,1), (2,2)}, {(1,1), (1,2), (2,1)} and the trivial relation itself.
%t A186081 Needs["Combinatorica`"];
%t A186081 f[list_] := Apply[Plus, Table[MatrixPower[list,n], {n,1,Length[list]}]];
%t A186081 Join[{1}, Table[Length[Select[Map[Flatten, Map[f, Tuples[Strings[{0, 1}, n], n]]], FreeQ[#, 0] &]], {n, 1, 4}]]
%t A186081 (* Second program: *)
%t A186081 a[ n_] := If[ n < 1, Boole[n == 0], With[{triv = matnk[n, 2^n^2 - 1]}, Sum[ Boole[triv === transitiveClosure[ matnk[n, k]]], {k, 0, 2^n^2 - 1}]]]; matnk[n_, k_] := Partition[ IntegerDigits[ k, 2, n^2], n]; transitiveClosure[x_] := FixedPoint[ Sign@(# + Dot[#, x]) &, x, Length@x]; (* _Michael Somos_, Mar 08 2012 *)
%Y A186081 Cf. A002416, A003030, A070322, A361269.
%K A186081 nonn,nice
%O A186081 0,3
%A A186081 _Geoffrey Critzer_, Feb 12 2011
%E A186081 a(0)=1 prepended by _Alois P. Heinz_, Aug 31 2015
%E A186081 a(6) from _Bert Dobbelaere_, Feb 16 2019
%E A186081 a(7)-a(12) from _Geoffrey Critzer_, Dec 04 2023