| [ QuizWit ] in KIDS 글 쓴 이(By): cycho (멋진척™) 날 짜 (Date): 2001년 10월 19일 금요일 오전 05시 33분 25초 제 목(Title): Re: urn puzzle Let X_k be the number of trials to reduce the total number of different colors from k+1 to k. We are to obtain E[X_(n-1) + X_(n-2) + ... + X_1]. E[X_(n-1)] = 1 The probability of selecting a pair of same color = C(n-k,2)/C(n,2). Thus, for 1<=k<=n-2, E[X_k] = 1 * (1 - C(n-k,2)/C(n,2)) + (E[X_k] + 1) * C(n-k,2)/C(n,2) E[X_k] = 1 + C(n-k,2) / (C(n,2) - C(n-k,2)) where C(a,b) = a!/(a-b)!/b! E[X_(n-1) + X_(n-2) + ... + X_1] = 1 + sum_{k=1}^{n-2} E[X_k] = 1 + (n-2) + sum_{k=1}^{n-2} C(n-k,2) / (C(n,2) - C(n-k,2)) |