Bell Number
Problem Solving/Algorithm notes 2009. 7. 12. 16:58
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 가 있다..
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도
이전에 공부했던 내용하고 이렇게 연결이 되는군..~
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 |