# How many functions [5]--->[5] have at least one fixed point?

• Jul 3rd 2010, 03:15 PM
oldguynewstudent
How many functions [5]--->[5] have at least one fixed point?
If f is a function and f(i) = i then we call i a fixed point of f.

a) How many functions [5]$\displaystyle \rightarrow$[5] have at least one fixed point?

I have been working on this for hours! I've written out [3]$\displaystyle \rightarrow$[3], and [4]$\displaystyle \rightarrow$[4].

I came up with this bizzare formula but I am sure it is incorrect. Please help!

$\displaystyle [\sum_{k=0}^{n-3}(n-k)(n-2)]+1$
• Jul 3rd 2010, 03:30 PM
Jhevon
Quote:

Originally Posted by oldguynewstudent
If f is a function and f(i) = i then we call i a fixed point of f.

a) How many functions [5]$\displaystyle \rightarrow$[5] have at least one fixed point?

I have been working on this for hours! I've written out [3]$\displaystyle \rightarrow$[3], and [4]$\displaystyle \rightarrow$[4].

I came up with this bizzare formula but I am sure it is incorrect. Please help!

$\displaystyle [\sum_{k=0}^{n-3}(n-k)(n-2)]+1$

How about thinking of it this way: what you want is the total number of functions minus the ones with NO fixed points.

How far can you get with that conceptualization?
• Jul 3rd 2010, 03:42 PM
oldguynewstudent
Quote:

Originally Posted by Jhevon
How about thinking of it this way: what you want is the total number of functions minus the ones with NO fixed points.

How far can you get with that conceptualization?

I have been working it from that angle also. I came out with$\displaystyle 4^5$ with no fixed points, but I could not justify that either.
• Jul 3rd 2010, 03:47 PM
Jhevon
Quote:

Originally Posted by oldguynewstudent
I have been working it from that angle also. I came out with$\displaystyle 4^5$ with no fixed points, but I could not justify that either.

yes, you have 5 elements, each of which has 4 choices of what to map to, that is, $\displaystyle 4^5$ functions. So the overall answer would be...?
• Jul 3rd 2010, 04:01 PM
oldguynewstudent
Quote:

Originally Posted by Jhevon
yes, you have 5 elements, each of which has 4 choices of what to map to, that is, $\displaystyle 4^5$ functions. So the overall answer would be...?

Yes thanks! That is the original answer I came up with 2 or 3 hours ago but then I thought it was wrong! $\displaystyle 5^5 - 4^5$
• Jul 3rd 2010, 04:49 PM
Jhevon
Quote:

Originally Posted by oldguynewstudent
Yes thanks! That is the original answer I came up with 2 or 3 hours ago but then I thought it was wrong! $\displaystyle 5^5 - 4^5$

Yup, that's it