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' 카테고리의 다른 글

Konig's Theorem  (0) 2010.08.01
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
Finding Minimum Path Cover in DAG  (0) 2009.06.15
Plane Equation (평면의 방정식)  (0) 2009.04.16
Ellipse (타원)  (0) 2009.04.15
Combination 개수 구하기 (Pascal's Triangle)  (2) 2009.02.07
Number of Swap Operations  (0) 2008.07.24

to Top