Results 1 to 7 of 7

Math Help - What does it mean to "count" bijections

  1. #1
    Junior Member
    Joined
    Jul 2008
    Posts
    51

    What does it mean to "count" bijections

    Count the bijections from A to B, given that |A|=|B|= n.

    homework hint: No proof required. Count the bijections from {1,2} to {1,2}, then count the bijections from {1,2,3} to {1,2,3}, etc. When you are confident you know the formula for the number of bijections from {1,2,...,n} to {1,2,...n}, then write it down.

    My question: what does counting bijections mean? I thought a function was either a bijection or not =|
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by crabchef View Post
    Count the bijections from A to B, given that |A|=|B|= n.

    homework hint: No proof required. Count the bijections from {1,2} to {1,2}, then count the bijections from {1,2,3} to {1,2,3}, etc. When you are confident you know the formula for the number of bijections from {1,2,...,n} to {1,2,...n}, then write it down.

    My question: what does counting bijections mean? I thought a function was either a bijection or not =|

    It means you have to count all the functions that are bijections between two given sets with n elements each. Try it with n = 1,2,3,4 and check whether you can find out a general pattern. Hint: factorial
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jul 2008
    Posts
    51
    Thanks for the response. I now understand what it means to count a bijection, but I still don't really understand what's going on here.

    Let's say n=1, then we have {1} to {1}...There's only one function here that works right? f(x)=x?
    Let's say n=2, then we have {1,2} to {1,2}...don't we still only have one function that works, f(x)=x?

    I don't understand the problem =(
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by crabchef View Post
    Let's say n=1, then we have {1} to {1}...There's only one function here that works right? f(x)=x?
    Let's say n=2, then we have {1,2} to {1,2}...don't we still only have one function that works, f(x)=x?(
    When you say “I don't understand the problem”, that is clearly the case.
    There are two bijections from \{1,2\}\to\{1,2\} they are \{\{1,1),(2,2)\}~\&~\{(1,2),(2,1)\}.

    There are 3!=6 bijections from \{1,2,3\}\to\{1,2,3\}.

    So in general, your answer for finite sets is simply n!.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2008
    Posts
    51
    I think the part that I don't understand is, how did you come up with (1,1),(2,2) and (1,2),(2,1) are bijections of {1,2} to {1,2}?

    Edit: Ah, I think I get it. When we say how many bijections are there from {1,2} to {1,2}, are we just asking how many different ways can we match numbers from one set to another? Like 1 can either go to 1 or 2. If the set was {1,2,3} then 1 can go to 1, 2, or 3? This would make sense to me...and gives me n! as an anwer

    Thanks for the help guys!!
    Last edited by crabchef; August 1st 2010 at 04:13 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16
    Yes, that's what bijections are. More formally, if you have these two sets, a bijective function between them is one that is one-to-one and onto.

    One-to-one means that it connects exactly 1 element from set A and goes to exactly 1 element in set B.
    Onto is when for every element x in set B, we have 1 or more elements in A that go to x.

    1 ------- 2
    2 ------- 1 is a bijection from {1,2,3} to {1,2,3}
    3 ------- 3

    1 ------- 2
    2 ------- 2 is not a bijection since it is neither one to one, nor onto
    3 ------- 3
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    No one mentioned it so far, so I will point out the obvious: counting bijections in this case is the same as counting permutations.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 17th 2011, 02:50 PM
  2. Replies: 1
    Last Post: September 16th 2011, 01:08 AM
  3. Replies: 2
    Last Post: June 4th 2011, 12:11 PM
  4. Replies: 2
    Last Post: April 24th 2011, 07:01 AM
  5. Replies: 1
    Last Post: October 25th 2010, 04:45 AM

Search Tags


/mathhelpforum @mathhelpforum