login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A284458 Number of pairs (f,g) of endofunctions on [n] such that the composite function gf has no fixed point. 2
1, 0, 2, 156, 16920, 2764880, 650696400, 210105425628, 89425255439744, 48588905856409920, 32845298636854828800, 27047610425293718239100, 26664178085975252011318272, 31009985808408471580603417296, 42017027730087624384021945067520 (list; graph; refs; listen; history; text; internal format)
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.

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

LINKS

Robert Israel, Table of n, a(n) for n = 0..214

StackExchance, Couple Probability.

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

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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 31 19:40 EDT 2020. Contains 334748 sequences. (Running on oeis4.)