The Recurrence Relation of Pascal's Triangle

By -
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.

Comments

  1. Samson Corwell11:31 PM

    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

Post a Comment

Popular posts from this blog

Libertarians, My Libertarians!

By -
Cruel to be kind means that I love you . Because, while I think you are mistaken, your hearts are in the right place -- yes, even you, Silas --  unlike some people . This Breitbart fellow (discussed in the link above), by all appearances, deliberately doctored a video of Shirley Sherrod to make her remarks appear virulently racist, when they had, in fact, the opposite import. I heard that at a recent Austrian conference, some folks were talking about "Callahan's conservative turn." While that description is not entirely inaccurate, I must say that a lot of these people who today call themselves conservative give me the heebie-jeebies.
Read more

"Pre-Galilean" Foolishness

By -
 I am currently reading The Master and His Emissary , which appears to be an excellent book. ("Appears" because I don't know the neuroscience literature well enough to say for sure, yet.) But then on page 186 I find: "Asking cognition, however, to give a perspective on the relationship between cognition and affect is like asking astronomer in the pre-Galilean geocentric world, whether, in his opinion, the sun moves round the earth of the earth around the sun. To ask a question alone would be enough to label one as mad." OK, this is garbage. First of all, it should be pre-Copernican, not pre-Galilean. But much worse is that people have seriously been considering heliocentrism for many centuries before Copernicus. Aristarchus had proposed a heliocentric model in the 4th-century BC. It had generally been considered wrong, but not "mad." (And wrong for scientific reasons: Why, for instance, did we not observe stellar parallax?) And when Copernicus propose...
Read more