Math 4370 Combinatorics
Homework

Fall 2010

Dr. Duval

Reading assignment

For Tuesday, November 30, reread section 5.3, and read ahead section 5.4.

For Thursday, December 2, reread section 5.3, as necessary, and read section 5.4.

Homework

1.10: 1, 2, 3, 4, 11.
1.10: 5 [grad students only].
1.10: 13, 14, 20, 22, 25.
1.10: 21 [grad students only].
1.10: 12, 28, 30, 31, 37, 39.
1.10: 24 [grad students only].
2.10: 1, 2, 4, 5, 6.
2.10: 3 [grad students only].
2.10: 7 [S(n,2) only], 8, 9. [this assignment will only count half as much as others; no extra problems for grad students.]
2.10: 14, 16, 18, 19, 21, due Thursday, October 7.
2.10: 15 [grad students only], due Thursday, October 7.
Note the following typographical errors:
15: B(n) should be B(n+1)
21: Replace "and nonzero" by "and possibly zero"
2.10: 24, 30, 31, 32, 38.
2.10: 22 [grad students only].
Note that in each of problems 24 and 30, p_k(n) should be interpreted as the number of partitions of n with *exactly* k parts.
2.10: 12, 34, 36.
3.10: 3, 4.
3.10: 1 [grad students only].
3.10: 2, 5, 9. [this assignment will only count half as much as others; no extra problems for grad students.]
3.10: 9, 10, 11, 12. [no extra problems for grad students.]
3.10: 21 [grad students only; see 3.8, exercise 21, for a hint].
extra problems
  1. Find the number of different ways to partition [n] into two subsets, give everybody in the first set two choices each, and pick a leader (special element) of the second set. In particular, the second set must be non-empty.
  2. Find the exponential generating function for the sequence that counts the number of different ways to partition [n] into three subsets, and arrange the first subset into a completely ordered list, such that the second subset has an even number of elements, and the third subset has an odd number of elements.
5.12: 3, 4, 5.
Cayley: Illustrate your understanding of the proof of Cayley's theorem by (a) finding the doubly-rooted tree corresponding to the function found below, and (b) finding the function [n]->[n] corresponding to the doubly-rooted spanning tree found below, due Tuesday, November 30.
5.12: 7, 9, 11, 13, due Tuesday, November 30.
5.12: 8 [grad students only; no proof required, but show evidence and count the size of the isomorphsim class], due Tuesday, November 30.
Cayley stuff here: 

(a)

 i | f(i)
---+-----
 1 |  6
 2 | 10
 3 |  1
 4 | 10
 5 |  6
 6 | 10
 7 |  2
 8 |  6
 9 |  2
10 |  3


(b)
      4
      |
      |
      8
      |
      |
5 -- 10 -- 1 -- 6 -- 9
      |         |
      |         |
      7         3
      |
      |
      2
start vertex is 4; end vertex is 9