# Catalan's triangle

The concept of Catalan's Triangle is an interesting area of combinatorics that offers insights into a variety of counting problems. This pattern generates a triangular array of numbers, where each entry represents a particular counting sequence or problem. In this article, we will explore the creation of Catalan's Triangle using a C program and provide a comprehensive explanation of its significance.

## Problem Statement and Description

Catalan's Triangle is a triangular array of numbers that contains binomial coefficients and is widely applicable in various combinatorial problems. Each entry in the triangle is calculated based on a specific recurrence relation, making it an excellent tool for solving problems involving well-formed parentheses expressions, polygon triangulations, and more.

## Example

Let's take a look at the initial rows of Catalan's Triangle:

``````  1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
...``````

## Idea to Solve the Problem

To create Catalan's Triangle, we can utilize dynamic programming techniques. The idea is to construct the triangle row by row, where each entry is calculated using a recurrence relation involving previous row entries.

## Standard Pseudocode

``````function catalansTriangle(n):
create a 2D array dp of size 2 x (n+1)
initialize dp[0][0] and dp[1][0] to 1

initialize row as 1

for i from 1 to n:
initialize dp[0][i] and dp[1][i] to 0

for j from 0 to i:
calculate dp[row][j] based on recurrence relation

print dp[row][j] followed by a space

print a new line

update row to 1 - row``````

## Algorithm Explanation

1. Initialize a 2D array `dp` of size 2 x (n+1) to store the entries of Catalan's Triangle.
2. Set the initial values of `dp[0][0]` and `dp[1][0]` to 1, as the first column consists of all ones.
3. Initialize the variable `row` to 1, which helps in alternating between two rows.
4. Iterate through `i` from 1 to `n`, representing the row number.
• Initialize `dp[0][i]` and `dp[1][i]` to 0 for the current row.
• Iterate through `j` from 0 to `i`, representing the column number.
• Calculate the value of `dp[row][j]` based on the recurrence relation, using previous row entries.
• Print the value of `dp[row][j]` followed by a space.
• Print a new line to move to the next row.
• Update the `row` variable to toggle between 0 and 1.

## Code Solution

``````// C Program for
// Catalan's triangle
#include <stdio.h>

void catalansTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
int dp[2][n + 1];
// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
int row = 1;
for (int i = 1; i <= n; ++i)
{
// Set initial value in current column
dp[0][i] = 0;
dp[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
printf("  %d", dp[row][j]);
}
// Include new line
printf("\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
int main()
{
/*
1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430
--------------------------------------------
Catalan's triangle when row = 9
*/
catalansTriangle(9);
return 0;
}``````

#### Output

``````  1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430``````
``````// Java program for
// Catalan's triangle
public class Triangle
{
public void catalansTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
int[][] dp = new int[2][n + 1];
// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
int row = 1;
for (int i = 1; i <= n; ++i)
{
// Set initial value in current column
dp[0][i] = 0;
dp[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
System.out.print(" " + dp[row][j]);
}
// Include new line
System.out.print("\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
public static void main(String[] args)
{
/*
1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430
--------------------------------------------
Catalan's triangle when row = 9
*/
}
}``````

#### Output

`````` 1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430``````
``````// Include header file
#include <iostream>
using namespace std;
// C++ program for
// Catalan's triangle
class Triangle
{
public: void catalansTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
int dp[2][n + 1];

// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;

// We can solve this problem only use two rows
// So initial select second row which position is 1
int row = 1;

for (int i = 1; i <= n; ++i)
{
// Set initial value in current column
dp[0][i] = 0;
dp[1][i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
cout << " " << dp[row][j];
}
// Include new line
cout << "\n";
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
};
int main()
{
/*
1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430
--------------------------------------------
Catalan's triangle when row = 9
*/
return 0;
}``````

#### Output

`````` 1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430``````
``````// Include namespace system
using System;
// Csharp program for
// Catalan's triangle
public class Triangle
{
public void catalansTriangle(int n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
int[,] dp = new int[2,n + 1];
// Set initial value of first column
dp[0,0] = 1;
dp[1,0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
int row = 1;
for (int i = 1; i <= n; ++i)
{
// Set initial value in current column
dp[0,i] = 0;
dp[1,i] = 0;
for (int j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row,j] = dp[row,j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row,j] = dp[0,j] + dp[row,j - 1];
}
else
{
// Change first row 'j' column value
dp[row,j] = dp[1,j] + dp[row,j - 1];
}
}
// Print element value
Console.Write(" " + dp[row,j]);
}
// Include new line
Console.Write("\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
public static void Main(String[] args)
{
/*
1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430
--------------------------------------------
Catalan's triangle when row = 9
*/
}
}``````

#### Output

`````` 1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430``````
``````package main
import "fmt"
// Go program for
// Catalan's triangle

func catalansTriangle(n int) {
if n <= 0 {
return
}
// Optimize N *N space by using 2 rows
var dp = make([][] int, 2)
for i:= 0; i < 2; i++{
dp[i] = make([]int,n+1)
}
// Set initial value of first column
dp[0][0] = 1
dp[1][0] = 1
// We can solve this problem only use two rows
// So initial select second row which position is 1
var row int = 1
for i := 1 ; i <= n ; i++ {
for j := 0 ; j < i ; j++ {
if j > 0 {
if j + 1 == i {
// When last element
dp[row][j] = dp[row][j - 1]
} else if row == 1 {
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1]
} else {
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1]
}
}
// Print element value
fmt.Print(" ", dp[row][j])
}
// Include new line
fmt.Print("\n")
// Change the row
if row == 1 {
row = 0
} else {
row = 1
}
}
}
func main() {

/*
1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430
--------------------------------------------
Catalan's triangle when row = 9
*/
catalansTriangle(9)
}``````

#### Output

`````` 1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430``````
``````<?php
// Php program for
// Catalan's triangle
class Triangle
{
public	function catalansTriangle(\$n)
{
if (\$n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
\$dp = array_fill(0, 2, array_fill(0, \$n + 1, 0));
// Set initial value of first column
\$dp[0][0] = 1;
\$dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
\$row = 1;
for (\$i = 1; \$i <= \$n; ++\$i)
{
for (\$j = 0; \$j < \$i; ++\$j)
{
if (\$j > 0)
{
if (\$j + 1 == \$i)
{
// When last element
\$dp[\$row][\$j] = \$dp[\$row][\$j - 1];
}
else if (\$row == 1)
{
// Change second row 'j' column value
\$dp[\$row][\$j] = \$dp[0][\$j] + \$dp[\$row][\$j - 1];
}
else
{
// Change first row 'j' column value
\$dp[\$row][\$j] = \$dp[1][\$j] + \$dp[\$row][\$j - 1];
}
}
// Print element value
echo(" ".\$dp[\$row][\$j]);
}
// Include new line
echo("\n");
// Change the row
if (\$row == 1)
{
\$row = 0;
}
else
{
\$row = 1;
}
}
}
}

function main()
{
/*
1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430
--------------------------------------------
Catalan's triangle when row = 9
*/
}
main();``````

#### Output

`````` 1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430``````
``````// Node JS program for
// Catalan's triangle
class Triangle
{
catalansTriangle(n)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
var dp = Array(2).fill(0).map(() => new Array(n + 1).fill(0));
// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
var row = 1;
for (var i = 1; i <= n; ++i)
{
for (var j = 0; j < i; ++j)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
process.stdout.write(" " + dp[row][j]);
}
// Include new line
process.stdout.write("\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
}
}
}

function main()
{
/*
1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430
--------------------------------------------
Catalan's triangle when row = 9
*/
}
main();``````

#### Output

`````` 1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430``````
``````#  Python 3 program for
#  Catalan's triangle
class Triangle :
def catalansTriangle(self, n) :
if (n <= 0) :
return

#  Optimize N *N space by using 2 rows
dp = [[0] * (n + 1) for _ in range(2) ]
#  Set initial value of first column
dp[0][0] = 1
dp[1][0] = 1
#  We can solve this problem only use two rows
#  So initial select second row which position is 1
row = 1
i = 1
while (i <= n) :
j = 0
while (j < i) :
if (j > 0) :
if (j + 1 == i) :
#  When last element
dp[row][j] = dp[row][j - 1]
elif (row == 1) :
#  Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1]
else :
#  Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1]

#  Print element value
print(" ", dp[row][j], end = "")
j += 1

#  Include new line
print(end = "\n")
#  Change the row
if (row == 1) :
row = 0
else :
row = 1

i += 1

def main() :
#  1
#  1  1
#  1  2  2
#  1  3  5  5
#  1  4  9  14  14
#  1  5  14  28  42  42
#  1  6  20  48  90  132  132
#  1  7  27  75  165  297  429  429
#  1  8  35  110  275  572  1001  1430  1430
#  --------------------------------------------
#  Catalan's triangle when row = 9

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

#### Output

``````  1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430``````
``````#  Ruby program for
#  Catalan's triangle
class Triangle
def catalansTriangle(n)
if (n <= 0)
return
end

#  Optimize N *N space by using 2 rows
dp = Array.new(2) {Array.new(n + 1) {0}}
#  Set initial value of first column
dp[0][0] = 1
dp[1][0] = 1
#  We can solve this problem only use two rows
#  So initial select second row which position is 1
row = 1
i = 1
while (i <= n)
j = 0
while (j < i)
if (j > 0)
if (j + 1 == i)
#  When last element
dp[row][j] = dp[row][j - 1]
elsif (row == 1)
#  Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1]
else

#  Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1]
end

end

#  Print element value
print(" ", dp[row][j])
j += 1
end

#  Include new line
print("\n")
#  Change the row
if (row == 1)
row = 0
else

row = 1
end

i += 1
end

end

end

def main()
#  1
#  1  1
#  1  2  2
#  1  3  5  5
#  1  4  9  14  14
#  1  5  14  28  42  42
#  1  6  20  48  90  132  132
#  1  7  27  75  165  297  429  429
#  1  8  35  110  275  572  1001  1430  1430
#  --------------------------------------------
#  Catalan's triangle when row = 9
end

main()``````

#### Output

`````` 1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430
``````
``````// Scala program for
// Catalan's triangle
class Triangle()
{
def catalansTriangle(n: Int): Unit = {
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
var dp: Array[Array[Int]] = Array.fill[Int](2, n + 1)(0);
// Set initial value of first column
dp(0)(0) = 1;
dp(1)(0) = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
var row: Int = 1;
var i: Int = 1;
while (i <= n)
{
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp(row)(j) = dp(row)(j - 1);
}
else if (row == 1)
{
// Change second row 'j' column value
dp(row)(j) = dp(0)(j) + dp(row)(j - 1);
}
else
{
// Change first row 'j' column value
dp(row)(j) = dp(1)(j) + dp(row)(j - 1);
}
}
// Print element value
print(" " + dp(row)(j));
j += 1;
}
// Include new line
print("\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Triangle = new Triangle();
/*
1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430
--------------------------------------------
Catalan's triangle when row = 9
*/
}
}``````

#### Output

`````` 1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430``````
``````// Swift 4 program for
// Catalan's triangle
class Triangle
{
func catalansTriangle(_ n: Int)
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
var dp: [
[Int]
] = Array(repeating: Array(repeating: 0, count: n + 1), count: 2);
// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
var row: Int = 1;
var i: Int = 1;
while (i <= n)
{
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
print(" ", dp[row][j], terminator: "");
j += 1;
}
// Include new line
print(terminator: "\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
i += 1;
}
}
}
func main()
{
/*
1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430
--------------------------------------------
Catalan's triangle when row = 9
*/
}
main();``````

#### Output

``````  1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430``````
``````// Kotlin program for
// Catalan's triangle
class Triangle
{
fun catalansTriangle(n: Int): Unit
{
if (n <= 0)
{
return;
}
// Optimize N *N space by using 2 rows
var dp: Array < Array < Int >> = Array(2)
{
Array(n + 1)
{
0
}
};
// Set initial value of first column
dp[0][0] = 1;
dp[1][0] = 1;
// We can solve this problem only use two rows
// So initial select second row which position is 1
var row: Int = 1;
var i: Int = 1;
while (i <= n)
{
var j: Int = 0;
while (j < i)
{
if (j > 0)
{
if (j + 1 == i)
{
// When last element
dp[row][j] = dp[row][j - 1];
}
else if (row == 1)
{
// Change second row 'j' column value
dp[row][j] = dp[0][j] + dp[row][j - 1];
}
else
{
// Change first row 'j' column value
dp[row][j] = dp[1][j] + dp[row][j - 1];
}
}
// Print element value
print(" " + dp[row][j]);
j += 1;
}
// Include new line
print("\n");
// Change the row
if (row == 1)
{
row = 0;
}
else
{
row = 1;
}
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
/*
1
1  1
1  2  2
1  3  5  5
1  4  9  14  14
1  5  14  28  42  42
1  6  20  48  90  132  132
1  7  27  75  165  297  429  429
1  8  35  110  275  572  1001  1430  1430
--------------------------------------------
Catalan's triangle when row = 9
*/
}``````

#### Output

`````` 1
1 1
1 2 2
1 3 5 5
1 4 9 14 14
1 5 14 28 42 42
1 6 20 48 90 132 132
1 7 27 75 165 297 429 429
1 8 35 110 275 572 1001 1430 1430``````

### Time Complexity:

The time complexity of the provided algorithm is O(n^2) due to the nested loops that iterate through the rows and columns of the triangle. The space complexity is O(n) since the program uses a 2D array of size 2 x (n+1) to store the triangle rows.

## 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.