Pascal Triangle Program In C Language

Pascal's Triangle is a geometric arrangement of numbers that has fascinated mathematicians for centuries due to its intricate patterns and relationships. It appears in various fields, from probability and combinatorics to algebra and computer science. In this article, you will learn how to generate Pascal's Triangle in C, exploring different programmatic approaches to understand its underlying structure.

Problem Statement

The core problem is to generate and display Pascal's Triangle for a given number of rows. Each number in Pascal's Triangle is the sum of the two numbers directly above it, with the edges always being 1. Understanding how to calculate these values efficiently and display them in the triangular pattern is key.

Example

For an input of rows = 5, the expected output for Pascal's Triangle would be:

1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

Background & Knowledge Prerequisites

To understand the C implementations for Pascal's Triangle, familiarity with the following concepts is helpful:

• Basic C Syntax: Variables, loops (for, while), conditional statements (if-else).
• Functions: Defining and calling functions.
• Arrays: Understanding one-dimensional and two-dimensional arrays (optional for some approaches).
• Mathematical Concepts:
• Factorials: The product of all positive integers up to a given integer (e.g., 5! = 5 * 4 * 3 * 2 * 1).
• Combinations (nCr): The number of ways to choose k items from a set of n items without regard to the order, calculated as n! / (k! * (n-k)!).

Use Cases or Case Studies

Pascal's Triangle appears in several practical and theoretical contexts:

• Binomial Expansion: The coefficients in the expansion of (x + y)^n are found in the n-th row of Pascal's Triangle. For example, (x+y)^3 = 1x^3 + 3x^2y + 3xy^2 + 1y^3.
• Probability: It helps calculate probabilities in scenarios like coin tosses. For instance, the numbers in row n represent the number of ways to get a certain number of heads (or tails) in n flips.
• Combinatorics: Directly used to determine the number of combinations (nCr), which has applications in selecting teams, forming passwords, or arranging items.
• Fractals: Patterns like the Sierpinski Gasket can be found by coloring the odd numbers in Pascal's Triangle.
• Computer Science Algorithms: Concepts of dynamic programming and memoization, often employed in generating the triangle, are fundamental to solving many optimization problems.

Solution Approaches

We will explore three distinct approaches to generate Pascal's Triangle, each with its own advantages in terms of clarity, efficiency, and resource usage.

Approach 1: Using the Binomial Coefficient Formula (nCr)

This approach directly applies the mathematical definition of combinations C(n, k) for each element in the triangle.

• One-line summary: Calculates each element C(row, col) using factorials.

// Pascal's Triangle using nCr
#include <stdio.h>

// Function to calculate factorial
long long factorial(int n) {
    long long res = 1;
    for (int i = 2; i <= n; i++) {
        res *= i;
    }
    return res;
}

// Function to calculate nCr
long long nCr(int n, int r) {
    if (r < 0 || r > n) {
        return 0; // Invalid combination
    }
    return factorial(n) / (factorial(r) * factorial(n - r));
}

int main() {
    int rows = 5; // Number of rows to generate

    printf("Pascal's Triangle (nCr approach):\\n");
    // Step 1: Iterate through each row
    for (int i = 0; i < rows; i++) {
        // Step 2: Print leading spaces for triangular shape
        for (int space = 0; space < rows - i - 1; space++) {
            printf(" ");
        }
        // Step 3: Iterate through each element in the current row
        for (int j = 0; j <= i; j++) {
            printf("%lld ", nCr(i, j)); // Calculate and print nCr
        }
        printf("\\n"); // Move to the next line for the next row
    }
    return 0;
}

Run

• Sample output:

Pascal's Triangle (nCr approach):
    1 
   1 1 
  1 2 1 
 1 3 3 1 
1 4 6 4 1

• Stepwise explanation:

1. A factorial function is defined to compute n! which is used by nCr.
2. The nCr function calculates the binomial coefficient using the formula n! / (r! * (n-r)!).
3. The main function iterates i from 0 to rows-1 (representing the current row number).
4. Inside the outer loop, leading spaces are printed to align the triangle.
5. An inner loop iterates j from 0 to i (representing the element position in the current row).
6. For each (i, j) pair, nCr(i, j) is called to get the value, which is then printed.

Approach 2: Using Dynamic Programming (Row by Row Summation)

This method builds the triangle row by row, where each number is the sum of the two numbers directly above it. It avoids redundant factorial calculations.

• One-line summary: Generates each row by summing elements from the previous row, storing results in an array.

