HMIC 2024 Problem 4

Given a positive integer $n$, let $[n]=\{1,2, \ldots, n\}$.

• Let $a_{n}$ denote the number of functions $f:[n] \rightarrow[n]$ such that $f(f(i)) \geq i$ for all $i$.
• Let $b_{n}$ denote the number of ordered set partitions of [ $n$ ], i.e., the number of ways to pick an integer $k$ and an ordered $k$-tuple of pairwise disjoint nonempty sets $\left(A_{1}, \ldots, A_{k}\right)$ whose union is [ $n$ ].

Prove that $a_{n}=b_{n}$.