
\documentclass[12pt]{article}
\usepackage{fullpage}

\newcommand{\falling}[2]{#1^{\underline{#2}}}
\newcommand{\rising}[2]{#1 ^{\overline{#2}}}
\newcommand{\stirling}[2]{\left\{ \begin{array}{c} #1 \\ #2 \end{array} \right\}}

\begin{document}
\begin{center}
\bf
CS 141, Advanced Topics in Algorithms \\
Spring 2004\\
Homework 1a \\
Due Monday, January 26
\end{center}
\vspace{0.5cm}

\begin{itemize}
	\item Please recall that solutions to homework assignments in this class must 
	be typeset, preferably in \LaTeX.  You should keep electronic versions of all
	of your homework submissions.
	
	\item Please also recall that homeworks are due at the very beginning of class.
\end{itemize}

\begin{enumerate}


\item {\bf [15 Points] Stirling Numbers of the Second Kind!}
In class we used ``Stirling Numbers of the Second Kind'' to help us
express regular powers as the sum of falling powers.  We defined Stirling's
Triangle and showed how it was constructed.  Specifically,
let $\left\{ \begin{array}{c} n \\ k \end{array} \right\}$ denote the 
Stirling number in the $k^{th}$ column of row $n$ of Stirling's Triangle.  
In class,
we said that the rule for building Stirling's Triangle works like this:
	\begin{enumerate}
		\item $\left\{ \begin{array}{c} 0 \\ 0 \end{array} \right\} = 1$.
		(That is, the element at the top of the triangle is 1.)
		\item $\left\{ \begin{array}{c} n \\ 0 \end{array} \right\} = 0$
		for all $n \geq 1$.  (That is, the left edge of the triangle
		is all 0's.)
		\item $\left\{ \begin{array}{c} n \\ n \end{array} \right\} 
		= 1$
		for all $n \geq 1$.  (That is, the right edge of the triangle
		is all 1's.)
		\item $\left\{ \begin{array}{c} n \\ k \end{array} \right\} =
		\left\{ \begin{array}{c} n-1 \\ k-1 \end{array} \right\}
		+ k \left\{ \begin{array}{c} n-1 \\ k \end{array} \right\}$
		for any $n \geq 1$.
	\end{enumerate}
This is very similar to the binomial coefficients $n \choose k$ in Pascal's
Triangle.  The Binomial coefficients have some special significance:
$n \choose k$ is the number of ways to choose $k$ objects from
$n$ distinct objects where order does not matter.
Do the Stirling Numbers of the Second Kind have some meaning as well
(other than being useful in Discrete Calculus)?  Yes!  It turns out
that $\left\{ \begin{array}{c} n \\ k \end{array} \right\}$ counts the number
of different ways to partition $n$ distinct objects into $k$ nonempty sets.
For example consider partitioning the three objects $1,2,3$ into two sets,
neither of which is empty.  There are only three ways to do this:
	\begin{itemize}
		\item $\{ 1, 2 \}$, $\{3 \}$.
		\item $\{ 1, 3 \}$, $\{2 \}$.
		\item $\{ 2, 3 \}$, $\{1 \}$.
	\end{itemize}
Notice that $\left\{ \begin{array}{c} 3 \\ 2 \end{array} \right\} = 3$ (just look
at Stirling's Triangle!).

	\begin{enumerate}
		\item Given that 
		$\left\{ \begin{array}{c} n \\ k \end{array} \right\}$
		counts the number of ways to partition $n$ distinct 
		objects into $k$ nonempty sets, give a combinatorial
		argument that explains 
		why  $\left\{ \begin{array}{c} n \\ k \end{array} \right\} =
		\left\{ \begin{array}{c} n-1 \\ k-1 \end{array} \right\}
		+ k \left\{ \begin{array}{c} n-1 \\ k \end{array} \right\}$.
		(Show that both sides count the same thing in two different
		ways.)

		\item Give a combinatorial argument to explain why
		$\left\{ \begin{array}{c} n \\ 2 \end{array} \right\} =
		2^{n-1} - 1$.

		\item Give a combinatorial argument to explain why
		$\left\{ \begin{array}{c} n \\ n-1 \end{array} \right\} =
		{n \choose 2}$.
	\end{enumerate}

\item \textbf{[20 Points] Stirling Numbers and The Discrete Calculus.}
In the previous problem you gave a combinatorial proof that: 
\[
\stirling{n}{k} = \stirling{n-1}{k-1} + k \stirling{n-1}{k}
\]
From this identity, we could build the Stirling Triangle of the Second Kind.  Then,
Ran made the following wild claim in class: 
\[
x^{n} = \sum_{k = 0}^{n} \stirling{n}{k} \falling{x}{k}
\]
for any integer $n \geq 0$.  This identity was very useful in computing all sorts of 
summations using the Discrete Calculus.  Now, you will prove this identity.
\begin{enumerate}
  \item First, show that $x \cdot \falling{x}{k} = \falling{x}{k+1} + k \falling{x}{k}$.
  \item Now, use induction on $n$ to show that 
\[
x^{n} = \sum_{k = 0}^{n} \stirling{n}{k} \falling{x}{k}
\]
The identity that you proved in part $(a)$ may be useful to you.

  \end{enumerate}

\item {\bf [10 Points] Deriving Amazing Formulae with Discrete Calculus!}
Use Discrete Calculus to derive a closed-form
                formula for 
                \[
                \sum_{k = 0}^{n} k^{3}. 
                \]
                Show your work in detail.  
\end{enumerate}
\end{document}



