\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\norm}[1]{\lVert#1\rVert}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{eg}{Example}
\newtheorem{ex}{Exercise}
\newtheorem{defi}{Definition}
\newtheorem{hw}{Problem}
\newenvironment{sol}
  {\par\vspace{3mm}\noindent{\it Solution}.}
  {\qed}

\newcommand{\ov}{\overline}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\ch}{{\cal H}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cz}{{\cal Z}}
\newcommand{\eps}{\varepsilon}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\dist}{\mbox{\rm dist}}
\newcommand{\bn}{{\mathbf N}}
\newcommand{\bz}{{\mathbf Z}}

\setlength{\parindent}{0pt}
%\setlength{\parskip}{2ex}
\newenvironment{proofof}[1]{\bigskip\noindent{\itshape #1. }}{\hfill$\Box$\medskip}

\begin{document}

$\;$\hfill Due: 2012/10/10 before class

\begin{center}
{\LARGE\bf Homework 3}
\end{center}

\begin{hw} A matrix is {\em good} if in each row there are no repeated elements, and in each column
there are no repeated elements.
How many good matrices are there with $2$ rows and $6$ columns whose elements are all from $[6]$?
\end{hw}

\begin{hw}
For each $n$, find the simple form for $S(n, n-2)$, $S(n, n-3)$, $s(n, n-2)$, and $s(n, n-3)$.
\end{hw}

\begin{hw}
Prove that the Stirling numbers of the 1st kind $s(n, k)$ is an even number whenever $2k < n$ and $n > 0$.
\end{hw}

\begin{hw}
Count the number of permutations $x_1, x_2, \cdots, x_{2n}$ of $[2n]$ such that $x_i + x_{i+1} \neq 2n+1$ for all $1 \leq i \leq 2n-1$.
\end{hw}

\begin{hw}
Suppose $n > 4$ and there is an array of numbers $a_1, a_2, ..., a_n$, where each $a_i$
is either $1$ or $-1$. If
\[ a_1a_2a_3a_4 +  a_2a_3a_4a_5 + ... + a_{n-1}a_na_1a_2 + a_na_1a_2a_3 = 0, \]
prove that $n$ is a multiple of 4.
\end{hw}

\begin{hw}
In an $n \times n$ matrix each entry is filled with an integer. In each step you can
select one line (a row or a column) and change the sign of all the $n$ numbers in that
line.

Prove that in finite number of steps, one can change it to a matrix with non-negative sums on
every line.
\end{hw}

\end{document}
