1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How many one-to-one functions f are possible?

  1. Mar 20, 2012 #1
    1. The problem statement, all variables and given/known data

    Suppose that |A| = n and |B| = m with n ≤ m. How many one-to-one functions f are possible with f: A → B?

    2. Relevant equations
    If |A| = |B| = m how many different bijections f: A → B are possible?
    Answer: m!

    3. The attempt at a solution
    I really do not know how to start off the question. If someone can help me get started into this equation that would be great!

    The relevant equation I did manage to get. but I do not know how to solve the problem when the size of A is not equal to the size of B.
  2. jcsd
  3. Mar 20, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    Well, you know f is a bijection into the subset of B given by f(A). Now you just have to figure out the number of ways to choose a subset of B of size |A|.
  4. Mar 20, 2012 #3
    Do you know how to compute the total number of functions from A to B? If you can do that, you can use the same type of reasoning for this problem, remembering that as you construct a function it must be 1-1.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook