Results 1 to 7 of 7

Math Help - Sets and bijections

  1. #1
    Member
    Joined
    Sep 2005
    Posts
    84

    Smile Sets and bijections

    My Question is

    Suppose A is a set with \left | A \right |=n
    How many functions are there from A to A which are not bijections ?

    I don't quite understand how to work this question out.

    any help is appreichated

    thanks

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by rpatel View Post
    Suppose A is a set with \left | A \right |=n
    How many functions are there from A to A which are not bijections?
    Given a finite set \left | A \right |=n then there are n! bijections from A to A.
    There are n^n functions from A to A.
    So what is the answer to your question?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Can you answer how many functions there are from A to A which *are* bijections?
    Last edited by Defunkt; December 28th 2009 at 10:29 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    oops, fixed.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Sep 2005
    Posts
    84
    ok so this is the answer n^{n}-n!

    thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,396
    Thanks
    1846
    Do you understand how Plato got those numbers?

    To construct a function from A to A, we have to map each member of A into something in A. For each member of A, then, we could choose each of the n members of A to map into. There are, of course, "n" ways to do that. Since there are n members of A, and we have n choices for each, by the "fundamental counting principle" we multiply each n by all the others: n multiplied by itself n times is n^n.

    Now, if a function from A to itself (or from one set to another of the same cardinality) is injective (one to one) it is also surjective (onto) and so a bijection. To construct an injective function from A to A, we choose a single member of A and then can choose any of the n members of A to map it to. There are n ways to do that. Now choose a second member of A. We can map it to any member of A except the one we just mapped the first member into. There are n-1 ways to do that. Now choose a third member of A. We can map it into any member of A except the first two. There are n-2 ways to do that. Continue that way through all members of A. We see that there are n(n-1)(n-2)\cdot\cdot\cdot 3(2)(1)= n! ways to do that.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2005
    Posts
    84
    thank you for the explanation. I understand my question now.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Bijections
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 14th 2010, 12:13 PM
  2. Proof regarding injections and bijections
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 19th 2010, 04:41 PM
  3. bijections
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: June 3rd 2010, 08:37 PM
  4. Bijections
    Posted in the Calculus Forum
    Replies: 7
    Last Post: March 6th 2009, 09:29 AM
  5. Counting and Bijections
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: November 11th 2007, 06:43 AM

Search Tags


/mathhelpforum @mathhelpforum