My Favorite One-Liners: Part 27

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them.

Here’s an anecdote that I’ll share when teaching students about factorials:

$1! = 1$

$2! = 1 \times 2 = 2$

$3! = 1 \times 2 \times 3 = 6$

$4! = 1 \times 2 \times 3 \times 4 = 24$

$5! = 1 \times 2 \times 3 \times 4 \times 5 = 120$

The obvious observation is that the factorials get big very, very quickly.

Here’s my anecdote:

Many years ago, I was writing lesson plans while the TV show “Wheel of Fortune” was on in the background. And the contestant solved the puzzle at the end, and Pat Sajak declared, “You have just won $40,320 in cash in prizes.

So I immediately thought to myself, “Ah, 8 factorial.”

Then I thought, ugh [while slapping myself in the forehead, grimacing, and shaking my head, pretending that I can’t believe that that was the first thought that immediately came to mind].

[Finishing the story:] Not surprisingly, I was still single when this happened.

My Mathematical Magic Show: Part 7

This mathematical trick, which may well be the best mathematical magic trick ever devised, was not part of my Pi Day magic show. However, it should have been. Here’s a description of the trick, modified from the description at http://mathoverflow.net/questions/20667/generalization-of-finch-cheneys-5-card-trick:

The magician walks out of the room. A volunteer from the crowd chooses any five cards at random from a deck, and hands them to your assistant so that nobody else can see them. The assistant glances at them briefly and hands one card back, which the volunteer then places face down on the table to one side. The assistant quickly place the remaining four cards face up on the table, in a row from left to right. After all of this is completed, the magician re-enters the room, inspects the faces of the four cards, and promptly names the hidden fifth card.

In turns out that the trick is a clever application of permutations (there are $3! = 6$ possible ways of ordering 3 objects) and the pigeon-hole principle (if each object belongs to one of four categories and there are five objects, then at least two objects must belong to the same category). These principles from discrete mathematics (specifically, combinatorics) make possible the Fitch-Cheney 5-Card Trick.

Unlike the other tricks in this series, the Fitch-Cheney 5-Card Trick requires a well-trained assistant (or a smartphone app that plays the role of the assistant).

A great description of how this trick works can be found at Math With Bad Drawings. For a deeper look at some of the mathematics behind this trick, I give the following references:

The number of digits of n!: Index

I’m doing something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on computing the number of digits in $n!$ .

Part 1: Introduction – my own childhood explorations.

Part 2: Why a power-law fit is inappropriate.

Part 3: The correct answer, using Stirling’s formula.

Part 4: An elementary derivation of the first three significant terms of Stirling’s formula.

The number of digits in n! (Part 4)

When I was in school, I stared at this graph for weeks, if not months, trying to figure out an equation for the number of digits in $n!$ . And I never could figure it out. However, even though I was not able to figure this out for myself, there is a very good approximation using Stirling’s approximation. The next integer after $\log_{10} n!$ gives the number of digits in $n!$ , and

$\log_{10} n! \approx \displaystyle \frac{\left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \displaystyle \frac{1}{2} \ln (2\pi)}{\ln 10}$

The graph below shows just how accurate this approximation really is. The solid curve is the approximation; the dots are the values of $\log_{10} n!$ . Not bad at all… the error in the curve is smaller than the size of the dots.

The following output from a calculator shows just how close the approximation to $log_{10} 69!$ is to the real answer. There are also additional terms to Stirling’s series that would get even closer answers.

As I mentioned earlier in this series, I’m still mildly annoyed with my adolescent self that I wasn’t able to figure this out for myself… especially given the months that I spent staring at this problem trying to figure out the answer.

First, I’m annoyed that I didn’t think to investigate $\log_{10} n!$ . I had ample experience using log tables (after all, this was the 1980s, before scientific calculators were in the mainstream) and I should have known this.

Second, I’m annoyed that I didn’t have at the tips of my fingers the change of base formula

$\log_{10} n! = \displaystyle \frac{\ln n!}{\ln 10}$

Third, I’m annoyed that, even though I knew calculus pretty well, I wasn’t able to get at least the first couple of terms of Stirling’s series on my own even though the derivation was entirely in my grasp. To begin,

