Problem Solving/Algorithm notes
Bell Number
helloneo
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 가 있다..