
\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 2}
\end{center}


\begin{itemize}
\item The due is on Tuesday, September 27, at beginning of the class.

\item Solve any all problems.
\end{itemize}


\noindent{\bf 1.} How many functions $f: [n]\to [n]$ are there such that for all $i<j$, we have $f(i)\le f(j)$?

\bigskip

\noindent{\bf 2.} Let $\pi(n)$ denote the number of primes not exceeding the number $n$. 
\begin{itemize}
\item [(a)] Show that the product of all primes $p$ with $m<p\le 2m$ is at most $\binom{2m}{m}$. 

\item [(b)] For a prime $p$, show that if $p^k$ divides $\binom{2m}{m}$, then $p^k\le 2m$.

\item [(c)] Using (a) and (b), prove that there exist absolute constants $c_1, c_2>0$ such that 
$$c_1\cdot \frac{n}{\log n}\le \pi(n)\le c_2\cdot \frac{n}{\log n}.$$
\end{itemize}

\bigskip


\noindent{\bf 3.} An {\it equivalence} of $[n]$ is just a partition of $[n]$ into $k$ non-ordered non-empty subsets for some $k$.
Denote the $n^{th}$ {\it Bell number} $B_n$ to be the total number of equivalence of $[n]$. 
Prove that $$ B_n=\frac{1}{e}\sum_{i=0}^\infty \frac{i^n}{i!}.$$ 


\bigskip

\noindent{\bf 4.} (a). Given a natural number $N$, determine the probability that two number $m,n\in [N]$ chosen independently at random are relatively prime.

(b). Prove that the limit of the probability in (a) for $N\to \infty$ equals the infinite product $\prod_{p} (1-1/p^2)$, where $p$ runs over all primes.



\bigskip

\noindent{\bf 5.} Show that the number $(6+\sqrt{37})^{999}$ has at least 999 zero following the decimal point.


\bigskip

\noindent{\bf 6.} Let $f_n(x)=x(x-1)...(x-n+1)$. Prove that $$f_n(x+y)=\sum_{k=0}^n \binom{n}{k} f_k(x)f_{n-k}(y).$$


\bigskip

\noindent{\bf 7.} Let $A_n$ be the number of ways of going up $n$ stairs, if we may take one or two steps at a time. Find the generating function $f(x)$ of $\{A_n\}_{n\ge 0}$.






\end{document}
