Possible combinations of functions

[nuuskur]

Homework Statement

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

Homework Equations

The Attempt at a Solution

In X we have 2ⁿ subsets and in Y we have 2^m 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 2^n+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

 

[mfb]

Why do you care about the number of subsets?

Can such an expression be a function?

There can be a function f : {a,b,c} -> {0,1,2,3,4}, sure. There are many options.

What happens when we consider f : {a,b,c,d} -> {1,2}? Is this a surjection?

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

There exists an original for every element in the image.

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), ...?

 

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

 

[mfb]

we have to find all the different functions.

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

 

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

 

[mfb]

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.

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

Start with simple examples:
n=1, m=3
n=3, m=1
n=2, m=2
Can you list all possible functions in each case?

 

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

 

[mfb]

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.

f(x1) = y1, f(x2) = y2

That is one option.

(is this a possibility? Empty set is in every set, according to definition)

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

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.

That does not make sense.

I do have to consider them as functions right?

Yes we are looking for functions.

There can't be 2+ different images for the same original.

Right.

 

[haruspex]

How many possibilities are there for f(x₁)? How many for f(x₂)? Are these independent? How many possibilities for the pair f(x₁), f(x₂)?

 

[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

 

[mfb]

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.

Right so far.

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

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

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

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

 

[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 anyone 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.

 

[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 mⁿ, 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 mⁿ? 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 -> mⁿ.

 

[haruspex]

Is the total possible number of functions mⁿ?

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

 

[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 &lt; 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 nthere 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 &lt; n and I assumed that bijections also do not exist when m &gt; n.

If m &gt; n, there can exist injections. Now we have to show that none of those injections are surjective. Assuming when m &gt; 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}?

 

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

 

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

 

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

 

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

 

[mfb]

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.

 

[haruspex]

the number of injections is:
\prod_{i = 0}^{n-1} (m-i) \colon m \geq n

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.