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, for any input x. Endofunction is just a fancy way of talking about a function whose domain and codomain are the same.
The challenge: consider the set ; how many different idempotent functions are there from to ? For example, when n = 3 one such function is given by , , and . Your answer should be an expression in terms of n.
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!).