Bell Numbers recursive relation : Explained with example | dynamic programming tutorial

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

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

Let's 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 are 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 are 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.

In this video, you will learn the recursive relation associated with the Bell Numbers. This relation will help you in partitioning a set of N elements into k partitions.

Yes, you read it right. This recursive relation will give you a control over the number of partitions.

This video is the second video in the 3 video series in Joey's dynamic programming tutorial. Below is the link to the first video in the series
which teaches you how to construct bell triangle.

Using bell triangle you can discover that the number of ways you can partition a set of 3 integers is 5.
However, to discover in how many ways you can partition a set of 3 integers into 2 partitions you will have to use the recursive relation.

So, let's do this in this video.
Make sure that you watch this video till the end.

Text justification problem dynamic programming

Box stacking problem dynamic programming

subset sum problem dynamic programming