Problem 1 Find the generating function for the number of integer partitions of n into parts, all of which must be ones. Find the generating function for the number of integer partitions of n into parts which are distinct, and all powers of 2. Why are these two generating functions equal?
Problem 2 Fix an positive integer $m$.
(a) What is the generating fucntion for, $p_m(n)$, the number of
integer partitions of $n$ into at most $m$ parts?
(b) use (a) to show that
$$
\lim_{n\to\infty} \frac{p_m(n)}{n^{m-1}/m!(m-1)!}=1.
$$
(c) Use (b) to show that
$$
\lim_{n\to\infty} \frac{p(n)}{n^C}=\infty
$$
for any positive constant $C$.
Problem 3 Find the generating function for $a_n$,
(a) the number of ways $n$ identical balls may be placed into 5 identical boxes,
with each box non-empty,
(b) the number of integer partitions of $n$ into even parts
(c) the number of integer partitions of $n$ into an even number of parts.
Problem 4 Use a Ferrers diagram to show that the number of partitions of $n$ into $k$ distinct parts is equal to the number of partitions of $n-\binom{k+1}{2}$ into at most $k$ parts.
Problem 5 Let $b_n$ be the number of rooted binary trees on $n$ vertices, so for example $b_2=2$, either "/" or "\". Put $b_0=1$, the empty tree with no vertices. Let $B(x)$ be the generating function of $b_n$. Show that $B(x)=1+x*B(x)^2$, find $B(x),$ thence $b_n$.
Problem 6 Use the explicit formula for the Catalan numbers to prove that $C_{n+1}\ge 2C_n$ if $n\ge 1.$
Problem 7 How many blockwalks from $(0,0)$ to $(8,8)$
(a) stay at or above the diagonal?
(b) stay at or below the diagonal?
(c) stay at or above the diagonal and hit the diagonal only at $(3,3)$ and $(8,8)?$
(d) stay at or above the diagonal and do not use the point $(4,4)$?
Problem 8 What is $$ \lim_{n\to\infty} \binom{3n}{n}*2^{2n}*\sqrt{n}/3^{3n} ? $$
Problem 9 Suppose that a six-sided die has arbitrary probabilities for each of the six sides. (Of course the sum of these 6 numbers is 1.) Show that if two identical such dice are rolled, the probability of doubles is always at least $\frac{1}{6}.$
Problem 10 A fair coin is flipped $n$ times. Let $X$ be the random variable which is the number of heads. Use a normal approximation to find a large value of $n$ such that $$ P(X\gt 0.51*n)<0.01. $$
Problem 11
Suppose we draw two cards without replacement from a standard 52-card deck.
(a) Find the probability that no queens are chosen.
(b) If we do this experiment 50 times in a row, what
is the probability that no queens are chosen in exactly
47 of the 50 trials.
Problem 12
Find all solutions to
(a) $7x+4\equiv 2\mod 11$
(b) $3x+2\equiv 7\mod 13$
(c) $x^2+2x\equiv 1\mod 13.$
Problem 13
TRUE or FALSE? If $a$ has inverse modulo $n$, then $n$ has an inverse modulo $a$.
Problem 14
What is $$ (42)^{10^{100}}\mod 1255? $$ Problem 15
TRUE or FALSE? If $p_1$, $p_2, \cdots p_n$ are odd primes, then $p_1*p_2*\cdots *p_n+2$ is another odd prime.
Problem 16 (harder)
Let $a_n$ be the sum over all partitions
of $n$ of the number of 1's in the partition. For example, the partitions of $4$ are
$\{4,31,22,211,1111\}$ so $a_4=0+1+0+2+4=7.$
Let $b_n$ be the sum over all partitions of $n$ of the number of different parts which appear.
So $b_4=1+2+1+2+1=7.$ Use generating functions to show that $a_n=b_n.$
Solution Let $y$ mark the number of 1's. Then $$ \sum_{n=0}^\infty a_n x^n = \frac{d}{dy}\frac{1}{(1-y*x)(1-x^2)(1-x^3)} y=1 $$
$$ = \frac{x}{(1-x)^2}\frac{1}{(1-x^2)(1-x^3)\cdots} $$
Let $z$ mark whenever a part is used. THen $$ \sum_{n=0}^\infty b_n x^n= \frac{d}{dz} (1+z*(x+x^2+x^3+\cdots)) (1+z*(x^2+x^4+\cdots))*(1+z*(x^3+x^6+x^9+\cdots))\cdots {\text{ at }} z=1 $$ Using the product rule we get $$ = \sum_{k=1}^\infty (x^k+x^{2k}+x^{3k}+\cdots)\frac{1-x^k}{(1-x)(1-x^2)(1-x^3)\cdots} $$
which is $$ = \sum_{k=1}^\infty x^k/(1-x)(1-x^2)\cdots= \frac{x}{(1-x)^2}\frac{1}{(1-x^2)(1-x^3)\cdots} $$