# Mapping of functions

1. Jul 29, 2006

### 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.......

2. Jul 29, 2006

### 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?

3. Jul 29, 2006

### supasupa

no order doesnt matter, only thing is once you map to set T, you cant map to the same element again to satisfy the 1-to-1 requirement

4. Jul 29, 2006

### 0rthodontist

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

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.
Code (Text):

n   m

1   5
2   4
3   2
4   7

Leftover m: 1, 3, 6

Is this the same function?

5. Jul 29, 2006

### nrqed

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.

6. Jul 29, 2006

### nrqed

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?

7. Jul 29, 2006

### supasupa

m^n doesnt work as you cant map to the same value at T, as then it wont be one-to-one.....

8. Jul 29, 2006

### 0rthodontist

So does order matter?

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

9. Jul 29, 2006

### 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 cant really see a pattern where i can come up with a formula in terms of n and m

10. Jul 29, 2006

### supasupa

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

11. Jul 29, 2006

### 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?

12. Jul 29, 2006

### 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)

13. Jul 29, 2006

### 0rthodontist

Yes, that's correct.

14. Jul 29, 2006

### nrqed

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

15. Jul 29, 2006

### nrqed

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

16. Jul 29, 2006

### 0rthodontist

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.