Wednesday, August 17, 2016

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

Distraction Deterrents in Small Contexts

"distracted from distraction by distraction" - T.S. Eliot I've been reading a little on how Facebook and other social netwo...