Pascal & Bernoulli & Floyd: Triangles

mgcadmin 11-24-2025

For todays post I'm going to go in a bit of a different direction than I normally do. After watching a pretty interesting video (in my humble opinion, anyway) on Pascals Triangle, I found myself surfing through wikipedia (as one does) and ultimately arrived on the page for a "list of triangles of numbers". These being trianglular arrays, or a half-matrix who's element's are comprised of different sets of integers. The most famous of these being Pascals Triangle. I'm sure most readers are familiar with pascals triangle, but for those who aren't it's this:

Or, I should say that's the first 8 rows of it: Pascals triangle is technically infinite. Infact, most common definitions of pascals triangle uses that very word to describe it as "An infinite triangluar array of the bionomial coefficients". A rather drab definition if I do say so myself. It also belies the startling number of practical applications peopl have found for it, everything from finding optimal shellsort sequences to fractal geometry, statistical analysis, and more.

Warming up: Floyd's Triangle

Before we really get in to Pascals triangle, there is another triangle I want to mention which caught my attention: Floyd's Triangle. It's not so much the integer sequence that makes this triangle interesting, but rather who it's named for: Robert Floyd of heapsort, and transitive closure fame.While it is among the least interesting of all the triangles on the list, it does have one important property: It exists merely to show how a triangluar matrix should be iterated in-order.

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21

Simply speaking, to process a triangular matrix we iterate the rows as normal, but the number of columns is governed by the number of rows:

    int count = 1;
    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < row; col++) {
            cout<<count++<<" ";
        }
        cout<<endl;
    }

Nothing earth shattering, I know. But since everything else in this post relies on using the same iteration order I thought it worth mentioning. And now back to something more interesting.

Computing Pascals Triangle with Dynamic Programming

By rotating Pascals triangle so it is layed out as floyds triangle, its not difficult to see how one computes each row. If we were to put it in a table, with the first column being comprised of all ones, we expand each following row by one place, computing the next digit from the sum of the two digits above it. A dynamic programming algorithm practically writes its-self from the above description:

void pascalsTri(int numRows) {
    vector<vector<int>> tri(numRows, vector<int>(numRows, 0));
    for (int i = 0; i < numRows; i++)
        tri[i][0] = 1;
    for (int i = 0; i < numRows; i++) {
        for (int j = 1; j <= i; j++) {
            tri[i][j] = (j-1 < i-1 ? tri[i-1][j-1]:0) + (j < i-1 ? tri[i-1][j]:1);
        }
    }
    printTri(tri);
}

 

The Less Obvious Approach

Another way of interpreting the above triangle is to use the recurrance relation known as "Pascals Rule":

(n)        (n-1)        (n-1)
       =             +
(k)        (k-1)          (k)

This applies to any integer where 0 < k < n, and (0/0) = 1. This yields the following triangle of bionomial coefficients:

The above formula also neatly translates into the following recursive procedure:

int pasc(int n, int k) {
    if (k == 0 || n == k)
        return 1;
    return pasc(n-1, k-1)+pasc(n-1, k);
}

This procedure computes independent elements, where n is the row and k is the column. So to print the entire triangle, we use a loop like the following:

 for (int n = 0; n < 10; n++) {
    for (int t = 10; t > n; t--) cout<<" ";
    for (int k = 0; k < 10; k++) {
        if (n > k && k >= 0)
            cout<<setw(3)<<pasc(n, k)<<" ";
    }
    cout<<setw(3)<<1<<endl;
  }

This is of course a terribly inneficient way of computing our triangle as we are constantly re-computing values we've already previously computed. The dynamic programming solution from above being far more efficient. 

If however, we were to take the same program from above, and tweak it so that instead of printing the computed number, we print a blank space if the number is even, and asterik if the number is odd? Strangely specific question, but as a matter of fact, a a funny thing happens.

mgoren@~$ ./pasc 16
                  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
           1   7  21  35  35  21   7   1
          1   8  28  56  70  56  28   8   1
         1   9  36  84 126 126  84  36   9   1
        1  10  45 120 210 252 210 120  45  10   1
       1  11  55 165 330 462 462 330 165  55  11   1
      1  12  66 220 495 792 924 792 495 220  66  12   1
     1  13  78 286 715 1287 1716 1716 1287 715 286  78  13   1
    1  14  91 364 1001 2002 3003 3432 3003 2002 1001 364  91  14   1
   1  15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105  15   1
                  *
                 *   *
                *       *
               *   *   *   *
              *               *
             *   *           *   *
            *       *       *       *
           *   *   *   *   *   *   *   *
          *                               *
         *   *                           *   *
        *       *                       *       *
       *   *   *   *                   *   *   *   *
      *               *               *               *
     *   *           *   *           *   *           *   *
    *       *       *       *       *       *       *       *
   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *

We get a Sirpenski Triangle!

---