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, 2021 at 19:17
  • $\begingroup$ @Fimpellizieri The only restriction given was $f(i) \neq i$ in the first question $\endgroup$
    – Techie5879
    Mar 5, 2021 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, 2021 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, 2021 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, 2021 at 19:25

1 Answer 1

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, 2021 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, 2021 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, 2021 at 5:19
  • $\begingroup$ Why $4^5$? Should be $5^5$. $\endgroup$ Mar 6, 2021 at 14:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .