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

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

\addtolength{\topmargin}{-.8in}
\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{\F}{\mathcal{F}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\tD}{\tilde{\mathcal{D}}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\Q}{\mathcal{Q}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\Flat}{\mathrm{Flat}}
\renewcommand{\S}{\mathcal S}
\renewcommand{\SS}{\mathfrak S}
\newcommand{\surj}{\mathrm{surj}}
\newcommand{\diag}{\mathrm{diag}}
\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)}


\begin{document}
\centerline{\bf Math 880 \hfill{\large\bf Homework 2}\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. 
LaTeX is encouraged, but not required.  
\\[1em]
Let $\P$ be the class of partitions 
$\lam = \{\lam_1\geq \cdots \geq \lam_\ell > 0\}$
with size $|\lam|=\lam_1+\cdots\lam_\ell=k$
and length $\ell(\lam) = \ell$, counted by $p(k)=\#\P_k$.
In terms of multiplicities, $\lam=1^{m_1}2^{m_2}\cdots$,
where $m_j=\#\{i \text{ with } \lam_i=j\}$.
The Product Principle leads to the generating function:
$$
P(x) \ =\ \sum_{k\geq 0} p(k)x^k 
\ = \ \prod_{j\geq 1} \frac{1}{1-x^j}.
$$
Let $\Q$ be the partitions into distinct parts: $\lam = (\lam_1{>} \lam_2 {>}\cdots {>} \lam_\ell {>}\,0)$, with $q(k) = \#\Q_k$.
\\[.5em]
A signed graded class $\A^\pm$ is endowed with a function $\sgn:\A\to\{\pm1\}$.
Its signed generating function is $A^\pm(x) = \sum_{k\geq 0} (\#\A_k^+ - \#\A_k^-) x^k$,
where $\A_k^+=\{a\text{ with } |a|=k \text{ and } \sgn(a) =+1\}$.
\\[.5em]
 {\sc involution priniciple:} 
Let $I:\A^\pm\to\A^\pm$ be a size-preserving, sign-reversing involution:
$I^{-1}=I$, $|I(a)| = |a|$, and $\sgn(I(a))=-\sgn(a)$
{\it except} for elements of $\F=\{a \text{ with } I(a)=a\}$.
Then the signed generating functions are equal:
$A^\pm\!(x) \ =\ F^\pm\!(x)$.
\\[1em]
{\bf 1.} Let $q_{\leq2}(k)$ be the number of partitions of $k$ 
with no part repeated three or more times, i.e.~$m_i\leq 2$:
for example $q_{\leq2}(4)=4$ counts 
$4, \ 3{+}1,\ 2{+}2,\  2{+}1{+}1$, 
but not $1{+}1{+}1{+}1 = 1^4$.
Also, let $p_{\nmid 3}(k)$ be the number of partitions of $k$
with no part divisible by 3: 
for example $p_{\nmid 3}(4)=4$ counts 
$4,\ 2{+}2,\ 2{+}1{+}1,\ 1{+}1{+}1{+}1$, but not $3{+}1$.
\\[.5em]
Prove $q_{\leq2}(k)=p_{\nmid 3}(k)$ via equality of generating functions $Q_{\leq2}(x)=P_{\nmid 3}(x)$.
\\[1em]
{\bf 2.}  {\sc euler pentagonal number theorem:} 
Let $\Q^\pm$ be the class of partitions into distinct parts with $\sgn(\lam) = (-1)^{\ell(\lam)}$.
Its signed generating function is equal to:
$$
Q^\pm(x) \ =\ \prod_{i\geq 1} (1{-}x^i)
\ =\ 1 + \sum_{\ell\geq 1} (-1)^\ell (x^{\ell(3\ell+1)/2} + x^{\ell(3\ell-1)/2}).
$$
We proved this using Franklin's involution $I$ defined in terms of 
$\min(\lam) = \lam_\ell$, and: 
$$
\diag(\lam) = \max(\{i \text{ with } \lam_j=\lam_1 - j + 1 \text{ for } j\leq i\}),
$$
the length of the top right diagonal of the tableau $\lam$.
If $\min(\lam)\leq \diag(\lam)$, 
then $I$ moves the bottom row of $\lam$
to a diagonal at the top right of $I(\lam)$.
If $\min(\lam)>\diag(\lam)$, then $I$ reverses this, moving
the upper-right consecutive diagonal to form a new bottom row.
\\[.3em]
\centerline{
\includegraphics[width=3.7in]{Franklin.png} 
}
If neither operation can be perfomed on $\lam$ within $\Q$, 
we let $I(\lam)=\lam$.
\\[.3em]
{\bf a.} Verify that $I$ is a size-preserving, sign-reversing involution staying within $\Q^\pm$.
\\[.3em]
{\bf b.} Explicitly find the two sequences of fixed elements $\lam=I(\lam)$
with $|\lam|=\frac12 \ell (3\ell{\pm}1)$, and show there are no other fixed elements.
\\[.3em]  
{\bf c.} Use the equation $P(x)\cdot Q^\pm\!(x) = 1$ to recursively compute $p(k)$ for $k\leq 20$.
%\\[.5em]
%{\bf d.} Similarly give a signed combinatorial class interpretation of 
%$(1+x)^n \frac{1}{\ (1+x)^n}=1$.
%\\
%{\it Extra Credit:} Give a sign-reversing involution to prove the above combinatorial identity.

\pagebreak

\noindent
{\bf 3.} {\sc principle of inclusion-exclusion:} For finite sets $\B_1,\ldots,\B_\ell\subset \A$, 
we have:
$$\textstyle 
\#\!\left(\A-\bigcup_{j=1}^\ell \B_j\right) \ =\
\sum_{J\subset [\ell]} (-1)^{\#\!J} \,\#\bigcap_{j\in J} \B_j.
$$
\\[-1.2em]
Re-prove this using the Involution Principle: $\#\widehat\A^+ - \#\widehat\A^- = \#\F^+ - \#\F^-$
on the signed set:
$$\textstyle
\widehat{\A}^\pm = \{(a,J) \text{ with } a\in \A, \, J\subset [\ell],\, a\in\bigcap_{j\in J}\B_j\}
\quad\text{and}\quad \sgn(a,J)=(-1)^{\#J}.
$$
\\[-1.2em]
Find a sign-reversing involution $I$ on $\widehat{\A}^\pm$ with fixed points: 
$$\textstyle
\F = \{(a,\varnothing) \text{ with } a\in \A\setminus\bigcup_{j=1}^\ell \B_j\}.
$$
\\[-1.4em]
{\sc Hint:} Let $I(a,J) = (a,J')$ for some $J'$ which is one larger or smaller than $J$.
\\[1em]
{\bf 4.} A {\it derangement} is a permutation $w:[k]\stackrel{\sim}{\rightarrow}[k]$ with no fixed points: $w(i)\neq i$ for all $i$. Let $D_k$ be number of derangements in $S_k$:
e.g.~$D_3 = 2$, counting $w=[231]$ and $[312]$, where 
we write $w= [w(1)\, w(2)\, w(3)]$.
\\[.3em]
{\bf a.} Use PIE to find a formula for $D_k$, the number of derangements in $S_k$.
\\[.3em]
{\bf b.} Use the formula to asymptotically estimate the fraction of $w\in S_k$ which are derangements.


\end{document}


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}$$

\noindent
{\bf 3.} 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)$.

\newpage

\noindent
{\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]
{\bf 4.} The class of {\it derangements} $\tD_k$ comprises all permutations 
$\pi\in\SS_k$ with $\pi(i)\neq i$ for all $i$. We saw that 
$\tD\cong \tilde{\text{\sc Set}}(\tilde{\text{\sc Cyc}}_{\geq 2}[1])$,
which gives:
$$
\tilde D(x) = 
\exp\left(\log\tfrac{1}{1-x} - x\right)
= \frac{e^{-x}}{1-x}\,, \qquad
D_k = k!(1-\tfrac{1}{1!}+\tfrac{1}{2!}-\cdots + (-1)^k \tfrac{1}{k!}).
$$
{\it Problem:} Prove the above formula for $D_k$ without generating functions,
instead using the Principle of Inclusion-Exclusion. 
For fixed $k$, start by finding a bigger set $\A$ 
containing $\tD_k$ as well as some bad sets $\B_1,\ldots,\B_k$
such that $\tD_k=\A\setminus (\B_1\cup\cdots\cup\B_k)$.
\\[1em]
{\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.
$$


\end{document}

