A354439 - OEIS

%I #11 Jun 13 2022 08:52:53

%S 1,1,11,445,62915,33191761,68513225711,562467034238845,

%T 18442237738757867675,2417685596975700938954281,

%U 1267626420876674359067163133991,2658442047280176152683906485150512245,22300713296975051923525143874710129389413715

%N Number of binary relations on [n] such that every component has at least one cycle.

%C Let A be a binary relation on [n].  Let M(A) be the unique maximal subset of [n] such that A restricted to M is nilpotent.  Then a(n) is the number of relations on [n] such that M is the empty set.

%F E.g.f.:  A(x)/B(x) where A(x) is the e.g.f. for A002416 and B(x) is the e.g.f. for A003024.

%e a(2)=11 because all 16 binary relations on [2] have the desired property except these 5:  {{0, 0}, {0, 0}}, {{0, 0}, {0, 1}}, {{0, 0}, {1, 0}},

%e {{0, 1}, {0, 0}}, {{1, 0}, {0, 0}}.

%t nn = 12; a[p_, k_] := If[p == k, 1,Sum[(2^k - 1)^n (2^(k (p - n - k))) Binomial[p, k] a[p - k, n], {n, 1, p - k}]];g[x_] := 1 + (Table[Sum[a[p, k], {k, 1, p}], {p, 1, nn}] Table[x^i/i!, {i, 1, nn}] // Total);h[x_] := Sum[2^(n^2) x^n/n!, {n, 0, nn}];Range[0, nn]! CoefficientList[Series[h[x]/g[x], {x, 0, nn}], x]

%Y Cf. A002416, A003024.

%K nonn

%O 0,3

%A _Geoffrey Critzer_, May 28 2022