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
loading...

6 thoughts on “Solution: 2011-3 Counting functions

  1. 익명

    위에 풀이 엄청 간결하고 좋네요.
    저는 보고 뭔가 term 하나하나가 정수가 아니다 보니 조합적 의미 부여하기에는 힘들어 보이고 generating function으로 풀어야 하는 삘이 나서 series로 그렇게 풀었어요 =_=;

  2. S. Oum Post author

    다들 그렇게 푼 거 맞습니다. 위에 뽑은 풀이 쓰신 분 혼자서 exponential generating function으로 푸셨지요.

  3. Minjae Park

    익명님이 강동엽씨인가보군요. 오른쪽 series가 점화식으로 계산되므로 왼쪽도 그 식에 짜맞추면 금방 풀리는데, 그리고 그게 출제자 의도인 줄 알았는데 다르게 풀 생각을 했다는 게 신기해서요~ 서기원 선배님도 생성함수로 푸셨다고 하시고.

  4. Pingback: 2011-3 Counting Functions « Everything's said

  5. Chiheon Kim

    저도 약간 다른 풀이를 내긴 했지요. 점화식으로 풀어놓고 마음에 안 들어서 삽질을… 근데 절대수렴성을 보여야 한단건 까맣게 잊고 있었네요 -_-ㅋ

Comments are closed.