MTHSC 360 HW10

3355 days ago by lpmcint

MTHSC 360 - HW10


Your name: Lauren McIntyre

Date: 9/28/12

 

var('x,y') p = [1] n = 7 for k in range(1,n): p.append(expand((x+y)*p[k-1])) print p[k] 
       
x + y
x^2 + 2*x*y + y^2
x^3 + 3*x^2*y + 3*x*y^2 + y^3
x^4 + 4*x^3*y + 6*x^2*y^2 + 4*x*y^3 + y^4
x^5 + 5*x^4*y + 10*x^3*y^2 + 10*x^2*y^3 + 5*x*y^4 + y^5
x^6 + 6*x^5*y + 15*x^4*y^2 + 20*x^3*y^3 + 15*x^2*y^4 + 6*x*y^5 + y^6
x + y
x^2 + 2*x*y + y^2
x^3 + 3*x^2*y + 3*x*y^2 + y^3
x^4 + 4*x^3*y + 6*x^2*y^2 + 4*x*y^3 + y^4
x^5 + 5*x^4*y + 10*x^3*y^2 + 10*x^2*y^3 + 5*x*y^4 + y^5
x^6 + 6*x^5*y + 15*x^4*y^2 + 20*x^3*y^3 + 15*x^2*y^4 + 6*x*y^5 + y^6
# For n = 1, 2, 3, 4 # Using sampling with replacement, choose samples of size n from a set of two items ('x' and 'y'). L = [] L.append(['x','y']) for k in range(1,4): list = [] for item in L[k-1]: list.append('x'+item) for item in L[k-1]: list.append('y'+item) L.append(list) for k in range(4): print L[k] 
       
['x', 'y']
['xx', 'xy', 'yx', 'yy']
['xxx', 'xxy', 'xyx', 'xyy', 'yxx', 'yxy', 'yyx', 'yyy']
['xxxx', 'xxxy', 'xxyx', 'xxyy', 'xyxx', 'xyxy', 'xyyx', 'xyyy', 'yxxx',
'yxxy', 'yxyx', 'yxyy', 'yyxx', 'yyxy', 'yyyx', 'yyyy']
['x', 'y']
['xx', 'xy', 'yx', 'yy']
['xxx', 'xxy', 'xyx', 'xyy', 'yxx', 'yxy', 'yyx', 'yyy']
['xxxx', 'xxxy', 'xxyx', 'xxyy', 'xyxx', 'xyxy', 'xyyx', 'xyyy', 'yxxx', 'yxxy', 'yxyx', 'yxyy', 'yyxx', 'yyxy', 'yyyx', 'yyyy']
# Generate bit strings that specify how to pick subsets of size k from n items L = [] L.append(['1','0']) for k in range(1,4): list = [] for item in L[k-1]: list.append('1'+item) for item in L[k-1]: list.append('0'+item) L.append(list) for k in range(4): print L[k] 
       
['1', '0']
['11', '10', '01', '00']
['111', '110', '101', '100', '011', '010', '001', '000']
['1111', '1110', '1101', '1100', '1011', '1010', '1001', '1000', '0111',
'0110', '0101', '0100', '0011', '0010', '0001', '0000']
['1', '0']
['11', '10', '01', '00']
['111', '110', '101', '100', '011', '010', '001', '000']
['1111', '1110', '1101', '1100', '1011', '1010', '1001', '1000', '0111', '0110', '0101', '0100', '0011', '0010', '0001', '0000']
# Given n items, say [a,b,c,d], these bit strings define subsets by taking the item when the corresponding bit is 1. # [abcd, abc, abd, ab, acd, ac, ad, a, bcd, bc, bd, b, cd, c, d, empty set] # Consequently the coefficients in the binomial expansion of (x+y)^n count # the number of ways to choose subsets of size k from a set of n items. 
       

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.

\[
\left( {\begin{array}{*{20}c}
   n  \\
   k  \\
\end{array}} \righ
def n_choose_k(n,k): y = [1 for i in range (0, k+1)] for j in range(1, n-k+1): for i in range (1, k+1): y[i] = y[i-1]+y[i] return y[k] 
       
for n in range(6): for k in range(n+1): print n_choose_k(n,k), print 
       
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

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.

def sample_subsets(n, list, subset, count): if n == 0: # print subset count += 1 else: for k in range(len(list)): subset.append(list[k]) count = sample_subsets(n-1, list[k+1:], subset, count) list[k] = subset.pop() return count 
       
N = 15 L = [i for i in range(N)] for k in range(N+1): print k,'\t',sample_subsets(k,L,[],0),'\t',n_choose_k(N,k) 
       
0 	1 	1
1 	15 	15
2 	105 	105
3 	455 	455
4 	1365 	1365
5 	3003 	3003
6 	5005 	5005
7 	6435 	6435
8 	6435 	6435
9 	5005 	5005
10 	3003 	3003
11 	1365 	1365
12 	455 	455
13 	105 	105
14 	15 	15
15 	1 	1
0 	1 	1
1 	15 	15
2 	105 	105
3 	455 	455
4 	1365 	1365
5 	3003 	3003
6 	5005 	5005
7 	6435 	6435
8 	6435 	6435
9 	5005 	5005
10 	3003 	3003
11 	1365 	1365
12 	455 	455
13 	105 	105
14 	15 	15
15 	1 	1

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.

for n in range(2,14,2): print n, n_choose_k(n,2)%n 
       
2 1
4 2
6 3
8 4
10 5
12 6
2 1
4 2
6 3
8 4
10 5
12 6
       

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.

# Check out random - random.func_defaults 
       
# Check out the built-in random function random() 
       
0.27703711225993732
0.27703711225993732
# Import the random package import random 
       
# Check out what we now have available random.betavariate 
       
<bound method Random.betavariate of <random.Random object at
0x1ed4560>>
<bound method Random.betavariate of <random.Random object at 0x1ed4560>>

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$

# Hockey Stick Patterns First Case # Does the first column matter? # Create the matrix of zeros N = 12 P1 = matrix(ZZ,N) # Set the first column to random integers for i in [0..N-1]: P1[i,0] = random.randrange(15) # Fill in the rest of the matrix using the defining property for i in [1,..,N-1]: for j in [1,..,N-1]: P1[i,j] = P1[i-1,j-1] + P1[i-1,j] print P1 
       
[  14    0    0    0    0    0    0    0    0    0    0    0]
[   9   14    0    0    0    0    0    0    0    0    0    0]
[   1   23   14    0    0    0    0    0    0    0    0    0]
[   2   24   37   14    0    0    0    0    0    0    0    0]
[   9   26   61   51   14    0    0    0    0    0    0    0]
[   0   35   87  112   65   14    0    0    0    0    0    0]
[   0   35  122  199  177   79   14    0    0    0    0    0]
[   1   35  157  321  376  256   93   14    0    0    0    0]
[   3   36  192  478  697  632  349  107   14    0    0    0]
[   9   39  228  670 1175 1329  981  456  121   14    0    0]
[  11   48  267  898 1845 2504 2310 1437  577  135   14    0]
[   6   59  315 1165 2743 4349 4814 3747 2014  712  149   14]
[  14    0    0    0    0    0    0    0    0    0    0    0]
[   9   14    0    0    0    0    0    0    0    0    0    0]
[   1   23   14    0    0    0    0    0    0    0    0    0]
[   2   24   37   14    0    0    0    0    0    0    0    0]
[   9   26   61   51   14    0    0    0    0    0    0    0]
[   0   35   87  112   65   14    0    0    0    0    0    0]
[   0   35  122  199  177   79   14    0    0    0    0    0]
[   1   35  157  321  376  256   93   14    0    0    0    0]
[   3   36  192  478  697  632  349  107   14    0    0    0]
[   9   39  228  670 1175 1329  981  456  121   14    0    0]
[  11   48  267  898 1845 2504 2310 1437  577  135   14    0]
[   6   59  315 1165 2743 4349 4814 3747 2014  712  149   14]

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.

def Hockey_stick_check(P): N = P.nrows() OK = True for i in [1,..,N-1]: for j in [1,..,N-1]: if P1[i,j] == P1[i-1,j-1] + P1[i-1,j]: return OK else: return "false" 
       
Hockey_stick_check(P1) N = P1.nrows() 
       
True
True


# Hockey Stick Patterns Second Case # Does the first row matter? # Create the matrix of zeros N = 12 P2 = matrix(ZZ,N) # Set the first row to random integers for j in [0..N-1]: P2[0,j] = random.randrange(15) # Set the first column to ones for i in [0..N-1]: P2[i,0] = 1 # Fill in the rest of the matrix using the defining property for i in [1,..,N-1]: for j in [1,..,N-1]: P2[i,j] = P2[i-1,j-1] + P2[i-1,j] print P2 
       
[    1     8     7     3    13     1     6     0    11     8     7    
5]
[    1     9    15    10    16    14     7     6    11    19    15   
12]
[    1    10    24    25    26    30    21    13    17    30    34   
27]
[    1    11    34    49    51    56    51    34    30    47    64   
61]
[    1    12    45    83   100   107   107    85    64    77   111  
125]
[    1    13    57   128   183   207   214   192   149   141   188  
236]
[    1    14    70   185   311   390   421   406   341   290   329  
424]
[    1    15    84   255   496   701   811   827   747   631   619  
753]
[    1    16    99   339   751  1197  1512  1638  1574  1378  1250 
1372]
[    1    17   115   438  1090  1948  2709  3150  3212  2952  2628 
2622]
[    1    18   132   553  1528  3038  4657  5859  6362  6164  5580 
5250]
[    1    19   150   685  2081  4566  7695 10516 12221 12526 11744
10830]
[    1     8     7     3    13     1     6     0    11     8     7     5]
[    1     9    15    10    16    14     7     6    11    19    15    12]
[    1    10    24    25    26    30    21    13    17    30    34    27]
[    1    11    34    49    51    56    51    34    30    47    64    61]
[    1    12    45    83   100   107   107    85    64    77   111   125]
[    1    13    57   128   183   207   214   192   149   141   188   236]
[    1    14    70   185   311   390   421   406   341   290   329   424]
[    1    15    84   255   496   701   811   827   747   631   619   753]
[    1    16    99   339   751  1197  1512  1638  1574  1378  1250  1372]
[    1    17   115   438  1090  1948  2709  3150  3212  2952  2628  2622]
[    1    18   132   553  1528  3038  4657  5859  6362  6164  5580  5250]
[    1    19   150   685  2081  4566  7695 10516 12221 12526 11744 10830]

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.

Hockey_stick_check(P2) 
       
True
True

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.

def Base_check(P1): OK = True for j in [1,..,N-1]: if P1[1,j] == P1[1,j-1]+P1[1,j]: return OK else: return "False" Base_check(P1) 
       
True
True

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.