
\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, 2020 Fall, USTC} \\
    {Homework 3}
\end{center}


\begin{itemize}
\item The due is on Tuesday, October 20, at beginning of the class.
\end{itemize}

\bigskip

\noindent{\bf 1.} Recall the Stirling number $S(n,k)$ of the second kind.
\begin{itemize}
\item [(1).] Prove that for all $1\le k\le n$, $$S(n+1,k)=S(n,k-1)+k\cdot S(n,k).$$
\item [(2).] For a fixed $k$, let $A_k(x)$ be the ordinary generating function of the sequence $\{S(n,k)\}_{n\ge 0}$. Find a closed form of $A_k(x)$.
(When $0\le n<k$, $S(n,k)$ is defined to be $0$.)
\end{itemize}


\bigskip

\noindent{\bf 2.} Let $a_n$ denote the number of mappings $f: [n]\to [n]$ such that if $f$ takes a value $i$, then it also takes every value $j$ for $1\le j\le i$. Let $a_0=1$. Find the closed form of the generating function $f(x)$ of $\{a_n\}_{n\ge 0}$.

\bigskip

\noindent{\bf 3.} A {\it binary tree} can be defined by induction as follows: a binary tree either is empty (it has no vertex), or consists of one distinguished vertex called the {\it root} plus an ordered pair of binary trees called the {\it left subtree} and {\it right subtree}.
Let $b_i$ be the number of binary trees with $n$ vertices. So $b_0=1, b_1=1, b_2=2, b_3=5$ and so on. Find a closed form for $b_n$.


\bigskip

\noindent{\bf 4.} Consider a random walk along the $x$-axis, where we start at the integer $0$ and in each coming step we move from integer $i$ to $i+1$ or to $i-1$ with probability $1/2$.
\begin{itemize}
\item[(1).] Prove that every integer $k$ is visited at least once with probability 1.
\item[(2).] For any positive integer $k\ge 1$, what is the expected number of steps needed to get at least $k$ steps away from $0$ (i.e., to reach $k$ or $-k$)?
\end{itemize}


\bigskip


\noindent{\bf 5.} Given arrangements of a special type, called the type I.
Let $a_n$ be the number of such arrangements of $n$ people, where $a_0=0$ (no empty group is allowed).
Let $A(x)$ be the exponential generating function of $\{a_n\}$.
We now define arrangements of $n$ people of a new type, called the type II, as follows.
Fix $k\ge 1$.
An arrangement of $n$ people of type II is obtained by dividing the given $n$ people into $k$ groups, called the $1^{st}$ group, the $2^{nd}$ group,..., and the $k^{th}$ group, and arranging each group by an arrangement of type I.
Let $b_n$ be the number of arrangements of $n$ people of type II; and let $B(x)$ be the exponential generating function of $\{b_n\}$.
Express the exponential generating function $B(x)$ using $A(x)$ in a closed form.

\bigskip

\noindent{\bf 6.} 
Construct as many pairwise non-isomorphic graphs with vertex set $[n]$ as possible (suppose that $n$ is very large number).
Prove that why your graphs are non-isomorphic. Can you find more than $n^2$ of them? At least $2^{n/10}$? Or even at least $2^{n^2/10}$?


\bigskip

\noindent{\bf 7.} Let $G$ be a graph in which all vertices have degree at least $d$. Prove that $G$ contains a cycle of length at least $d+1$.


\end{document}
