Thread: Pigeon Hole Proof

On a homework assignment I was given the following:

How many functions are there from {1,...,n} to {1,...,n} that are not 1-to-1?

I immediately thought the answer to this question was zero. I tried proving this with the pigeon hole principal. I said let there be n boxes and let there be n balls. I then have n/n = 1, which tells me that there is one ball in each box which then tells me that there is no function that is not one to one. Are my assumptions correct?

What about the function f(n) = 1?

Edit: It's easy to find the number of all functions and the number of 1-to-1 functions (the latter are permutations).

Would it be the same problem to count the number of possible functions from {1,...,n} to {1,...,n} and then subtract the number that are one-to-one? If that's the case, I think the number of possible functions is n^n (since there are n choices in the range that each of the n items in the domain can be mapped to), and the number of functions that are one-to-one would be n! (n choices for 1, n-1 choices for 2, etc. like you said). So it might be n^n - n!

You are correct.