Pascal's triangle

Why this matters

Pascal's triangle is a grid of numbers with a simple rule. Each row starts and ends with 1. Every other value is the sum of the two values directly above it. The rule is short, but the triangle appears in many places. It gives the number of ways to choose items from a group, it gives the coefficients when you multiply out a sum such as (a + b) raised to a power, and it gives the odds in some counting problems.

For a beginner, the triangle is a good exercise because it needs three skills at once. You need to store rows that have different lengths, you need to read a value from the row above, and you need to make sure the first and last value of each row are set correctly. The earlier lessons in this module used loops to print shapes. This lesson uses a loop to build values, which is the next step.

The rows also show a pattern that you can check with a formula. That check is the main reason to read the rows as numbers, not as a shape.

The samples are in C++ and use the standard library. They compile with g++ -std=c++20 -Wall and the output shown was produced by running them on g++ 15.2.

The rule, built up one row at a time

Start with the first row. It has one value, and that value is 1.

row 0:  1

Each new row has one more value than the row above. The first and last values of every row are 1. Every other value is found by adding the two values just above it, one on the upper left and one on the upper right.

Here is row 1. It has two values, and both are the ends, so both are 1.

row 1:  1 1

Here is row 2. It has three values. The ends are 1. The middle value is the sum of the two values above it, which are 1 and 1. So the middle is 2.

row 2:  1 2 1

Here is row 3. It has four values. The ends are 1. The middle two values are found from row 2.

• The second value is the sum of the first two values of row 2, which is 1 + 2 = 3.
• The third value is the sum of the last two values of row 2, which is 2 + 1 = 3.

row 3:  1 3 3 1

Here is row 4. It has five values. The ends are 1. The middle three come from row 3.

• 1 + 3 = 4
• 3 + 3 = 6
• 3 + 1 = 4

row 4:  1 4 6 4 1

Each row is built from the row above it, and the rule never changes. That is the whole idea. The rest of the lesson is about writing the rule as a loop, and about checking the result.

Indexes: where a value lives

To write the rule in code, you need names for positions. Count rows from 0 at the top. Count the values inside a row from 0 at the left. The value in row r at position c is written as triangle[r][c].

Row r has r + 1 values. Row 0 has one value, row 1 has two, row 4 has five. The positions in row r run from 0 to r.

The value above and to the left of triangle[r][c] is triangle[r - 1][c - 1]. The value above and to the right is triangle[r - 1][c]. So the rule is:

triangle[r][c] = triangle[r - 1][c - 1] + triangle[r - 1][c]

This rule works only for the middle positions, where c is between 1 and r - 1. The ends are special. For c equal to 0 or c equal to r, the value is 1, and the rule would try to read a position that does not exist. That is why the code sets every value to 1 first, then changes only the middle ones.

Worked example 1: building the triangle in code

The program below keeps the rows in a std::vector of std::vector values. The outer vector holds the rows. Each inner vector holds the values of one row. A new row is made with r + 1 values, all set to 1. The loop then changes the middle values using the row above.

#include <iomanip>
#include <iostream>
#include <vector>
 
int main() {
    const int rows = 6;
    std::vector<std::vector<long long>> triangle;
 
    for (int r = 0; r < rows; ++r) {
        std::vector<long long> row(r + 1, 1);   // r + 1 values, all set to 1
        for (int c = 1; c < r; ++c) {           // the ends stay 1
            row[c] = triangle[r - 1][c - 1] + triangle[r - 1][c];
        }
        triangle.push_back(row);
    }
 
    for (int r = 0; r < rows; ++r) {
        for (int s = 0; s < rows - 1 - r; ++s) {
            std::cout << "  ";
        }
        for (long long value : triangle[r]) {
            std::cout << std::setw(4) << value;
        }
        std::cout << '\n';
    }
}

Output:

             1
           1   1
         1   2   1
       1   3   3   1
     1   4   6   4   1
   1   5  10  10   5   1

Three details matter in this program.

The row is created with std::vector<long long> row(r + 1, 1);. The first number is the size, and the second is the value that fills every position. This line gives the two ends the value 1 in one step.

