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

%I #54 Jan 20 2023 05:28:53

%S 1,0,2,156,16920,2764880,650696400,210105425628,89425255439744,

%T 48588905856409920,32845298636854828800,27047610425293718239100,

%U 26664178085975252011318272,31009985808408471580603417296,42017027730087624384021945067520

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

%C 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).

%C 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.

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

%H Robert Israel, <a href="/A284458/b284458.txt">Table of n, a(n) for n = 0..214</a>

%H Math StackExchange, <a href="https://math.stackexchange.com/questions/713370/an-unexpected-application-of-non-trivial-combinatorics">An unexpected application of non-trivial combinatorics</a>, 2014.

%H Math StackExchange, <a href="https://math.stackexchange.com/questions/982134/couple-probability">Couple Probability</a>, 2014.

%H Eric Weisstein's MathWorld, <a href="http://mathworld.wolfram.com/ConfluentHypergeometricFunctionoftheSecondKind.html">Confluent Hypergeometric Function of the Second Kind</a>

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

%F a(n) = A343700(n)/A350558(n). - _Dan Eilers_, Jan 17 2023

%e For two boys A,B and two girls A',B', the a(2) possibilities are:

%e A loves A' who loves B who loves B' who loves A;

%e A loves B' who loves B who loves A' who loves A.

%p a:=n->add((-1)^k*binomial(n,k)^2*k!*n^(2*(n-k)),k=0..n):

%p seq(a(n),n=0..15);

%t Table[Sum[(-1)^k Binomial[n,k]^2 * k! * n^(2*(n - k)), {k, 0, n}], {n, 1, 15}] (* _Indranil Ghosh_, Mar 27 2017 *)

%t Table[HypergeometricU[-n, 1, n^2], {n, 1, 15}] (* _Jean-François Alcover_, Mar 29 2017 *)

%o (PARI) a(n) = sum(k=0, n, (-1)^k * binomial(n,k)^2 * k! * n^(2*(n-k))); \\ _Michel Marcus_, Apr 04 2017

%Y Cf. A065440, A350558, A343700.

%K nonn

%O 0,3

%A _Robert FERREOL_, Mar 27 2017