Title: 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.
Download the example to experiment with it and to see additional details.