$\ln n! = \ln (1 \cdot 2 \cdot 3 \dots \cdot n) = \ln 1 + \ln 2 + \ln 3 + \dots + \ln n$

For example, if $n = 10$ , then $\ln 10!$ would be the areas of the 9 rectangles shown below (since $\ln 1 = 0$):

The areas of these nine rectangles is closely approximated by the area under the curve $y = \ln x$ between $x =1\frac{1}{2}$ and $x = 10\frac{1}{2}$ . (Indeed, I chose a Riemann sum with midpoints so that the approximation between the Riemann sum and the integral would be very close.)

In general, for $n!$ instead of $10!$ , we have

$\ln n! \approx \displaystyle \int_{3/2}^{n+1/2} \ln x \, dx$

This is a standard integral that can be obtained via integration by parts:

$\ln n! \approx \bigg[ \displaystyle x \ln x - x \bigg]_{3/2}^{n+1/2}$

$\ln n! \approx \left[ \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n + \displaystyle \frac{1}{2} \right) - \left(n + \displaystyle \frac{1}{2} \right) \right] - \left[ \displaystyle \frac{3}{2} \ln \frac{3}{2} - \frac{3}{2} \right]$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n + \displaystyle \frac{1}{2} \right) - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

We can see that this is already taking the form of Stirling’s approximation, given above. Indeed, this is surprisingly close. Let’s use the Taylor approximation $\ln(1+x) \approx x$ for $x \approx 0$ :

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln \left(n \left[1 + \displaystyle \frac{1}{2n}\right] \right) - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \left[\ln n + \ln \left(1 + \displaystyle \frac{1}{2n} \right) \right] - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \left[\ln n + \displaystyle \frac{1}{2n} \right] - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n + \left(n + \displaystyle \frac{1}{2} \right) \displaystyle \frac{1}{2n} - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n +\displaystyle \frac{1}{2} + \frac{1}{4n} - n - \displaystyle \frac{3}{2} \ln \frac{3}{2} + 1$

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \left(\displaystyle \frac{3}{2} - \displaystyle \frac{3}{2} \ln \frac{3}{2} \right) + \displaystyle \frac{1}{4n}$

By way of comparison, the first few terms of the Stirling series for $\ln n!$ are

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \displaystyle \frac{1}{2} \ln (2\pi) + \displaystyle \frac{1}{12n}$

We see that the above argument, starting with an elementary Riemann sum, provides the first two significant terms in this series. Also, while the third term is incorrect, it’s closer to the correct third term that we have any right to expect:

$\displaystyle \frac{3}{2} - \displaystyle \frac{3}{2} \ln \frac{3}{2} \approx 0.8918\dots$

$\displaystyle \frac{1}{2} \ln (2\pi) \approx 0.9189\dots$

The correct third term of $\displaystyle \frac{1}{2} \ln(2\pi)$ can also be found using elementary calculus, though the argument is much more sophisticated that the one above. See the MathWorld website for details.

The number of digits in n! (Part 3)

The following graph shows the number of digits in $n!$ as a function of $n$ .

When I was in school, I stared at this graph for weeks, if not months, trying to figure out an equation that would fit these points. And I never could figure it out.

When I took calculus in college, I distinctly remember getting up the nerve to ask my professor, the great L.Craig Evans (now at UC Berkeley), if he knew how to solve this problem. To my great consternation, he immediately wrote down what I now realize to be the right answer, using Stirling’s approximation:

$\ln n! \approx \left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \frac{1}{2} \ln (2\pi)$

While I now know that this was the way to go about solving this problem, I didn’t appreciate how this formula could help me at the time. I only saw the $n!$ on the left-hand side and did not see the immediate connection between this formula and the number of digits in $n!$ .

But now I know better.

For starters, the number of base-10 digits in a number $n$ is always the next integer greater that $\log_{10} n$ . For example, $\log_{10} 2000 \approx 3.301$, and the next integer larger than $3.301$ is 4. Unsurprisingly, the number $2000$ has 4 digits.

Second, the change of base formula for logarithms gives

