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 ofnidempotent functions from { 1 , 2 , . . . , n } to itself. Compute
∞
∑
.n in !
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 numbernof idempotent functions from { 1 , 2 , . . . , n } to itself. Compute
∞
∑
.n in !
n =1
Proposed by: Carl Schildkraute
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 − kn
A = kk,n
( )knfor 1 ≤ k ≤ n because there are ways to choose the fixed points and all n − k remaining elementskn − kmust map to fixed points, which can happen in k ways. Hence
∞ ∞ n
∑ ∑ ∑
I An k,nn ! n !=
n =1 n =1
k =1
∞ nn − k
∑ ∑
=kk !( n − k )!
n =1 k =1
∞ ∞
n − k
∑ ∑
1 kk ! ( n − k )!=
k =1 n = k
∞ ∞
∑ ∑n
1 kk ! n !=
n =0
k =1
∞
∑
k 1 = ek !
k =1 = e − 1 .e