Daily Archives: March 2, 2011

Solution: 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}}.\]

The best solution was submitted by Kang, Dongyub (강동엽), 전산학과 2009학번. Congratulations!

Here is his Solution of Problem 2011-3.

Alternative solutions were submitted by 서기원 (수리과학과 2009학번, +3), 박민재 (2011학번, +3), 김치헌 (수리과학과 2006학번, +2), 이동민 (수리과학과 2009학번, +2), 구도완 (해운대고등학교 3학년, +2).

P.S. A common mistake is to assume that \(\sum_{i}\sum_{j}\) can be swapped without showing that a sequence converges absolutely.


GD Star Rating