% !TeX spellcheck = en_US
\documentclass[12pt,letter]{amsart}
%\usepackage[french]{babel}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{textcomp}
\usepackage[margin=2cm]{geometry}
\usepackage{graphicx, graphics}
\usepackage{todonotes}

\usepackage{pgf,tikz,pgfplots}
\pgfplotsset{compat=1.13}
\usepackage{mathrsfs}
\usetikzlibrary{arrows}
\usepackage{hyperref}

%for the due date to appear at the beggining of the page
\usepackage{etoolbox}
\makeatletter
\patchcmd{\@maketitle}
{\ifx\@empty\@dedicatory}
{\ifx\@empty\@date \else {\vskip3ex \centering\footnotesize\@date\par\vskip1ex}\fi
	\ifx\@empty\@dedicatory}
{}{}
\patchcmd{\@adminfootnotes}
{\ifx\@empty\@date\else \@footnotetext{\@setdate}\fi}
{}{}{}
\makeatother

\linespread{1.2}
\setlength\parindent{0pt}
\sloppy


\title{Homework II}
\author{Algebraic Combinatorics (Math 68)}
\date{\vspace{-.5em}Due September 25, 2019, at the \textbf{beginning of the class}}

\begin{document}
    \maketitle
    Collaboration among students to find key to the solution is encouraged, but each person must write the homework in his/her own words. You must write the name of the students with whom you work for each problem, as well as any written resource (web, book, etc.) that has been extensively used.
    
    You must write the appropriate justification as part of the solutions.\\
    
    \section*{Derangements}
    
    A \textit{derangement} is a permutation without any fixed point (a fixed point of $\sigma$ is some integer $i$ such that $\sigma(i)=i$). There is no known closed formula for the number of derangements of $n$, $d_n$. However, there are many ways of counting them.
    
    The first values of $(d_n)_{n \in \mathbb{N}}$ are $d_0=1$ and $d_1=0$.
    \begin{enumerate}   
    \item Prove the following recurrences.
    \begin{enumerate}
    	\item $n! = \sum_{k=0}^{n} \binom{n}{k}d_{n-k}$, \qquad \qquad for all $n\geq 0$
    	\item $d_n = (n-1)(d_{n-1}+d_{n-2})$, \quad for all $n\geq 2$ \label{rec}
    	\item $d_n = n d_{n-1}+ (-1)^n$, \qquad \qquad for all $n\geq 1$ \qquad \textit{Hint: use induction and \#\ref{rec}.}\label{alternate_signs}\\
	\end{enumerate}    
    
    \item %Express sum for permutations with at least a given number of fixed points
    \begin{enumerate}
    	\item What is the number of permutations of $[n]$ with at least $k$ fixed points? \label{fixed_pts}
    	\item Can you use inclusion-exclusion to give a way to count derangements using \#\ref{fixed_pts}?\\
    \end{enumerate}
    \item The \textit{exponential generating function} of a sequence $(a_n)_{n\in \mathbb{N}}$ is the formal power series 
    \[ \sum_{n\geq 0} a_n \frac{x^n}{n!}.  \]
    For example, $e^x$ is the exponential generating function of the sequence $(1,1,1,1,\ldots)$, because $e^x = \sum_{n\geq 0} \frac{x^n}{n!}$.
    Prove that the exponential generating function of the derangements is
    \[ \sum_{n\geq 0} d_n \frac{x^n}{n!} = \frac{e^{-x}}{1-x}. \]
    \textit{Hint: use \#\ref{alternate_signs}}.\\
    
   \item Prove that, for all $n\geq 0$,
   \[ \frac{d_n}{n!} = \sum_{k=0}^n \frac{(-1)^k}{k!}. \]\label{ratio}
   \textit{Hint: use \#\ref{alternate_signs} and induction.}\\
   
   \item  \begin{enumerate}
   	\item Can you use \#\ref{ratio} to deduce the asymptotic behavior? \textit{(Hint: The left-hand side of the equation in question \#\ref{ratio} is the evaluation of a well-known function).}
   	\item For the Christmas party in the department (where there are over 30 persons), we will have a gift exchange. Next week, every member of the department will have his or her name in a hat, and draw a name randomly. We hope that no one will draw his or her own name. How is this likely to happen?
   	\begin{itemize}
   		\item $<1\%$
   		\item $1-10 \%$
   		\item $10-50\%$
   		\item $>50\%$
   	\end{itemize}
   \textit{Hint: There is a reason for which I'm asking it here...}
   \end{enumerate}
   \section*{Other stuff}
   \item Explain why the Fibonacci numbers are the numbers of possible rhythms for verses with a given duration in the Sanskrit poetry. (As a remainder of how Sanskrit poetry works, you can use the excerpt on the right of \href{https://www.quantamagazine.org/number-theorist-manjul-bhargava-is-awarded-fields-medal-20140812}{this article} from Quanta Magazine; you don't have to read the full article).\\
\end{enumerate}

    \textbf{Don't forget that the solution is not the same as the answer.}
    \begin{center}
    	\textbf{Good luck!}
    \end{center}
\end{document}