\documentclass[12pt]{amsart}
\usepackage{amsmath}
\usepackage{graphicx, epic,eepic, pstricks}

\setlength{\textwidth}{15.5cm} \setlength{\headheight}{0.5cm}
\setlength{\textheight}{21.5cm} \setlength{\oddsidemargin}{0.25cm}
\setlength{\evensidemargin}{0.25cm} \setlength{\topskip}{0.5cm}
\setlength{\footskip}{1.5cm} \setlength{\headsep}{1cm}
\setlength{\topmargin}{0.5cm}

% Fuzz -----------------------------------------------------------
\hfuzz5pt % Don't bother to report overfull boxes < 5pt
% MATH -----------------------------------------------------------
\DeclareMathOperator{\RE}{Re} \DeclareMathOperator{\IM}{Im}
\DeclareMathOperator{\ess}{ess}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}
\newcommand{\h}{\mathcal{H}}
\newcommand{\s}{\mathcal{S}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\BOP}{\mathbf{B}}
\newcommand{\BH}{\mathbf{B}(\mathcal{H})}
\newcommand{\KH}{\mathcal{K}(\mathcal{H})}
\newcommand{\Real}{\mathbf{R}}
\newcommand{\Complex}{\mathbf{C}}
\newcommand{\Field}{\mathbf{F}}
\newcommand{\RPlus}{\Real^{+}}
\newcommand{\Poly}{\mathcal{P}}
\newcommand{\EssD}{\mathcal{D}}
\newcommand{\Lom}{\mathcal{L}}
\newcommand{\States}{\mathcal{T}}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\seq}[1]{\left<#1\right>}
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\essnorm}[1]{\norm{#1}_{\ess}}
% THEOREM ENV. ------------------------------------------------------------
\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{con}{Conjecture}
\newtheorem{lem}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{clm}{Claim}
\newtheorem{obs}{Observation}
\newtheorem{conj}{Conjecture}
\newtheorem{prob}{Problem}
%\renewcommand{\thethm}{}  % unnumbered
\pagestyle{empty}
\renewcommand{\baselinestretch}{1.15}
%%% ----------------------------------------------------------------------

\begin{document}
\begin{center}
{\bf Math 432 Homework Five}\\
Due: Friday, Feb 26, 2016
\end{center}

\bigskip


\begin{enumerate}

\item Find the number of integers between $1$ and $10000$ that are
not divisible by $4,6,7$, or $10$.



\item Count the permutations $i_1i_2i_3i_4i_5i_6$ of $[6]$, where
$i_1\not=1,5; i_3\not=2,3,5; i_4\not=4$ and $i_6\not=5,6$.


\item Give a combinatorial proof (via inclusion-exclusion) for the
identity below.
\[
\sum_{k=0}^n (-1)^k {n\choose k}{2n-2k\choose n-1}=0.
\]


\item Let $S(n,k)$ be the number of ways to partition $[n]$ into $k$ nonempty subsets ($S(n,k)$ is called the Stirling number of second kind).  Prove the following identity by inclusion-exclusion:  
$$S(n,k)=\frac{1}{k!} \sum_{i=0}^k (-1)^i {k\choose i}(k-i)^n$$


\item Let $a_n$ be the number of words of length $n$ from the
alphabet $\{w,x,y,z\}$ such that $x$ appears an even number of times
and $y$ appears an odd number of times. Build the EGF for the sequence $a_1, a_2, \ldots, a_n, \ldots$ and
use it to obtain a formula for $a_n$.


\item Let $a_n$ be the number of involutions on an $n$-element set.
Derive a recurrence for the number, and use the generating function
method to obtain the EGF from it.




\end{enumerate}
\end{document}
