FALL 2007:  MATH 3012 (Applied Combinatorics)
 
 
This section is titled 3012 T, where T is a code the scheduler uses for bookkeeping that
the class meets laTe in the afternoon!
 
  Click here for an outline
 
Turn in solutions to only the EVEN numbered problems in ALL HWs.
 
HOMEWORK 1 (Due: Wednesday, August 29th) :
  Sections 1.1-1.2 (pages 11-14): Problems 4, 9, 19, 20, 30, 31
  Sections 1.3 (pages 24-26): Problems 3, 4, 5, 8, 11, 17, 20, 21, 25, 26, 30
 
HOMEWORK 2 (Due: Monday, September 10th) :
  Sections 1.4 : Problems 4, 7, 10, 12, 13, 17, 23, 27
  Sections 1.5 : Problems 9, 10
  Sections 4.1 : Problems 2, 4, 7, 14, 15, 19
 
QUIZ 1 on Sept. 10th in class -- syllabus: Chapter 1.  
  Click here for a sample quiz  
  Quiz 1 with solutions
 
HOMEWORK 3 (NO NEED TO TURN IN):
  Sections 4.3 : Problem 8
  Sections 4.4 : Problems 1, 3, 11, 14, 15, 21
  Supplementary exercises (Ch. 4) : Problems 11, 17, 19, 20

  Solns. to HWs 2 and 3
 
TEST 1 on Sept. 17th in class -- syllabus: Chapters 1, 4.  

  Solns. Test 1
 
HOMEWORK 4 (Due : Monday, October 1st):
  Sections 5.1 : Problem 10
  Sections 5.2 : Problems 2, 3, 15, 22, 26, 27
  Sections 5.3 : Problems 2, 4, 5, 6, 10, 15, 18
 
  Solns. to HW 4
 
QUIZ 2 on Oct. 15th (Monday) in class -- syllabus: Chapters 5, 8.  
(Sections 5.1, 5.2, 5.3, 5.5, and 8.1 on Quiz 2)  
  Quiz 2 with solutions
 
HOMEWORK 5 (Due : Monday, October 15th):
  Sections 5.5 : Problems 3, 7, 10, 14, 18, 20, 24
  Sections 8.1 : Problems 4, 6, 10, 11, 17, 18
 
HOMEWORK 6 (Due : Wednesday, October 24th):
  Sections 11.3 : Problems 12, 13, 20, 23, 24, 26, 36
  Sections 11.4 : Problems 2, 5, 11, 14, 16, 18, 19, 21, 26
 
NOTE : TEST 2 on Nov. 5th (Monday) in class --
  Syllabus: Chapter 11 (all sections, EXCEPT 11.5) and Sec. 12.1; OPEN NOTES
 
HOMEWORK 7 (NO NEED TO SUBMIT):
  Sections 11.6 : Problems 7, 9, 13, 15, (3 done in class)
  Chapter 11 (Supplementary exercises) : Problems 3, 5, 9
  Sections 12.1 : Problems 5, 7, 9, 14, (21 done in class), 23, (24 will be done in class)
 
Solution to 12.1.14: Answer is floor of (n+1)/2:
 
* First note that each spanning tree of K_{2,n} has degrees (a,b) on one side and (1,1,...,1,2) on the other side,
where in the first list a+b=n+1 (with a, b positive integers), and
the second list has (n-1) 1's and one 2 -- if there are two 2's on the second list, there will be a cycle.
 
* Now easy to see that the number of unordered choices for (a,b) is the floor of (n+1)/2,
namely, (1,n), (2,n-1), ..., (floor{n+1/2}, ceil{n+1/2})
 
***HOMEWORK 8 (Due: MONDAY/TUESDAY, NOV. 19/20th)***:
  Sections 9.1 : Problems 2, 4
  Sections 9.2 : Problems 13, 14, 15, 16, 18
  Sections 9.4 : Problems 2(b, f), 4(a, b), 9, 10
 
*** NOTE : QUIZ 3 on Nov. 28th (Wednesday) in class --
*** Syllabus : Sections 9.1,9.2, 9.4, and Sections 10.1, 10.2, 10.3
(OPEN NOTES for QUIZ 3)
NOTE: Office hours from Nov. 26th onwards: Mon, Tue, Wed : 1:30--2:30pm

*** NOTE: AS announced in class, the final is OPEN NOTES AND OPEN TEXTBOOK! ***