% !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 III}
\author{Algebraic Combinatorics (Math 68)}
\date{\vspace{-.5em}Due October 2, 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.\\
\begin{enumerate}
\item Give both the exponential and ordinary generating functions for the sequences $\mathbb{N}$ and $\{3^n\}_{n\in \mathbb{N}}$.\\
\item Use generating functions to prove that $\sum_{k=0}^n \binom{n}{k} = 2^n$.\\
\item Give the number of bijective functions from a set $N$ to a set $X$, and distinguish the cases where the objects in the sets are distinguishable or indistinguishable. \\
\item Compute the number of partitions of 30, and explain how you did it (using the computer is allowed).\\
\item The goal of this exercise is to prove the generating function of the Catalan numbers. Recall that this is
\[ C(x) = \sum_{n\geq 0} \frac{1}{n+1}\binom{2n}{n} = \frac{1-\sqrt{1-4x}}{2x}. \]
\begin{enumerate}
\item Prove that $xC^2(x)- C(x) +1 = 0$. \\
\textit{Hint: Use the recurrence we found when I talked about Catalan numbers (on September 20).}
\item Solve this equation. You will get two solutions.
\item Determine which one is the actual generating function (using the binomial theorem can use, but you can do it without knowing that.)\\
\end{enumerate}
\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}