Question 38
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 $(A_{1}, \ldots, A_{k})$ whose union is $[n]$.
Prove that $a_{n}=b_{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 $(A_{1}, \ldots, A_{k})$ whose union is $[n]$.
Prove that $a_{n}=b_{n}$.