| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2001년 7월 21일 토요일 오전 10시 39분 56초 제 목(Title): Re: [Q] Partition 하는 경우의 수 조합론 관련 책에서 Stirling numbers나 Bell numbers를 찾아보세요. (그냥 간단히 웹을 뒤져도 되고요.) 간단히 정리해보죠. Stirling numbers of the second kind(두번째 Stirling 수)는 m 개의 원소를 n개의 집합으로 나누는 방법의 수입니다. S(m,n)이라고 표시하죠. S(m,n) = 0 if 1 <= n <= m S(0,0) = 1 S(m,n) = S(m-1, n-1) + n * S(m-1, n) m 개를 n 개로 나누는 방법은 m-1 개를 n-1 개로 나눈 후에 m번째 걸 따로 만들거나, m-1 개를 n개로 나눈 후에 m번째 걸 이 중 하나에 넣으면 됩니다. 위 점화식은 그걸 말해주는 거죠. 이걸 표로 그리면.. 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 식이 됩니다. 이제 우리가 원하는 m개의 원소를 가진 집합을 나누는 방법의 수(Bell numbers)는 간단히 위 숫자들을 더해주면 나옵니다. B(m) = Sum_{n=0}^m S(m,n) 혹은 B(m) = Sum_{j=0}^{m-1} (m-1 choose j) B(j) -- 박.. |