Results 1 to 4 of 4

Math Help - Pigeon Hole Proof

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    56

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    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).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    56
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    You are correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeon-hole Principle (3)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 5th 2011, 09:22 AM
  2. pigeon-hole
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 01:41 PM
  3. Pigeon Hole Principle Help!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 16th 2008, 11:14 PM
  4. Pigeon hole-proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 11th 2008, 08:34 AM
  5. Pigeon hole-proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 11th 2008, 01:02 AM

Search Tags


/mathhelpforum @mathhelpforum