CS202: Discrete Structures

Read this article for more information on the algebra of combinations.

Pascal's triangle is a simple, manual way to calculate binomial coefficients.

Look at the table at the bottom of the reading. The first column, (0,1,2,3,4,5), contains the numbers of the rows - the 0^th row, 1^st row, 2^nd row, etc. - and corresponds to the exponent 'n' in (x + y)_n .

Ignore the first column for the moment. Take the n^th row and shift it n spaces to the left, i.e. the 0^th row is not shifted, the 1^st row is shifted 1 space to the left, the 2^nd row is shifted 2 spaces to the left, the 3^rd row is shifted 3 spaces to the left, etc. This shifting results in a shape of a triangle - '1' is at the top of the triangle in the 0^th row, '1 1' is next in the 1^st row offset by one space (so that the '1' at the top is above the space in '1 1'), etc. This triangle for n from 0 to 5 generalizes to any n and is called Pascal's triangle. These numbers are the coefficients for the binomial equation presented in the following subunit.