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

  • Thread starter Thread starter snipekiller
  • Start date Start date
  • Tags Tags
    Functions
Click For Summary
SUMMARY

The discussion focuses on determining the number of one-to-one functions (injective functions) from set A to set B, where |A| = n and |B| = m with the condition that n ≤ m. The key conclusion is that the number of one-to-one functions is given by the formula m! / (m-n)!, which accounts for selecting n distinct elements from set B. This formula is derived from the concept of permutations, where the order of selection matters, and is essential for calculating injective mappings.

PREREQUISITES
  • Understanding of set theory and cardinality
  • Familiarity with permutations and combinations
  • Knowledge of functions, specifically injective functions
  • Basic algebra for manipulating factorials
NEXT STEPS
  • Study the concept of permutations in combinatorics
  • Learn about injective, surjective, and bijective functions
  • Explore the application of the formula m! / (m-n)! in various mathematical problems
  • Investigate the relationship between set sizes and function mappings in discrete mathematics
USEFUL FOR

Mathematics students, educators, and anyone interested in combinatorial analysis and function theory will benefit from this discussion.

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.
 

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
Show that a multivariate function is bijective
  • · Replies 1 ·
Replies
1
Views
3K
Please help me understand a definition of a covariance function
  • · Replies 2 ·
Replies
2
Views
1K
Can You Apply the Implicit Function Theorem Correctly?
  • · Replies 6 ·
Replies
6
Views
2K
Minimum or Maximum value of a multivariate function
  • · Replies 5 ·
Replies
5
Views
2K
Linearly independent functions with identically zero Wronskian
  • · Replies 1 ·
Replies
1
Views
2K
Proving the range of a piecewise function
  • · Replies 3 ·
Replies
3
Views
2K