$\log_{10} n! = \displaystyle \frac{\ln n!}{\ln 10}$

Therefore, the number of digits in $n!$ will be about

$\displaystyle \frac{\left(n + \displaystyle \frac{1}{2} \right) \ln n - n + \frac{1}{2} \ln (2\pi)}{\ln 10}$

The graph below shows just how accurate this approximation really is. The solid curve is the approximation; the dots are the values of $\log_{10} n!$ . (In other words, this series of dots are only slightly different than the dots above, which have integers as coordinates.) Not bad at all… the error in the approximation is smaller than the size of the dots in this picture.

The number of digits in n! (Part 2)

The following graph shows the number of digits in $n!$ as a function of $n$ .

When I was in school, I stared at this graph for weeks, if not months, trying to figure out an equation that would fit these points. And I never could figure it out.

In retrospect, my biggest mistake was thinking that the formula had to be something like $y = a x^m$ , where the exponent $m$ was a little larger than 1. After all, the graph is clearly not a straight line, but it’s also not as curved as a parabola.

What I didn’t know then, but know now, is that there’s a really easy way to determine to determine if a data set exhibits power-law behavior. If $y = a x^m$ , then

$\ln y = \ln a + m \ln x$ .

If we make the substitutions $Y = \ln Y$ , $B = \ln a$ , and $X = \ln x$ , then this equation becomes

$Y = m X + B$

In other words, if the data exhibits power-law behavior, then the log-transformed data would look very much like a straight line. Well, here’s the graph of $(X,Y)$ after applying the transformation:

Ignoring the first couple of pots, the dots show an ever-so-slight concave down pattern, but not enough that would have discouraged me from blindly trying a pattern like $y = a x^m$ . However, because these points do not lie on a straight line and exhibit heteroscedastic behavior, my adolescent self was doomed to failure.

The number of digits in n! (Part 1)

When I was in school, perhaps my favorite pet project was trying to find a formula for the number of digits in $n!$ . For starters:

$0! = 1$ : 1 digit
$1! = 1$ : 1 digit
$2! = 2$ : 1 digit
$3! = 6$ : 1 digit
$4! = 24$ : 2 digits
$5! = 120$ : 3 digits
$6! =720$ : 3 digits
$7! = 5040$ : 4 digits
$8! = 40,320$ : 5 digits

I owned what was then a top-of-the-line scientific calculator (with approximately the same computational capability as a modern TI-30), and I distinctly remember making a graph like the following on graph paper. The above calculations contribute the points $(0,1)$ , $(1,1)$ , $(2,1)$ , $(3,1)$ , $(4,2)$ , $(5,3)$ , $(6,3)$ , $(7,4)$ , and $(8,5)$ .

I had to stop (or, more accurately, I thought I had to stop) at $69!$ because my calculator couldn’t handle numbers larger than $10^{100}$ .

I stared at this graph for weeks, if not months, trying to figure out an equation that would fit these points. And I never could figure it out.

And, to this day, I’m somewhat annoyed at my adolescent self that I wasn’t able to figure out this puzzle for myself… since I had all the tools in my possession needed to solve the puzzle, though I didn’t know how to use the tools.

In this series of posts, I’ll answer this question with the clever application of some concepts from calculus and precalculus.

Why does 0! = 1? (Index)

I’m using the Twelve Days of Christmas (and perhaps a few extra days besides) to do something that I should have done a long time ago: collect past series of posts into a single, easy-to-reference post. The following posts formed my series on how I explain to students that $0! = 1$ .

Part 1: Multiplication and division.

Part 2: Combinatorics.

Lessons from teaching gifted elementary school students (Part 3a)

Every so often, I’ll informally teach a class of gifted elementary-school students. I greatly enjoy interacting with them, and I especially enjoy the questions they pose. Often these children pose questions that no one else will think about, and answering these questions requires a surprisingly depth of mathematical knowledge.

Here’s a question I once received:

Suppose

$A \times A = B$

$B \times B \times B = C$

$C \times C \times C \times C= D$

If the pattern goes on, and if $A = 2$ , what is $Z$ ?

I leave a thought bubble in case you’d like to think this. (This is significantly more complicated to do mentally than the question posed in yesterday’s post.) One way of answering this question appears after the bubble.

