2년전에 뽑아놓고 구석에 쳐박아둔 프린트물을 우연히 봤는데..
Bell Number에 대해서 정리된 글이다..
오옷.. 이런게 있었다니..!!

B[n] = number of ways a set of N elements can be partitioned into K nonempty sets

ex) There are 5 partitions of the set {1, 2, 3}
=> {{1,2,3}}, {{1,2}, {3}}, {{1,3}, {2}}, {{1}, {2,3}}, {{1}, {2}, {3}}

Relations:

B[n+1] = Sum{i=0..n} B[i] * BinomialCoefficent(n, i)
or
B[n] = S(n, 0) + S(n, 1) + ... + S(n, n)  <---- sum of the stirling 2nd numbers


Binomial Coefficient에 대해서는 뭔가 부족하지만 여기에 포스팅한적이있고
Stirling Number도 비록 1st kind지만 여기서 등장한적이 있다.. ㅋㅋ
이전에 공부했던 내용하고 이렇게 연결이 되는군..~

Bell Number를 응용한 문제로는 LA 2871 - Rhyme Schemes 가 있다..

'Problem Solving > Algorithm notes' 카테고리의 다른 글

Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23
Modular Exponentiation (Big Mod)  (2) 2010.02.19
KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15
Sorting Algorithm O(n^2)  (0) 2009.08.31
Bell Number  (0) 2009.07.12
Finding Minimum Path Cover in DAG  (0) 2009.06.15
Plane Equation (평면의 방정식)  (0) 2009.04.16
Ellipse (타원)  (0) 2009.04.15
Modular Arithmetic 1탄 - Extended Euclid  (2) 2009.02.22
Combination 개수 구하기 (Pascal's Triangle)  (2) 2009.02.07

Leave a Comment


to Top