返回题库

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

HMMT February 2020 — Guts Round — Problem 23

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  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 ofnidempotent functions from { 1 , 2 , . . . , n } to itself. Compute
    ∞
    ∑
    .n in !
    n =1
解析

英文解析

  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