[C# Helper]
Index Books FAQ Contact About Rod
[Beginning Database Design Solutions, Second Edition]

[Beginning Software Engineering, Second Edition]

[Essential Algorithms, Second Edition]

[The Modern C# Challenge]

[WPF 3d, Three-Dimensional Graphics with WPF and C#]

[The C# Helper Top 100]

[Interview Puzzles Dissected]

[C# 24-Hour Trainer]

[C# 5.0 Programmer's Reference]

[MCSD Certification Toolkit (Exam 70-483): Programming in C#]

Title: Calculate a row of Pascal's triangle in C#

[Calculate a row of Pascal's triangle in C#]
[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 [Calculate a row of Pascal's triangle in C#], 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 [Calculate a row of Pascal's triangle in C#].

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

For example, here are the values for row 5:

[Calculate a row of Pascal's triangle in C#]

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.

© 2009-2023 Rocky Mountain Computer Consulting, Inc. All rights reserved.