### kate’s gauntlet

May 6, 2010 in Uncategorized

## (Partial) Contents Page

Vlorbik On Math Ed ('07—'09)

(a good place to start!)## Categories

- "="
- "categories" is broken
- 21-point Tic-Tac-Toe
- ATAAOA
- Bacon
- binary tetr'al
- Blogs
- Bread
- Carnival
- Combinatorics
- Comics
- Cool Tricks
- daadd
- Damn
- desargues
- Exegesis
- Exercises
- Finite Geometry
- FTI
- Grading
- Graphics
- Gush
- Handwriting
- Homepage
- hymnal
- Job
- joyce's milkmaid
- KTM
- Lectures Without Words
- Life Story
- Links
- Math 104
- Math 132
- Math 148
- Math 151
- MathEdZine
- Mene Mene Tekel
- Meta
- Music
- National Math. Advisory Panel
- Notations
- Number Theory
- Ohs
- Photo
- Projective Spaces
- Rambles
- Rants
- Sandwiches
- Seven Stories
- Taters
- TeX
- Textbooks
- The Statistics Coup
- Uncategorized
- UUCE
- Verse
- VPD
- Warez
- wp fail
- Zines

## Bookmarks

vlorblog (homepage).

e-mail: vlorbik@gmail.comW'press login.

Alas, gmail.

Carmen.

Buckeye Link.**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)## Archives

- March 2021 (1)
- December 2020 (1)
- November 2020 (1)
- September 2020 (8)
- August 2020 (9)
- July 2020 (7)
- June 2020 (24)
- May 2020 (5)
- February 2020 (1)
- June 2019 (2)
- April 2019 (2)
- February 2019 (1)
- December 2018 (1)
- July 2018 (1)
- December 2017 (3)
- November 2017 (4)
- February 2017 (11)
- January 2017 (2)
- November 2016 (5)
- October 2016 (2)
- September 2016 (1)
- August 2016 (6)
- July 2016 (3)
- February 2016 (1)
- November 2015 (11)
- October 2015 (6)
- September 2015 (4)
- August 2015 (3)
- July 2015 (2)
- June 2015 (3)
- May 2015 (11)
- April 2015 (12)
- March 2015 (4)
- February 2015 (1)
- January 2015 (5)
- September 2014 (5)
- August 2014 (6)
- July 2014 (13)
- June 2014 (3)
- April 2014 (13)
- March 2014 (8)
- February 2014 (4)
- August 2013 (1)
- July 2013 (12)
- June 2013 (1)
- March 2013 (1)
- February 2013 (3)
- January 2013 (2)
- December 2012 (2)
- November 2012 (2)
- September 2012 (1)
- August 2012 (2)
- June 2012 (3)
- May 2012 (2)
- March 2012 (2)
- January 2012 (6)
- November 2011 (2)
- September 2011 (3)
- August 2011 (1)
- July 2011 (7)
- June 2011 (5)
- May 2011 (7)
- April 2011 (9)
- March 2011 (10)
- February 2011 (9)
- January 2011 (12)
- December 2010 (13)
- November 2010 (4)
- October 2010 (5)
- September 2010 (2)
- August 2010 (2)
- July 2010 (1)
- June 2010 (2)
- May 2010 (11)
- April 2010 (8)
- March 2010 (15)
- February 2010 (11)
- January 2010 (23)
- March 2009 (1)
- February 2009 (15)
- January 2009 (29)
- December 2008 (16)
- November 2008 (14)
- October 2008 (12)
- September 2008 (7)
- August 2008 (3)
- July 2008 (11)
- June 2008 (13)
- May 2008 (13)
- April 2008 (17)
- March 2008 (16)
- February 2008 (20)
- January 2008 (8)
- December 2007 (9)
- November 2007 (12)
- October 2007 (17)
- September 2007 (14)
- August 2007 (29)
- July 2007 (15)
- June 2007 (14)

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