Pascal’s triangle starts with a 1 at the top. To construct a new row for the triangle, you add a 1 below and to the left of the row above. After that, each entry in the new row is the sum of the two entries above it. Figure 1 shows the first six rows (numbered 0 through 5) of the triangle.

Pascal’s triangle has many interesting properties. One of the most basic is that it generates binomial coefficients. The binomial coefficient , which is pronounced “n choose k,” is the number of ways you can select k items from a set of n items. For example, suppose you have a set containing four items: {A, B, C, D}. There are six ways you can select two items from this set (AB, AC, AD, BC, BD, and CD) so .

If you number the rows and columns in Pascal’s triangle starting with 0, then sits in row n column k of the triangle. For example, and entry 2 in row 4 is 6.

The post Calculate the binomial coefficient “N choose K” efficiently in C# shows how you can calculate a single value in the triangle. You can also use the method described above to build a full Pascal’s triangle, but if you only want to know the values in a particular row or diagonal you can calculate them directly. See this Wikipedia entry for details.

To calculate the values in a row, you start with the value 1. Then if you’re building row n, you multiply the value by as k = 1, 2, 3, …, n.

For example, here are the values for row 5:

This example uses the following code to generate the values in a row of Pascal’s triangle.

// Return the coefficients in a row of Pascal's triangle. private List<long> PascalRow(long row_number) { checked { long n = row_number; // Make the results as a list of long. List<long> results = new List<long>(); long value = 1; results.Add(value); // Calculate the values. for (int k = 1; k <= n; k++) { value = (value * (n + 1 - k)) / k; results.Add(value); } return results; } }

The method creates a List<long> to hold the values for the row. It then makes variable `k` loop from 1 to `n` and calculates each of the row’s values.

The only trick here is that the code must multiply the previous value by `(n + 1 - k)` before it divides by `k` because `k` may not divide evenly into either the previous value or `(n + 1 - k)` and every entry in Pascal’s triangle must be an integer.

For example, look at the fifth equation in the calculation of the values for row 5. The value 4 doesn’t divide evenly into the previous value 10 or the numerator 2 so you must multiply 10 and 2 before you try to divide by 4.

The example program uses the `PascalRow` method to generate the values for a row of the triangle and then displays the results in a string. Download the example to see additional details.

For more information on Pascal’s triangle, see Wikipedia or Wolfram MathWorld.

It never ceases to amaze me that there is always a simple solution to an otherwise involved problem. This is so much better than trying to calculate using factorials and much more convenient than creating a lookup table. Thanks!