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,3

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.

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

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

Example

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.

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 *)

Prog

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

Crossrefs

Cf. A065440, A350558, A343700.

Sequence in context: A000725 A151614 A103042 * A260886 A142006 A233575

Adjacent sequences: A284455 A284456 A284457 * A284459 A284460 A284461

Keyword

nonn

Author

Robert FERREOL, Mar 27 2017

Status

approved