# Bell Triangle

Bell Triangle is a pattern of numbers arranged in a triangular shape. It is named after Eric Temple Bell, a mathematician who made significant contributions to number theory. The Bell Triangle represents the Bell numbers, which are a sequence of numbers that count the number of ways a set with a certain number of elements can be partitioned into non-empty subsets. The Bell numbers start with 1 and increase rapidly as the number of elements in the set grows.

## Problem Statement

The goal of the Bell Triangle problem is to generate the Bell Triangle for a given number of rows, where each row contains a sequence of Bell numbers.

## Example

Let's consider generating the Bell Triangle with 4 rows.

The Bell Triangle for 4 rows will look like this:

```1
1 2
2 3 5
5 7 10 15
```

## Explanation

• In the first row, we have the first Bell number, which is 1.
• In the second row, we have the second Bell number, which is 2, and the third Bell number, which is 3.
• In the third row, we have the fourth Bell number, which is 5, the fifth Bell number, which is 7, and the sixth Bell number, which is 10.
• In the fourth row, we have the seventh Bell number, which is 15.

Each element in the Bell Triangle is obtained by adding the element in the previous row immediately to its left with the element in the current row immediately to its right.

## Pseudocode and Algorithm

``````function generateBellTriangle(row):
if row <= 0:
return

// Create a 2D array to store the Bell Triangle
let result[2][row + 1]

// Initialize variables to keep track of the current row and the first element
let activeRow = 0
let back = 1

for i from 1 to row do:
// Set the first element of the current row to 'back'
result[activeRow][0] = back

// Set initial values for the other elements in the current row
for j from 1 to i do:
result[activeRow][j] = 0

// Calculate the elements in the current row and print them
for j from 1 to i do:
if activeRow is 0:
result[activeRow][j] = result[activeRow][j - 1] + result[1][j - 1]
else:
result[activeRow][j] = result[activeRow][j - 1] + result[0][j - 1]

print result[activeRow][j]
back = result[activeRow][j]

// Switch the active row for the next iteration
activeRow = 1 - activeRow
print newline

end function
``````

The given code already provides an implementation of the Bell Triangle in C. Here's the standard pseudocode and algorithm for the same:

1. Start with an empty 2D array `result` to store the Bell Triangle elements.
2. Initialize `activeRow` to 0 to indicate the current row we are filling, and `back` to 1 as the initial value for the first element.
3. For each row `i` from 1 to the desired number of rows: a. Set the first element of the current row (`result[activeRow][0]`) to the value of `back`. b. Set all other elements of the current row to the sum of the element immediately to their left in the same row (`result[activeRow][j - 1]`) and the element immediately to their left in the previous row (`result[1 - activeRow][j - 1]`). c. Print each element's value as it is calculated. d. Update `back` to the last element of the current row (`result[activeRow][j]`). e. Switch the value of `activeRow` between 0 and 1 to alternate between rows.

## Code Solution

``````/*
C program for
Bell Triangle
*/
#include <stdio.h>

void bellTriangle(int row)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
int result[2][row + 1];
// Current row
int activeRow = 0;
// First element
int back = 1;
for (int i = 1; i <= row; ++i)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;
// Set initial value
result[0][i] = 0;
result[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[0][j - 1];
}
}
// Print element value
printf("  %d", result[activeRow][j]);
back = result[activeRow][j];
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
printf("\n");
}
}
int main(int argc, char const *argv[])
{
/*
row  = 8
----------
1
1       2
2       3    5
5       7   10   15
15     20   27   37  52
52     67   87   114  151  203
203    255  322  409    523  674  877
877  1080  1335  1657  2066  2589  3263  4140
*/
bellTriangle(8);
return 0;
}``````

#### Output

``````  1
1  2
2  3  5
5  7  10  15
15  20  27  37  52
52  67  87  114  151  203
203  255  322  409  523  674  877
877  1080  1335  1657  2066  2589  3263  4140``````
``````/*
Java program for
Bell Triangle
*/
public class BellNumbers
{
public void bellTriangle(int row)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
int[][] result = new  int[row + 1][row + 1];
// Current row
int activeRow = 0;
// First element
int back = 1;
for (int i = 1; i <= row; ++i)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;
// Set initial value
result[0][i] = 0;
result[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[0][j - 1];
}
}
// Print element value
System.out.print("  " + result[activeRow][j] );
back = result[activeRow][j];
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
System.out.print("\n");
}
}
public static void main(String[] args)
{
BellNumbers task = new BellNumbers();

/*
row  = 8
----------
1
1       2
2       3    5
5       7   10   15
15     20   27   37  52
52     67   87   114  151  203
203    255  322  409    523  674  877
877  1080  1335  1657  2066  2589  3263  4140
*/
}
}``````

