A284458 Number of pairs (f,g) of endofunctions on [n] such that the composite function gf has no fixed point.

1, 0, 2, 156, 16920, 2764880, 650696400, 210105425628, 89425255439744, 48588905856409920, 32845298636854828800, 27047610425293718239100, 26664178085975252011318272, 31009985808408471580603417296, 42017027730087624384021945067520

Offset: 0

Author

Robert FERREOL, Mar 27 2017

Keywords

• nonn

Comments

Consider n boys and n girls, each boy secretly loving a girl and vice versa. The probability that no couple could be formed is a(n)/n^(2n).

a(n) is the number of pairs of binary matrices n X n (M, N), M having only one 1 per row, N having only one 1 per column, such that M + N has no coefficient equal to 2.

Limit_{n -> infinity} a(n)/n^(2n) = 1/e.

Examples

			For two boys A,B and two girls A',B', the a(2) possibilities are:
A loves A' who loves B who loves B' who loves A;
A loves B' who loves B who loves A' who loves A.
		

Links

• Robert Israel, Table of n, a(n) for n = 0..214
• Math StackExchange, An unexpected application of non-trivial combinatorics, 2014.
• Math StackExchange, Couple Probability, 2014.
• Eric Weisstein's MathWorld, Confluent Hypergeometric Function of the Second Kind

Crossrefs

Cf. A065440, A350558, A343700.

Programs

Maple

a:=n->add((-1)^k*binomial(n,k)^2*k!*n^(2*(n-k)),k=0..n):
seq(a(n),n=0..15);

Mathematica

Table[Sum[(-1)^k Binomial[n,k]^2 * k! * n^(2*(n - k)), {k, 0, n}], {n, 1, 15}] (* Indranil Ghosh, Mar 27 2017 *)
Table[HypergeometricU[-n, 1, n^2], {n, 1, 15}] (* Jean-François Alcover, Mar 29 2017 *)

PARI

a(n) = sum(k=0, n, (-1)^k * binomial(n,k)^2 * k! * n^(2*(n-k))); \\ Michel Marcus, Apr 04 2017

Formula

a(n) = Sum_{k=0..n} (-1)^k * binomial(n,k)^2 * k! * n^(2*(n-k)).

a(n) = A343700(n)/A350558(n). - Dan Eilers, Jan 17 2023