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