

A186081


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


0




OFFSET

0,3


LINKS

Table of n, a(n) for n=0..6.


EXAMPLE

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.


MATHEMATICA

f[list_] := Apply[Plus, Table[MatrixPower[list, n], {n, 1, Length[list]}]]; Table[Length[Select[Map[Flatten, Map[f, Tuples[Strings[{0, 1}, n], n]]], FreeQ[#, 0] &]], {n, 0, 4}]
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 *)


CROSSREFS

Cf. A002416.
Sequence in context: A186418 A122747 A069135 * A138176 A203424 A055209
Adjacent sequences: A186078 A186079 A186080 * A186082 A186083 A186084


KEYWORD

nonn,nice,more


AUTHOR

Geoffrey Critzer, Feb 12 2011


EXTENSIONS

a(0)=1 prepended by Alois P. Heinz, Aug 31 2015
a(6) from Bert Dobbelaere, Feb 16 2019


STATUS

approved



