Maths Olympiad Prep

Library / /514 of 860

Combinatorics Difficulty 5.2 AIME, harder Find the answer

A function f:AAf: A \rightarrow A is called idempotent if f(f(x))=f(x)f(f(x))=f(x) for all xAx \in A. Let InI_{n} be the number of idempotent functions from {1,2,,n}\{1,2, \ldots, n\} to itself. Compute n=1Inn!\sum_{n=1}^{\infty} \frac{I_{n}}{n!}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let Ak,nA_{k, n} denote the number of idempotent functions on a set of size nn with kk fixed points. We have the formula Ak,n=(nk)knkA_{k, n}=\binom{n}{k} k^{n-k} for 1kn1 \leq k \leq n because there are (nk)\binom{n}{k} ways to choose the fixed points and all nkn-k remaining elements must map to fixed points, which can happen in knkk^{n-k} 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.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.