#### Output

``````  1
1  2
2  3  5
5  7  10  15
15  20  27  37  52
52  67  87  114  151  203
203  255  322  409  523  674  877
877  1080  1335  1657  2066  2589  3263  4140``````
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Bell Triangle
*/
class BellNumbers
{
public: void bellTriangle(int row)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
int result[row + 1][row + 1];
// Current row
int activeRow = 0;
// First element
int back = 1;
for (int i = 1; i <= row; ++i)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;
// Set initial value
result[0][i] = 0;
result[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] +
result[0][j - 1];
}
}
// Print element value
cout << "  " << result[activeRow][j];
back = result[activeRow][j];
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
cout << "\n";
}
}
};
int main()
{
BellNumbers *task = new BellNumbers();
/*
row  = 8
----------
1
1       2
2       3    5
5       7   10   15
15     20   27   37  52
52     67   87   114  151  203
203    255  322  409    523  674  877
877  1080  1335  1657  2066  2589  3263  4140
*/
return 0;
}``````

#### Output

``````  1
1  2
2  3  5
5  7  10  15
15  20  27  37  52
52  67  87  114  151  203
203  255  322  409  523  674  877
877  1080  1335  1657  2066  2589  3263  4140``````
``````// Include namespace system
using System;
/*
Csharp program for
Bell Triangle
*/
public class BellNumbers
{
public void bellTriangle(int row)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
int[,] result = new int[row + 1,row + 1];
// Current row
int activeRow = 0;
// First element
int back = 1;
for (int i = 1; i <= row; ++i)
{
// Previous row last element as
// first element in current row .
result[activeRow,0] = back;
// Set initial value
result[0,i] = 0;
result[1,i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow,j] =
result[activeRow,j - 1] + result[1,j - 1];
}
else
{
result[activeRow,j] =
result[activeRow,j - 1] + result[0,j - 1];
}
}
// Print element value
Console.Write("  " + result[activeRow,j]);
back = result[activeRow,j];
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
Console.Write("\n");
}
}
public static void Main(String[] args)
{
BellNumbers task = new BellNumbers();
/*
row  = 8
----------
1
1       2
2       3    5
5       7   10   15
15     20   27   37  52
52     67   87   114  151  203
203    255  322  409    523  674  877
877  1080  1335  1657  2066  2589  3263  4140
*/
}
}``````

#### Output

``````  1
1  2
2  3  5
5  7  10  15
15  20  27  37  52
52  67  87  114  151  203
203  255  322  409  523  674  877
877  1080  1335  1657  2066  2589  3263  4140``````
``````package main
import "fmt"
/*
Go program for
Bell Triangle
*/

func bellTriangle(row int) {
if row <= 0 {
return
}
// Optimize result by only 2 rows
var result = make([][] int, 2)
for i:= 0; i < 2; i++{
result[i] = make([]int,row+1)
}
// Current row
var activeRow int = 0
// First element
var back int = 1
for i := 1 ; i <= row ; i++ {
// Previous row last element as
// first element in current row .
result[activeRow][0] = back
// Set initial value
result[0][i] = 0
result[1][i] = 0
for j := 0 ; j < i ; j++ {
if j > 0 {
if activeRow == 0 {
result[activeRow][j] = result[activeRow][j - 1] +
result[1][j - 1]
} else {
result[activeRow][j] = result[activeRow][j - 1] +
result[0][j - 1]
}
}
// Print element value
fmt.Print("  ", result[activeRow][j])
back = result[activeRow][j]
}
// Change active row
if activeRow == 0 {
activeRow = 1
} else {
activeRow = 0
}
fmt.Print("\n")
}
}
func main() {

/*
row  = 8
----------
1
1       2
2       3    5
5       7   10   15
15     20   27   37  52
52     67   87   114  151  203
203    255  322  409    523  674  877
877  1080  1335  1657  2066  2589  3263  4140
*/
bellTriangle(8)
}``````

#### Output

``````  1
1  2
2  3  5
5  7  10  15
15  20  27  37  52
52  67  87  114  151  203
203  255  322  409  523  674  877
877  1080  1335  1657  2066  2589  3263  4140``````
``````<?php
/*
Php program for
Bell Triangle
*/
class BellNumbers
{
public	function bellTriangle(\$row)
{
if (\$row <= 0)
{
return;
}
// Optimize result by only 2 rows
\$result = array_fill(0, \$row + 1, array_fill(0, \$row + 1, 0));
// Current row
\$activeRow = 0;
// First element
\$back = 1;
for (\$i = 1; \$i <= \$row; ++\$i)
{
// Previous row last element as
// first element in current row .
\$result[\$activeRow][0] = \$back;
for (\$j = 0; \$j < \$i; ++\$j)
{
if (\$j > 0)
{
if (\$activeRow == 0)
{
\$result[\$activeRow][\$j] =
\$result[\$activeRow][\$j - 1] +
\$result[1][\$j - 1];
}
else
{
\$result[\$activeRow][\$j] =
\$result[\$activeRow][\$j - 1] +
\$result[0][\$j - 1];
}
}
// Print element value
echo("  ".\$result[\$activeRow][\$j]);
\$back = \$result[\$activeRow][\$j];
}
// Change active row
if (\$activeRow == 0)
{
\$activeRow = 1;
}
else
{
\$activeRow = 0;
}
echo("\n");
}
}
}