Let’s calculate the first few terms to try to find a pattern:

$B = 2 \times 2 = 2^2$

$C = 2^2 \times 2^2 \times 2^2 = 2^6$

$D = 2^6 \times 2^6 \times 2^6 \times 2^6 = 2^{24}$

etc.

Written another way,

$A = 2^1 = 2^{1!}$

$B = 2^{2!}$

$C = 2^{3!}$

$D = 2^{4!}$

Naturally, elementary school students have no prior knowledge of the factorial function. That said, there’s absolutely no reason why a gifted elementary school student can’t know about the factorial function, as it only consists of repeated multiplication.

Continuing the pattern, we see that $Z = 2^{26!}$ . Using a calculator, we find $Z \approx 2^{4.032014611 \times 10^{26}}$ .

If you try plugging that number into your calculator, you’ll probably get an error. Fortunately, we can use logarithms to approximate the answer. Since $2 = 10^{\log_{10} 2}$ , we have

$Z = \left( 10^{\log_{10} 2} \right)^{4.032014611 \times 10^{26}} = 10^{4.032014611 \times 10^{26} \log_{10} 2}$

Plugging into a calculator, we find that

$Z \approx 10^{1.214028268 \times 10^{26}} = 10^{121.4028628 \times 10^{24}}$

We conclude that the answer has more than 121 septillion digits.

How big is this number? if $Z$ were printed using a microscopic font that placed 100,000 digits on a single line and 100,000 lines on a page, it would take 12.14 quadrillion pieces of paper to write down the answer (6.07 quadrillion if printed double-sided). If a case with 2500 sheets of paper costs $100, the cost of the paper would be $484 trillion ($242 trillion if double-sided), dwarfing the size of the US national debt (at least for now). Indeed, the United States government takes in about $3 trillion in revenue per year. At that rate, it would take the country about 160 years to raise enough money to pay for the paper (80 years if double-sided).

And that doesn’t even count the cost of the ink or the printers that would be worn out by printing the answer!

Why does 0! = 1? (Part 2)

This common question arises because $0!$ does not fit the usual definition for $n!$ . Recall that, for positive integers, we have

$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$

$4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$

$3! = 3 \cdot 2 \cdot 1 = 6$

$2! = 2 \cdot 1 = 2$

$1! = 1$

In Part 1 of this series, I discussed descending down this lines with repeated division to define $0!$ .

Here’s a second way of explaining why $0!=1$ that may or may not be as convincing as the first explanation. Let’s count the number of “words” that can made using each of the three letters A, B, and C exactly once. Ignoring that most of these don’t appear in the dictionary, there are six possible words:

ABC, ACB, BAC, BCA, CAB, CBA

With two letters, there are only two possible words: AB and BA.

With four letters, there are 24 possible words:

ABCD, ABDC, ACBD, ACDB, ADBC, ADCB,
BACD, BADC, BCAD, BCDA, BDAC, BDCA,
CABD, CADB, CBAD, CBDA, CDAB, CDBA,
DABC, DACB, DBAC, DBCA, DCAB, DCBA.

Evidently, there are $4!$ different words using four letters, $3!$ different words using three letters, and $2!$ different words using two letters.

Why does this happen? Let’s examine the case of four letters. First, there are $4$ different possible choices for the first letter in the word. Next, the second letter can be anything but the first letter, so there are $3$ different possibilities for the second letter. Then there are $2$ remaining possibilities for the third letter, leaving $1$ possibility for the last.

In summary, there are $4 \cdot 3 \cdot 2 \cdot 1$ , or $4!$ , different possible words. The same logic applies for words formed from three letters or any other number of letters.

What if there are 0 letters? Then there is only 1 possibility: not making any words. So it’s reasonable to define $0!=1$ .

green line

It turns out that there’s a natural way to define $x!$ for all complex numbers $x$ that are not negative integers. For example, there’s a reasonable way to define $\left( \frac{1}{2} \right)!$ , $\left(- \frac{7}{3} \right)!$ and even $(1+2i)!$ . I’ll probably discuss this in a future post.