\documentclass[12pt]{amsart}

\usepackage[margin=1in]{geometry}
\usepackage{hyperref}

\newcommand{\cL}{\mathcal{L}}
\newcommand{\bC}{\mathbf{C}}
\newcommand{\bD}{\mathbf{D}}

\begin{document}

Math 188, Spring 2021

Homework 7

Due: May 21, 2021 11:59PM via Gradescope (late penalty waived for this assignment)

~

Solutions must be {\bf clearly} presented. Incoherent or unclear solutions will lose points. 

{\bf Reminder:} The outline for the final project is also due on May 21 via Gradescope. It must be typed, or it will receive 0 credit.

\url{http://www.math.ucsd.edu/~ssam/188/project.html}

\begin{enumerate}    
\item Let $a_n$ be the number of functions $f \colon [n] \to [n]$ such that $f \circ f = f$. Find a simple formula for the EGF $A(x) = \sum_{n \ge 0} a_n \frac{x^n}{n!}$. Hint at end.
  
\item Let $G(x)$ be the unique formal power series such that $[x^n] G(x)^{n+1} = 1$ for all $n \ge 0$. Find a simple formula for $G(x)$. Hint at end.   

\item Given $G(x)$ with $G(0) \ne 0$, define its {\bf logarithmic derivative} to be $\cL(G) = \frac{DG(x)}{G(x)}$. By HW2 \#3, we have $\cL(e^{F(x)}) = DF(x)$ and $\cL(G_1(x)G_2(x)) = \cL(G_1(x)) + \cL(G_2(x))$.
  \begin{enumerate}
  \item Let $a_n$ be the number of involutions of size $n$ and let $A(x) = \sum_{n \ge 0} a_n \frac{x^n}{n!}$. From Example 5.11, we have $A(x) = \exp(x+\frac{x^2}{2})$. Apply $\cL$ to prove for all $n \ge 0$ that (interpret $a_n=0$ if $n<0$)
    \[
      a_{n+1} = a_n + na_{n-1}.
    \]
    
  \item Let $a_n$ be the number of simple labeled graphs with $n$ vertices where every vertex has degree $2$. Use the same method as in (a), but using the formula in Example 5.12, to prove for all $n \ge 0$ that (interpret $a_n=0$ if $n<0$):
    \[
      a_{n+1} = na_n + \binom{n}{2} a_{n-2}.
    \]
  \end{enumerate}
  
\item Let $n \ge 1$. Given a labeled tree $T$ with vertices $1,\dots,n$, define $x(T) = x_1^{d_1} \cdots x_n^{d_n}$ where $d_i$ is the degree of vertex $i$, i.e., the number of edges containing $i$. Define $\bC_n = \sum_T x(T)$ where the sum is over all labeled trees $T$ with vertices $1,\dots,n$. Also define
  \[
    \bD_n = x_1 \cdots x_n (x_1+x_2 + \cdots + x_n)^{n-2}.
  \]
  \begin{enumerate}
  \item Given a polynomial $p(x_1,\dots,x_n)$, let $p^{(i)}$ be the result of plugging in $x_i=0$ into the partial derivative $\frac{\partial p}{\partial x_i}$, i.e., the coefficient of $x_i$ if you think of the other variables as constants. If $n \ge 2$, show that
    \begin{align*}
      \bC^{(n)}_n &= (x_1+x_2+\cdots+ x_{n-1}) \bC_{n-1},\\
      \bD^{(n)}_n &= (x_1+x_2+\cdots+ x_{n-1}) \bD_{n-1}.
    \end{align*}
    
  \item Assuming that $\bC_{n-1}=\bD_{n-1}$ show that $\bC_n^{(i)} = \bD_n^{(i)}$ for all $i=1,\dots,n$.

  \item Conclude that $\bC_n = \bD_n$ for all $n \ge 1$.

    [You may use without proof that every tree with at least 2 vertices has a vertex of degree 1.]            
  \end{enumerate}

  \section{Optional problems (don't turn in)}

\item $F(x) = \sum_{n \ge 0} f_n x^n$ is a formal power series that satisfies the following identity:
  \[
    F(x) = \exp\left(\frac{x}{2}(F(x) + 1) \right).
  \]
  Find a formula for $f_n$.

\item Let $n$ be a positive integer. Given a group of $n$ people, we want to divide them into nonempty committees and choose a leader for each committee, and also choose one of the committees to be in charge of all of the others. Let $h_n$ be the number of ways to do this and set $h_0 = 1$. Give a simple expression for the exponential generating function $H(x) = \sum_{n \ge 0} \frac{h_n}{n!} x^n$.

\item Let $h_n$ be the number of bijections $f \colon [n] \to [n]$ with the property that $f \circ f \circ f$ is the identity function. Give a simple expression for the exponential generating function $H(x) = \sum_{n \ge 0} \frac{h_n}{n!} x^n$.

\item Let $a_n$ be the number of set partitions of $[n]$ such that every block has at least $2$ elements. By convention, $a_0=1$. Give a simple expression for the exponential generating function
    \[
      A(x) = \sum_{n \ge 0} \frac{a_n}{n!} x^n.
    \]
  
\end{enumerate}

\section{Hints}

(1): It may be helpful to think of functions $f \colon [n] \to [n]$ as directed graphs on $[n]$ where an edge $i \to j$ means $f(i)=j$.

(2): Consider the equation $A(x) = x G(A(x))$; from the proof of Lagrange inversion, $G(x) B(x) = x$ where $B$ is the compositional inverse of $A$.

\end{document}
