# 2011-3 Counting functions

Let us write $$[n]=\{1,2,\ldots,n\}$$. Let $$a_n$$ be the number of all functions $$f:[n]\to [n]$$ such that $$f([n])=[k]$$ for some positive integer $$k$$. Prove that $a_n=\sum_{k=0}^{\infty} \frac{k^n}{2^{k+1}}.$

GD Star Rating