# Math 4370 Combinatorics Homework

## Dr. Duval

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: 13, 14, 20, 22, 25.

1.10: 12, 28, 30, 31, 37, 39.

2.10: 1, 2, 4, 5, 6.

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.
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: 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