HMMT 二月 2020 · 冲刺赛 · 第 23 题

HMMT February 2020 — Guts Round — Problem 23

[12] A function f : A → A is called idempotent if f ( f ( x )) = f ( x ) for all x ∈ A . Let I be the number of n idempotent functions from { 1 , 2 , . . . , n } to itself. Compute ∞ ∑ I n . n ! n =1

解析

[12] A function f : A → A is called idempotent if f ( f ( x )) = f ( x ) for all x ∈ A . Let I be the number n of idempotent functions from { 1 , 2 , . . . , n } to itself. Compute ∞ ∑ I n . n ! n =1 Proposed by: Carl Schildkraut e Answer: e − 1 Solution: Let A denote the number of idempotent functions on a set of size n with k fixed points. k,n We have the formula ( ) n n − k A = k k,n k ( ) n for 1 ≤ k ≤ n because there are ways to choose the fixed points and all n − k remaining elements k n − k must map to fixed points, which can happen in k ways. Hence ∞ ∞ n ∑ ∑ ∑ I A n k,n = n ! n ! n =1 n =1 k =1 ∞ n n − k ∑ ∑ k = k !( n − k )! n =1 k =1 ∞ ∞ n − k ∑ ∑ 1 k = k ! ( n − k )! k =1 n = k ∞ ∞ n ∑ ∑ 1 k = k ! n ! n =0 k =1 ∞ ∑ 1 k = e k ! k =1 e = e − 1 .