A question on counting the almost (!) injective monotone functions of two sets

Question

Let's define a function almost injective $f: A \rightarrow B$ if for every $b \in B$ the number of elements with $f(a) = b$ is at most $2$. Let $M(n)$ be the number of almost injective monotone functions from a set $[n]$ to itself $[n] \rightarrow [n]$. How to compute $M(n)$ in a general case? Or as an example for $M(5)$?

Answer 1

As clarified in comments, you want the function to be weakly increasing.

To map $k$ pairs to the same element, you can choose $\binom{n-k}k$ positions for the $k$ pairs among the $k+(n-2k)=n-k$ pairs and singletons, and then you can choose $\binom n{n-k}$ values for the $n-k$ pairs and singletons, for a total of

$$ M(n)=\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}\binom n{n-k}\binom{n-k}k=\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}\frac{n!}{(n-2k)!k!^2} $$

functions. You could reach the same result by choosing $k$ values with zero preimages, $k$ values with two preimages and $n-2k$ values with one preimage.

In your example,

$$ M(5)=5!\left(\frac1{5!}+\frac1{3!}+\frac1{2!^2}\right)=1+20+30=51\;. $$

---

This is the answer I originally posted, when I'd overlooked the word “monotone”.

If $k$ pairs of elements are mapped to the same element, there are $\binom n{2k}$ ways to choose those elements, $\frac{(2k)!}{2^kk!}$ ways to group them into pairs, and $\frac{n!}{k!}$ ways to map the $k+(n-2k)=n-k$ pairs and singletons to different elements. Thus, the total number of almost injective functions from $[n]$ to $[n]$ is

$$ M(n)=\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}\frac{n!^2}{2^k(n-2k)!k!^2}\;. $$

In your example,

$$ M(5)=5!^2\left(\frac1{5!}+\frac1{2\cdot3!}+\frac1{4\cdot2!^2}\right)=2220\;. $$