QC > Math > chanusa > 636 > Homework Syllabus • Topics • Schedule • Homework • 636
Homework Assignments
Combinatorics – Spring 2009
NOTE! Refresh your browser to get updates!
Practice Homework 13
  • Please complete an additional course evaluation. The ratings you provide are used by the department to see how you view my teaching. Thank you in advance.
  • In preparation for Exam 2 on Monday, May 18, here is a list of practice problems. You are not required to complete these problems, but they revisit the topics from the sections covered. The bolded questions are especially suggested to practice key concepts.
    • Chapter 6: 16, 20, 21
    • Chapter 7: 9, 18, 19, 20, 36, 37
    • Chapter 8: 1, 3, 4, 13, 15
    • 13-1.  Use the monomino-domino interpretation of the Fibonacci numbers to prove that b0+b2+b4+...+b2n=b2n+1.
      (Hint: IS THERE a last square in the tiling somewhere?)
    • 13-2.  We can make a four-sided die using a tetrahedron. If the sides of the die are 1, 2, 3, and 4, then there is a particular distribution of possible sums between 2 and 8. Determine a relabeling of the two dice which gives the exact same distribution of sums. How many possibilities are there? (For background, see this blog.)
    • 13-3.  Determine the generating function for the sequence en defined by e0=1, e1=1, e2=4, and en=3cn-1+1, where cn is the nth Catalan number.
    • 13-4.  Draw the Ferrers diagram for all partitions of 6.
  • Exam 2 will cover all topics discussed through Wednesday, May 6. This will probably include the following sections/topics:
    • Chapter 6, Sections 1, 2, 3, 4
    • Chapter 7, Sections 1, 4, 5, 6
    • Chapter 8, Sections 1, 2 (Stirling), 3
    • Combinatorial interpretations and proofs involving Fibonacci numbers
    • Generating function manipulations (generatingfunctionology to page 10)
    • Lectures on partitions by Herbert Wilf (through Thm 4).
Homework 12
To be turned in on Wednesday, May 6, 2009.
  • Read Sections 1-3 (through Thm 4) (pages 4-12) of this file, a series of lectures on partitions by Herbert Wilf.
  • Complete the following problems.
    • 12-1.  8.6.27
    • 12-2.  Determine the generating function for the number of partitions of n satisfying
      (a) there are at most two parts of the same size. (4111 is not allowed since 1 appears thrice.)
      (b) the parts are all of size equal to a power of two. (Example: 844221.)
    • 12-3.  Let p(n) be the number of partitions of n and let q(n) be the number of partitions of n with no parts equal to one. Give a bijective proof showing p(n)=p(n-1)+q(n).
    • 12-4.  Show that the number of Ferrers diagrams that fit inside an m by n rectangle is (m+nm). (Hint: look for a bijection with walks in a lattice.)
    • 12-5.  Similar to the idea of a partition of n is the idea of a composition of n, where now the parts are not necessarily decreasing in size. For example, whereas 211 is the only partition of 4 into three parts, the sequences 211, 121, and 112 are each compositions of 4. Conjecture a formula for the number of compositions of n and prove it.
  • Bring questions you have about the topics from the second half of the course to class.
  • There is no class on Monday, May 11; use the class time to finish up your poster!
  • Posters are due Wednesday, May 13. Bring your poster to class and be ready to present your findings to your classmates and instuctor. Do not forget to bring in 15 copies of your one-page summary of your work to distribute to your classmates.
Homework 11
To be prepared for discussion on Wednesday, April 29, 2009.
  • Read Sections 8.2 (starting with Thm. 8.2.4) and 8.3. Then prepare solutions to the following questions.
    • 11-1.  7.8.29
    • 11-2.  A six-digit number is lucky if the sum of the first three digits is the same as the sum of its last three digits. How many 6-digit lucky numbers are there? [Use generating functions.]
    • 11-3.  (a) Determine all partitions of the set S={1, :), apple, #, *} into 3 indistinguishable boxes.
      (b) Determine all set partitions of S.
      (c) Determine all integer partitions of 7.
    • 11-4.  (a) 8.6.11
      (b) 8.6.16
      (c) 8.6.12(d)
    • 11-5.  Complete Problem 8.6.26, making sure to draw representative Ferrers diagrams and their conjugates.
    • 11-6.  The Catalan numbers cn satisfy the generating function
      c(x)=Σn≥0 cnxn=(1 - sqrt(1-4x))/2.
      Consider an integer sequence dn which has as its generating function
      d(x)=Σn≥0 dnxn=1 - 5 sqrt(1-4x).
      Determine a formula for dn in terms of the nth Catalan number, cn.
  • Remember: Your project outlines are also due Wednesday, April 29. You should explain some preliminary results about your investigations, and discuss the structure of your poster. (Determine how much of the poster will be allotted to what topics.)
Homework 10
To be turned in on Wednesday, April 22, 2009. (Final version, updated 3/27)
  • Read Sections 7.4 and 7.5 through the top of p.246 and generatingfunctionology to page 10. Then write up solutions to the following questions.
    • 10-1.  Let an be the maximal number of pieces into which you can cut a circle using n straight lines. Determine the first few values of an. Use the online encyclopedia of integer sequences (OEIS) to determine what the formula is for a general term. On that webpage, look at the graph of the sequence and listen to the sequence. Write down the 42nd term of the sequence. Then, via the WebCam link at the bottom of the page, look through a few sequences and write down one that looks interesting and say why.
    • 10-2.  6.7.16
    • 10-3.  (a) 6.7.25 (b) 6.7.26
    • 10-4.  7.8.30, parts (a) and (d)
    • 10-5.  (a) 7.8.35 (b) 7.8.34
Homework 9
To be prepared for discussion on Wednesday, April 1, 2009.
  • Read Section 6.4 and in Sections 7.1 and 7.2, read pages 206-208, m210-212, m215-m216, and 218-m219 (where mXXX means ``the middle of page XXX''). Then complete the following questions for in-class presentations.
    • 9-1.  6.7.15 (Also find a numerical answer for parts a-c and compare this to 7!.)
    • 9-2.  6.7.17
    • 9-3.  6.7.24
    • 9-4.  Use the square-domino interpretation of the Fibonacci numbers to prove that bm+n=bmbn+bm-1bn-1
    • 9-5.  Use the square-domino interpretation of the Fibonacci numbers to prove that (n0)+(n-11)+(n-22)+...=bn
    • 9-6.  7.8.28
  • Remember that your revised project proposal is due before Spring break. Once again, sending your proposal by email is fine.
Homework 8
To be turned in on Wednesday, March 25, 2009.
  • Read Sections 6.1, 6.2, and 6.3. Then write up solutions to the following questions.
    • 8-1.  (a) 6.7.1 (b) 6.7.3
    • 8-2.  6.7.5
    • 8-3.  6.7.8
    • 8-4.  6.7.11
    • 8-5.  Prove that the sum from j=2 to infinity of [1 over (j2)] equals 2.
      [Hint: Write the denominator as a polynomial of j, then use partial fractions]
  • Remember that your project proposals are due next Monday, March 30. Write me a paragraph or two describing the topic you would like to explore. Sending your proposal by email is fine. Feel free to stop by my office hours or schedule a meeting with me if you would like some advice on refining the scope of your project.
  • Past poster projects
Practice Homework 7
Practice for Wednesday, March 11, 2009.
  • In preparation for Exam 1 on Monday, March 16, here is a list of practice problems. You are not required to complete these problems, but they revisit the topics from the sections covered. The bolded questions are especially suggested to practice key concepts.
    • Chapter 1: 1, 3, 4, 30, 31, 34
    • Chapter 3: 4, 8, 10, 11, 21, 25, 30, 41, 48, 51
    • Chapter 5: 3, 7, 9, 13, 16, 18, 19, 23, 24, 25, 37, 40, 43
    • 7-1.  Calculate how many different bijections there are from [n] to [m] for various m and n.
  • Exam 1 will cover all topics discussed through Monday, March 9. This will probably include the following sections/topics:
    • Chapter 1, Sections 1, 2, 5, 7
    • Chapter 3, Sections 1, 2, 3, 4, 5
    • Chapter 5, Sections 1, 2, 3, 5, 6
    • Combinatorial interpretations of binomial coefficients
    • Combinatorial proofs
    • Bijections
