| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1999년 4월 9일 금요일 오전 12시 11분 25초 제 목(Title): Re: 그것(확률)이 알고 싶다.... m개의 element를 갖는 set을 n개의 class로 나누는 경우의 수를 S(m,n)이라 기호붙이고 Stirling's triangle of the second kind라고 부릅니다. 조합론에서 자주 나오는 수열이며, 조합론, 이산수학 책을 보면 나옵니다. Knuth의 공구리 수학(Concrete Mathematics)을 봐도 나옵니다. 그 값은 다음과 같은 점화식으로 나타납니다. S(m,n) = 0 unless n,m is integer & 1 <= n <= m S(0,0) = 1 S(m,n) = S(m-1, n-1) + n S(m-1, n) m \ n | 0 1 2 3 4 --------+---------------- 0 | 1 1 | 0 1 2 | 0 1 1 3 | 0 1 3 1 4 | 0 1 7 6 1 대충 이렇게 나갑니다. 이제 우리가 원하는 N개의 공을 M개의 주머니에 넣을 때에 k개의 주머니만 사용할 확률은... 전체 경우의 수가 M^N가지. M개 주머니중 k개의 주머니를 차례로 뽑는 경우의 수인 (M)k k개의 주머니에 N개의 공을 나눠 넣는 가지의 수 S(N, k) 니깐... S(N,k)*(M)k / (M^N)이 되겠죠. 이때 (n)m = n개에서 m개를 뽑는 경우의 수 = n(n-1)(n-2)...(n-m+1) 맞나 확인해봅시다. outsider 님의 표 중에 4개의 공을 5개의 주머니에 넣을 때에 3개로 나뉘는 경우만 검산해봅니다. outsider 님의 값은 72/125 제 값은 S(4,3)* (5)3 / (5^4) = 6 * (5*4*3) / 5^4 = 6 * 12 / 5^3 = 72/125 Bingo! ^_^ -- 박종대 |