For $m,n\ge0$ let $O(m,n)$ be the number of onto functions
a) Explain why $O(m,n)=0$ when $m\lt n$ I said: since O is an onto function it implies that for all elements of n there is atleast one m with f(m)=n. Therefore if $m\lt n$ there will be atleast one m where no f(m)=n exists.
b)For $m\ge1$ what is $O(m,1)$? I said its $\sum (-1)^k $$1\choose 1-k$$(1-k)^m$
c)Suppose $m\ge n \gt 1$. Give argument to justify the recurrence $O(m,n)=nO(m-1,n-1)+nO(m-1,n) $
I dont know how to do this?
For b) if $f$ is a function from $\{1,2, \dots , m\}$ onto $\{1\}$ then $f(x) = 1$ for any $x $ in $\{1,2, \dots , m\}$ hence the only function is the constant function $f(x) = 1$.
For c) consider $f:\{1,2, \dots , m\} \rightarrow \{1,2, \dots , n \}$ such that $f$ is onto and $f(m)$ is not equal to $f(x)$ for any $1 \leq x < m$. Then $f(m)$ has $n$ possible images and $f$ restricted to $\{1,2, \dots , m-1\}$ is an onto function from $\{1,2, \dots , m-1\}$ into a set of size $n-1$. This gives the $n O(m-1,n-1)$ term. A very similar argument for the case $f(m) = f(x)$ for some $x \not = m$ gives the other term.