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

  • Thread starter Thread starter snipekiller
  • Start date Start date
  • Tags Tags
    Functions
Click For Summary
To determine the number of one-to-one functions from set A to set B, where |A| = n and |B| = m with n ≤ m, the key is to recognize that each function must map distinct elements of A to distinct elements of B. The process involves selecting n elements from B to form a subset and then arranging them, which can be calculated using the formula m!/(m-n)!. This accounts for the fact that the first element of A can map to any of the m elements in B, the second to m-1, and so on, until n elements are chosen. Understanding this combinatorial approach is essential for solving the problem effectively. The discussion emphasizes the importance of grasping the concept of bijections and one-to-one mappings in set theory.
snipekiller
Messages
2
Reaction score
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
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|.
 
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.
 

Thread 'Distance between a Clock's hands when the distance is increasing most rapidly'

Question: A clock's minute hand has length 4 and its hour hand has length 3. What is the distance between the tips at the moment when it is increasing most rapidly?(Putnam Exam Question) Answer: Making assumption that both the hands moves at constant angular velocities, the answer is ## \sqrt{7} .## But don't you think this assumption is somewhat doubtful and wrong?
View full post »

Similar threads

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