How many one-to-one functions f are possible?

  • Thread starter snipekiller
  • Start date
  • Tags
    Functions
In summary, to find the number of one-to-one functions f: A → B, where |A| = n and |B| = m with n ≤ m, we can use the fact that for |A| = |B| = m, the number of different bijections f: A → B is m!. Therefore, the number of one-to-one functions is also m!.
  • #1
snipekiller
2
0

Homework Statement



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

Homework Equations


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

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.
 
Physics news on Phys.org
  • #2
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|.
 
  • #3
snipekiller said:

Homework Statement



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

Homework Equations


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

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.

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.
 

FAQ: How many one-to-one functions f are possible?

What is a one-to-one function?

A one-to-one function is a mathematical concept in which each input (or element in the domain) has a unique output (or element in the range). In other words, no two inputs can have the same output. This is also known as an injective function.

How do you determine the number of possible one-to-one functions?

The number of possible one-to-one functions depends on the size of the domain and range. For a domain of size n and a range of size m, the number of possible one-to-one functions is given by m!/(m-n)!, where ! represents the factorial function.

Can a one-to-one function have a larger range than domain?

Yes, a one-to-one function can have a larger range than domain. This means that some elements in the range will not have a corresponding element in the domain, but all elements in the domain will have a unique element in the range.

Is a one-to-one function the same as a bijection?

Yes, a one-to-one function is the same as a bijection. Both terms refer to a function in which each input has a unique output and vice versa.

Are all one-to-one functions also onto functions?

No, not all one-to-one functions are onto functions. An onto function, also known as a surjective function, is one in which every element in the range has a corresponding element in the domain. A one-to-one function can have a larger range than domain, meaning not all elements in the range will have a corresponding element in the domain.

Similar threads

Problem involving recursion theorem
Replies
11
Views
893
Prove every subset of countable set is either finite or else countable
Replies
1
Views
1K
Find the number of possible functions from one set to another
Replies
2
Views
1K
Problem 1-23 and 1-24 from Spivak's Calculus on Manifolds
Replies
6
Views
1K
Please help me understand a definition of a covariance function
Replies
2
Views
619
Show that a multivariate function is bijective
Replies
1
Views
3K
Can You Apply the Implicit Function Theorem Correctly?
Replies
6
Views
895
Linearly independent functions with identically zero Wronskian
Replies
1
Views
970
Minimum or Maximum value of a multivariate function
Replies
5
Views
2K
Proving the range of a piecewise function
Replies
3
Views
1K

Hot Threads

Recent Insights

Back
Top