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

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

\begin{document}

\psol{8}{April 21, 1995}

\bigskip


\begin{problems}

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


We will do this analytically, much like $\sum_{k=0}^n k{n \choose k}$.  We
know from the binomial theorem that
\[
(x+1)^n = \sum_{k=0}^n {n \choose k}x^k
\]
Differentiating both sides gives us
\[
n(x+1)^{n-1} = \sum_{k=1}^n k{n \choose k}x^{k-1}
\]
and also 
\[
n(n-1)(x+1)^{n-2} = \sum_{k=2}^n k(k-1){n \choose k}x^{k-2}
\]
Substituting $x=1$ and accounting for the missing terms (we started the
summation at $k=2$) gives
\[
\sum_{k=0}^n k{n \choose k} = n2^{n-1}
\]
and
\[
n(n-1)2^{n-2} = \sum_{k=0}^n k^2{n \choose k} - n - \sum_{k=0}^n k{n \choose
k} + n
\]
thus,
\[
\sum_{k=0}^n k^2{n \choose k} = n(n-1)2^{n-2} + n2^{n-1} = n(n+1)2^{n-2}
\]

We now have all of the pieces we need to find the required sum.
By differentiating once more we have
\begin{eqnarray*}
n(n-1)(n-2)(x+1)^{n-3} & = & \sum_{k=3}^n k(k-1)(k-2){n \choose k}x^{k-3}\\
 & = & \sum_{k=3}^n(k^3 - 3k^2 + 2k)x^{k-3}
\end{eqnarray*}
Substituting $x=1$ once more and gathering up the missing terms we have
\begin{eqnarray*}
n(n-1)(n-2)2^{n-3} & = & \sum_{k=0}^n k^3{n \choose k} -n - 8{n \choose 2}
-3\left[n(n+1)2^{n-2} - n -4 {n \choose 2} \right] \\
 & & + 2\left[n2^{n-1} -n -2 {n \choose 2} \right]\\
 & = & \sum_{k=0}^n k^3 {n \choose k} - 3\sum_{k=0}^n k^2 {n \choose k} +
 2\sum_{k=0}^n k {n \choose k} \\
 & = & \sum_{k=0}^n k^3 {n \choose k} - 3n(n+1)2^{n-2} + n2^n
\end{eqnarray*}

Rearranging terms gives us the solution
\begin{eqnarray*}
\sum_{k=0}^n k^3 {n \choose k} & = & n(n-1)(n-2)2^{n-3} + 3n(n+1)2^{n-2} -
n2^n \\
 & = & 2^{n-3}(n(n-1)(n-2) + 6n(n+1) - 8n) \\
 & = & 2^{n-3}(n^3 + 3n^2) \\
 & = & n^2(n+3)2^{n-3}
\end{eqnarray*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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?

Let $A(n,k)$ be the number of $n$ digit numbers where each digit (we have
$k$ of them) appears at least once.  We know from Lecture $16$ that
$A(n,k) = \sum_{j=0}^k (-1)^j {k \choose j} (k-j)^n$.  To count those that
start with a significant digit we break them up into two cases:
\begin{enumerate}
\item The digit that it starts with appears again in the number.  We have
$A(m-1,k)$ different numbers for each significant digit
\item The digit does not appear again.  We have $A(m-1,k-1)$ different
numbers for each significant digit
\end{enumerate}

Thus the total count equals $(k-1)(A(m-1,k) + A(m-1,k-1))  =$
\[
(k-1)\left[ \sum_{j=0}^k (-1)^j{k \choose j}(k-j)^{m-1} + \sum_{j=0}^{k-1}
(-1)^j {k-1 \choose j} (k-1-j)^{m-1} \right]\]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

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

\begin{proof}
We know that $B_{n+1}$ counts the number of partitions of
$\{1,\ldots,n+1\}$.  Let's pick an element of the set and call it $x$.  We
now count all of the partitions in which the class containing $x$ has
$j$ elements.  There are ${n \choose j-1}B_{n+1-j}$ such partitions.  Why?  There are ${n \choose j-1}$ ways of choosing the remaining elements in $x$'s class and $B_{n+1-j}$ ways of partitioning the rest of the elements.  

Thus the total number of partitions of $\{1,\ldots,n+1\}$ is the sum over
all $j$ of the above expression
\begin{eqnarray*}
B_{n+1} & = & \sum_{j=1}^{n+1} {n \choose j-1}B_{n+1-j}\\
        & = & \sum_{l=0}^n {n \choose l}B_{n-l}\\
		& = & \sum_{l=0}^n {n \choose n-l}B_{n-l}\\
		& = & \sum_{k=0}^n {n \choose k}B_k
\end{eqnarray*}

\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.
There are $75$ even and $75$ odd numbers in the given interval. To choose
$3$ distinct numbers so that their sum is even we either choose
\begin{enumerate}
\item \ $3$ even numbers.  We can do this in ${75 \choose 3}$ ways. 
\item \ $2$ odd numbers and $1$ even number.  We can do this in ${75 \choose
2}*75$ ways.
\end{enumerate}
Thus the total number is $75*{75 \choose 2} + {75 \choose 3} = 275650$.

\ppart odd.  
The sum of the three numbers is either even or odd.  Thus the number of
different ways we can choose three distinct numbers so that their sum is odd
is ${150 \choose 3} - $(answer from part(a)).  This equals $275650$.

\ppart a multiple of $3$.
In the interval we are given there are $50$ numbers whose remainder when
divided by $3$ is $0$, $50$ whose remainder is $1$ and $50$ whose remainder
is $2$.  For the sum of the $3$ numbers to be a multiple either
\begin{enumerate}
\item All $3$ numbers have the same remainder when divided by $3$.  We can
choose these in $3 {50 \choose 3}$ ways.
\item Their remainders as all different.  We can choose these in $50^3$
ways. 
\end{enumerate}
Thus the total number of ways is $3 {50 \choose 3}  + 50^3 = 183800$.

\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}}
\]
\begin{proof}

