Calculate a row of Pascal’s triangle in C#


[Pascal's triangle]

[Pascal's triangle]

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 [Pascal's triangle], 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 [Pascal's triangle].

If you number the rows and columns in Pascal’s triangle starting with 0, then [Pascal's triangle] sits in row n column k of the triangle. For example, [Pascal's triangle] 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 [Pascal's triangle] as k = 1, 2, 3, …, n.

For example, here are the values for row 5:


[Pascal's triangle]

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.


Download Example   Follow me on Twitter   RSS feed   Donate




About RodStephens

Rod Stephens is a software consultant and author who has written more than 30 books and 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java.
This entry was posted in algorithms, mathematics and tagged , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *