Bell Numbers - Learn to construct bell triangle | dynamic programming tutorial

Показать описание

To solve the partitioning problems of a set it is necessary to know the concept of Bell Numbers.

The obvious question is what are bell numbers?

A bell number B(n) gives you the number of possible ways to partition a set of N integers.

Below is the classic bell numbers list -

1,1,2,5,15,52,203 and so on

Lets drill down this list of bell numbers.
Here, B0=1 (It is always 1)

B1=1 (this means that when there is 1 integer the only possible way to partition it is just 1)

B2=2 ,this signifies that the possible ways to partition a set of 2 integers is 2.
For example, consider the below set -

{1,2}
The possible ways to partition the above set will be

[{1},{2}] & [{1,2}]

Similarly, when we have 3 integers in the set {1,2,3} the bell number series indicates that the possible ways to partition the set is 5.

Bell numbers are very important to solve the partitioning problems and pairing problems like the Friends pairing problem.
While building the partitioning algorithms, bell numbers form an integral part. Coding and algorithms go hand-in-hand.

Without putting the bell numbers concept in the middle you cannot code a few programs solving the partitioning problems even when you
are using the dynamic programming technique.

This video is the first video in the 3 video series in Joey's dynamic programming tutorial. In this video, I will teach how to construct a bell triangle.

Using the bell triangle you can determine the bell numbers list easily.
It is not a difficult task to construct a bell triangle. In fact, it is fun and you can do it easily using dynamic programming.

If you learn bell numbers properly then you will learn the Friends Pairing problem which I consider as one of the most interesting DP problems for beginners.

All you have to do is to watch this video till the end.

Text justification problem dynamic programming

Box stacking problem dynamic programming

subset sum problem dynamic programming