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
loading...
loading...
별해입니다. 다들 이렇게 풀 줄 알았는데=_=
위에 풀이 엄청 간결하고 좋네요.
저는 보고 뭔가 term 하나하나가 정수가 아니다 보니 조합적 의미 부여하기에는 힘들어 보이고 generating function으로 풀어야 하는 삘이 나서 series로 그렇게 풀었어요 =_=;
다들 그렇게 푼 거 맞습니다. 위에 뽑은 풀이 쓰신 분 혼자서 exponential generating function으로 푸셨지요.
익명님이 강동엽씨인가보군요. 오른쪽 series가 점화식으로 계산되므로 왼쪽도 그 식에 짜맞추면 금방 풀리는데, 그리고 그게 출제자 의도인 줄 알았는데 다르게 풀 생각을 했다는 게 신기해서요~ 서기원 선배님도 생성함수로 푸셨다고 하시고.
Pingback: 2011-3 Counting Functions « Everything's said
저도 약간 다른 풀이를 내긴 했지요. 점화식으로 풀어놓고 마음에 안 들어서 삽질을… 근데 절대수렴성을 보여야 한단건 까맣게 잊고 있었네요 -_-ㅋ