Finding number of functions

Pranav

Well-known member
Problem:
Let $f:\{1,2,3,4,5\}\rightarrow \{1,2,3,4,5\}$, then the number of functions which are into and satisfy $f(i)=i$ for at least one $i=1,2,3,4,5$ are

A)435
B)2121
C)2025
D)None of these

Attempt:
Looking at the opposite case i.e where $f(i)=i$ for at least one of the given i's is not satisfied, I can find the number of derangements but I am not sure if it helps. I need a few hints to begin with. My mind goes blank on these combinatorics problems.

Any help is appreciated. Thanks!

mathbalarka

Well-known member
MHB Math Helper
Keyword : Derangement function.

Count the number of permutations (this is just $5!$) and then exclude the derangement.

Pranav

Well-known member
Keyword : Derangement function.

Count the number of permutations (this is just $5!$) and then exclude the derangement.
Hi mathbalarka!

I am not sure but number of possible functions are $5^5$ or perhaps I misunderstood what you meant by the number of permutations.

The derangement is $!5=44$.

Thanks!

mathbalarka

Well-known member
MHB Math Helper
Pranav said:
I am not sure but number of possible functions are $5^5$
Then we are talking of different things. Is $f(\{1, 2, 3, 4, 5\}) = \{2, 2, 2, 2, 2\}$ allowed?

Pranav

Well-known member
Then we are talking of different things. Is $f(\{1, 2, 3, 4, 5\}) = \{2, 2, 2, 2, 2\}$ allowed?
Yes.

mathbalarka

Well-known member
MHB Math Helper
Pranav said:
Then you are obviously correct.

Pranav

Well-known member
Then you are obviously correct.
???

I still have no idea about approaching this problem.

mathbalarka

Well-known member
MHB Math Helper
Neither do I. This new interpretation seems harder than mine.

Klaas van Aarsen

MHB Seeker
Staff member
Problem:
Let $f:\{1,2,3,4,5\}\rightarrow \{1,2,3,4,5\}$, then the number of functions which are into and satisfy $f(i)=i$ for at least one $i=1,2,3,4,5$ are

A)435
B)2121
C)2025
D)None of these

Attempt:
Looking at the opposite case i.e where $f(i)=i$ for at least one of the given i's is not satisfied, I can find the number of derangements but I am not sure if it helps. I need a few hints to begin with. My mind goes blank on these combinatorics problems.

Any help is appreciated. Thanks!
Hey Pranav!

Let's indeed look at the opposite case, where $f(i) \ne i$ for each $i$.
Then $1$ can be mapped to 4 possible numbers and so can any of the other numbers.
Therefore the opposite case contains $4^5$ functions.

Pranav

Well-known member
Hey Pranav!

Let's indeed look at the opposite case, where $f(i) \ne i$ for each $i$.
Then $1$ can be mapped to 4 possible numbers and so can any of the other numbers.
Therefore the opposite case contains $4^5$ functions.
Hi ILS!

Yes, agreed, so the total number of functions where $f(i)=i$ for at least one $i$ are $5^5-4^5=2101$. This brings me close to option C. Since I need the into functions, I have to subtract the onto ones but how should I do it?

Last edited:

Plato

Well-known member
MHB Math Helper
Yes, agreed, so the total number of functions where $f(i)=i$ for at least one $i$ are $5^5-4^5=2101$. This brings me close to option C. Since I need the into functions, I have to subtract the onto ones but how should I do it?
I think that there is a typo in the question. I thinkm 2101 is correct.
Using inclusion/exclusion I get $$\sum\limits_{k = 1}^5 {{{\left( { - 1} \right)}^{k + 1}}\binom{5}{k}{{\left( 5 \right)}^{5 - k}}} = 2101$$. See here

Pranav

Well-known member
Sorry for the late reply.

I think that there is a typo in the question. I thinkm 2101 is correct.
Using inclusion/exclusion I get $$\sum\limits_{k = 1}^5 {{{\left( { - 1} \right)}^{k + 1}}\binom{5}{k}{{\left( 5 \right)}^{5 - k}}} = 2101$$. See here
Hi Plato!

I found the number of functions where $f(i)=i$ for at least one $i$ by $5^5-4^5=2101$ but I don't see how it deals with the into functions. I mean there can be onto functions too in these 2101 functions. How do I eliminate those?

Plato

Well-known member
MHB Math Helper
I found the number of functions where $f(i)=i$ for at least one $i$ by $5^5-4^5=2101$ but I don't see how it deals with the into functions. I mean there can be onto functions too in these 2101 functions. How do I eliminate those?
That is a matter of vocabulary. If $$f:A\to B$$ it is easy to find text material says the $$f$$ maps $$A$$ into $$B.$$.

On the other hand, to say $$f$$ is onto means that $$f(A)=B$$.

I am not saying that there is no author who uses into in some special way. I am just saying that I am not aware of such.

To see what I mean look at this.

Last edited:

Pranav

Well-known member
That is a matter of vocabulary. If $$f:A\to B$$ it is easy to find text material says the $$f$$ maps $$A$$ into $$B.$$.

On the other hand, to say $$f$$ is onto means that $$f(A)=B$$.

I am not saying that there is no author who uses into in some special way. I am just saying that I am not aware of such.

To see what I mean look at this.
Thank you Plato! I just saw my textbook and yes, there is really no special use of "into".

I remember my teacher saying that into functions are those where range is not equal to co-domain but I am unable find this definition anywhere, I will have to talk about this to my teacher. Thank you once again Plato.