MHB How Many Functions Meet the Fixed Point Criterion?

[Saitama]

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. (Doh)

Any help is appreciated. Thanks!

 

[mathbalarka]

Keyword : Derangement function.

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

 

[Saitama]

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]

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?

 

[Saitama]

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

Yes.

 

[mathbalarka]

Yes.

Then you are obviously correct.

 

[Saitama]

Then you are obviously correct.

?

I still have no idea about approaching this problem. :(

 

[mathbalarka]

Neither do I. This new interpretation seems harder than mine.

 

[I like Serena]

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. (Doh)

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.

 

[Saitama]

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?

 

[Plato2]

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

 

[Saitama]

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?

Please help, I have got a mindblock here. (Sweating)

 

[Plato2]

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.

 

[Saitama]

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. :)