Day 10: CM, Page x

Day 10. This section is called "A Note on Notation". It has a discussion of some of the notation used later in the book. Let's look at some of the interesting notation.

n¡ is a subfactorial: n!/0! - n!/1! + ... + (-1)^n * n!/n!. A subfactorial "gives the number of permutations of a sequence of n distinct values in which none of the elements occur in their original place.... In practical terms, subfactorial is the number of ways in which n persons can each give one present to one other person so that everyone receives a present" (wikipedia).

ln x: natural logarithm: log base e of x. "The mathematical constant e is the unique real number such that the function e^x has the same value as the slope of the tangent line, for all values of x." I got distracted reading about e and stumbled across Cantor's diagonal argument. I had forgotten about that from college. It's a great little observation about why the set of all sequences of 1s and 0s are not countable (i.e. there are more sequences of 1s and 0s than there are natural numbers).

s₁ = (0, 0, 0, 0, 0, 0, 0, ...)

s₂ = (1, 1, 1, 1, 1, 1, 1, ...)

s₃ = (0, 1, 0, 1, 0, 1, 0, ...)

s₄ = (1, 0, 1, 0, 1, 0, 1, ...)

s₅ = (1, 1, 0, 1, 0, 1, 1, ...)

s₆ = (0, 0, 1, 1, 0, 1, 1, ...)

s₇ = (1, 0, 0, 0, 1, 0, 0, ...)

...

s₀ = (1, 0, 1, 1, 1, 0, 1, ...)

Each sequences s1, s2, etc, above is some unique sequence of 1s and 0s. Each sequence is numbered from 1 out to infinity. s zero is constructed so that it is different from every other sequence in it's nth position. This suggests a mapping from the sequences of ones and zeros to the natural numbers cannot be constructed. For any sequence we can create and put in our list, we can create a sequence that is not in the list (s zero).

We'll get to the rest of the notation in more gory detail later. Here's a picture of Cantor: