\documentstyle[12pt,twoside]{article}
\input{macros-course}

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{8}{April 13,1995}{In recitation, April 21}

\bigskip


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\points{5}
Discover and prove a formula for
\[
\sum_{k=0}^n k^3 {n \choose k}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\points{5}
How many $m$ digit numbers are there such that each one starts with a
significant digit (i.e.\ not $0$) and all digits appear in each number?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\points{10}
Prove that the Bell numbers satisfy the recurrence
\[
B_{n+1} = \sum_{k=0}^n {n \choose k} B_k
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\points{10}
Calculate how many ways $3$ distinct numbers can be selected from
$\{1,2,3,\ldots,150\}$ so that their sum is
\bparts
\ppart even
\ppart odd
\ppart a multiple of $3$
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\points{20}
In this problem we will prove that the number of labeled trees on
$n$ vertices is $n^{n-2}$.
\bparts
\ppart Prove the following generalization of Pascal's triangle
\[
{m \choose {m_1\ldots m_k}} = \sum_{i=1}^k {m-1 \choose {m_1 \ldots m_{i}-1\ldots m_k}}
\]
\ppart Let $t(n;d_1,\ldots ,d_n)$ be the number of trees on $n$ vertices such that the degree of vertex $i$ is $d_i$.  Show that
\[
t(n;d_1,\ldots,d_{n-1},1) = \sum_{i=1}^{n-1} t(n-1;d_1,\ldots,d_i - 1,\ldots,d_{n-1})
\]
\ppart Show that the number of trees on $n$ vertices such that the degree of
vertex $i$ is $d_i$ is
\[
{n-2 \choose {(d_1-1)(d_2-1)\ldots(d_n-1)}}
\]
(Hint:  Use parts (a) and (b) and induction on $n$)
\ppart Now prove that the number of labeled trees on $n$ vertices is
$n^{n-2}$.
\eparts
\end{problems}

\end{document}

