for the classroomBookmarks
Open A Vein (homepage).
e-mail: vlorbik@gmail.comW'press login.
More mathy stuff by me:
Lectures Without Words (drawings mostly)
Community College Calculus (S '09)
Math 148: Precalculus (W '09)
.
Listserv posts: amte (11/98—8/00)... math-teach (6/05—11/06)Alas, gmail.
Carmen.
Buckeye Link.
VK on facebook.
May 6, 2010 at 8:26 pm
the lecture notes i wrote up in TeX once
but have very likely lost were along the
following lines.
consider grids of “streets”
AX
XB
AXX
XXX
XXB
AXXX
XXXX
XXXX
XXXB
and so on; count “paths”
from A to B using “east”
and “south” “moves”…
May 7, 2010 at 1:08 pm
not lost. presently useless though.
\def\nCr#1#2{{#1}\choose{#2}}
\noindent
Consider a grid of city blocks, with numbered streets and lettered avenues.
Suppose your daily routine includes walking from the corner of
$1^{st}$ and A to the corner of $5^{th}$ and E.
$$\matrix
\null&1^{st}&\null&2^{nd}&\null&3^{rd}&\null&4^{th}&\null&5^{th}\cr
A&\circ&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
B&\bullet&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
C&\bullet&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
D&\bullet&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
E&\bullet&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\text{?}\cr
\endmatrix$$
You like a lot of variety, so you decide to try all the different
paths available. Of course, you don’t want to backtrack, so you’ll
always be travelling either East or South. Maybe the first day you
go EEEESSSS, that is, you travel along A Street to the east for
four blocks and then go south on $5^{th}$ Avenue for four blocks.
The next day you might take the “zig-zag” path SESESESE: go
south on $1^{st}$, turn east on B, turn south on $2^{nd}$, turn
east on C, and continue to turn each time. It’s easy to see that
there are quite a few different paths you might take, and it’s
natural to ask “how many?”.
This is a good point to stop and try to answer that question.
I’ll wait right here.
Okay, are you through? Good. Let’s see if our answers agree.
In typical math teacher fashion, though, I’m not going to give you
my answer right out—it’s the reasoning {\it behind} the answer
that’s interesting, so I’ll try to explain every step of the way.
It’s a pretty hard problem. A good strategy in the face of a hard
problem is to try to find an easier problem with some of the same
features. For example, it’s pretty easy to see that in the much
simpler set-up
$$\matrix
\null&1^{st}&\null&2^{nd}\cr
A&\circ&\rightarrow&\bullet\cr
\null&\downarrow&\null&\downarrow\cr
B&\bullet&\rightarrow&\text{?}\cr
\endmatrix$$
there are exactly {\it two} possibilities: ES and SE.
This doesn’t seem to shed much light, though, so try another.
$$\matrix
\null&1^{st}&\null&2^{nd}&\null&3^{rd}\cr
A&\circ&\rightarrow&\bullet&\rightarrow&\bullet\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
B&\bullet&\rightarrow&2&\rightarrow&\bullet\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
C&\bullet&\rightarrow&\bullet&\rightarrow&\text{?}\cr
\endmatrix$$
The “2” indicates that there are two ways to reach $2^{nd}$ and
B (as we saw a moment ago). But how many paths are there to get
to $3^{rd}$ and C?
A little experimentation yields EESS, ESES, ESSE, SEES, SESE, and
SSEE; apparently there are {\it six} such paths. Can this fact be
explained in some way? Well, let’s fill in {\it all}
the numbers.
$$\matrix
\null&1^{st}&\null&2^{nd}&\null&3^{rd}\cr
A&\circ&\rightarrow&1&\rightarrow&1\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
B&1&\rightarrow&2&\rightarrow&\text{?}\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
C&1&\rightarrow&\text{?}&\rightarrow&6\cr
\endmatrix$$
All along A avenue, there’s only {\it one} path: keep moving
east. Likewise for $1^{st}$ street: keep moving south.
What about the corners marked with ?’s ? Well, to get to
$2^{nd}$ and C, we’ll have to go a total of three blocks;
exactly one of them will be to the east. So we have
ESS, SES, and SSE. Similarly, to reach $3^{rd}$ and B
we’ll have to go three blocks, but this time exactly one
of them must be to the south: SEE, ESE, and EES.
Three ways each.
Now it so happens that
$6 = 3 + 3$: is this a coincidence, or did it happen for
some reason? Well, think of it this way: to reach the
“6” in our diagram, we have to go through exactly one
of the ?’s. Either we’ll go to $2^{nd}$ and C and then
go east or go to $3^{rd}$ and B and then go south.
In the first case, we’ll put an “E” at the end of
one of ESS, SES, or SSE; in the second case we’ll put
an “S” at the end of one of SEE, ESE, and EES. So
it’s not at all a coincidence that the equation $6 = 3 + 3$
contains the numbers at these three corners: there’s
a very general rule at work.
$$\matrix
\null&\null&X\cr
\null&\null&\downarrow\cr
Y&\rightarrow&\text{?}\cr
\endmatrix$$
For much the same reason, if we suppose the number of ways to get to
point $X$ in the diagram above is $x$ and the number of ways to get
to point $Y$ is $y$, there will be $x+y$ ways to get to the “?”:
go to X and then go south ($x$ ways to do this) or go to
Y and then go east ($y$ ways to do this).
We can use this idea to fill in the entire original diagram; the
reader should verify that the answer to our original question is
70.
$$\matrix
\null&1^{st}&\null&2^{nd}&\null&3^{rd}&\null&4^{th}&\null&5^{th}\cr
A&\circ&\rightarrow&1&\rightarrow&1&\rightarrow&1&\rightarrow&1\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
B&1&\rightarrow&2&\rightarrow&3&\rightarrow&4&\rightarrow&5\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
C&1&\rightarrow&3&\rightarrow&6&\rightarrow&10&\rightarrow&\bullet\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
D&1&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet\cr
\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow&\null&\downarrow\cr
E&1&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\bullet&\rightarrow&\text{?}\cr
\endmatrix$$
\def\la{\swarrow}\def\ra{\searrow}
Let’s rotate the diagram (and replace South and East with Left and Right).
$$\matrix
& & & & & & &\circ& & & & & & & \cr
& & & & & &\la& &\ra& & & & & & \cr
& & & & & 1 & & & & 1 & & & & & \cr
& & & &\la& &\ra& &\la& &\ra& & & & \cr
& & & 1 & & & & 2 & & & & 1 & & & \cr
& &\la& &\ra& &\la& &\ra& &\la& &\ra& & \cr
& 1 & & & & 3 & & & & 3 & & & & 1 & \cr
\la& &\ra& &\la& &\ra& &\la& &\ra& &\la& &\ra \cr
\endmatrix$$
\def\rdots{\mathinner{\mkern-1mu\raise7pt\vbox{\kern-14pt\hbox{.}}
\mkern-4mu\raise4pt\hbox{.}\mkern-4mu\raise1pt\hbox{.}\mkern-2mu}}
Finally, omitting the “starting point” and all the arrows, we have
$$
\matrix
& & & & & 1 & & 1 & & & & \cr
& & & & 1 & & 2 & & 1 & & & \cr
& & & 1 & & 3 & & 3 & & 1 & & \cr
& & 1 & & 4 & & 6 & & 4 & & 1 & \cr
& 1 & & 5 & &10 & &10 & & 5 & & 1\cr
& & & & & &\vdots&& & & & \cr
\endmatrix$$
This is the standard form of the table known as {\bf Pascal’s
triangle}.\plainfootnote{*}{Blaise Pascal (1623–1662) was one
of the most brilliant mathematicians of his day, with important
contributions to probability and projective geometry (for example).
He is perhaps even better known as a religious philosopher, the
author of the famous {\it Pens\’ees}. He was {\it not} the first
to discover “Pascal’s triangle” (not by several hundred years,
in fact).}
The numbers appearing in Pascal’s triangle appear quite frequently
in mathematics.
Consider the numbers in the $3^{rd}$ row: 1, 3, 3, 1.
Each of these numbers tells us how many of a certain type of
“path” can be found. To be precise, we have eight different
paths, all of length three, as shown.
\smallskip
\centerline{
\hfil
\vbox{\hbox to .5in{\hfil 1 \hfil}\hbox to .5in{\hfil \text{LLL} \hfil}}
\hfil
\vbox{\hbox to 1.5in{\hfil 3 \hfil}
\hbox to 1.5in{\hfil \text{LLR LRL RLL} \hfil}}
\hfil
\vbox{\hbox to 1.5in{\hfil 3 \hfil}
\hbox to 1.5in{\hfil \text{LRR RLR RRL} \hfil}}
\hfil
\vbox{\hbox to .5in{\hfil 1 \hfil}\hbox to .5in{\hfil \text{RRR} \hfil}}
\hfil
}
\smallskip\noindent
The set of paths associated to each number is characterised by the
{\it number of right turns\/}: zero, one, two, or three.
Thus, the first “1” tells us that of all possible paths of
length {\it three}, there’s exactly one that has {\it zero}
right turns (namely LLL). The first “3” tells us that there
are three paths of length three with {\it one} right turn.
And so on across.
We will use the notation $\nCr n r$ to denote the number of paths
of length $n$ with exactly $r$ right turns.
So $\nCr 3 0=1$ (because LLL is the only path of length three with
no right turns), $\nCr 3 1 =3$ (LLR, LRL, and RLL), and so on.
This gives us a way to describe the entries of Pascal’s triangle:
$$
\matrix
& & & & & \nCr 1 0 & & \nCr 1 1 & & & & \cr
& & & & \nCr 2 0 & & \nCr 2 1 & & \nCr 2 2 & & & \cr
& & & \nCr 3 0 & & \nCr 3 1 & & \nCr 3 2 & & \nCr 3 3 & & \cr
& & \nCr 4 0 & & \nCr 4 1 & & \nCr 4 2 & & \nCr 4 3 & & \nCr 4 4 & \cr
& \nCr 5 0 & & \nCr 5 1 & &\nCr 5 2 & &\nCr 5 3 & & \nCr 5 4 & & \nCr 5 5\cr
& & & & & &\vdots&& & & & \cr
\endmatrix$$
$$
\matrix
&\hskip.25in&\hskip.25in&\hskip.25in&\hskip.25in& 1 &\hskip.25in& 1 &\hskip.25in&\hskip.25in&\hskip.25in& \cr
&\hskip.25in&\hskip.25in&\hskip.25in& 1 &\hskip.25in& 2 &\hskip.25in& 1 &\hskip.25in&\hskip.25in& \cr
&\hskip.25in&\hskip.25in& 1 &\hskip.25in& 3 &\hskip.25in& 3 &\hskip.25in& 1 &\hskip.25in& \cr
&\hskip.25in& 1 &\hskip.25in& 4 &\hskip.25in& 6 &\hskip.25in& 4 &\hskip.25in& 1 & \cr
& 1 &\hskip.25in& 5 &\hskip.25in&10 &\hskip.25in&10 &\hskip.25in& 5 &\hskip.25in& 1\cr
&\hskip.25in&\hskip.25in&\hskip.25in&\hskip.25in&\hskip.25in&\vdots&&\hskip.25in&\hskip.25in&\hskip.25in& \cr
\endmatrix$$
In principle, we could compute any entry by filling in enough rows of
Pascal’s triangle. But for numbers like $\nCr {20} 3$ this is impractical.
Suppose we think of the “$n$” in $\nCr n r$ as a number of slots
to be filled in with L’s and R’s. The number $\nCr n r$ is then
the number of different ways to select exactly $r$ spaces (to write
R’s in, say). For example, we can see by the charts above that
$\nCr 4 2 = 6$ and there are {\it six} ways to choose 2 out of
four slots.
\smallskip
\hbox to\hsize{$
\hfil\underline{R}\,\underline{R}\,
\underline{\phantom{R}}\,\underline{\phantom{R}}\hfil
\underline{R}\,\underline{\phantom{R}}\,
\underline{R}\,\underline{\phantom{R}}\hfil
\underline{R}\,\underline{\phantom{R}}\,
\underline{\phantom{R}}\,\underline{R}\hfil$}
\smallskip
\hbox to\hsize{$
\hfil\underline{\phantom{R}}\,\underline{R}\,
\underline{R}\,\underline{\phantom{R}}\hfil
\underline{\phantom{R}}\,\underline{R}\,
\underline{\phantom{R}}\,\underline{R}\hfil
\underline{\phantom{R}}\,\underline{\phantom{R}}\,
\underline{R}\,\underline{R}\hfil$}
\smallskip
The Lipschutz-Lipson text gives a proof
(in sections 6.4 \& 6.5) that the
number of ways to choose $r$ things from a set of $n$ is
$${\nCr n r} = {{n!}\over{r!(n-r)!}}\,;$$
the purpose of the preceding discussion has been to connect
this formula with the entries of Pascal’s triangle by
examining the various “paths” that lead to a particular entry.
For example, the “3” entry in the $20^{th}$ row (which is actually
the {\it fourth} entry from the left; remember to count the “0”
entry) is
$$\eqalign{
\nCr {20} 3 &= {{20!}\over{3!17!}}\cr
&= {{20\cdot19\cdot18}\over{3\cdot2\cdot1}}\cr
&=20\cdot19\cdot3\cr
&=1140\,.}$$
(Remember to look for cancelations when you’re calculating $\nCr n r$.)
Future editions of the present document will of course
have a self-contained explanation of the formula for
$\nCr n r$.
\bye
June 14, 2010 at 3:27 am
http://function-of-time.blogspot.com/2010/05/drumroll-please.html