Calculate a row of Pascal’s triangle in C#

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.