# How to find the number of onto and into functions or increasing/decreasing functions, given certain conditions?

I have two related questions that I have a problem in. Here's the 1st one:

What I mean by into functions: Function f from set A to set B is Into function if at least set B has a element which is not connected with any of the element of set A.

1. Number of into/onto functions

Let $$A=\{1,2,3,4,5\}$$ and $$f:A \rightarrow A$$ be an into function such that $$f(i)≠i,∀$$ $$i\in A$$, then the number of such functions is? (Answer is $$980$$)

I know the total number of functions is of course $$4^5$$, but I didn't know how to find the number of into functions, so I looked at the solution for help.

The solution says that the number of required functions is:

Total number of functions − Number of onto functions, and they find the number of onto functions to be $$44$$. The question then is simple enough but I don't know how to find the number of onto functions here. Seeing the number $$44$$ I thought it to be the Derangement of $$5$$, and I'm pretty sure that comes from the fact the its given $$f(i) \neq i$$, but how do I know that it is only the "onto functions"? Can someone elaborate this for me?

2. Number of increasing/decreasing functions

Number of strictly increasing functions $$f: A \rightarrow B$$, where $$A= \{a_1,a_2,a_3,a_4,a_5,a_6\}$$ and $$B=\{1,2,3,4,5,6,7,8,9\}$$ such that $$a_{i+1}>a_i$$ and $$f(a_i) \neq i$$

I do not not how to approach this one. I tried in the following way, I let $$a_1$$ map to $$2$$, (as $$f(i) \neq i$$), so then $$a_2$$ can map with $$3,4,....$$ and so on for the other elements upto $$a_6$$. So the other elements apart from $$a_1$$ can have $$7 \choose5$$ ways. I have a doubt here. Does this also consider the case, that, for $$a_1=2$$ and $$a_2=3$$, $$a_3$$ may be $$4,5,6$$? How does it restrict that the functions obtained here are increasing only? The answer for this one is $${7 \choose5}+{6 \choose 5}+{5 \choose 5}$$. Please help me in understanding how and why to go about determining cases like this.

• Do you mean onto functions that fix no elements? The number of onto functions (with no other restrictions) from $A$ to $A$ would be different otherwise. Notice of course that since $A$ is finite onto functions are also into and vice-versa (ie, they are bijections). Mar 5 at 19:17
• @Fimpellizieri The only restriction given was $f(i) \neq i$ in the first question Mar 5 at 19:18
• That would be a derangement on $A$ then, as you correctly pointed out. The number is precisely $D_5 = 44$. What exactly is the matter in this case? Mar 5 at 19:20
• If $f$ is injective (as I assume you mean by "into") then it is a bijection. There are only $5!=120$ bijections, a far cry from your $908$.
– lulu
Mar 5 at 19:21
• @Fimpellizieri Our books here in India have that in all of them, I wasn't aware it was non standard, I'll edit in the definition Mar 5 at 19:25

For question $$(1)$$, you are correct that the number is obtained from derangements. First, notice that if $$S$$ is finite and $$f:S\longrightarrow S$$, then the following are equivalent:

• $$f$$ is bijective
• $$f$$ is injective
• $$f$$ is surjective (onto)

Now, a permutation on some set is a bijection from that set to itself. Finally, derangement numbers count precisely the permutations $$f$$ that leave no element fixed, that is, such that $$f(i)\neq i$$ for all $$i$$.

For question $$(2)$$, notice that given any choice of $$6$$ distinct values from $$B$$, there is exactly one way to arrange them in increasing/decreasing order.

Now, of course, $$1$$ cannot be a chosen value from $$B$$, for then we would violate the condition of $$f(a_i)\neq i$$ by having to assign $$1$$ to $$a_1$$. Can you show that whenever $$1$$ is not chosen from $$B$$, then the arrangement of the values in increasing order will produce a valid assignment for the $$f(a_i)$$?

In that case, the number of functions will be the number of ways to choose $$6$$ distinct values from $$B\setminus\{1\}$$, which is precisely $$\binom 86 = 28$$.

• How would I think about the 1st question, if no restrictions were present? Mar 6 at 4:53
• Like I said in the comments, that would be just the number of permutations on a set of $5$ elements. That's $5!$. You can think about it like this: there are $5$ choices for the first element, then $4$ choices for the second (cause one's already been taken by the first), then $3$ choices for the third (cause two have already been taken by the first two), then $2$ choices for the fourth element (cause three have already been taken by the first three) and finally a single choice for the last element (all others have been taken by this point). This gives you $5\times4\times3\times2\times1 = 5!$. Mar 6 at 5:13
• That would be the number of onto functions right? And the number of into functions would be $4^5-5!$ Is that correct? Mar 6 at 5:19
• Why $4^5$? Should be $5^5$. Mar 6 at 14:42