Most of the problems are assigned from the required textbook Bona, Miklos. A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific Publishing Company, 2011. ISBN: 9789814335232. [Preview with Google Books]
A problem marked by * is difficult; it is not necessary to solve such a problem to do well in the course.
Problem Set 5
- Due in Session 14
- Practice Problems
- Session 11: Chapter 7: Exercises 4, 5, 6, 7, 8, 9, 10, 13
- Session 12: None
- Session 13: Chapter 8: Exercises 8, 15, 16*
- Additional practice problem: Let f(n) be the number of ways to choose a composition of n and then color each odd part either red or blue. For instance, when n=3 there are two ways to color the compositions 3, 2+1, and 1+2 (so six in all) and eight ways to color 1+1+1. Thus f(3)=14. Find Σn≥1 f(n)xn, and find a formula for f(n). Your formula for f(n) should involve √3. Hint. Use Theorem 8.13.
- Problems Assigned in the Textbook
- Chapter 7: Exercises 17, 27, 36
- Additional Problems
- None
- Bonus Problems
- (B1) Let En denote the number of permutations a1a2…an of 1,2,…,n such that a1>a2<a3> a4<…. (The signs > and < alternate.) For instance, E4=5, corresponding to 2143, 3142, 3241, 4132, 4231. Show that for n>0,
E2n = {2n\choose 2}E2n-2 - {2n\choose 4}E2n-4 + {2n\choose 6}E2n-6 - ….
Deduce from this recurrence a simple formula for the generating function Σn≥0 E2n x2n/(2n)!.
- (B1) Let En denote the number of permutations a1a2…an of 1,2,…,n such that a1>a2<a3> a4<…. (The signs > and < alternate.) For instance, E4=5, corresponding to 2143, 3142, 3241, 4132, 4231. Show that for n>0,
Recall that bonus problems do not count toward your problem set grade. You can hand them in "for fun" to be graded. Perhaps they will come in handy if your grade at the end of the course is a close decision.