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 - rowAlgorithm Explanation
- Initialize a 2D array
dpof size 2 x (n+1) to store the entries of Catalan's Triangle. - Set the initial values of
dp[0][0]anddp[1][0]to 1, as the first column consists of all ones. - Initialize the variable
rowto 1, which helps in alternating between two rows. - Iterate through
ifrom 1 ton, representing the row number.- Initialize
dp[0][i]anddp[1][i]to 0 for the current row. - Iterate through
jfrom 0 toi, 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.
- Calculate the value of
- Print a new line to move to the next row.
- Update the
rowvariable to toggle between 0 and 1.
- Initialize
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)
{
Triangle task = 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
*/
task.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// 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()
{
Triangle *task = 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
*/
task->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// 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)
{
Triangle task = 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
*/
task.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 1430package 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()
{
$task = 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
*/
$task->catalansTriangle(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()
{
var task = 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
*/
task.catalansTriangle(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() :
task = 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
task.catalansTriangle(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()
task = Triangle.new()
# 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
task.catalansTriangle(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
*/
task.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// 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()
{
let task: Triangle = 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
*/
task.catalansTriangle(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
{
val task: Triangle = 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
*/
task.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 1430Time 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.
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.
New Comment