The inner loop starts at c = 1 and stops before c = r. That covers exactly the middle values. If it started at 0, it would try to read triangle[r - 1][-1], which is outside the row.

The type is long long, not int. The reason is shown in the mistakes section. The values in the sixth row are small, but the same program would overflow with int if it went much further.

The printing loop adds spaces before each row so the triangle looks centred. The first inner loop prints rows - 1 - r pairs of spaces. Row 0 has the most spaces, and the last row has none. Each value is then printed with std::setw(4), which makes every number take at least four columns. This keeps the columns lined up, even when the numbers have different lengths.

Worked example 2: the rows are binomial coefficients

The value in row r, position c is a known quantity in mathematics. It is written C(r, c) and read as "r choose c". It is the number of ways to choose c items from a group of r items, when the order of the chosen items does not matter.

For example, C(4, 2) is 6. A group of four people has six ways to pick a pair. The pairs are AB, AC, AD, BC, BD and CD. The value 6 is in row 4, position 2 of the triangle.

This means that you can check any value without the triangle. The formula for C(n, k) is:

C(n, k) = n! / (k! * (n - k)!)

The exclamation mark means factorial. The factorial of 4 is 4 * 3 * 2 * 1, which is 24. Computing full factorials is a poor choice in code, because the numbers grow very fast and overflow early. A better method multiplies one factor at a time and divides right away:

#include <iostream>
 
// Number of ways to choose k items from n, computed one factor at a time.
// After step i the running value is C(n - k + i, i), so each division is exact.
long long binomial(int n, int k) {
    long long result = 1;
    for (int i = 1; i <= k; ++i) {
        result = result * (n - k + i) / i;
    }
    return result;
}
 
int main() {
    std::cout << "C(5,2) = " << binomial(5, 2) << '\n';
    std::cout << "C(6,3) = " << binomial(6, 3) << '\n';
    std::cout << "C(10,0) = " << binomial(10, 0) << '\n';
    std::cout << "C(34,17) = " << binomial(34, 17) << '\n';
}

Output:

C(5,2) = 10
C(6,3) = 20
C(10,0) = 1
C(34,17) = 2333606220

The comment in the function explains why the division is safe. After the first i steps, the running value is a whole number of ways, and the next multiplication and division keep it whole. In code, result * (n - k + i) / i is evaluated left to right, so the multiplication happens before the division. Doing the division first would give wrong answers.

The values match row 5, position 2 (10), and row 6, position 3 (20). You can check them by hand with the triangle from worked example 1.

Checking two patterns in the triangle

A check is a good habit. The next example checks two patterns that show up in the triangle.

The first pattern is symmetry. Each row reads the same from left to right and from right to left. Position c and position r - c hold the same value.

The second pattern is in the second position of each row. Position 1 of row r is always r, because C(r, 1) is the number of single items you can choose from r items.

#include <iostream>
#include <vector>
 
int main() {
    const int rows = 8;
    std::vector<std::vector<long long>> triangle;
 
    for (int r = 0; r < rows; ++r) {
        std::vector<long long> row(r + 1, 1);
        for (int c = 1; c < r; ++c) {
            row[c] = triangle[r - 1][c - 1] + triangle[r - 1][c];
        }
        triangle.push_back(row);
    }
 
    for (int r = 0; r < rows; ++r) {
        bool symmetric = true;
        for (int c = 0; c <= r; ++c) {
            if (triangle[r][c] != triangle[r][r - c]) {
                symmetric = false;
            }
        }
        std::cout << "row " << r << " symmetric: " << std::boolalpha << symmetric << '\n';
    }
 
    std::cout << "second value of each row:";
    for (int r = 1; r < rows; ++r) {
        std::cout << ' ' << triangle[r][1];
    }
    std::cout << '\n';
}

Output:

row 0 symmetric: true
row 1 symmetric: true
row 2 symmetric: true
row 3 symmetric: true
row 4 symmetric: true
row 5 symmetric: true
row 6 symmetric: true
row 7 symmetric: true
second value of each row: 1 2 3 4 5 6 7