Homework 6
To be turned in on Wednesday, March 4, 2009.
  • Read Sections and 5.3. Then write up solutions to the following questions.
    • 6-1.  3.6.22
    • 6-2.  3.6.47
    • 6-1.  5.8.11
    • 6-2.  Read Problem 3.6.53. (a) Find the desired bijection (aka one-to-one correspondence).
      (b) Prove that your rule is an injection and a surjection.
      (c) Conclude how many such towers there are by way of your bijection.
    • 6-5.  Create a bijection between two-member subsets of {1, 2,..., n, n+1} and all possibilities of placing one pair of parentheses in a string of n letters. For example, if n were three, we see that there are six two-member subsets of {1,2,3,4} and there are six ways to place one pair of parentheses in the word abc: (a)bc, (ab)c, (abc), a(b)c, a(bc), and ab(c). Notice that a()bc is not valid---there are no letters between the parentheses.
Homework 5
To be prepared for discussion on Wednesday, February 25, 2009.
  • Read Sections 3.5 and 5.3. Then complete the following questions for in-class presentations.
    • 5-1.  3.6.38
    • 5-2.  3.6.19
    • 5-3.  3.6.50
    • 5-4.  3.6.47
    • 5-5.  3.6.54 [Also, try to think of a bijection that could prove your answer more easily.]
    • 5-6.  Give a combinatorial proof of Equation (5.14) on page 138.
      [Hint: Condition on when the last chosen element occurs.]
Homework 4
To be turned in on Wednesday, February 18, 2009.
  • Read sections 3.3 and 3.4. Then write up solutions to the following questions.
    • 4-1.  3.6.20
    • 4-2.  3.6.28
    • 4-3.  (a) 3.6.39a (b) 3.6.39b (c) 3.6.40c [Notice the introduction of variables in (c).]
    • 4-4.  3.6.43
    • 4-5.  3.6.45
Homework 3
To be prepared for discussion on Wednesday, February 11, 2009.
  • Read Sections 1.7, 3.1, and 3.2. Then complete the following questions for in-class presentations.
    • 3-1.  (a) 1.8.29 (b) (Determine all possible first moves for player 1 or explain why only one exists.)
    • 3-2.  1.8.35
    • 3-3.  3.6.1
    • 3-4.  3.6.7
    • 3-5.  The book-designer used four fonts (thick roman, thick italic, thin roman, thin italic) and four colors (red, orange, yellow,and blue, more or less) in writing the word ``combinatorics'' on the cover subject to the constraint that adjacent letters must be different fonts and different colors. Determine the number of ways in which this may be accomplished.
    • 3-6.  3.6.13
  • (You do not need to submit written solutions to these problems; however, you should write up solutions for your own benefit and to help with your presentations.)
Homework 2
To be turned in on Wednesday, February 4, 2009.
  • Read sections 1.1 (pp. 4-5), 1.2, and 1.5. Then complete the following questions.
    • 2-1.  1.8.2
    • 2-2.  1.8.7
    • 2-3.  1.8.23
    • 2-4.  (a) 1.8.26 (b) 1.8.27
    • 2-5.  1.8.37
  • Please reference the people you worked with on your homework. (Acknowledgments are nice for everyone!)
  • Remember what is expected:
    • Follow the guidelines for turning in homework.
    • Write in full sentences.
    • When the problem says "Find object X with property A", you need to give an example of X and explain why the X has the property you claim it does.
    • When the problem says "Prove X" or "Show X", you need to give a rigorous mathematical argument explaining why "X" is true.
    • It may be the case that an example or a counterexample is the key to your rigorous mathematical proof. If this is the case, you will need to explain why you have drawn it and what purpose it serves.
Homework 1
To be completed for Wednesday, January 28, 2009.
  • Take the time to read the syllabus thoroughly. This should answer any questions you have about the course.
  • Read the letters from past students to get a feel of what you should expect from this class.
  • Go online to Blackboard and introduce yourself to your classmates.
  • Read Section 1.0 in the textbook (through the top of page four) and figure out what phrase completes the following statement:
    ``The more problems one solves...''

Back to the Combinatorics Home Page.
Christopher Hanusa – Queens College – Mathematics Department.