function main()
{
\$task = new BellNumbers();
/*
row  = 8
----------
1
1       2
2       3    5
5       7   10   15
15     20   27   37  52
52     67   87   114  151  203
203    255  322  409    523  674  877
877  1080  1335  1657  2066  2589  3263  4140
*/
}
main();``````

#### Output

``````  1
1  2
2  3  5
5  7  10  15
15  20  27  37  52
52  67  87  114  151  203
203  255  322  409  523  674  877
877  1080  1335  1657  2066  2589  3263  4140``````
``````/*
Node JS program for
Bell Triangle
*/
class BellNumbers
{
bellTriangle(row)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
var result = Array(row + 1).fill(0).map(
() => new Array(row + 1).fill(0));
// Current row
var activeRow = 0;
// First element
var back = 1;
for (var i = 1; i <= row; ++i)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;

for (var j = 0; j < i; ++j)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] + result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] + result[0][j - 1];
}
}
// Print element value
process.stdout.write("  " + result[activeRow][j]);
back = result[activeRow][j];
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
process.stdout.write("\n");
}
}
}

function main()
{
var task = new BellNumbers();
/*
row  = 8
----------
1
1       2
2       3    5
5       7   10   15
15     20   27   37  52
52     67   87   114  151  203
203    255  322  409    523  674  877
877  1080  1335  1657  2066  2589  3263  4140
*/
}
main();``````

#### Output

``````  1
1  2
2  3  5
5  7  10  15
15  20  27  37  52
52  67  87  114  151  203
203  255  322  409  523  674  877
877  1080  1335  1657  2066  2589  3263  4140``````
``````#    Python 3 program for
#    Bell Triangle
class BellNumbers :
def bellTriangle(self, row) :
if (row <= 0) :
return

#  Optimize result by only 2 rows
result = [[0] * (row + 1) for _ in range(row + 1) ]
#  Current row
activeRow = 0
#  First element
back = 1
i = 1
while (i <= row) :
#  Previous row last element as
#  first element in current row .
result[activeRow][0] = back
j = 0
while (j < i) :
if (j > 0) :
if (activeRow == 0) :
result[activeRow][j] = result[activeRow][j - 1] + result[1][j - 1]
else :
result[activeRow][j] = result[activeRow][j - 1] + result[0][j - 1]

#  Print element value
print("  ", result[activeRow][j], end = "")
back = result[activeRow][j]
j += 1

#  Change active row
if (activeRow == 0) :
activeRow = 1
else :
activeRow = 0

print(end = "\n")
i += 1

def main() :
#    row  = 8
#    ----------
#    1
#    1       2
#    2       3    5
#    5       7   10   15
#    15     20   27   37  52
#    52     67   87   114  151  203
#    203    255  322  409    523  674  877
#    877  1080  1335  1657  2066  2589  3263  4140

if __name__ == "__main__": main()``````

#### Output

``````   1
1   2
2   3   5
5   7   10   15
15   20   27   37   52
52   67   87   114   151   203
203   255   322   409   523   674   877
877   1080   1335   1657   2066   2589   3263   4140``````
``````#    Ruby program for
#    Bell Triangle
class BellNumbers
def bellTriangle(row)
if (row <= 0)
return
end

#  Optimize result by only 2 rows
result = Array.new(row + 1) {Array.new(row + 1) {0}}
#  Current row
activeRow = 0
#  First element
back = 1
i = 1
while (i <= row)
#  Previous row last element as
#  first element in current row .
result[activeRow][0] = back
j = 0
while (j < i)
if (j > 0)
if (activeRow == 0)
result[activeRow][j] =
result[activeRow][j - 1] + result[1][j - 1]
else

result[activeRow][j] =
result[activeRow][j - 1] + result[0][j - 1]
end

end

#  Print element value
print("  ", result[activeRow][j])
back = result[activeRow][j]
j += 1
end

#  Change active row
if (activeRow == 0)
activeRow = 1
else

activeRow = 0
end

print("\n")
i += 1
end

end

end

