A function is called idempotent if for all . Let be the number of idempotent functions from to itself. Compute .
Solution
Let denote the number of idempotent functions on a set of size with fixed points. We have the formula for because there are ways to choose the fixed points and all remaining elements must map to fixed points, which can happen in ways. Hence $\sum_{n=1}^{\infty} \frac{I_{n}}{n!} =\sum_{n=1}^{\infty} \sum_{k=1}^{n} \frac{A_{k, n}}{n!} =\sum_{n=1}^{\infty} \sum_{k=1}^{n} \frac{k^{n-k}}{k!(n-k)!} =\sum_{k=1}^{\infty} \frac{1}{k!} \sum_{n=k}^{\infty} \frac{k^{n-k}}{(n-k)!} =\sum_{k=1}^{\infty} \frac{1}{k!} \sum_{n=0}^{\infty} \frac{k^{n}}{n!} =\sum_{k=1}^{\infty} \frac{1}{k!} e^{k} =e^{e}-1
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.