HMC Math 55: Discrete Mathematics (Spring, 1999)
Homework

1st Midterm: Friday, Feb. 26

(No homework due Wed. 3/3)

Assignment #5 (due Wed. 2/24):

Section 15 (pg 105) (Prove these combinatorially): 4, 6
(Optional hint for #4: *'s & |'s)
Section 16 (pg 113): 1, 4
Section 20 (pg 151): 4, 7
5A: For each of the following "stars & bars" notations, name the corresponding multiset and the set of candidates from which it was chosen (i.e., for "*|**|", the correct answer is "<1,2,2> from {1,2,3}"... since 3 *'s indicate a size k=3 multiset and 2 |'s indicate a size n=2+1 candidate pool).
(i) | | | |*****
(ii) ***| | |**
(iii) | |*****| | |
(iv) *| |**| |**| |
(v) *|**|***|
(vi) *****
5B: Find some function f : Z->Z+ (from the integers to the positive integers) which is a 1-1 correspondence. Actually prove that f is 1-1 and onto.
5C: Prove that a function f : A->B is 1-1 and onto iff it has a well-defined inverse function g : B->A.
5D: In how many ways can n identical chemistry books, r identical math books, s identical physics books and t identical biology books be arranged on 3 (distinct) bookshelves? (Any shelf may get any number of books)
Warning: As of this assignment, you MUST write problem statements on your homework for each problem.

Assignment #4 (due Wed. 2/17):

Section 14 (pg 96): 14
Section 17 (pg 120): 1, 4, 6
Section 18 (pg 131): 4, 5 (prove these by induction, not the techniques of Section 18)
Section 19 (pg 139): 4b, 4e
4A: Give a proper proof by induction that the kth entry of the nth row of Pascal's triangle is "n choose k". Take as the definition of Pascal's triangle the constructive description given on page 92 of the text.

Extra Credit: Section 14, #21. Your output may be in simple ASCII, and may use *'s or something similar. An equispaced font is required. This problem will be worth about 10 bonus points (half an assignment), and these points are independent of your score on this assignment. Please print out your picture and your source code and submit them to me directly (do not attach to Assignment #4).
Warning: This assignment is not compatible with last semester's version of the text!

Assignment #3 (due Wed. 2/10):

Section 6 (pg 37): 7, 10
Section 14 (pg 96): 3, 10, 12, 13
3A: In Poker, if a hand is garbage (no two values the same, and no straights or flushes), it's value is determined by the highest valued card in the hand. So how many distinct poker hands have the value "Ace high"? That is, the hand is garbage (5 different values, no straights or flushes), and the highest valued card in the hand is an ace? (Note: Ace has highest value of all 13 values). Hint: These hands are a subset of the garbarge hands we did in class, and the counting process is very similar.

Warning: This assignment is not compatible with last semester's version of the text!

Assignment #2 (due Wed. 2/3):

Section 5 (pg 27): 17, 18
Section 6 (pg 37): 2, 3, 6
Section 7 (pg 41): 5, 8
Section 9 (pg 52): 1gj, 2gj
Section 10 (pg 63): 3, 5, 8

Note: This assignment is compatible with last semester's version of the text

Assignment #1 (due Wed. 1/27):

Section 1 (pg 4): 2, 3bdf
Section 2 (pg 13): 3, 8
Section 3 (pg 20): 6
Section 4 (pg 23): 3
Section 5 (pg 27): 9, 11ab, 14
Also: Read pages 1-27 (Sections 1-5)
Note: This assignment is compatible with last semester's version of the text

Return to: Math 55 Main Page * Greg Levin's Page * Department of Mathematics
Email: levin@hmc.edu