Finding Number of Onto Functions | Set A & Set B

  • Thread starter Thread starter Vishalrox
  • Start date Start date
AI Thread Summary
The discussion focuses on determining the number of onto functions from set A with n elements to set B with m elements. It is established that onto functions can only exist when n is less than or equal to m, with the specific case of mPn being valid only when n equals m. The conversation suggests using permutations and mentions a method involving a summation to derive the total number of onto functions. Additionally, there is a hint to consider the total number of functions and how to identify non-surjective functions to aid in the calculation. The overall goal is to clarify the conditions under which onto functions can exist and explore different methods for deriving the answer.
Vishalrox
Messages
20
Reaction score
0
Nice ques to solve !

Homework Statement



Let set 'A' have 'n' number of elements and let set 'B' have 'm' number of elements and let their's a defined function f:A→B. Determine the number of possible 'onto' functions that are possible and valid..!..prove it by mapping of elements from 'A' to 'B'..!

2. The attempt at a solution

According to my logic there are mP1 + mP2 + mP3 +... + mPn Permutations..
is my answer correct...and i could understand that Only if m=n, we will have mPn onto functions. If n<m, none of the functions would be onto...is my statement correct for n>m...and also gimme other logic or methods..!
 
Physics news on Phys.org


To be a little more clear would you be able to write the question word for word as it appears in your homework?

Are you asking "How many surjective functions exist from a domain of m elements to a co-domain of n elements?"? I believe that there is a very handy method that gives this answer with one equation involing a 0 to n summation, have you covered any such equations?

Edit, looking back it seems that you are trying to derive that equation.

Think about the total number of functions. Can you think of a way to find the number of non-surjective functions?

Hint: A non surjective function going to the co-domain B can be discribed as a surjective function going to a smaller co-domain.
 
Last edited:

Thread 'Finding the number of ways to arrange identical balls in a circle (3 different colors)'

I tried to combine those 2 formulas but it didn't work. I tried using another case where there are 2 red balls and 2 blue balls only so when combining the formula I got ##\frac{(4-1)!}{2!2!}=\frac{3}{2}## which does not make sense. Is there any formula to calculate cyclic permutation of identical objects or I have to do it by listing all the possibilities? Thanks
View full post »

Thread 'Greatest possible value of a constant in polynomial'

Since ##px^9+q## is the factor, then ##x^9=\frac{-q}{p}## will be one of the roots. Let ##f(x)=27x^{18}+bx^9+70##, then: $$27\left(\frac{-q}{p}\right)^2+b\left(\frac{-q}{p}\right)+70=0$$ $$b=27 \frac{q}{p}+70 \frac{p}{q}$$ $$b=\frac{27q^2+70p^2}{pq}$$ From this expression, it looks like there is no greatest value of ##b## because increasing the value of ##p## and ##q## will also increase the value of ##b##. How to find the greatest value of ##b##? Thanks
View full post »

Similar threads

Determine which set is a function
Replies
3
Views
2K
Does there exist a surjection from the natural numbers to the reals?
Replies
4
Views
3K
Show that gcd(a,b) is the smallest positive element in the set {ma+nb}
Replies
2
Views
2K
Prove that a set of positive rational numbers is countable
Replies
24
Views
5K
Is f Injective? Understanding the Composition of Functions
Replies
3
Views
2K
Proving that the inverse of a rational number exists
Replies
8
Views
2K
Which functions are missing from {1,2,3} to {a,b} and why?
Replies
4
Views
2K
Prove every subset of countable set is either finite or else countable
Replies
1
Views
2K
Combinatorics Homework: Calculating Possible Combinations with Set A and B
Replies
7
Views
2K
Number of functions from a to b where {123} is in the range of (f)
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top