Pascal's Triangle

By -

For a computer programmer, an interesting way to understand Pascal's triangle is to look at it as describing strings of n bits, where n is a row of the triangle.

The first and the last elements in the row, which are always one, are the number of ways to have all bits zero or all bits one, which is naturally just one way. The second element and the second-to-last element are the number of ways to have one bit on, and the number of ways to have all but one bit on. These are always going to be equal to the length of the string, or, in other words, the row number. That is because if your string is, say, three bits, you can have bit zero on, bit one on, or bit two on: three ways to have one bit turned on:


100            010           001


And so on.

This of course very easily makes clear that the numbers in row n will add up to 2n: that is how many numbers you can represent with a string of n bits!

Comments

  1. shonk6:38 PM

    And now, for extra fun, prove that the number of ways of turning on exactly k out of n bits satisfies the recurrence relation that defines Pascal's triangle.

    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