Due 8/28/2009
10 points
Prove: nC(n-1,r)=(r+1)C(n,r+1)

Due 9/2/2009
10 points
Three integers are selected from 1,2,...,1000. How many ways can they be selected so that their sum is divisible by 3?

Due 9/4/2009
10 points
There are 100 people at a party. Each person has an even number (possibly zero) of acquaintances. Prove that there are three people at the party with the same number of acquaintances.

Due 9/9/2009
10pts: #3, p119
Use the algorithm of section 4.1, mobile numbers,, to generate the first 50 permutations of {1,2,3,4,5}
10pts: #7b, p119
Construct the permutation of {1,2,3,4,5,6,7,8} with inversion sequence 6,6,1,4,2,1,0,0
10pts: #10, p119
Bring the permutations 256143 and 436251 to 123456 by successive switches of adjacent numbers.



Due 9/16/2009
(10 points) #13, p.120
Let S={x7, x6, ..., x1, x0}. Determine the subsets of S corresponding to the following 8-tuples a. 00011011 b. 01010101 c. 00001111


Due 9/18/2009
20 points #21, p. 120
Construct the reflected Gray code of order 5 using a. the inductive definition b. the Gray code algorithm


Due 9/21/2009
20 pts, P. 120 #31, 37
Generate the 3-permutations of {1,2,3,4,5}


Let R' and R'' be two partial orders on a set X. Define a new relation R on X to be xRy iff both xR'y and xR''y both hold. Prove that R is also a partial order on X


Due 9/23/2009
10 points P. 257, #1c
Let f_0, f_1, f_2, ... denote the Fibonacci sequence. By evaluating each of the following expressions for small values of n, conjecture a general formula and then prove it, using mathematical induction and the Fibonacci recurrence: f_0-f_1+f_2-...+(-1)^n f_n


Due 9/25/2009
10 points, p. 257 #1d
Let f_0, f_1, f_2, ... denote the Fibonacci sequence. By evaluating each of the following expressions for small values of n, conjecture a general formula and then prove it, using mathematical induction and the Fibonacci recurrence: (f_0)^2+(f_1)^2+...+(f_n)^2


Back