|
|
A186081
|
|
Number of binary relations R on {1,2,...,n} such that the transitive closure of R is the trivial relation.
|
|
2
|
|
|
1, 1, 4, 144, 25696, 18082560, 47025585664, 450955726792704, 16260917603754029056, 2253010420928564535951360, 1219004114245442237742488879104, 2601909995433633381004133738019815424, 22040854392120341022554569447470527813779456
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
For n >= 2, a(n) is the number of strongly connected binary relations on [n]. - Geoffrey Critzer, Dec 04 2023
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: 1 + s(2*x) - x where s(x) is the e.g.f. for A003030. (End)
|
|
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
|
Needs["Combinatorica`"];
f[list_] := Apply[Plus, Table[MatrixPower[list, n], {n, 1, Length[list]}]];
Join[{1}, Table[Length[Select[Map[Flatten, Map[f, Tuples[Strings[{0, 1}, n], n]]], FreeQ[#, 0] &]], {n, 1, 4}]]
(* Second program: *)
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
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|