Welcome to our community

Be a part of something great, join today!

Finding number of functions

Pranav

Well-known member
Nov 4, 2013
428
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

Well-known member
MHB Math Helper
Mar 22, 2013
573
Keyword : Derangement function.

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

Pranav

Well-known member
Nov 4, 2013
428
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
Mar 22, 2013
573
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
Nov 4, 2013
428

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573

Pranav

Well-known member
Nov 4, 2013
428

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573
Neither do I. This new interpretation seems harder than mine.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
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.
 

Pranav

Well-known member
Nov 4, 2013
428
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? :confused:
 
Last edited:

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
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? :confused:
I think that there is a typo in the question. I thinkm 2101 is correct.
Using inclusion/exclusion I get [tex]\sum\limits_{k = 1}^5 {{{\left( { - 1} \right)}^{k + 1}}\binom{5}{k}{{\left( 5 \right)}^{5 - k}}} = 2101[/tex]. See here
 

Pranav

Well-known member
Nov 4, 2013
428
Sorry for the late reply. :eek:

I think that there is a typo in the question. I thinkm 2101 is correct.
Using inclusion/exclusion I get [tex]\sum\limits_{k = 1}^5 {{{\left( { - 1} \right)}^{k + 1}}\binom{5}{k}{{\left( 5 \right)}^{5 - k}}} = 2101[/tex]. 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? :confused: :confused:

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

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
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 [tex]f:A\to B[/tex] it is easy to find text material says the [tex]f[/tex] maps [tex]A[/tex] into [tex]B.[/tex].

On the other hand, to say [tex]f[/tex] is onto means that [tex]f(A)=B[/tex].

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
Nov 4, 2013
428
That is a matter of vocabulary. If [tex]f:A\to B[/tex] it is easy to find text material says the [tex]f[/tex] maps [tex]A[/tex] into [tex]B.[/tex].

On the other hand, to say [tex]f[/tex] is onto means that [tex]f(A)=B[/tex].

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