Pascals Triangle

mgcadmin 11-24-2025

For todays post I'm going to go in a bit of a different direction than I normally do. 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 define 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 its found useful in, everything from finding optimal shellsort sequences to fractal geometry, statistics, and more.

The Obvious Approach

From looking at the above image its not difficult to see how one comeputes 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!

---