\documentclass[12pt]{article}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{graphicx}

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

\addtolength{\topmargin}{-.7in}
\addtolength{\textheight}{1.5in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\textwidth}{1.0in}
\pagestyle{empty}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\bF}{\,\overline{\!\mathcal{F}}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\tD}{\tilde{\mathcal{D}}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\Flat}{\mathrm{Flat}}
\renewcommand{\S}{\mathcal S}
\renewcommand{\SS}{\mathfrak S}
\newcommand{\surj}{\mathrm{surj}}
\newcommand{\sgn}{\mathrm{sgn}}

\newcommand{\lam}{\lambda}

%\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)}

\newcommand{\stirling}[2]{\left\{\!
\genfrac{}{}{0pt}{}{#1}{#2}\!\right\}}

\newcommand{\cycle}[2]
{\left[
\genfrac{}{}{0pt}{}{#1}{#2}
\right]}

\newcommand{\form}[1]{[[#1]]}


\begin{document}
\centerline{\bf Math 880 \hfill{\large\bf Homework 3}\hfill Fall 2025}
\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. 
\\[.5em]
Recall constructions for labeled  
$\tilde\C$ with exponential generating function $\tilde C(x) = \sum_{k\geq 0}C_k\frac{x^k}{k!}$.
$$\begin{array}{l@{\ }lcl@{\ }l}
 \tilde \C =  \tilde\A * \tilde\B, &   \tilde C(x) = \tilde A(x) \tilde B(x)
&\quad&
 \tilde \C =  \tilde\A^{\text{min}}\! * \tilde\B, &  \tilde C(x) = \int\!\tilde A'(x) \tilde B(x)\,dx
\\[.2em]
 \tilde \C = \tilde{\text{\sc Seq}}_n \tilde\A, &  \tilde C(x) = \tilde A(x)^n
&&
 \tilde \C = \tilde{\text{\sc Seq}}\, \tilde\A, &  \tilde C(x) = 1/(1{-}\tilde A(x))
\\[.2em]
\tilde \C = \tilde{\text{\sc Set}}_n \tilde\A, &   \tilde C(x) = \tilde A(x)^n/n!
&&
 \tilde \C = \tilde{\text{\sc Set}}\, \tilde\A, &   \tilde C(x) = \exp\tilde A(x)
\\[.2em]
 \tilde \C = \tilde{\text{\sc Cyc}}_n \tilde\A, &  \tilde C(x) = \tilde A(x)^n/n
&&
 \tilde \C = \tilde{\text{\sc Cyc}}\, \tilde\A, &   \tilde C(x) = -\log (1{-}\tilde A(x))
\end{array}
$$
There are no labeled multisets: distinct labels prevent exact copies
within an object.
\\[1em]
{\bf 1.} The class of {\it derangements} $\tD_k$ comprises all permutations 
$w\in\SS_k$ with $w(i)\neq i$ for all $i$. 
Analyze $\tD$ using the above constructions, find the generating function $\tilde D(x)$,
and obtain a formula for $D_k$. ({\it Hint:} A permutation is a set of cycles.)
Compare this formula with the P.I.E.~formula from the previous HW.
\\[1em]
{\bf 2.} Recall the Euler number $E_k$ which counts the down-up permutations
$\pi\in \SS_k$ with
$
\pi(1)>\pi(2)<\pi(3)>\cdots
$.
For example, $E_3=2$ counts the permutations $\pi=213, 312$.
We split these into the permutations $\tilde\J$ 
with odd length $k=2\ell{+}1$, 
so that $J_{2\ell+1}=E_{2\ell+1}$ and $J_{2\ell}=0$;
and also the permutations $\tilde \K$ with even length $k=2\ell$,
so that $K_{2\ell}=E_{2\ell}$ and $K_{2\ell+1}=0$.

Deleting $\pi(j)=1$ from an odd permutation produced the recurrence:
 $$
 \tilde\J \ \cong \ \tilde\J\star[1]^{\text{min}}\star\tilde\J \,+\, [1],
 $$
 which can be solved via generating functions to give $\tilde J(x)=\tan(x)$.
\\[.5em]
{\bf a.} Use a similar method to determine $\tilde K(x)$.
\\[.5em]
{\bf b.} Check that the smallest complex singularities of 
$\tilde E(x)=\tilde J(x)+\tilde K(x)$ are $\alpha=\frac\pi2, \beta=-\frac\pi2$.
Find the residues $A, B$ such that: 
$$
\tilde E(x) \ = \ \frac{A}{1-x/\alpha}  + \frac{B}{1-x/\beta} + f(x),
$$
where $f(x)$ is analytic (non-singular) on $|x|\leq \frac32\pi$.
Hints: In the complex plane $\cos(x) = \frac12(e^{ix}+e^{-ix})$. 
The residue of $\tilde E(x)$ at $x=\alpha$ is computed by $A=\lim_{x\to\alpha} \tilde E(x) (1-x/\alpha)$.

By Flajolet-Sedgewick Thm IV.10 p.~258, this implies the asymptotic expansion
$$
\frac{E_k}{k!} \sim A\alpha^{-k}+B\beta^{-k}.
$$
Use Stirling's approximation $k!\sim \sqrt{2 \pi k}\,(k/e)^k$
to get a simple asymptotic for $E_k$.  Look up $E_{99}$ and $E_{100}$
(in a standard Taylor series) to see how accurate this is in percentage terms.
\\[1em]

\newpage

\noindent
{\bf 3.}  {\it Tree Structures.}  A {\it plane tree} is a combinatorial graph with
$k$ unlabeled vertices: an ancestor (root vertex) at the top, and below each vertex 
is a list of children in age order. Let $\B_k$ be the class of such trees, 
$B_k$ the counting number. E.g.~$B_4=5$:

\centerline{
\includegraphics[width=2in]{HW-03.png} 
}
\vspace{0in}

\noindent
The difference between the 3rd and 4th trees is whether 
the ancestor's older or younger child has a child.
Set $\B_0=\{\}$. 
Deleting the root gives recursively:
$$
\B \ \cong\  \{\bullet\}\times \text{\sc Seq}(\B) ,
$$
where $\{\bullet\}$ denotes the class with a single element of size 1, and 
$$
\text{\sc Seq}(\B) \ =\ \{\varnothing\} \ \sqcup\ \B \ \sqcup\  \B{\times}\B\ \sqcup\  \cdots
$$ 
denotes all lists of elements in $\B$.
By the Graded Product Principle:
$$
B(x) \ =\ x(1+B(x)+B(x)^2+\cdots)
\ =\ \frac{x}{1-B(x)}.
$$
Solving gives $B(x) = \frac12(1-\sqrt{1-4x})$;
comparing this to the Catalan generating function implies $B_k = C_{k-1}=\frac{1}{k} \binom{2k-2}{k-1}$. 

The Catalan formula can be obtained easily by Lagrange inversion: 
if a power series $f(x)$ has inverse function $g(x)$, so that $f(g(x))=x$, then 
the $x^k$ coefficient of $g(x)=f^{-1}(x)$ is given by:
$\frac1k [x^{-1}]\frac 1{f(x)^k}$.
Here $B(x)(1{-}B(x)) = x$, so $f(x) = x(1{-}x)$.
%
%A more general technique is to write: 
%$$
%F(B(x)) \ = \ B(x)(1-B(x)) \ = \ x, 
%$$ 
%i.e.~$B(x)$ is the inverse function of $F(x)=x(1{-}x)$. 
%By the Lagrange Inversion Formula:
%$$
%B_k \ = \  \frac{1}{k}[x^{-1}] \frac1{\, F(x)^k} 
 %\ = \  \frac{1}{k}[x^{k-1}]\frac{1}{(1-x)^k} 
 % \ = \  \frac{1}{k} \multi{k}{k-1} \ =\ \frac{1}{k} \binom{2k-2}{k-1} 
%\,=\, C_{k-1}.
%$$
\\[.5em]
{\sc Problem:} Use the above techniques to count the following types of rooted trees:
\\[.5em]
{\bf a.} Binary plane trees: $k$ unlabeled vertices, no children or two ordered children.
\\[.5em]
{\bf b.} Labeled plane trees: $k$ {\it labeled} vertices, any number of ordered children.
\\[.5em]
{\bf c.}  Increasing trees: $k$ labeled vertices, any number of {\it unordered} children, and
each child must have a larger label than its parent (so the root must be 1). For example, 
$k=2$ gives two trees: $1{-}2{-}3$ and $1{-}\{2,3\}$.
{\it Hint:} Use the directed labeled product $\A^{\text{min}}*\B$.  \ 
{\it Extra Credit:} Bijectively prove the simple formula that results.
\\[.3em]
{\bf d.} Ternary trees: $k$ unlabeled vertices with the root at top,
and each vertex having zero or three ordered children. 
Hint: Any ternary tree has $k=3j+1$ vertices.

\newpage

\noindent
 {\bf 4.}  {\it Formal power series and connected graphs.}
We define the ring $\CC\form x$ as the set of all infinite sequences of complex numbers $(a_0,a_1,a_2,\ldots)$, which we write in the notation of power series $A(x) = a_0+a_1 x+ a_2x^2+\cdots$, even when the series does not converge for any $x\neq 0$. 
Addition and multiplication are identical to the corresponding operations on power series:
$(\sum_i a_i x^j)(\sum_j b_j x^j) = \sum_k c_k x^k$ with
$c_k=\sum_{i+j=k} a_ib_j$; the additive identity is $0 = 0 + 0x + 0x^2+\cdots$ and the multiplicative identity $1 = 1+0x+0x^2+\cdots$. 

The ring of complex analytic functions near $x=0$ embeds as a subring of $\CC\form x$, by mapping a function to its (convergent) Taylor series. However, $\CC\form x$ includes elements like the (divergent) generating function of all labeled graphs, $\tilde G(x)=\sum_{k\geq 0} 2^{\binom k2}\frac{x^k}{k!}$.  
Any formula which holds for analytic functions is guaranteed to hold 
for all series in $\CC\form x$, provided it involves only finitely many terms in
the coefficient of each $x^k$.  For example, multiplication of power series 
is associative because the multiplication of analytic functions is so.
\\[.5em]
{\bf a.} For a list of formal series $A^{(n)}(x)=\sum_k a_k^{(n)}x^k$, define the {\it formal limit} 
\smash{$\lim\limits_{n\to\infty} A^{(n)}(x) = A(x)$} to mean: for each $k$, there is some $n(k)$ such that \smash{$a_{k}^{(n)}=a_k$} for all $n\geq n(k)$\,;
i.e., the $k ^{\text{th}}$ coefficient stabilizes for large enough $n$.
(Also called {\it convergence in the $x$-adic topology}.)

For $A(x),B(x)\in\CC\form x$, we define the the composite series as:
$$
A(B(x)) \ =\ \lim_{n\to\infty} a_0 + a_1 B(x) + a_2 B(x)^2 +\cdots + a_n B(x)^n+\cdots.
$$
{\sc problem:} Show that this limit formally converges if and only if $b_0=0$ or $A(x)$ is a polynomial (of finite degree).
\\[.5em]
{\bf b.} Since a graph is a set of connected subgraphs,
the Exponential Formula implies $\tilde G(x) = \exp\,\tilde C(x)$, where
$\tilde C(x)$ is the exponential generating function of connected graphs on vertices labeled $\{1,\ldots,k\}$. 
Using the fact that an analytic inverse function is also a formal inverse, this implies:
$$
 \tilde{C}(x) \ =\ \sum_{k\geq 1} c_k\frac{x^k}{k!} \ =\ 
\log\, \tilde{G}(x)\ =\ \log\!\left(1+\sum_{k\geq 1}2^{\binom k2} \frac{x^k}{k!}\right)\!,
$$
where the outside function of the composition is the series $\log(1+x) = x-\frac{x^2}{2}+\frac{x^3}{3}-\cdots$. 
(I use small $c_k$ to avoid confusion with Catalan numbers.)

Find a way to evaluate this series in Wolfram Alpha or Mathematica, at least far enough
to compute $c_k$ for $k=4$.
Verify the result by directly enumerating the connected graphs on 4 vertices, 
which can have 3,4,5, or 6 edges: count labeled graphs per unlabeled graph.
 \\[.5em]
 {\bf c.}  Use the {\it Dlog Method} to find a recurrence for $C_k$.
 That is, given $e^{\tilde{C}(x)} = \tilde{G}(x)$,
 perform logarithmic differentiation $\frac{d}{dx}\log$ to both sides, 
 clear denominators,  and equate coefficients on the two sides.
 Finally, solve for $c_{k+1}$.


%
 %  {\it Ans:} $C_k = 2^{\binom k2}-\sum_{i=1}^{k-1}\binom{k-1}{i-1}2^{\binom{k-i}2}C_i$, like Bell numbers.  Bijection: Consider $k$-vertex disconn graphs with  $i$-vertex component of 1, choose any graph on $k{-}i$.

\end{document}

\bigskip

\noindent
{\bf 1.}  Show that the number $e_{2k}$ of permutations in $\mathfrak S_{2k}$ which have only even-length cycles is $(1\cdot 3\cdot 5\cdots (2k{-}1))^2$. For example, $e_4=(1\cdot 3)^2=9$
counts the permutations: 
$$(1234),(1243),(1324),(1342),(1423),(1432),(12)(34),(13)(24),(14)(23).$$
 {\it Hint:} The even part of a function $f(x)$ is $\frac12(f(x)+f(-x))$.        \\
{\it Extra Credit:} Give a bijective transformation proof of this formula.
\\[1em]
 {\bf 5.}  From considering permutations as sets of cycles, 
we computed the bivariate generating function:
$$
\tilde S(x,y) \ =\  \sum_{k,n\geq 0} \cycle kn y^n \frac{x^k}{k!}
\ =\  \exp\!\left( y\log\tfrac{1}{1-x}\right) \ =\  \frac{1}{(1-x)^y}\,,
$$
as well as the one-variable 
$
S_k(y) \ =\ \sum_{n=1}^k \cycle kn y^n \ =\ y^{\overline{k}}\ =\ y(y{+}1)\cdots (y{+}k{-}1)
$
and 
$
S^{(n)}(x) \ =\ \sum_{k\geq 0} \cycle kn y^n \ =\ (\log\!\frac 1{1-x})^n$.

Consider the average or expected number of cycles in a permutation $w\in S_k$:
$$
a_k \,=\, %\mathbb{E}(\text{cyc}) \,=\, 
\frac{1}{k!} \sum_{w\in S_k}  \text{cyc}(w)
\,=\,\frac{1}{k!}\,\sum_{n=1}^k \cycle kn n.
$$
Show that the generating function of $a_k$ is a partial derivative of $\tilde S(x,y)$:
$$
A(x) \,=\, \sum_{k\geq 0} a_k x^k \,=\,  \left[\frac{\partial}{\partial y} \tilde S(x,y)\,\right]_{y=1}.
$$
(This is a general fact about bivariate generating functions.)

Compute $A(x)$, and  find a simple asymptotic approximation $a_k\sim f(k)$:
What is the approximate number of cycles expected for a permutation $w\in S_k$?
Hint: Harmonic series.
\\[1em]

\end{document}


{\bf 5.} A labeled signed graded class 
is split into positive and negative elements 
$\tilde \A^\pm_k=\tilde A_k^+\cup \tilde \A_k^-$,
and has the signed generating function:
$$
\tilde A^{\pm}(x) 
\ =\  \sum_{k\geq 0} (A_k^+{-}A_k^-)\frac{x^k}{k!}.
$$
{\bf a.} The  {\it Labeled Graded Product Principle} states that a 
labeled Cartesian product $\tilde\A\star\tilde\B$
has generating function $\tilde A(x)\tilde B(x)$.
\\[.5em]
 {\it Problem:} Prove that this also holds for the Cartesian product of 
{\it signed} labeled graded classes 
(with an appropriate definition of $\sgn$).
\\[1em]
{\bf b.} The  {\it Involution Priniciple} assumes a bijection 
$I:\tilde\A_k^\pm\to\tilde\A_k^\pm$ with $I^{-1}=I$
which reverses sign, $\mathrm{sgn}(I(a))=-\mathrm{sgn}(a)$,
except on the fixed-point set $\tilde\F_k^\pm=\{a\in \tilde\A_k^\pm\mid I(a)=a\}$.
In the non-fixed part of $\tilde \A^\pm_k$, the involution
 pairs positive and negative elements, leaving
 only the fixed points unpaired; 
 thus the we get the equality of signed generating functions:
 $$
 \tilde F^\pm(x)=\tilde A^\pm(x).
 $$
 {\it Problem:} Prove the equation:
 $$
\tilde D(x) \ = \ 
\frac{1}{1-x}\cdot e^{-x}
$$
by interpreting the right side as the product of signed exponential generating functions for two simple signed labeled graded classes.
Then find an involution whose fixed points (all positive) are in bijection with derangements:
$$
\tilde\F^{\pm}\ =\ \tilde\F^{+} \ \cong\ \tD_k.
$$

*************************************************************************************************

% \pagebreak

\addtolength{\topmargin}{-.5in}

\noindent
{\bf 2.} {\it Burnside Lemma:} For group $G$ acting on set $\F$,
the orbit set $\bF=\F/G=\{Gf\mid f\in \F\}$ is counted by
the average number of fixed points $\F^g=\{f\in \F\,|\, gf{\,=\,}f\}$: 
$$
\#\bar\F \ =\ \frac{1}{\#G}\sum_{g\in G}
\#\F^g\,.
$$
%\\[-.5em]
%To prove this, note that the size of each orbit is $\#Gf=\#G/\#\mathrm{Stab}(f)$,
% where $\mathrm{Stab}(f)=\{g\in G\mid gf = f\}$.
%The set $\S=\{(g,f)\in G\times \F\mid gf=f\}$ can
%be counted as: $\#\S= \sum_{f\in \F} \#\mathrm{Stab}(f)=\sum_{g\in G} \#\F^g$.
%Thus:
%$$
%\#\bar\F \ =\ \sum_{f\in\F}\frac{1}{(\#Gf)} 
%\ = \ \sum_{f\in \F} \frac{\#\mathrm{Stab}(f)}{\#G\ } 
%\ =\ \frac{\#\S}{\#G}
%\ =\ \frac{1}{\#G}\sum_{g\in G} \#\F^g\,.
%$$
If $\F$ is graded and $G$ acts on each $\F_k$,
we get the generating function formula:
$$
\bar F(x) \ = \ 
\frac{1}{\#G}\sum_{g\in G} F^g(x).
$$
{\bf a.} Define the {\it Euler phi-function} $\phi(k)=\#\{j\leq k \mid \gcd(j,k)=1\}$,
the number of integers in $[k]$ which are relatively prime to $k$. For
example, $\phi(p)=p{-}1$ for $p$ prime.
Use Inclusion-Exclusion to prove that if $k$ has prime factorization $k=p_1^{\ell_1} p_2^{\ell_2}\cdots$, then $\phi(k) =\prod_{i}\, p_i^{\ell_i-1} (p_i{-}1)$.
\\[.5em]
{\bf b.} For a group of permutations $G\subset S_k$, 
define the {\it cycle index polynomial}:
$$
Z_G(z_1,\ldots,z_k)\ =\ \sum\nolimits_{g\in G} z_1^{c_1(g)}\cdots z_k^{c_k(g)},
$$
where $c_i(g)=\#$ $i$-cycles of $g$.  For example, $G=S_3$ has
 $Z_G = z_1^3 + 3z_1 z_2 + 2z_3$.
 
Determine the cycle index $Z_G(z_1,\ldots, z_k)$ for $G=C_k$, the cyclic group generated by
$(12\cdots k)\in S_k$.  The answer will involve the phi-function.
\\[.5em]
{\bf c.} Let $\F= \{f:[k]\rightarrow\A\}\cong \A^k$ be functions
from $[k]$ to graded class $\A$, with $|f| = \sum_{i=1}^k |f(i)|$,
and let $G\subset \mathfrak{S}_k$ permute $[k]$, inducing an action on $\F$.
The fixed-point set $\F^g$ consists of 
$f: \{\text{cycles of $g$}\}\to\A$, functions
constant on each cycle of~$g$. 
Use graded counting principles to compute the generating functions of $\F^g$ and $\bF$:
$$
F^g(x)=A(x)^{c_1(g)} A(x^2)^{c_2(g)}\cdots A(x^k)^{c_k(g)},
$$
$$
\bar F(x)=\tfrac{1}{\#G}Z_G(A(x),A(x^2),\ldots, A(x^k)).
$$
{\bf d.} For a graded unlabeled class $\A$, 
consider the class $\bF=\text{\sc Cyc}_k\,\A$ consisting
of all cyclic arrangements of $k$ elements of $\A$, 
up to rotation symmetry.
Use the previous problems to find the generating function $\bar F(x)$ in terms of $A(x)$. 
%$\bar F(x)\ =\ \frac1k \sum_{d|k} \phi(d) A(x^d)^{k/d}$}
%
%
\\[1em]

****************************************************************
