
\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{mathrsfs}
\addtolength{\topmargin}{-.5in} \addtolength{\textheight}{1in}
\addtolength{\oddsidemargin}{-.6in}
\addtolength{\evensidemargin}{-.6in} \addtolength{\textwidth}{1.2in}
\usepackage{latexsym,amsmath,amssymb,amsfonts,epsfig,graphicx,cite,psfrag}
\usepackage{eepic,color,colordvi,amscd}


\def\qed{\hfill \rule{4pt}{7pt}}

\def\pf{\noindent {\it Proof. }}




\pagestyle{plain}


\begin{document}
\begin{center}
    \large{Combinatorics, 2016 Fall, USTC} \\
    {Homework 1}
\end{center}


\begin{itemize}
\item The due is on Tuesday, Sep. 13.

\item Solve all problems.
\end{itemize}


\noindent{\bf 1.} How many 9-digit numbers can be made of digits $1,2,\ldots, 9$ so that no $i$ is put in the $i$'th position, and the number of not a {\it palindrome}. (A palindrome is a word or a number that reads the same in either direction. For example, ``rotator" and ``12321" are palindromes, but ``1231231" is not.)

\bigskip

\noindent{\bf 2.} Let $n,r$ be be positive integers and $n\ge r$.  Give a {\bf combinatorial proof} of $$\binom{2n}{2r}\equiv \binom{n}{r} (mod~2).$$

\bigskip

\noindent{\bf 3.} Find a closed formula for $$\sum_{k=m}^n \binom{k}{m}\binom{n}{k}.$$


\bigskip


\noindent{\bf 4.} Suppose there are $n$ objects of $r$ different kinds, where the $i$th kind has $k_i$ identical objects and $k_1+k_2+...+k_r=n$.
How many distinct arrangements of those $n$ objects (listed in a row from left to right) in total are there?


\bigskip

\noindent{\bf 5.} Let $n$ be a positive integer. Prove that the identity $$x^n=\sum_{k=1}^n S(n,k)(x)_k$$ holds for every real number $x$, where $S(n,k)$ is the Stirling number of the second kind, and $(x)_k:=x(x-1)...(x-k+1)$.

Hint: first prove the case when $x$ is a positive integer by double-counting certain mappings.


\bigskip

\noindent{\bf 6.} Find a closed formula of $$\sum_{k=0}^{\lfloor n/7 \rfloor} \binom{n}{7k}.$$ (Try to simplify this expression to a summation with at most four terms)

Hint: let $\epsilon =e^{2\pi i/7}$, where $i$ is the imaginary unit, and then consider the value of $\sum_{j=0}^6 \epsilon^{kj}$.

\bigskip

\noindent{\bf 7.} Let $n\ge m$. Prove $$\sum_{k=0}^m \binom{m}{k} \binom{n+k}{m}=\sum_{k=0}^m \binom{m}{k} \binom{n}{k} 2^k.$$








\end{document}
