Crazy Binomial Summation

Let $|X|=n$ and $|Y|=r$ , and let $S$ be the set of all functions from $X$ to $Y$ , so that $|S|=r^n$ . Suppose that $Y = \{y_1,y_2,...,y_r\}$ , and let $A_j$ be the set of functions $g \in S$ such that $y_j$ is not in the range of $g$ . Then $S_1 \cup S_2 \cup \cdots \cup S_r$ is the set of nonsurjective functions from $X$ to $Y$ . By the Inclusion-Exclusion Principle, $|S_1 \cup S_2 \cdots \cup S_r| \; = \; \sum_{k=1}^r (-1)^{k-1}\sum_{1 \le j_1 < j_2 < \cdots < j_k \le r}\big|S_{j_1} \cap S_{j_2} \cap \cdots \cap S_{j_k}\big|$ Now $\big| S_{j_1} \cap S_{j_2} \cap \cdots \cap S_{j_k}\big| \; = \; (r-k)^n$ and hence we deduce that $|S_1 \cup S_2 \cup \cdots \cup S_k| \; = \; \sum_{k=1}^r (-1)^{k-1} \binom{r}{k}(r-k)^n$ so that the number of surjective functions is $r^n - |S_1 \cup S_2 \cup \cdots \cup S_k| \; = \; r!f(r,n)$ Of course this means that $f(r,n) = 1$ when $r=n$ and $f(r,n) = 0$ when $r > n$ .