# Homework Help: Possible combinations of functions

1. Nov 23, 2014

### nuuskur

1. The problem statement, all variables and given/known data
Let there be exactly n elements in X and exactly m elements in Y. How many different functions f: X -> Y can we form? How many different injections, surjections (and bijections for that matter)? (There is no further info on m, n.)

2. Relevant equations

3. The attempt at a solution
In X we have 2n subsets and in Y we have 2m subsets.

Just to try out where I end up, I'll let X = {a,b,c,d}, Y= {0,1,2,3,4}.

We have 16 subsets of X and for every subset in X we have 32 different subsets in Y. By that logic we could have 2n+m different functions.
First question:
What can we say about, for example f : {a,b,c} -> {0,1,2,3,4}? Since it's a function, no argument can have more than one image. Can such an expression be a function? It can't be surjective, since there doesn't exist an original for every element in the image.
What happens when we consider f : {a,b,c,d} -> {1,2}? Is this a surjection? There exists an original for every element in the image.
Don't want to presume too much. I'd like you to tell me if I am heading in the right direction in my reasoning and if not, where have I made a mistake?

Thanks

2. Nov 23, 2014

### Staff: Mentor

Why do you care about the number of subsets?
There can be a function f : {a,b,c} -> {0,1,2,3,4}, sure. There are many options.

You did not specify f yet, so we don't know (it can be one).
We don't know yet.

f: X->Y just defines the sets where the function is defined. A function definition also needs the specific images: what is f(a), f(b), ...?

3. Nov 23, 2014

### nuuskur

I must have mis-understood the problem. You keep saying "specify f". I thought that when we are asked Different functions, we would have to combine all the possible subsets of X, Y. Otherwise we would just have f: X -> Y, the sets are fixed.

..or wait.
Of course, *smacks forehead* , we have to find all the different functions.
Since it's a function, there can be no more than 1 image for every element in X, but there can be any number of images of elements in Y in f-1 : Y -> X, correct?

Last edited: Nov 23, 2014
4. Nov 23, 2014

### Staff: Mentor

This is the problem statement, yes (or, well, you just have to find out how many there are).

5. Nov 23, 2014

### nuuskur

Right, it was confusing, at first. I was thinking of something completely different.
So, we have:
$$f\colon \{x_1, x_2 , ..., x_n\}\to \{y_1, y_2, ... ,y_m\}$$
I could reconfigure the X set so that there are n! different functions whose image is the set Y.
I can also leave X as it is and reconfigure Y in m! different ways then there are m! different functions.
Can I say there are m!n! different possible functions?

Something doesn't feel right, a set is the same regardless of the order of the elements.

6. Nov 23, 2014

### Staff: Mentor

I don't understand that.
And the answer is not right.

n=1, m=3
n=3, m=1
n=2, m=2
Can you list all possible functions in each case?

7. Nov 23, 2014

### nuuskur

Ok, let $f\colon \{x_1, x_2\}\to \{y_1,y_2\}$. So we can have:
These 2 should be bijective.
x1, x2 to y1, y2 such that f(x1) = y1, f(x2) = y2
x1, x2 to y2, y1

x1, x2 to y1, such that f-1(y2) = empty (is this a possibility? Empty set is in every set, according to definition)
x1, x2 to y2, same idea(think square parabola)

x1, x2 to empty set, no image has an original. Is this possible?

If we have $f\colon \{x_1\}\to \{y_1,y_2,y_3 \}$
x1 to y1, y2, y3 have no original
x1 to y2, y1, y3 have no original
x1 to y3, y2,y1 have no original
x1 to empty set, no other element in Y has an original.

I do have to consider them as functions right? There can't be 2+ different images for the same original.

Actually, no, have to think about it more. According to definition the image of an empty set is empty, and the original of an empty set is also empty, I think I have violated the rules here.

Last edited: Nov 23, 2014
8. Nov 23, 2014

### Staff: Mentor

You are overthinking this. You can simply define what f(x1) and f(x2) are and write that down. Those are elements of Y, not subsets.
That is one option.

The empty set is a subset of every set, but not an element of every set. Subsets are not relevant.

That does not make sense.

Yes we are looking for functions.
Right.

9. Nov 23, 2014

### haruspex

How many possibilities are there for f(x1)? How many for f(x2)? Are these independent? How many possibilities for the pair f(x1), f(x2)?

10. Nov 24, 2014

