$\begingroup$
Consider functions from a set with $5$ elements to a set with $3$ elements.
[a] How many functions are there?
[b] How many are one-to-one?
[c] How many are onto?
a] Each element mapped to $3$ images.
$3 \cdot 3 \cdot 3 \cdot 3 \cdot 3$
b] $0$
c] How do I do this?
Edit: I tried doing this way.
EDIT: There can be a set of cardinality {3,1,1} or {2,2,1}.
For {3,1,1}: 5C3 * 2C1 * 1C1 * 3!
For {2,2,1}: 5C2 * 3C2 * 1C1 * 3!
And i realized my 3! is wrong. Should be * 3 only. Why is that so?
asked Apr 28, 2016 at 8:47
RStyleRStyle
6071 gold badge5 silver badges14 bronze badges
$\endgroup$
5
$\begingroup$
You correctly found that there are $3^5$ functions from a set with five elements to a set with three elements. However, this counts functions with fewer than three elements in the range. We must exclude those functions. To do so, we can use the Inclusion-Exclusion Principle.
There are $\binom{3}{1}$ ways of excluding one element in the codomain from the range and $2^5$ functions from a set with five elements to the remaining two elements in the codomain.
There are $\binom{3}{2}$ ways of excluding two elements in the codomain from the range and $1^5$ functions from a set with five elements to the remaining element in the codomain.
By the Inclusion-Exclusion Principle, the number of surjective [onto] functions from a set with five elements to a set with three elements is
$$3^5 - \binom{3}{1}2^5 + \binom{3}{2}1^5$$
answered Apr 28, 2016 at 9:11
N. F. TaussigN. F. Taussig
68.2k13 gold badges52 silver badges70 bronze badges
$\endgroup$
2
$\begingroup$
Hint on c]
The "onto"-function will induce a partition of its domain [as any function] and this partition [actually the fibres of the function] will - because it is onto - have exactly $3$ elements. So to be found is in the first place how many such partitions exist. A fixed partition gives room for $3\times2\times1=6$ functions.
So you end up with: $$6\times\text{number of partitions on }\{1,2,3,4,5\}\text{ that have exactly }3\text{ elements}$$
Also have a look here [especially the counting of partitions].
A general formula for the number of onto-functions $\{1,\dots,n\}\to\{1,\dots,k\}$ is: $$k!S[n,k]$$where $S[n,k]$ stands for the Stirling number of the second kind.
answered Apr 28, 2016 at 8:55
drhabdrhab
143k9 gold badges70 silver badges191 bronze badges
$\endgroup$
1
Video Transcript
Hello there. In this exercise we need to count how many functions 1-1 functions are. Also. You can call it inductive functions. Ah are if this function map from a set with five elements to and we have here some possibilities. So what happened if how many of those functions are we map from uh set with five elements to a set of four elements. Well here there is no such uh such functions because you can imagine this way here you have five elements, 12345 And here you have only four elements 34 So the point to be 1-1 function means that each element here should be assigned with only one on the target 123 four. And then the remaining one should be Related to one with other element here that's going to be repeated. And there is a contradiction for 1-1 function. Technically you can verify the meaning of 1 to 1 function can be verified that if f of X one is equal to F X two, That implies that X one is equal to X two. But in this case you can see that that is not satisfied because here these two different functions is to different points are up to the same value, but those are not the same. They are different. So that's why there's a contradiction is from the mathematical point of view. And so there is no such function. So no at this case, what happened if you have five elements? So now you can start to count and the idea here is that you can see this uh following way. So you can see that the the domain of this function as holes and you're going to of course assign one hole to one element in the target. Okay, but in the target you're going to have some elements, right? So for each hole here, you can assign Any of these five possible elements in the target set. So you have In summer you have here five holes. And you at the first hold you have five possible elements. But this function is 1-1. That means that these elements cannot be repeated. We cannot assign The same hole, two elements on the other on the other side. So if you assigned one element to this first hole, okay, then you cannot assign the same element to the second one, or you can understand the same element to the second. To do this too to the another element in the domain. So now here you have four possibilities. And then for the rest you have three possibilities. And then for the next you have two possibilities. And for the last one you have only one possibility. So you have all these dis possibilities for each place to assign to each element on the domain of this function. Okay, So there's going to be the domain. This is the co domain or range or target whatever. To the point is that you have this possibilities for each, For each location, for each element in the domain, that means five times four times three times two times one, which is the cost of five factorial. And that in this case is equal to 120. Okay, So you can think in this way to to do this kind of counting with functions When you have only two functions or want to want functions or rejected functions. So now let's both that the target set has six elements. So in this case now following the same procedure as before to each element in the domain are elements in the domain. We have five. But for the first one we can assign six from the from the range. For the second element we can assign five possibilities and then war three and two. Okay, so you can think this this this this thing of functions to calculate how many functions is similar. Two locate six elements on five. six, for example, balls or any element on boxes. Okay. Or holes is the same analogy. So the holes are going to be the elements of the domain. So in this case we have five boxes where we're going to locate these six elements and these elements are not going to repeat. So it's not allowing the repetition. So in the first box you can put six of these elements on the second, you have five and so on. That is the same that I'm doing here. So in general you can calculate the both the number of injected functions or onto or 1-1 functions just by knowing the number of elements in the domain. So let's say that this map from a set A to accept the and the number of elements in A is a cost to N and the number of elements in B is M. Okay. So all the possible map ing's, all the possible functions that are 1 to 1 that's not from A to B. And the numbers of elements are N and B respectively. It's going to be equal to M. Factorial divided but by m minus and factorial and it's necessary that end should be greater. Sorry, less or equal than. Okay. So there's a condition and this is the formula so that I'm giving here the general formula for these kind of exercises. So in this case the M is the cost to six. And the end for all these exercises going to be equal to five. So you can see that there's going to be six factorial divided by 6 -5 factorial. And the the end it is just six factorial. That is equal to six times five times four times three times two times one. That is the same that we have as you can observe and the value yes seven 120. And now in this formula then the last one is immediately. So now the the range or The target set has seven elements. So we follow the formula so it's seven factorial divided by 7 -5 factorial. And they're supposed to seven factorial divided by two factorial. And they're supposed to seven times 65 times three times 2 times three here, four times that's it. And there is equal to 2520