The symmetry check uses two loops. The outer loop goes through the rows. The inner loop compares each value with the value at the mirrored position, r - c. The inner loop does not stop early when it finds a difference. It sets a flag and keeps going, which is simple and fast enough for a small table.

The second value check shows the values 1, 2, 3, and so on, one for each row. This is the first column of the triangle that is not made of ones.

Worked example 3: the row sums double

Add up the values in each row. The sums for the first six rows are 1, 2, 4, 8, 16 and 32. Each sum is double the one before it. The row sums are powers of 2.

You can see why from the rule. Each value in a row is added into two places in the next row, one place to its lower left and one to its lower right. The ends of each row are 1, and each of them is added into only one place. A short calculation shows that the sum of the next row is twice the sum of the current row.

Here is the program that prints the sums. It builds the same triangle, then adds up the values in each row.

#include <iostream>
#include <vector>
 
int main() {
    const int rows = 6;
    std::vector<std::vector<long long>> triangle;
 
    for (int r = 0; r < rows; ++r) {
        std::vector<long long> row(r + 1, 1);
        for (int c = 1; c < r; ++c) {
            row[c] = triangle[r - 1][c - 1] + triangle[r - 1][c];
        }
        triangle.push_back(row);
    }
 
    std::cout << "row sums:";
    for (const auto& row : triangle) {
        long long sum = 0;
        for (long long value : row) {
            sum += value;
        }
        std::cout << ' ' << sum;
    }
    std::cout << '\n';
}

Output:

row sums: 1 2 4 8 16 32

The range-based for loop, written for (long long value : row), visits each value in the row once. It is easier to read than an index loop when you do not need the position.

Going further: one row at a time

The program so far keeps every row in memory. That is useful when you need to look at any row later. If you only need to print the rows in order, you need just one row at a time. The new row can be built in the same vector that holds the old row, if you change the values in the right order.

Take row 2, which is 1 2 1, and build row 3 in the same vector. Add a 1 at the right end, so the vector is 1 2 1 1. Now update the middle values. Position 2 should become 1 + 2 = 3, which uses the value at position 1 of the old row. Position 1 should become 1 + 2 = 3, which uses the value at position 0. Position 1 must be updated after position 2, because position 2 needs the old value at position 1. Changing the values from right to left keeps the old values where they are needed.

#include <iostream>
#include <vector>
 
int main() {
    const int rows = 6;
    std::vector<long long> row = {1};   // holds only the current row
 
    for (int r = 0; r < rows; ++r) {
        for (long long value : row) {
            std::cout << value << ' ';
        }
        std::cout << '\n';
 
        // Build the next row in place. Going right to left means each
        // row[c - 1] still holds the value from the row above.
        row.push_back(1);                  // the new right end
        for (int c = static_cast<int>(row.size()) - 2; c >= 1; --c) {
            row[c] += row[c - 1];
        }
    }
}

Output:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 

The push_back(1) adds the new right end. Then the loop starts at the last position that is not the end, which is row.size() - 2 after the push. The loop stops at position 1, because position 0 is always 1. The line row[c] += row[c - 1]; is the rule written as a single step: the new value at c is the old value at c plus the old value at c - 1. Because the loop goes right to left, row[c - 1] has not been changed yet when it is read.

The cast static_cast<int>(row.size()) makes c a signed int, which matches the c >= 1 test. Without it the loop still runs correctly, but it mixes signed and unsigned values, the same mix that the warning in the hourglass lesson flags.

Each row is printed with a trailing space at the end of the line. That is harmless, but it is visible when you compare outputs, so keep it in mind.

Common mistakes

Overflow with int

The sum of two int values that is too big for an int is called an overflow. An int on most current systems holds values up to 2,147,483,647. The middle value of row 34 is 2,333,606,220, which is too big for an int.

The program below uses int for every value, and it prints two middle values:

#include <iostream>
#include <vector>
 
