Mapping of Functions from S to T: n<=m

[supasupa]

There are 2 parts to this question:

How many functions are there from a set S with n elements to a set T with m elements? Assume n<=m, how many one-to-one functions are there from S to T?


I am pretty sure that the answer to the first part is mn. So if there are 3 elements in the first set and 4 elements in the 2nd set, then there are a total of 3 X 4 functions.

But for 1 to 1, it would be (for the same set example used above), 4+3+2 = 9 functions.
I am unsure on how to come up with the general formula for the mapping of one-to-one functions.


Any help is appreciated...

 

[0rthodontist]

In the first part, each element of the domain can choose from among m elements of the codomain. What does that translate to?

In the second part, you have to match up the elements in the domain with the elements of the codomain in a one-to-one fashion. Let's say for concreteness that the elements of the domain are 1, 2, ... n. Then you have m elements, n of which you must match up against those numbers in some way. Does order matter?

 

[supasupa]

no order doesn't matter, only thing is once you map to set T, you can't map to the same element again to satisfy the 1-to-1 requirement

 

[0rthodontist]

Let's say n = 1...4 and m = 1...7. Then a function might look something like this:

n	m

1	5
2	2
3	4
4	7

Leftover m: 1, 3, 6

Let's say that you switch the order that the elements of m are assigned to the elements of n.

n	m

1	5
2	4
3	2
4	7

Leftover m: 1, 3, 6

Is this the same function?

 

[nrqed]

Let's say n = 1...4 and m = 1...7. Then a function might look something like this:

n	m

1	5
2	2
3	4
4	7

Leftover m: 1, 3, 6

Let's say that you switch the order that the elements of m are assigned to the elements of n.

n	m

1	5
2	4
3	2
4	7

Leftover m: 1, 3, 6

Is this the same function?

I am pretty sure it would not be considered the same function! f(2) does not give the sam eresult in both cases so it's a different function.

 

[nrqed]

There are 2 parts to this question:

How many functions are there from a set S with n elements to a set T with m elements? Assume n<=m, how many one-to-one functions are there from S to T?


I am pretty sure that the answer to the first part is mn. So if there are 3 elements in the first set and 4 elements in the 2nd set, then there are a total of 3 X 4 functions.

It depends. do all the elements of S need to be mapped? Must the mapping be onto?
If all the elements of S must be mapped but there is not other restriction, I would say m^n. You pick one element of S and you can map it to any of the m elements of T. That's m choices. You take the second element of S and you can still map it to any of the m elements of T, that's another m choices, and so on. So m^n, no?

 

[supasupa]

m^n doesn't work as you can't map to the same value at T, as then it won't be one-to-one...

 

[0rthodontist]

I am pretty sure it would not be considered the same function! f(2) does not give the sam eresult in both cases so it's a different function.

So does order matter?

Another hint: 5247 completely determines the first function I mentioned, and 5427 completely determines the second one I mentioned.

 

[supasupa]

i am kinda confused now...

you are right when u say that f(2) is not the same function. So how do you take in all possibilities... I can't really see a pattern where i can come up with a formula in terms of n and m

 

[supasupa]

yeah order does matter as it maps a different function... but i just can't undersatnd how to work out all the possible funtions there can be

 

[0rthodontist]

Okay--it's a permutation of some kind. What is it permuting--how many does it permute out of a set of what size?

 

[supasupa]

thats what i have been trying to use. The set size is m and you are choosing from n. Is it correct in saying P(m,n)

 

[0rthodontist]

Yes, that's correct.

 

[nrqed]

m^n doesn't work as you can't map to the same value at T, as then it won't be one-to-one...

I was talking about the *first* question. In that case the function does not have to be one-to-one, no?

 

[nrqed]

So does order matter?

Another hint: 5247 completely determines the first function I mentioned, and 5427 completely determines the second one I mentioned.

I see what you are saying but it feels to me that it's a bit misleading to talk about "order" here because that plays no role in the problem. it just happens that the elements of the first set are 1, 2,3,4 but since we are talking about mapping discrete elements, order plays no role here. I mean, the elements could have been called "A, epsilon, 7 and aleph" as well without changing the problem at all.
My point was that two functions are equal if they map all the elements of the first set to the same elements of the second set (order not playing any role here). In your first function above, the element 2 of the first set is mapped to the elemnt 2 of the second set whereas in the second function, the 2 is mapped to 4. I don't see anyway to think of two functions as being equivalent if they don't map the same elements to the same elements.

Regards

Patrick

 

[0rthodontist]

I see what you are saying but it feels to me that it's a bit misleading to talk about "order" here because that plays no role in the problem. it just happens that the elements of the first set are 1, 2,3,4 but since we are talking about mapping discrete elements, order plays no role here. I mean, the elements could have been called "A, epsilon, 7 and aleph" as well without changing the problem at all.
My point was that two functions are equal if they map all the elements of the first set to the same elements of the second set (order not playing any role here). In your first function above, the element 2 of the first set is mapped to the elemnt 2 of the second set whereas in the second function, the 2 is mapped to 4. I don't see anyway to think of two functions as being equivalent if they don't map the same elements to the same elements.

Regards

Patrick

The point is that you are considering only one-to-one functions. If the elements of the first set were as you said, then you could simply order them "A, epsilon, 7, aleph" and each function would still be determined by writing four elements of the second set in some order next to those ordered elements of the first set. Of course, this representation would also satisfy the usual rules for equality of functions. It is just a way for denoting one-to-one functions. Often, as in this case, being able to denote something in a nice way tells you how to count it.