\documentclass[10pt]{article}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{color}

\usepackage{enumitem}
\setenumerate[0]{label=(\alph*)}

%\addtolength{\topmargin}{-.7in}
%\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.4in}
\addtolength{\textwidth}{.8in}
\pagestyle{empty}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\Flat}{\mathrm{Flat}}
\renewcommand{\S}{\mathcal S}
\newcommand{\surj}{\mathrm{surj}}

%\newcommand{\multi}[2]{\left(\!\binom{#1}{#2}\!\right)}
%\newcommand{\multi}[2] { \genfrac {(} {)} {0em} {} {#1} {#2} }
\newcommand{\multi}[2]{\left(\!\left(\!
\genfrac{}{}{0pt}{}{#1}{#2}\!\right)\!\right)}


\begin{document}
\centerline{\bf Math 880 \hfill{\large\bf Homework 1}\hfill Fall 2023}
\vspace{1em}      

\noindent  Feel free to discuss homework problems with other students, and to learn from references, but please do not look up specific answers.
Write out solutions in your own words, and give explicit credit for any significant help. 
LaTeX is encouraged, but not required.  
\\[1em]
The {\it Method of Generating Functions} consists of steps linking various more-or-less equivalent forms of combinatorial and analytic data:
\begin{itemize}
\item[(i)] Graded class $\A=\coprod_{k\geq 0} \A_k$ of combinatorially defined objects 
$a\in \A$ with size $|a|=k$
\item[(ii)] Recurrence constructing $\A_k$ from smaller classes;
recursive formula for $A_k=\#\A_k$
\item[(iii)] Explicit formula for the generating function  
$A(x)  = \sum_{k\geq 0} A_k x^k = \sum_{a\in \A} x^{|a|}$
\item[(iv)] Explicit formula for $A_k$
\item[(v)] Asymptotic approximation $A_k\sim \alpha(k)$ for simple $\alpha(k)$, 
with $A_k/\alpha(k)\to 1$ as $k\to\infty$.
\end{itemize}

\noindent An enumeration problem usually starts with the first two forms of data,
and the main goal is to derive the last two forms.
The generating function is the central unifying object.
\\[1em]
{\bf 1.}  Define a {\it multiset} to be like a set, but with repeat elements allowed, 
such as $M=\{1,3,3,5\}$. 
The number $\multi nk$, $n$ multi-choose $k$, 
counts all multisets of $k$ elements chosen from 
$[n]=\{1,2,\ldots,n\}$. {\sc example:} $\multi 23=4$ counts $M=\{1,1,1\},
\{1,1,2\}, \{1,2,2\}$, $\{2,2,2\}$. 
\\[.5em]
Analyze $\multi nk$ similarly to $\binom nk$, using the class
$\A^{(n)}=\coprod_{k\geq 0}\A^{(n)}_k$
of all multisets from $[n]$.

\begin{enumerate}

\item (i)\,$\Longrightarrow$\,(iii). 
From the combinatorial definition of $\A^{(n)}$,
find a multiset analog of the Bit-string Transformation of sets,
which allowed us to apply the Product Principle to get 
$\sum_{k\geq 0}\binom nk x^k=(1+x)^n$.
Similarly, derive a simple formula for $A^{(n)}(x)=\sum_{k\geq 0}\multi nk x^k$.

\item (i)\,$\Longrightarrow$\,(ii). Use Deletion Transform to find a Pascal's Triangle type recurrence for $\multi nk$. 

\item (iii)\,$\Longrightarrow$\,(ii). Derive the recurrence directly from the
generating function by manipulating the denominator of $A^{(n)}(x)$.

\item (iii)\,$\Longrightarrow$\,(iv). Use the coefficient formula for Taylor series to get
a simple formula for $\multi nk$, similar to $\binom nk=\frac{n^{\underline k}}{k!}$.
Using this, find a binomial coefficient which is equal to the multi-choose number:
$\multi nk = \binom mk$ for appropriate $m$. 

\item (i)\,$\Longrightarrow$\,(iv). Give a bijection which proves the above identity 
$\multi nk = \binom mk$, transforming $k$-element multi-sets from $[n]$ into
$k$-element sets from $[m]$.

\item (iv)\,$\Longrightarrow$\,(v). 
Show $\multi nk\sim \frac{k^{n-1}}{(n-1)!}$ for 
$k\to\infty$ and fixed $n$.

\end{enumerate}

\newpage

\noindent
{\bf 2.} Recall the combinatorial class of surjections, doubly graded by $k\geq n$:
 $$
 \S^n_k = \{ \text{surjective functions } f:[k] \twoheadrightarrow [n]\},
 $$
 and its counting number $\surj(k,n)=\#\S^n_k$.
 The two indexes $k,n$ produce two types of generating functions:
 $$
 S^{(n)}(x) = \sum_{k\geq 0}\surj(k,n)\, x^k
 \qquad\text{and}\qquad
 S_{(k)}(y) = \sum_{n\geq 0}\surj(k,n)\,y^n.
 $$

\begin{enumerate}

\item (i)\,$\Longrightarrow$\,(ii).  Use a Deletion Transform 
to show a Pascal-type recurrence  for $\surj(k,n)$.

\item (ii)\,$\Longrightarrow$\,(iii). Use the recurrence to write
$S^{(n)}(x)$ in terms of $S^{(n-1)}(x)$, and solve this to get a simple formula for $S^{(n)}(x)$.

\item (iii)\,$\Longrightarrow$\,(iv). Find the partial fraction expansion of $S^{(n)}(x)$,
and a formula for $\surj(k,n)$.
Compare to our formula from class using the Principle of Inclusion-Exclusion.

%\item (iv)\,$\Longrightarrow$\,(v). Find a simple asymptotic formula for $\surj(k,n)$ as $n\to\infty$ and fixed $k$.

\end{enumerate}

\end{document}


{\bf X.}  Consider the recurrence: 
$$
A_n=A_{k-1}+2 A_{k-2}\text{ for }k\geq2, \quad \text{with initial values }  A_0=A_1=1,
$$
 giving the sequence $1,1,3,5,11,21,\ldots$\,.
Analyze this recurrence similarly to the Fibonacci sequence,
starting with form (ii) and deriving forms (iii), (iv), (v), and also (i).
\\[.5em]
For (ii) $\Longrightarrow$ (iii), use the recurrence to obtain an equation involving the generating function $F(x)$, 
then  solve the equation for $f(x)$. For (iv) \& (v), expand $f(x)$ by partial fractions.
For (i), reverse the Graded Sum and Product Principles to define a combinatorial class
$\A_k$.
\bigskip

{\bf Y.} We proved the formula $\binom nk = \frac{ n^{\underline{k}} }{k!}$ 
without generating functions by using an ingenious combinatorial bijection.  
Consider the Accordion Transform which changes multisets to sets:
$M=\{t_1\leq \cdots\leq t_k\}$ with $t_i\in[n]$ corresponds to 
$S=\{s_1<\cdots<s_k\}$ with $s_i = t_i+i-1$. 
Show this is a bijection, and count the resulting sets to
derive a formula for $\multi nk$.

{\bf Z.} In lecture, we considered the class $\A=\{ (a_1,\ldots,a_k) \,\mid\, a_i\in[n] \text{ and }  a_i\neq a_j\text{ for } i\neq j\}$, sequences
of $k$ distinct elements in $[n]=\{1,\ldots,n\}$.
Then $\#A = n^{\underline{k}} \stackrel{\text{def}}{=} n(n{-}1)\cdots(n{-}k{+}1)$.
\\[.2em]
(a) Define a transformation version of this formula, namely a bijective mapping: 
$$
T\,:\,\A\ \longrightarrow\ [n]\times [n{-}1]\times\cdots\times [n{-}k{+}1].
$$
Specify $T$ precisely using set notation.
{\it Hint:} Perhaps use $\mathrm{rank}(a,A)=  \#\{b\in A\,\mid\, b\leq a\}$; i.e., the smallest
$a\in A$ is ranked 1, the second smallest 2, etc.
\\[.2em]
(b) Define the inverse  of the above transformation,
$T^{-1}(i_1,\ldots,i_k)=(a_1,\ldots,a_k)$.\\
{\it Hint:} Define $a_i$ recursively in terms of $a_1,\ldots, a_{i-1}$, using the $i^{\text{th}}$-from-the-bottom function $\min(i,S) = s_i$ for a set $S=\{s_1<s_2<s_3<\cdots\}$.
\bigskip

{\bf W. }  Prove the Graded Product Principle