MTHSC 360 - HW10

Your name: Lauren McIntyre

Date: 9/28/12

We define the number $\left({\begin{array}{*{20}c}n  \\ k  \\ \end{array}} \right)$ which is read as $n$ choose $k$ as the number of subsets of size $k$ from a set of size $n$.  Based on the facts that we can draw a sample (without replacement) of size $k$ from a set on $n$ items in $n(n-1)\cdots(n-[k-1])$ ways and that $k$ items can be arranged in $k!$ ways, we can conclude that the following formula is correct.

\[

\left( {\begin{array}{*{20}c}

   n  \\

   k  \\

\end{array}} \right) = \frac{{n(n - 1) \cdots (n - [k - 1])}}{{k!}} = \frac{{n!}}{{k!{\kern 1pt} {\kern 1pt} (n - k)!}}

\]

Exercise 1:  Complete the following function for $n$ choose $k$.  Do not use the built-in factorial function. Then execute subsequent block.

Exercise 2:  Copy your code from HW09 that generates all subsets of size k from a set of size n and returns the count.  Comment out the line that prints each subset.  Then run the test cases in the subsequent block.

Exercise 3:  Using the the definition of $\left({\begin{array}{*{20}c}n  \\ k  \\ \end{array}} \right)$ show on a separate piece of paper that 

$\left({\begin{array}{*{20}c}n+1  \\ k  \\ \end{array}} \right) = \left({\begin{array}{*{20}c}n  \\ k-1  \\ \end{array}} \right) + \left({\begin{array}{*{20}c}n  \\ k  \\ \end{array}} \right)$

The Binomial Theorem:  For $0 \le n$

  \[

(x + y)^n  = \sum\limits_{k = 0}^n {\left( {\begin{array}{*{20}c}

   n  \\

   k  \\

\end{array}} \right)} x^{n - k} y^k 

\]

In particular, this means that the $n,k$ entry in the Pascal Triangle is the number $\left({\begin{array}{*{20}c}n  \\ k  \\ \end{array}} \right)$.  Consequently these numbers are also referred to as the Binomial Coefficients.

Exercise 4:  On a separate piece of paper show that if $n$ is a prime number then the entries on row $n$ of the Pascal Triangle, except for the first and last, are all divisible by $n$. 

Exercise 5:  For n=2, 4, 6, 8, 10, and 12, calculate n_choose_k(n,2) % n.

On a separate piece of paper show that if $n$ is an even number then n_choose_k(n,2) % n =  n/2.

In the following section we will want to generate some random integers.  The built-in random function only returns floating point numbers between 0 and 1.  But there is a package called random, which provides many more functions for working with random numbers.  In the following blocks check "random.", "random(", and after executing "import random" check "random." again.  Check by placing the cursor next to the last character and pressing the tab key.

In Project 1, everyone observed that the Pascal Triangle supported the Hockey Stick pattern, which we stated more precisely as follows:

$\sum_0^n P_{i,j} = P_{n+1,j+1}$ for $j = 0, 1, 2, ....$ and $n = 1, 2, ....$

I suggested that if you want to explore a proof you can assume the following three properties.

$P_{i,0} = 1$  for  $i=0,1,2,....$

$P_{i,j} = 0$  whenever  $i<j$

$P_{i,j} = P_{i-1,j-1} + P_{i-1,j}$  for  $i=1,2,....$ and $j=1,2,....$

An important question is which of these properties are really necessary.  The last statement might be called the defining property and the first two statements might be called initializing properties.  Let's see what happens if we throw the first one out and simplify the second one to 

$P_{1,j} = 0$  whenever  $0<j$

Exercise 6:  The preceding block created P1, a 12-by-12 matrix of zeros.  It then placed random numbers in the first column of P1.  Finally it filled in the rest of the matrix, P1, using the defining property.  In the following block write a function that given a matrix returns True if the Hockey Stick pattern is satisfied for all $i,j$ entries with $0<i$ and $0<j$ and returns False otherwise.  Then evaluate the subsequent block.

Exercise 7:  The preceding block created P2, a 12-by-12 matrix of zeros.  It then placed random numbers in the first row of P2.  It then placed ones in the first column. Finally it filled in the rest of the matrix, P2, using the defining property.  Evaluate the following block to determine whether P2 satisfies the Hockey Stick pattern.

Exercise 8:  The two previous results indicate first that the Hockey Stick pattern is not unique to the Pascal Triangle and second that a proof by induction should proceed by rows.  In particular the Base Step should be 

For any $j$ greater than 0, $P_{1,j} = \sum_{k=0}^0 P_{k,j-1}$

Prove that this statement is True.  Hint, it is not an induction argument.

Once the Base Step has been established, then the induction argument is simply,

• Assume that $P_{i,j} = \sum_{k=0}^{i-1} P_{k,j-1}$
• $P_{i+1,j} = P_{i,j-1} + P_{i,j}$, by the defining property
• $P_{i+1,j} = P_{i,j-1} + \sum_{k=0}^{i-1} P_{k,j-1}$ by the assumption
• $P_{i+1,j} =  \sum_{k=0}^{i} P_{k,j-1}$ by the definition of summation.