# MTHSC 360 - HW10

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

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.