### nuuskur

Heaven, help me!

$f\colon \{x\}\to \{y\}$: Only one possibility, f(x) = y, right?
$f\colon \{x_1, x_2\}\to \{y\}$: f(x1) = y, f(x2) = y? Again one possibility.
$f\colon \{x_1, x_2\}\to \{y_1, y_2\}$:
f1 : f(x1) = y1, f(x2) = y2
f2 : f(x2) = y1, f(x1) = y2
$f\colon \{x_1, x_2\}\to \{y_1,y_2,y_3\}$: this one is confusing
f1 : f(x1) = y1, f(x2) = y2, but then f1-1(y3) = what?, neither x1 nor x2 can be originals to y3 while either of them already have one image according to f1, but I defined f1 from x1,x2 to y1,y2,y3. Confusing :s

11. Nov 24, 2014

### Staff: Mentor

Right so far.
Those are two options. What about f3(x1)=y1, f3(x2)=y2? There is also a fourth option.

So what? The function does not have to be surjective. We are just looking for all possible functions here.

12. Nov 24, 2014

### RUber

Each point in X has to have an image in Y, so before talking about injectivity, surjectivity, etc., a function from X to Y should be defined for each point in X. That is n points.
For every one of those n points, you can choose any one of the m points in Y. Think of this as choosing balls out of a bag, but each time you pick one, you put it back into the bag, so your next choice is unaffected by earlier draws.

Once you have that, surjections will map to all the points in Y, so $m\leq n$ is necessary.
Injections will map every point in X to a unique point in Y, so $n\leq m$ is necessary.

Do not consider subsets. That will lead you astray.

13. Nov 25, 2014

### nuuskur

