• Feb 3rd 2013, 05:55 AM
juliie
Let m ≥ n and let A = {1,2,...,m} and let B = {1,2,...,n}. In this exercise you will determine a formula for the number of surjective functions from A to B. For each i ∈ B, let Ai denote the set of all functions f : A → B such that i is not in the image of f, that is, for all x ∈ A we have f(x) 6= i. Thus the set of all functions from A to B which are not surjective is A1 ∪ A2 ∪ ··· ∪ An.

1. a) Let 1 ≤ k ≤ n. In how many ways can we choose integers i1,i2,...,ik such that 1 ≤ i1 < i2 < ··· < ik ≤ n?

b) Let 1 ≤ i1 < i2 < ··· < ik ≤ n. Show that |Ai1 ∩ Ai2∩ ··· ∩ Aik| = (n − k)^m.
• Feb 3rd 2013, 06:41 AM
Plato
Quote:

Originally Posted by juliie
Let m ≥ n and let A = {1,2,...,m} and let B = {1,2,...,n}. In this exercise you will determine a formula for the number of surjective functions from A to B. For each i ∈ B, let Ai denote the set of all functions f : A → B such that i is not in the image of f, that is, for all x ∈ A we have f(x) 6= i. Thus the set of all functions from A to B which are not surjective is A1 ∪ A2 ∪ ··· ∪ An.
1. a) Let 1 ≤ k ≤ n. In how many ways can we choose integers i1,i2,...,ik such that 1 ≤ i1 < i2 < ··· < ik ≤ n?

b) Let 1 ≤ i1 < i2 < ··· < ik ≤ n. Show that |Ai1 ∩ Ai2∩ ··· ∩ Aik| = (n − k)^m

It appears to me that you do indeed understand the process.

Thus I will give you the final answer, from which I hope you can put together your answer.

$\sum\limits_{k = 0}^m {\left( { - 1} \right)^k \binom{n}{k}\left( {n - k} \right)^m } = n^m - \left( {\sum\limits_{k = 1}^m {\left( { - 1} \right)^{k - 1} \binom{n}{k}\left( {n - k} \right)^m } } \right)$
• Feb 3rd 2013, 06:52 AM
juliie