The Recurrence Relation of Pascal's Triangle

Start here.

Then, let's say we want to have three bits (k) on in a five-bit (n) word: how many ways can we do this?

Well, we can start by saying bit zero must be on or off.

If it is on, then we have 4 (or n - 1) bits left from which to choose 2 (or k - 1) on bits.

If it is off, then we have 4 (or n - 1) bits left from which to choose 3 (or k) on bits.

Thus, the number of ways we can choose k on bits from n bits equals the number of ways we can choose (k - 1) bits from (n -1) bits plus the number of ways we can choose k bits from (n - 1) bits. Or:


And thus we derive the recurrence relation for Pascal's triangle from an analysis of it as describing bit strings.

1 comment:

  1. Is there a non-recursive way to calculate it? Like a function that takes the level in the triangle and the distance from the "center" as parameters and returns the number at that position?

    ReplyDelete