<aside> ✌️ Natasha recently shared to me an interesting problem, sometimes asked in statistical interviews, which is surprisingly close to my own research field of graph theory. This particular problem appeared to be asked by Snapchat.
Consider $n$ boys and $n$ girls, each boy secretly loving a girl and vice versa. What is the probability that no couple could be formed?
An alternative mathematical formulation would be
Given two finite sets $A$ and $B$, each containing $n$ elements, how many pairs of functions $f \colon A \to B$ and $g \colon B \to A$ are there, such that their composition $h = g \circ f$ has no fixed points?
The problem appears to be on OEIS and has two math.stackexchange entries with several very nice attempts. Apparently, my approach with generating functions seems to be new.
</aside>
An example of a pair of functions with two mutual friendships 1-1 and 4-5. Each mutual friendship corresponds to a fixed point of the composition.
Here is the link to the OEIS sequence of the first several terms
This OEIS entry also contains two links to Math StackExchange discussions
An unexpected application of non-trivial combinatorics
I personally love such kinds of problems because $n^n$ denoting the total number of endofunctions (i.e. functions from a set to itself) is also the number of rooted trees with one marked vertices. There are nice combinatorial bijections which can be used for asymptotic analysis.
Let us start with an easier problem.
Given a finite set $A$ of size $n$, how many functions $f \colon A \to A$ are there without fixed points?
Clearly, for each of the $n$ points there are $(n-1)$ allowed possibilities of where the function $f$ would be pointing to. The number of functions is therefore $(n-1)^n$. The probability that a randomly chosen function does not have fixed points is asymptotically
$$ \lim_{n \to \infty} \dfrac{(n-1)^n}{n^n} = \lim_{n \to \infty} \left( 1 - \dfrac{1}{n} \right)^n = e^{-1} \, . $$
In this case, all the fixed points are formed independently, which is not the case in our problem.
Furthermore, if we look at the exact formula from OEIS, we observe
$$ \sum_{k=0}^n (-1)^k \binom{n}{k}^2 k! n^{2(n-k)} $$
which I guess could be obtained by some kind of inclusion-exclusion. However, asymptotic analysis of such formulae may be sometimes difficult, while can still be useful for numerical simulations. In this case, however, asymptotic analysis is possible because the summands do not give increasingly divergent contributions.
Let us take a closer look at each of the summands as $n \to \infty$.
$$ S_{k,n} := (-1)^k \binom{n}{k}^2 k! n^{2(n-k)} = (-1)^k\binom{n}k\frac{n!}{n^{2k}(n-k)!}
$$