int main() {
    const int rows = 35;
    std::vector<std::vector<int>> triangle;
 
    for (int r = 0; r < rows; ++r) {
        std::vector<int> row(r + 1, 1);
        for (int c = 1; c < r; ++c) {
            row[c] = triangle[r - 1][c - 1] + triangle[r - 1][c];
        }
        triangle.push_back(row);
    }
 
    std::cout << "row 33 middle: " << triangle[33][16] << '\n';
    std::cout << "row 34 middle: " << triangle[34][17] << '\n';
}

Output from this program on g++ 15.2:

row 33 middle: 1166803110
row 34 middle: -1961361076

Row 33 is still correct. Row 34 prints a negative number, which cannot be right, because every value in Pascal's triangle is positive. In C++, a signed int overflow is undefined behaviour. That means the language does not promise any result. This compiler wrapped the value around, but a different compiler or a different optimisation setting could do something else. The fix is to use long long, as the lessons above do, or to check the result against the formula.

Reading past the end of a row

If the code reads a position that does not exist, the program may crash. Standard containers have a checked function, at(), which throws an exception when the position is out of range. This program has a row with four values, and it reads five:

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> row = {1, 3, 3, 1};
    for (int c = 0; c <= 4; ++c) {
        std::cout << row.at(c) << ' ';
    }
    std::cout << '\n';
}

Output:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 4) >= this->size() (which is 4)

The exit code is 134, which is the code for a program that stopped because of an unhandled exception. The message says the position was 4 and the size was 4. The valid positions are 0 to 3. The loop should run while c < row.size(), not c <= 4.

Using row[c] without at() does not check the position. The program may then print a random value or crash in a different place. That makes the error harder to find, so use at() while learning and switch to [] only when you are sure the positions are right.

Forgetting the ends

The rule for the middle values reads from the row above. The ends are not produced by the rule. If the code leaves an end unset, the value in it is not 1. Starting the inner loop at c = 0 makes the code read triangle[r - 1][-1], which is a position before the start of the row. Keep the loop from c = 1 to c < r, and set every value to 1 when the row is created.

Practice

1. Write the row 7 of Pascal's triangle without running the program. Then check your answer with binomial(7, k) for each k from 0 to 7.

Show the answer

The row is 1 7 21 35 35 21 7 1. Each middle value is the sum of two values from row 6, which is 1 6 15 20 15 6 1. For example, 6 + 15 = 21 and 15 + 20 = 35. The program that prints binomial(7, k) for k from 0 to 7 gives the same eight numbers.

2. Use the row sum pattern to find the sum of row 10 without building the row.

Show the answer

The sum is 2 to the power 10, which is 1024. Row r sums to 2^r, so row 10 sums to 1024.

3. Use binomial to print C(20, 10).

Show the answer

The output is 184756. The program is a call to binomial(20, 10) inside std::cout, with the same function as worked example 2.

4. Write a loop that prints the third value of each row, from row 2 to row 9. What pattern do you see?

Show the answer

The third value is C(r, 2), which is the number of pairs in r items. The values are 1, 3, 6, 10, 15, 21, 28 and 36. Each value is the previous one plus the row number minus 1, so the gaps grow by 1 each time. A loop that prints triangle[r][2] for r from 2 to 9 gives these eight numbers.

5. Change the program in worked example 1 so the triangle is printed left-aligned, with no spaces before the rows. Then say what changes in the code and what does not.

Show the answer

Remove the first inner loop that prints the spaces. Each row is then printed starting at the left edge. The loop that builds the triangle does not change, because the values do not depend on the spaces. Only the printing part is different.

Summary

• Each row of Pascal's triangle starts and ends with 1, and every other value is the sum of the two values above it.
• A row r has r + 1 values, and the position of a value is found with two indexes, the row and the column.
• A std::vector of std::vector values can hold rows of different lengths, and each new row is built from the row above it.
• The value in row r, position c, equals C(r, c), which a multiply-then-divide loop can compute without building the triangle.
• Row sums double from one row to the next, so row r sums to 2^r.
• Use long long for the values, and use at() while learning, so overflow and out-of-range positions are easier to spot.