\documentclass[]{article}

\usepackage{epsfig}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{graphicx}
\pagestyle{empty}
%\setlength{\topmargin}{-1in}
%\setlength{\oddsidemargin}{-.3in}
%\setlength{\textheight}{9.5in}
%\setlength{\textwidth}{7.2in}
\newcommand{\bZ}{\mathbb{Z}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\mcg}{\vspace{0.3cm}}
\newcommand{\blank}{\underline{\hspace{2cm}}}
\newcommand{\solution}[1]{\parbox{1cm}{} \hfill {#1}\parbox{3cm}{: \hrulefill} \\}
\begin{document}

\begin{center}
\Large Hwk 2
\end{center}

{\Large M366} \hfill {\Large Fall 2013} \\


\vspace{0.5cm}



\begin{enumerate}

\item Prove that for any positive integer $n$:
$$
\sum_{k=0}^n {{n}\choose{k}}=2^n
$$

\item Prove that for any positive integer $n$:
$$
\sum_{k=0}^n (-1)^k{{n}\choose{k}}=0
$$
\item  Let $X$ be a set with n elements. Given three nonnegative integers $a,b,c$ such that $a+b+c=n$, how many ways can you partition $X$ into three disjoint subsets with $a,b$ and $c$ elements?

{\it (I am looking for an answer in terms of products and quotients of factorials, just like in case of the binomial coefficient).}

\item{\bf Challenge:} can you generalize problem 3. the following way: let $X$ be a set with $n$ elements, and  $a_1, a_2, …, a_k$  nonnegative integers adding up to $n$. How many ways can you partition X into $k$ subsets $S_i$ such that the cardinality of $S_i$ is $a_i$. This number is called the multi-nomial coefficient ${ {n}\choose {a_1, …, a_k}}$. 

\item {\bf Extra challenge:} can you figure out how Newton’s binomial theorem generalizes to a “ Newton multi-nomial theorem”? I.e. can you prove a formula for the expansion of
$$
(x_1+x_2+\ldots +x_k)^n= ?
$$


{\it  First make a guess to what the formula should be. Verify it in for some small values of n and k. Then try to prove it either by induction or just by explaining why the coefficients are what they are.}

\end{enumerate}
\end{document}