// Pascal's Triangle using Dynamic Programming
#include <stdio.h>

int main() {
    int rows = 5; // Number of rows to generate
    int triangle[rows][rows]; // 2D array to store triangle values

    printf("Pascal's Triangle (Dynamic Programming approach):\\n");
    // Step 1: Iterate through each row
    for (int i = 0; i < rows; i++) {
        // Step 2: Print leading spaces
        for (int space = 0; space < rows - i - 1; space++) {
            printf(" ");
        }
        // Step 3: Iterate through each element in the current row
        for (int j = 0; j <= i; j++) {
            // Step 4: Calculate element value
            if (j == 0 || j == i) {
                triangle[i][j] = 1; // Edges are always 1
            } else {
                // Sum of two elements from the previous row
                triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
            }
            printf("%d ", triangle[i][j]); // Print the calculated value
        }
        printf("\\n"); // Move to the next line
    }
    return 0;
}

Run

• Sample output:

Pascal's Triangle (Dynamic Programming approach):
    1 
   1 1 
  1 2 1 
 1 3 3 1 
1 4 6 4 1

• Stepwise explanation:

1. A 2D array triangle is declared to store the numbers.
2. The outer loop iterates for each row i.
3. Leading spaces are printed for formatting.
4. The inner loop iterates for each element j in the current row.
5. If j is the first element (0) or the last element (i) of the row, its value is 1.
6. Otherwise, the element triangle[i][j] is calculated by summing triangle[i-1][j-1] (element directly above-left) and triangle[i-1][j] (element directly above-right).
7. The calculated value is stored and printed.

Approach 3: Optimized Iterative Calculation (Space-Efficient)

This method calculates each number C(n, k) in a row efficiently by leveraging the relationship C(n, k) = C(n, k-1) * (n-k+1) / k. This avoids using factorials or storing the entire triangle in a 2D array, thus being more space-efficient.

• One-line summary: Iteratively calculates each element in a row from the previous element, avoiding factorials and large arrays.

// Pascal's Triangle using Optimized Iteration
#include <stdio.h>

int main() {
    int rows = 5; // Number of rows to generate

    printf("Pascal's Triangle (Optimized Iterative approach):\\n");
    // Step 1: Iterate through each row
    for (int i = 0; i < rows; i++) {
        // Step 2: Print leading spaces
        for (int space = 0; space < rows - i - 1; space++) {
            printf(" ");
        }
        
        long long current_val = 1; // The first element in any row is 1
        // Step 3: Iterate through each element in the current row
        for (int j = 0; j <= i; j++) {
            printf("%lld ", current_val); // Print the current element
            // Step 4: Calculate the next element using the formula:
            // C(i, j) = C(i, j-1) * (i - j + 1) / j
            current_val = current_val * (i - j) / (j + 1);
        }
        printf("\\n"); // Move to the next line
    }
    return 0;
}

Run

• Sample output:

Pascal's Triangle (Optimized Iterative approach):
    1 
   1 1 
  1 2 1 
 1 3 3 1 
1 4 6 4 1

• Stepwise explanation:

1. The outer loop iterates for each row i.
2. Leading spaces are printed for formatting.
3. current_val is initialized to 1 for the first element of each row.
4. The inner loop iterates for each element j in the current row.
5. The current_val is printed.
6. The current_val for the *next* element is then calculated using the relationship: C(i, j+1) = C(i, j) * (i - j) / (j + 1). This avoids recalculating factorials and uses only the previous element's value. This calculation maintains precision by performing multiplication before division where possible to minimize floating-point errors (though for small numbers, integer division works well here).

Conclusion

Generating Pascal's Triangle offers an excellent opportunity to practice fundamental programming concepts in C while exploring mathematical patterns. We've seen how to implement it using direct factorial calculations, a more efficient dynamic programming approach that stores previous row values, and an optimized iterative method that calculates each element based on its predecessor in the same row, being both time and space efficient.

Summary

• Pascal's Triangle Basics: Each number is the sum of the two above it; edges are always 1.
• nCr Approach: Direct application of n! / (k! * (n-k)!), clear but can be inefficient for large numbers due to factorial calculations and potential overflows.
• Dynamic Programming: Builds the triangle row by row, element = prev_row[j-1] + prev_row[j], which is more efficient by avoiding factorial recalculations and managing values systematically. Requires a 2D array for storage.
• Optimized Iterative: Calculates C(i, j) from C(i, j-1) using current_val = current_val * (i - j) / (j + 1). This is the most space-efficient for generating the triangle row by row without storing the entire structure.