So we are obliged to "pick a ball" for every X.
Ok, if n=3, m=1. There are only 3 possibilities, since I can only choose one Y value for every X.
if n=2, m=2, I can choose 2 values in Y for every X so that's 2 x 2.
So $f\colon \{x_1, x_2\}\to \{y_1, y_2\}$ yields 4 different functions:
f1 : f(x1) = y1, f(x2) = y2 bijection
f2: f(x2) = y1, f(x1) = y2 bijection
f3: f(x1) = y1, f(x2) = y1 , y2 has no original, therefore not a surjection. f(x1) = f(x2) : x1 =/= x2 (because a set can't contain identical elements), therefore not an injection.
f4: f(x1) = y2, f(x2) = y2 , not a surjection, not an injection.

$f\colon \{x_1, x_2,x_3\}\to \{y_1, y_2\}$
f1: f(x1) = y1, f(x2) = y1, f(x3) = y2
f2: f(x1) = y1, f(x2) = y2, f(x3) = y1
f3: f(x1) = y2, f(x2) = y1, f(x3) = y1
f4: f(x1) = y2, f(x2) = y2, f(x3) = y1
f5: f(x1) = y1, f(x2) = y2, f(x3) = y2
f6: f(x1) = y2, f(x2) = y1, f(x3) = y2
f7: f(x1) = y1, f(x2) = y1, f(x3) = y1
f8: f(x1) = y2, f(x2) = y2, f(x3) = y2
8 results - maybe mn, then?

I could deduce this much, that injections and consequently, bijections, cannot exist when m < n for we always have functions where at least 2 X values have the same image.

Is the total possible number of functions mn? If people represented the X values and the Y values were different coloured balls (of which we have an unlimited supply): there is a selection made out of m colours n times and since the colours can repeat, each person has an equal choice -> mn.

14. Nov 25, 2014

### haruspex

Yes. For each in X independently, there are m possible targets.
Now how about injections? Having chosen a target for x1 (choice of m) how many targets are there for x2?

15. Nov 25, 2014

### nuuskur

If the first person makes a choice out of m colours, the next person can choose between m-1 colours, the third person between m-2 for there can be no repetition.
According to the definition of injectivity in this scenario: $x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$, therefore the number of injections is:
$$\prod_{i = 0}^{n-1} (m-i) \colon m \geq n$$
so we have m(m-1)(m-2)(m-3)...(m-(n-1)). $m \geq n$, because if $m < n \Rightarrow \exists x_1, x_2\in X\colon x_1 \neq x_2 \Rightarrow f(x_1) = f(x_2)$

If m = n, then there is one specific setup for the colours, however, their respective originals (the people) can vary, therefore we have m! = n! injections (also bijections)

According to surjectivity: $\forall y \in Y, \exists x \in X \colon f(x) = y$
All of the available colours have to be picked, at least, once.
Let's try with a simple example:
$f\colon \{x_1, x_2, x_3\}\to \{y_1,y_2\}$
there exist 6 surjections out of 8 total possible functions, but since I showed that in case of injections $m \geq n$there can exist no injections, hence no bijections.

$f\colon \{x_1, x_2\}\to \{y_1,y_2,y_3\}$ there should be 9 different functions.
Since $m \geq n$, we should have 6 injections. There can be no bijections since only 2 people choose between 3 colours. If there are no bijections, then none of the 6 injections can be surjective at the same time, which leaves only 3 possible surjections.
Trying to generate them, however, leads nowhere
f1: f(x1) = y1, f(x2) = y2 and there is no argument left to make a surjection, which leaves y3 without original. No surjections are possible. Hypothesis: surjection exists iff $m\leq n$, if m = n, then it's also an injection, hence a bijection.

IS it correct to assume that bijections only exist when m = n, in which case the number of bijections is m! (it would make sense, since the word bijection itself means 1:1). I showed that there can not exist injections when $m < n$ and I assumed that bijections also do not exist when $m > n$.

If $m > n$, there can exist injections. Now we have to show that none of those injections are surjective. Assuming when $m > n.\ \forall y\in Y,\exists x\in X: \forall x_1,x_2 \in X, x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$.. and now I'm a bit stuck. How to show this leads to contradiction?

As for the number of surjections, in case of n=3, m=2, there are 6 surjections. if m = n, there are m! surjections and if m > n, there can be no surjections.
This feels like permutation with repetition. We can distribute m different colours between the n people such that we satisfy surjectivity and then we can have any number of colours between the rest of the people. If $m \leq n$, then there are $(\binom{n}{m})!$ possibilities to create the so-called base of surjectivity. We are left with m colours, now to be distributed between n-m people and then apply the rule of product: if $m \leq n$, there are $(\binom{n}{m})!\cdot (\binom{m}{n-m})!$ surjections? Mhh, what about when m=1, n=9? $\binom{1}{8}$???

Last edited: Nov 25, 2014
16. Nov 25, 2014

### nuuskur

EDIT: Right, permutations with repetition.
Number of surjections:
$$\binom{n}{m}!\cdot m^{n-m},\ m\leq n$$
Which leaves one final problem: how to show surjections cannot exist if m > n?

Last edited: Nov 25, 2014
17. Nov 25, 2014

### RUber

I think the proof that surjections cannot exist if m>n should be straightforward. Assume one does. Every one of the m points in Y must have a pre-image under f in X. m pre-images in X, but only n points in X. m>n, so at least one point in X maps to two points in Y. This breaks the assumption that f is a function.

18. Nov 25, 2014

### RUber

The more I look at the count for surjections, the more complicated it seems.
For example, if n=4 and m =1, then there is only one function, thus one surjection.
If n=4 and m =2, there are 16 functions, and only 2 of them are not surjections. Does your function above work for these cases?

19. Nov 25, 2014

### nuuskur

Okay :/
4 people 1 colour, only 1 possible surjection.
4 people, 2 colours, 14 possible surjections??
Umm:$\binom{n}{m}$ for the surjections, but no permutation, since order doesn't matter, now that I look at it. A set is the same regardless of the order of the elements inside, we get the different possible mappings to satisfy surjectivity via combinations. But the leftover spots...I just can't see any other possibility other than permutation with repetition.
$$\binom{n}{m}\cdot m^{n-m}$$
not working :/ Got an idea, but don't have time to look at it tonight, to be continued...

Last edited: Nov 25, 2014
20. Nov 25, 2014

### Staff: Mentor

Working from m=1 to m=2, m=3, ... allows to guess a formula, I'm not sure if the proof works in the same way.

As a cross-check: for n=10, m=5 I get 5 103 000 possible functions.

Interestingly, the same formula even works for n<m, giving the correct result of 0.

Last edited: Nov 25, 2014
21. Nov 25, 2014

### haruspex

Can you write that in terms of factorials?

For surjections, not sure there is such a simple formula. You can get a summation for it using the principle of inclusion and exclusion. First, count all the mappings; next, for each m-1 subset count the mappings from the n to those and subtract this from the first count. But now you've subtracted some twice over, so you have to add those back in, etc.