We know from the multinomial theorem that the coefficient of
$x_1^{m_1} \ldots x_k^{m_k}$ in $(x_1 \ldots + x_k)^m$ is ${m
\choose m_1 \ldots m_k}$.  Another way of computing this coefficient is by
noting that 

\[
(x_1 + \ldots + x_k)^m = (x_1 + \ldots + x_k)^{m-1}(x_1 + \ldots + x_k)
\]

We can thus get $x_1^{m_1}\ldots x_k^{m_k}$ by multiplying $x_1^{m_1}\ldots
x_i^{m_i-1}\ldots x_k$ by $x_i$ for $i=1,\ldots,k$.  Thus the required
coefficient is 
\[
\sum_{i=1}^k {m-1 \choose {m_1 \ldots m_{i}-1 \ldots m_k}}
\]

\end{proof}

\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})
\]

We know that vertex $n$ has degree $1$ so it's a leaf.  It must be connected
to some vertex, call it $i$.  We will now count how many trees have vertex
$n$ connected to vertex $i$.  If we remove vertex $n$ we have a tree on
$n-1$ vertices where the degree sequence is almost the same -- vertex $i$ has
degree $d_i-1$.  Thus we have $t(n-1;d_1,\ldots,d_{i}-1,\ldots,d_{n-1})$
such trees.  So to find the number of trees on $n$ vertices we just sum the
expression above from $i=1$ to $n-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$)

We will do this by induction on $n$.  

\begin{description}
\item[Base Case:] \ $n=2$.  Both are equal to $1$.
\item[Inductive step:] We know that
\[
t(n;d_1,\ldots,1) = \sum_{i=1}^{n-1} t(n-1;d_1,\ldots,d_i-1,\ldots,d_{n-1})
\]

We must now find a formula for $t(n;d_1,\ldots,d_n)$.  Without loss of
generality we can assume that $d_n = 1$. ($t$ is independent of the order of
the degree sequence and there must be some leaf). Thus,

\[
\begin{array}{llll}
\displaystyle t(n;d_1,\ldots,d_n) & = & \displaystyle \sum_{i=1}^{n-1}
t(n-1;d_1,\ldots,d_i-1,\ldots,d_{n-1}) & \\
 & = & \displaystyle \sum_{i=1}^{n-1} {n-3 \choose {(d_1-1)\ldots (d_i-1-1) \ldots
 (d_{n-1}-1)}} & \mbox{\ (Inductive hypothesis)} \\
 & = & \displaystyle{n-2 \choose (d_1-1)\ldots(d_{n-1}-1)} & \mbox{\ (part (a))} \\
 & = & \displaystyle{n-2 \choose {(d_1-1) \ldots (d_n-1)}} & \mbox{\ ($d_n-1 = 0$)} \\
\end{array}
\]

\end{description}

\ppart Now prove that the number of labeled trees on $n$ vertices is
$n^{n-2}$.
\begin{proof}

To find the total number of trees we just sum the expression above over all
degree sequences.  If we let $k_i = d_i-1$ the sum is

\[
\sum_{\stackrel{k_1,\ldots,k_n}{k_1+\ldots+k_n=n-2}} {n-2 \choose {k_1 \ldots k_n}} = n^{n-2} \mbox{\ \ \ (from the multinomial theorem)}
\]

Note that since we have a tree the sum of the degrees is $2(n-1) = 2n-2$ and
so $\sum_{i=1}^n k_i = n-2$.

\end{proof}

\eparts
\end{problems}

\end{document}

