Consider two sets $X$ and $Y$ with $|X| = m$ and $|Y| = n$ A function $f : X → Y$ is called almost-onto if $f$ misses at most one element of $Y$...

Question

Consider two sets $X$ and $Y$ with $|X| = m$ and $|Y| = n$ A function $f : X → Y$ is called almost-onto if $f$ misses at most one element of $Y$. Find and prove a formula for the number of almost onto functions from $X$ to $Y$.

• We had a general overview lecture of the Inclusion-Exclusion principle and how it relates to the addition principle as well as did several permutation-based problems involving permutations of certain sizes and finding how many total permutations fit a given criteria, although I do not see how that would help me with this proof. Any help is appreciated.

Answer 1

Have a look at the page twelvefold way on Wikipedia. It treats the case of onto (denoted as surjective) functions under various assumptions, which may help you get around some of the issues you are having. Then you can consider your problem as an extension. If the number of onto functions is $f(n,m)$ your answer should be $$n f(n-1,m)$$ i.e. you need to multiply the number of onto functions to a set of size $n-1$ with the number of $(n-1)$-subsets of $Y.$

Answer 2

It should be clear that if $n\ge1$ and $m<n-1,$ then there are no such functions. Likewise, if $n=0$ and $m>0,$ then there are no such functions. In the case $m=n=0,$ there is exactly one function $X\to Y,$ and it is necessarily onto.

Otherwise, $m\ge n-1\ge 0.$ Observe that there are $n$ subsets $Z$ of $Y$ such that $|Z|=n-1,$ and that an almost-onto function $X\to Y$ is either a map onto $Y$ or a map onto one of these sets $Z.$

As you can see in the answers to this question, for any integer $0\le k\le m,$ there are $$\sum_{j=0}^k(-1)^j\binom{k}j(k-j)^m$$ functions from a given $m$-element set onto a given $k$-element set. Hence, the number of almost-onto functions $X\to Y$ is $$\sum_{j=0}^n(-1)^j\binom{n}j(n-j)^m+n\sum_{j=0}^{n-1}(-1)^j\binom{n-1}j(n-1-j)^m.$$

In fact, this formula works for every case except the $n\ge1$ and $m<n-1$ case.

Answer 3

I’ll sketch the argument for counting the functions from $X$ onto $Y$; try to use it as a model to get the functions that map $X$ onto all of $Y$ except one point; you can then combine the two partial results.

There are altogether $n^m$ functions from $X$ to $Y$. For each $y\in Y$ we want to throw out the functions that don’t have $y$ in their ranges, i.e., the functions that map $X$ to $Y\setminus\{y\}$. For each $y\in Y$ there are $(n-1)^m$ such functions, and there are $n$ points in $Y$, so we’re throwing out $n(n-1)^m$ functions, leaving us with $n^m-n(n-1)^m$ functions. Unfortunately, if $y_1$ and $y_2$ are distinct points of $Y$, any function from $X$ to $Y$ whose range omits both $y_1$ and $y_2$ has been thrown out twice, once for $y_1$ and once for $y_2$. Thus, we’ve counted each of those functions $-1$ times: once in $n^m$, and $-2$ times in the correction term. We don’t want to count those functions at all, since they’re not onto $Y$, so we want to add them back in. There are $\binom{n}2$ pairs of elements of $Y$, and for each pair there are $(n-2)^m$ functions from $X$ to $Y$ whose ranges contain neither element of the pair, so our third approximation is

$$n^m-n(n-1)^m+\binom{n}2(n-2)^m=\binom{n}0(n-0)^m-\binom{n}1(n-1)^m+\binom{n}2(n-2)^m\;.$$

At this point you can probably guess that the final count is going to be

$$\sum_{k=0}^n\binom{n}k(-1)^k(n-k)^m\;.$$

To put this in more formal terms, for each $y\in Y$ let $\mathscr{A}_y$ be the set of functions from $X$ to $Y\setminus\{y\}$. Then $\bigcup_{y\in Y}\mathscr{A}_k$ is the set of functions from $X$ to $Y$ that are not onto $Y$, and the number of functions from $X$ onto $Y$ is therefore

$$n^m-\left|\bigcup_{y\in Y}\mathscr{A}_k\right|\;.$$

By the inclusion-exclusion principle this is equal to

$$n^m-\sum_{\varnothing\ne F\subseteq Y}(-1)^{|F|-1}\left|\bigcap_{y\in F}\mathscr{A}_y\right|\;.$$

Now $\bigcap_{y\in F}\mathscr{A}_y$ is just the set of functions from $X$ to $Y\setminus F$, so its cardinality is

$$|Y\setminus F|^m=(n-|F|)^m\;.$$

Moreover, for $k=1,\ldots,n$ there are $\binom{n}k$ subsets of $Y$ of cardinality $k$, so

$$\begin{align*} n^m-\sum_{\varnothing\ne F\subseteq Y}(-1)^{|F|-1}\left|\bigcap_{y\in F}\mathscr{A}_y\right|&=n^m-\sum_{k=1}^n(-1)^{k-1}\binom{n}k(n-k)^m\\ &=\binom{n}0(n-0)^m+\sum_{k=1}^n(-1)^k\binom{n}k(n-k)^m\\ &=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^m\;. \end{align*}$$