Pascal’s Triangle in C – Recurrence, Centered Output, and C(n,k) Formula

Pascal’s Triangle is a triangular array where each number is the sum of the two numbers directly above it. Row n, column k holds the binomial coefficient C(n,k) — the number of ways to choose k items from n. It appears in combinatorics, probability, the binomial theorem, and polynomial expansion. The C program below builds the triangle using the recurrence relation, prints it centered, and then demonstrates the closed-form C(n,k) formula. Both approaches are O(n²) in time and space.

The Recurrence and the Triangle

Row 0:              1
Row 1:            1   1
Row 2:          1   2   1
Row 3:        1   3   3   1
Row 4:      1   4   6   4   1
Row 5:    1   5  10  10   5   1
Row 6:  1   6  15  20  15   6   1

Rules:

• Every row starts and ends with 1: tri[i][0] = tri[i][i] = 1
• Every interior element is the sum of the two elements directly above it: tri[i][j] = tri[i-1][j-1] + tri[i-1][j]

This recurrence is the same as Pascal’s identity for binomial coefficients: C(n,k) = C(n−1,k−1) + C(n−1,k).

C Program: Pascal’s Triangle

/* Pascal's Triangle
 * Compile: gcc -ansi -Wall -Wextra pascal.c -o pascal */
#include <stdio.h>
#define MAXN 15

int main(void)
{
    int tri[MAXN][MAXN];
    int n, i, j;

    printf("Enter number of rows (1-%d): ", MAXN);
    if (scanf("%d", &n) != 1 || n < 1 || n > MAXN) {
        printf("Invalid.\n"); return 1;
    }

    /* Build using the recurrence */
    for (i = 0; i < n; i++) {
        tri[i][0] = 1;
        tri[i][i] = 1;
        for (j = 1; j < i; j++)
            tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
    }

    /* Print centered: each value in a 4-char field.
       Indent = 2*(n-1-i) keeps the triangle symmetric around a
       vertical axis. */
    for (i = 0; i < n; i++) {
        printf("%*s", 2 * (n - 1 - i), "");
        for (j = 0; j <= i; j++)
            printf("%4d", tri[i][j]);
        printf("\n");
    }
    return 0;
}

Sample Output (7 rows)

Enter number of rows (1-15): 7
                1
             1   1
           1   2   1
         1   3   3   1
       1   4   6   4   1
     1   5  10  10   5   1
   1   6  15  20  15   6   1

Code Explanation

• Build phase: The two boundary assignments (tri[i][0] = 1, tri[i][i] = 1) handle the edges of each row. The inner loop fills only the interior positions j = 1..i-1, which are the only positions where the recurrence applies. For row 0 and row 1 the inner loop body never executes (i < 1 and i < 2 respectively), so only the boundary assignments run — correct, since rows 0 and 1 are just [1] and [1,1].
• Centering with %*s: The format specifier printf("%*s", width, "") prints width spaces by using the integer argument as the field width for an empty string. The indent 2*(n-1-i) decreases by 2 per row; since each row gains one 4-char element, the visual center stays fixed.
• %4d per element: This gives each number a 4-character right-aligned field. For row n=15, the largest value is C(14,7) = 3432 (4 digits), which just fits. For n > 15, values exceed 4 digits and the alignment would break — increase the field width or reduce MAXN.
• Memory: tri[MAXN][MAXN] allocates a 15×15 array (225 ints = 900 bytes) on the stack. Only the lower-triangular half is used, but the declaration is still clean and the wasted space is negligible.

The Closed-Form Formula: C(n,k) Without a Table

To compute a single value C(n,k) without building the whole triangle, use the multiplicative formula. It avoids factorial overflow by dividing at every step:

/* Compute C(n,k) using the multiplicative formula.
 * Compile: gcc -ansi -Wall -Wextra cnk.c -o cnk */
#include <stdio.h>

long long cnk(int n, int k)
{
    long long result = 1;
    int i;
    if (k > n - k) k = n - k;    /* C(n,k) == C(n,n-k); use smaller k */
    for (i = 0; i < k; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}

int main(void)
{
    int n, k;
    printf("Enter n and k: ");
    if (scanf("%d %d", &n, &k) != 2 || k < 0 || k > n) {
        printf("Invalid.\n"); return 1;
    }
    printf("C(%d,%d) = %lld\n", n, k, cnk(n, k));
    return 0;
}

Key Properties of Pascal’s Triangle

Frequently Asked Questions

Related Programs

• Factorial in C
• Combinations and Permutations in C – C(n,k) Formula
• Pattern Programs in C – Triangle and Pyramid
• N-Queens in C – Backtracking

Recommended books:
The C Programming Language — K&R (India) |
(US)
 | 
C Programming: A Modern Approach — K.N. King (India) |
(US)

Test your C knowledge: C Aptitude Questions — or try our C Programming Quiz App on Android.