Via Topological Musings comes another neat little counting problem.
A function is idempotent if applying it twice gives the same result as applying it once: that is, 
The challenge: consider the set 
Feel free to post various approaches and solution methods in the comments, but I won’t be posting a solution later; for that I’ll just direct you to Vishal’s post where I got this problem. He goes on to discuss the relation to exponential generating functions and combinatorial species, which is an amazing topic (although quite a ways above the normal level of TMLT; you have been warned!).
The Math Less Traveled 
Hi,
First, I should state that I really like your blog, which is why I provided a link to it from our blog a long time ago!
Second, I should mention that it was Todd (my co-blogger) who came up with the egf solution via species. Since he is a category theorist (but certainly not just that!), he knows this kind of stuff really well! Hope you learn as much as I did from that post.
By brute force,
for n = 1, 1
for n = 2:
{(1,1), (2,2)}
{(1,2), (2,1)}
2
for n = 3, aha! interesting:
{(1,1), (2,2), (3,3)}
{(1,1), (2,3), (3,2)}
{(1,2), (2,1), (3,3)}
{(1,3), (2,2), (3,1)}
4
Do I have the right idea?
Jonathan,
I don’t think you’re right. In your listing for n=2, you have f(1)=2, f(2)=1, which isn’t idempotent, since f(f(1)) != f(1).
Here’s my thoughts…
If you have f(k)=x, then f(f(k)) = k, so f(x) = x, so if f in an idempotent function on 1..N, then (a) there is some non-empty fixed subset A of 1..N where a in A implies f(a) = a, and (b) for every k, f(k) in A.
The set of idempotent functions with a particular fixed subset A of size a is a^(N-a), and there are C(N,a) subsets A of size a, so the total number of idempotent functions is the sum of C(N,a)a^(N-a) for a from 1 to N.
I’m not a combinatorial expert, so I don’t know a way to simplify that…
It comes down to the number of fixed points. Each set S must have at least one fixed point and all non-fixed-points must map to fixed points. With a little bit of thought, this should become obvious.
I will be using the following short-hand for mappings: f(1) = 2 will be represented by 1–2.
For S = {1} where n = 1:
one fixed point:
1–1
*There is 1 idempotent endofunction for n=1.
For S = {1,2} where n = 2:
one fixed point:
1–1 2–1
1–2 2–2
two fixed points:
1–1 2–2
*There are 3 idempotent endofunctions for n=2.
For S = {1,2,3} where n = 3:
one fixed point:
1–1 2–1 3–1
1–2 2–2 3–2
1–3 2–3 3–3
two fixed points:
1–1 2–2 3–1
1–1 2–2 3–2
1–1 2–1 3–3
1–2 2–3 3–3
1–2 2–2 3–3
1–3 2–2 3–3
three fixed points:
1–1 2–2 3–3
*There are 10 idempotent endofunctions for n=3.
So we’re starting to see a pattern emerge.
If k is the number of fixed points, then there are n CHOOSE k ways to choose which points will be fixed.
For example, when n = 3 and k = 1, we can let 1,2, or 3 be the fixed point. Therefore, there are 3 CHOOSE 1 = 3 ways to choose the fixed point.
If n = 3 and k = 2, then the fixed points can be 1 and 2, 1 and 3, or 2 and 3. Therefore, there are 3 CHOOSE 2 = 3 ways to choose which 2 numbers will be our fixed points.
So it appears that we are interested in the # of possible functions that can be created for each possible value of k. In the example above, when n = 3, there are 3 possible functions when k = 1, there are 6 possible functions when k = 2, and there is only 1 possible function when k = 3.
It appears that our identity will involve a summation that includes the expression n CHOOSE k, the number of ways to choose our fixed points. However it appears that this expression must be multiplied by an expression representing the number of functions possible for each value of k. This is where I’m getting stuck.
Any suggestions?
By the way, a while back, I got into reading a book on Chaotic Dynamical Systems (until I got stuck on Chapter 6, which talked about saddle-node bifurcations, a topic that haunts me to this day). The first 5 chapters talked in great length about fixed points.
Is there any connection between idempotent endofunctions and chaotic dynamical systems?
Shoot! I made a mistake in my first post. Under n = 3, the fourth function under “two fixed points” should read:
1–1 2–3 3–3
I think I’ve got the other part.
For each number of fixed points, k, the number of functions is equal to the number of ways that the remaining n-k non-fixed points can be mapped to the k fixed points.
There are k ^(n-k) ways for n-k fixed points to be mapped to k fixed points. So we are looking for the summation, from k = 1 to n of all (n CHOOSE k) * (k^(n-k)).
Thanks, Blaise. I misunderstood.
What a strange thing! I’ll go back and play some more (without looking at Dave’s comment – trying not to peek — trying hard not to notice my favorite letters…)