def main()
#    row  = 8
#    ----------
#    1
#    1       2
#    2       3    5
#    5       7   10   15
#    15     20   27   37  52
#    52     67   87   114  151  203
#    203    255  322  409    523  674  877
#    877  1080  1335  1657  2066  2589  3263  4140
end

main()``````

#### Output

``````  1
1  2
2  3  5
5  7  10  15
15  20  27  37  52
52  67  87  114  151  203
203  255  322  409  523  674  877
877  1080  1335  1657  2066  2589  3263  4140
``````
``````/*
Scala program for
Bell Triangle
*/
class BellNumbers()
{
def bellTriangle(row: Int): Unit = {
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
var result: Array[Array[Int]] = Array.fill[Int](row + 1, row + 1)(0);
// Current row
var activeRow: Int = 0;
// First element
var back: Int = 1;
var i: Int = 1;
while (i <= row)
{
// Previous row last element as
// first element in current row .
result(activeRow)(0) = back;
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (activeRow == 0)
{
result(activeRow)(j) =
result(activeRow)(j - 1) + result(1)(j - 1);
}
else
{
result(activeRow)(j) =
result(activeRow)(j - 1) + result(0)(j - 1);
}
}
// Print element value
print("  " + result(activeRow)(j));
back = result(activeRow)(j);
j += 1;
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
print("\n");
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BellNumbers = new BellNumbers();
/*
row  = 8
----------
1
1       2
2       3    5
5       7   10   15
15     20   27   37  52
52     67   87   114  151  203
203    255  322  409    523  674  877
877  1080  1335  1657  2066  2589  3263  4140
*/
}
}``````

#### Output

``````  1
1  2
2  3  5
5  7  10  15
15  20  27  37  52
52  67  87  114  151  203
203  255  322  409  523  674  877
877  1080  1335  1657  2066  2589  3263  4140``````
``````/*
Swift 4 program for
Bell Triangle
*/
class BellNumbers
{
func bellTriangle(_ row: Int)
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
var result: [
[Int]
] = Array(repeating:
Array(repeating: 0, count: row + 1), count: row + 1);
// Current row
var activeRow: Int = 0;
// First element
var back: Int = 1;
var i: Int = 1;
while (i <= row)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;
// Set initial value
result[0][i] = 0;
result[1][i] = 0;
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] + result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] + result[0][j - 1];
}
}
// Print element value
print("  ", result[activeRow][j], terminator: "");
back = result[activeRow][j];
j += 1;
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
print(terminator: "\n");
i += 1;
}
}
}
func main()
{
let task: BellNumbers = BellNumbers();
/*
row  = 8
----------
1
1       2
2       3    5
5       7   10   15
15     20   27   37  52
52     67   87   114  151  203
203    255  322  409    523  674  877
877  1080  1335  1657  2066  2589  3263  4140
*/
}
main();``````

#### Output

``````   1
1   2
2   3   5
5   7   10   15
15   20   27   37   52
52   67   87   114   151   203
203   255   322   409   523   674   877
877   1080   1335   1657   2066   2589   3263   4140``````
``````/*
Kotlin program for
Bell Triangle
*/
class BellNumbers
{
fun bellTriangle(row: Int): Unit
{
if (row <= 0)
{
return;
}
// Optimize result by only 2 rows
var result: Array < Array < Int >> = Array(row + 1)
{
Array(row + 1)
{
0
}
};
// Current row
var activeRow: Int = 0;
// First element
var back: Int = 1;
var i: Int = 1;
while (i <= row)
{
// Previous row last element as
// first element in current row .
result[activeRow][0] = back;
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (activeRow == 0)
{
result[activeRow][j] =
result[activeRow][j - 1] + result[1][j - 1];
}
else
{
result[activeRow][j] =
result[activeRow][j - 1] + result[0][j - 1];
}
}
// Print element value
print("  " + result[activeRow][j]);
back = result[activeRow][j];
j += 1;
}
// Change active row
if (activeRow == 0)
{
activeRow = 1;
}
else
{
activeRow = 0;
}
print("\n");
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: BellNumbers = BellNumbers();
/*
row  = 8
----------
1
1       2
2       3    5
5       7   10   15
15     20   27   37  52
52     67   87   114  151  203
203    255  322  409    523  674  877
877  1080  1335  1657  2066  2589  3263  4140
*/
}``````

#### Output

``````  1
1  2
2  3  5
5  7  10  15
15  20  27  37  52
52  67  87  114  151  203
203  255  322  409  523  674  877
877  1080  1335  1657  2066  2589  3263  4140``````

## Time Complexity

The time complexity of the provided code is O(n^2) where 'n' is the number of rows in the Bell Triangle. This is because for each row, we calculate the elements by adding elements from the previous row. As the number of rows increases, the number of elements to be calculated in each row increases quadratically. Therefore, the overall time complexity is quadratic.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.