Homework 3:
E1: Let $k$ be the number of $2$'s, so $2k\le n.$ There are $[(n+2)/2]$ choices for $k$, for example if $n=6$ there 4 such partitions.
E2:Using $$ 1+x+x^2=\frac{1-x^3}{1-x} $$ it is partitions whose parts are not multiples of 3.
E3:
Change 18 to 99, and keep 9, so we have a total of three 9's.
Since 15 is odd, we keep 15. For 12 we create 4 3's.
Also 4 changes to four 1's, 2 to two 1's, for a
total of seven 1's. The answer is 15 999 3333 1111111.
E4: Suppose the NW square is $j$ by $j$. Then $j^2$ boxes are in this square. To the right of the square, the columns may be any lengths from 1 to $j$, we know the generating function here is $$ \frac{1}{(1-x)(1-x^2)(1-x^3)\cdots (1-x^j)} $$ Below the square are any rows of lengths $1$ to $j$, which have the same generating function. This gives the square in the denominator.
E5: These are counted by blockwalks, so $$\binom{7}{3}=35. $$
E6: TRUE. The partitions of $n$ which do contain $1$ are in bijection with the partitions of $n-1$ just by appending a 1.
E7: (a) $C_6=132.$
(b) $C_3*C_2=10.$
(c) $C_2*C_3*C_1=10$.
E8: $C_3*C_3=25.$
E9: $C_n/\binom{2n}{n}=\frac{1}{n+1}.$
E10:(b) Proof by induction on n. Suppose that $T=(r, T_1,T_2)$. Then $T_1$ and $T_2$ are rooted complete binary trees with fewer number of vertices, so this number must odd for each of them say $2k+1,$ and $2(n-k)-1.$ So $T$ has $2n+1$ vertices, and by induction $k+1+(n-k)=n+1$ leaves.
(c) Let the number of these trees be $D_n.$ We'll show that $D_n$ satisfies the Catalan recurrence. If $T_1$ has $2k+1$ vertices, $T_1$ has $D_k$ choices, while $T_2$ has $D_{n-1-k}$ choices. So $$ D_n=\sum_{k=0}^{n-1} D_k*D_{n-1-k}, $$ the Catalan recurrence with $D_1=1.$
E11: These are blockwalks at or above the diagonal, $C_n$.