kate’s gauntlet

(x+y)^n = \sum_{j=0}^n {n\choose j}x^j y^{n-j} for the classroom.

Advertisements

  1. 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”…

  2. 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




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s



%d bloggers like this: