|
Homework assignments will be posted and updated on Blackboard.
Homework 8
To be prepared for discussion on Tuesday, November 23, 2010.
Read Chapter 8 on generating functions (through the top of page 157) and course notes pages 11-30. Then solve the following problems and turn them in before class begins.
#8-1: Verify the following equation and use it to determine how many ways there are to score 100 points in basketball.
#8-2: (a) Determine the generating function for the number of partitions of n such that
there are at most two parts of the same size. (4111 is not allowed since 1 appears thrice.)
(b) Determine the generating function for the number of partitions of n such that
the parts are all of size equal to a power of two. (Example: 844221.)
#8-3: Determine the compact form for the generating function E(x)=Σn≥0 enxn for the sequence en defined by
e0=1, e1=1, e2=4,
and en=3cn-1+1 for n>3, where cn is the nth Catalan number.
#8-4: We know that 14 is a Catalan number cn for some n---determine the 14 n-permutations that are 321-avoiding. Explain how you found them.
#8-5: (a) Describe all permutations which are 132-avoiding and 231-avoiding. (See early exercises of Chapter 14.) (b) Can a permutation be 123-avoiding, 132-avoiding, and 231-avoiding? If not, explain why not. If so, give a description of them.
|