0
$\begingroup$

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.

$\endgroup$
15
  • $\begingroup$ 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). $\endgroup$ Mar 5 at 19:17
  • $\begingroup$ @Fimpellizieri The only restriction given was $f(i) \neq i$ in the first question $\endgroup$
    – Techie5879
    Mar 5 at 19:18
  • $\begingroup$ 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? $\endgroup$ Mar 5 at 19:20
  • $\begingroup$ 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$. $\endgroup$
    – lulu
    Mar 5 at 19:21
  • 1
    $\begingroup$ @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 $\endgroup$
    – Techie5879
    Mar 5 at 19:25
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ How would I think about the 1st question, if no restrictions were present? $\endgroup$
    – Techie5879
    Mar 6 at 4:53
  • $\begingroup$ 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!$. $\endgroup$ Mar 6 at 5:13
  • $\begingroup$ That would be the number of onto functions right? And the number of into functions would be $4^5-5!$ Is that correct? $\endgroup$
    – Techie5879
    Mar 6 at 5:19
  • $\begingroup$ Why $4^5$? Should be $5^5$. $\endgroup$ Mar 6 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.