\documentclass[12pt]{article}
\usepackage{amssymb, amsmath}
\tolerance 10000
\headheight 0in
\headsep 0in
\evensidemargin 0in
\oddsidemargin \evensidemargin
\textwidth 6.5in
\topmargin .25in
\textheight 8.7in

\newcommand{\CC}{{\mathbb C}}
\newcommand{\QQ}{{\mathbb Q}}
\newcommand{\RR}{{\mathbb R}}
\newcommand{\ZZ}{{\mathbb Z}}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\FF}{{\mathbb F}}

\newcommand{\Zerobold}{{\boldsymbol 0}}
\newcommand{\Onebold}{{\boldsymbol 1}}
\newcommand{\xbold}{{\boldsymbol x}}

\newcommand{\mfrak}{{\mathfrak m}}

\newcommand{\Acal}{{\mathcal A}}
\newcommand{\Ncal}{{\mathcal N}}
\newcommand{\Pcal}{{\mathcal P}}
\newcommand{\Qcal}{{\mathcal Q}}

\newcommand{\sqbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}
\newcommand{\angbinom}[2]{\genfrac{\langle}{\rangle}{0pt}{}{#1}{#2}}

\newcommand{\qddx}{(d/dx)_{q}}

\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\maj}{maj}
\DeclareMathOperator{\ev}{ev}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\trace}{tr}
\DeclareMathOperator{\inv}{inv}

\begin{document}

\begin{center}
{\bf Math 249 Fall 2016---Problem Set 2}
\end{center}

\bigskip

1.  Prove that the number of partitions of $n$ with no
parts divisible by $d$ is equal to the number of partitions of $n$
with no part repeated $d$ or more times, for all $n$ and $d$.

\medskip

2.  Let $p_{+}(n)$ be the the number of partitions of $n$ with an even
number of parts and $p_{-}(n)$ the number with an odd number of parts.
Let $p_{DO}(n)$ be the number of partitions of $n$ with distinct odd
parts, and let $k(n)$ be the number of partitions $\lambda $ of $n$ 
such that $\lambda =\lambda ^{*}$.  Prove that
\[
k(n) = p_{DO}(n) = (-1)^{n}(p_{+}(n)-p_{-}(n)).
\]
Hint: if $\lambda =\lambda ^{*}$, dissect the diagram of $\lambda $
into `hooks' whose sizes are odd and distinct.

\medskip

3.  The following two identities are due to Gauss:
\begin{align*}
\sum _{n\in \ZZ }(-1)^{n}q^{n^{2}}	& = \prod _{i\geq
1}\frac{1-q^{i}}{1+q^{i}};\\  
\sum _{n\geq 0}q^{\binom{n+1}{2}}	& = \prod _{i\geq
1}\frac{1-q^{2i}}{1-q^{2i-1}}.
\end{align*}

(a) Interpret them combinatorially as partition identities.

\smallskip

(b) Prove them, either combinatorially (not so easy) or using Jacobi's
triple product identity.

\medskip

4. The {\em Durfee square} of a partition $\lambda $ is the largest
$k\times k$ square that fits inside its Young diagram.  Use Durfee
squares to prove the following identities [Stanley, 2nd Ed.,
Proposition 1.8.6(b) and Ex.\ 1.76]:

\smallskip

(a)
\[
\prod _{i\geq 1} \frac{1}{1-t x^{i}} = \sum _{k\geq 0}\frac{t^{k}
x^{k^{2}}}{(1-x)\cdots (1-x^{k})\, (1-tx)\cdots (1-tx^{k})}
\]

\smallskip

(b) 
\[
\prod _{i\geq 1} {1+t x^{2i-1}} = \sum _{k\geq 0}\frac{t^{k}
x^{k^{2}}}{(1-x^{2})\cdots (1-x^{2k})}
\]

\medskip

5.  (a) Use Durfee squares to obtain an identity analogous to part (a) of the
previous problem, but enumerating partitions with distinct parts.

\smallskip

(b) Deduce {\it Sylvester's identity}
\[
\prod _{i\geq 1} (1-t q^{i}) = 1 + \sum _{n\geq 1} (-1)^{n} t^{n}
\left(q^{(3n^{2}+n)/2} \prod _{i=1}^{n} \frac{1 - t q^{i}}{1 - q^{i}}
+ q^{(3n^{2}-n)/2} \prod _{i=1}^{n-1} \frac{1 - t q^{i}}{1 -
q^{i}}\right),
\]
a generalization of Euler's pentagonal number theorem.

\medskip

6.  Show that the Stirling numbers of the second kind $S(n,k)$ have a
$q$-analog $S_{q}(n,k)$ characterized by any of the following
properties, where $[k]_{q} = (1-q^{k})/(1-q) = 1+q+\cdots +q^{k-1}$ is
the $q$ analog of $k$.

\smallskip

(a)  They satisfy the recurrence
\[
S_{q}(n,k) = [k]_{q}S_{q}(n-1,k) + q^{k-1}S_{q}(n-1,k-1),
\]
with inital condition $S_{q}(0,n) = S_{q}(n,0) = \delta _{0,n}$.

\smallskip

(b) They satisfy the following $q$-analog of the classical formula
$x^{n} = \sum _{k}S(n,k)(x)_{k}$:
\[
[r]_{q}^{n} = \sum _{k}S_{q}(n,k) [r]_{q}[r-1]_{q}\cdots [r-k+1]_{q}
\]

\smallskip

(c) For each $k$, they are given by the ordinary generating function
\[
\sum _{n}S_{q}(n,k)x^{n} =
\frac{q^{\binom{k}{2}}x^{k}}{(1-x)(1-[2]_{q}x)\cdots (1-[k]_{q}x)}.
\]

\smallskip

(d) Given a partition $\pi =\{B_{1},\ldots,B_{k} \} $ of $[n]$, with
the blocks numbered so that $\min (B_{i})<\min (B_{j})$ for $i<j$,
define $\nu (\pi ) = \sum _{i}(i-1)|B_{i}|$.  Then $S_{q}(n,k) = \sum
_{\pi }q^{\nu (\pi )}$, where the sum is over partitions of $[n]$ into
$k$ blocks.

\medskip

7.  One way to define a $q$-analog of the Eulerian polynomial
$A_{n}(x)$ is
\[
A_{n}(x,q) = \sum _{\sigma \in S_{n}}x^{d (\sigma )+1}q^{\maj (\sigma
)}.
\]

\smallskip

(a) Show that with this definition we have
\[
\sum _{r} [r]_{q}^{n} x^{r} = \frac{A_{n}(x,q)}{(1-x)(1- qx)\cdots
(1-q^{n}x)}
\]

\smallskip

(b) Deduce the formula
\[
A_{n}(x,q) = \sum _{k}[k]_{q}! S_{q}(n,k) x^{k} \prod _{i = k+1}^{n}(1-xq^{i}),
\]
where $S_{q}(n,k)$ are the $q$-analogs of Stirling numbers defined in
the previous problem.

\medskip

8.  Define the descent set of a word $w\in \NN ^{n}$ to be $D(w) =
\{i\in [n-1]: w(i)>w(i+1) \}$, just as one does for permutations.
Similarly, define $\maj (w) = \sum _{d\in D(w)}d$.

\smallskip

(a) Show that if $w\in [r]^{n}$ and $w(n)=s$, then $w' = (1\;2\;\cdots
\;r)^{r-s}\circ w$ has $\maj (w') = \maj(w)-(k_{s+1}+\cdots +k_{r})$,
where $k_{i}$ is the number of occurences of $i$ in the word $w$.

\smallskip

(b) Use (a) and the recurrence for $q$-multinomial coefficients in
Problem Set 1, Problem 11 to prove that
\[
\sum _{w\in S_{n}\cdot (1^{k_{1}},\, 2^{k_{2}},\, \ldots,\,
r^{k_{r}})} t^{\maj (w)} = \sum _{w\in S_{n}\cdot (1^{k_{1}},\,
2^{k_{2}},\, \ldots,\, r^{k_{r}})} t^{\inv (w)},
\]
for all $k_{1}+\cdots +k_{r} = n$.

\smallskip

(c) Use (b) to prove that for all $D\subseteq [n-1]$,
\[
\sum _{\substack{\pi \in S_{n}\\ D(\pi ^{-1})=D}} t^{\maj (\pi )} =
\sum _{\substack{\pi \in S_{n}\\ D(\pi ^{-1})=D}} t^{\inv (\pi )},
\]
that is, $\inv $ and $\maj $ are equidistributed on inverse descent
classes.

\smallskip

(d) Deduce that 
\[
\sum _{\pi \in S_{n}} q^{\inv (\pi )} t^{\maj (\pi )} = 
\sum _{\pi \in S_{n}} q^{\maj (\pi ^{-1})} t^{\maj (\pi )}.
\]
This gives a different proof than the one we did in class that the
sum on the left-hand side is symmetric in $q$ and $t$.

\smallskip

Remark: part (c) implies that $\sum _{\pi \in S_{n}}x^{d(\pi
)+1}q^{\maj (\pi ^{-1})} = \sum _{\pi \in S_{n}}x^{d(\pi )+1}q^{\inv
(\pi )}$, which suggests that the common value of these two
expressions might be a `better' $q$-analog of $A_{n}(x)$ than the one
Problem 7.  However, I don't know of nice identities for this
alternative $q$-Eulerian polynomial like those in Problem 7.

\medskip

9.  A {\em distribution} is a function together with a linear ordering
on the preimage of each element of the codomain.  Use exponential
generating functions to obtain the formula
\[
(n)_{k}(n-1)_{n-k}.
\]
for the number of surjective distributions from a set of $n$ labelled
objects to a set of $k$ labelled places.

\medskip

10.  An {\em at most binary tree} is an unordered rooted tree in which
each node has at most two children.  

\smallskip

(a) Find the exponential generating function for the number of
at most binary trees on $n$ labelled nodes.

\smallskip

(b) Find the ordinary generating function for the number of
at most binary trees on $n$ unlabelled nodes.

\medskip

In the next three problems we use the `double factorial' notation 
\[
n!!  = (2n-1)(2n-3)\cdots 3\cdot 1.
\]

\medskip

11.  Use the exponential generating function for the species of
perfect matchings to show that the number of perfect matchings on a
set of size $2n$ is $n!!$ (as seen by a direct counting argument in
Problem Set 1, Problem 15(a))

\medskip

12.  Let $e_{2n}$ be the number of permutations $w\in S_{2n}$ such that
every cycle of $w$ has even length.

\smallskip

(a) Find the exponential generating function $\sum
_{n}e_{2n}x^{2n}/(2n)!$, and deduce that $e_{2n} = (n!!)^{2}$.

\smallskip

(b) It follows that if $S$ is a set of size $2n$, the number of
permutations of $S$ with only even cycles is equal to the number of
pairs of perfect matchings on $S$.  Construct a direct bijection
between the two.  You will probably need to fix $S$ to be
$\{1,2,\ldots,2n \}$ and use the numerical values of its elements to
make some auxiliary choices.

\smallskip

(c) Show that the species of permutations with even-length cycles and
the species of pairs of perfect matchings are not equivalent.  This
can be understood as explaining the need for auxiliary choices in part
(b).

\medskip

13.  Find the exponential generating function $\sum
_{n}r_{n}x^{n}/n!$, where $r_{n}$ is the number of permutations of odd
order of an $n$ element set.  Deduce that $r_{2n} = (n!!)^{2}$ and
$r_{2n+1} = (2n+1)(n!!)^{2}$.

\medskip

14.  Let $g_{+}(n)$, $g_{-}(n)$ denote the number of connected simple
graphs on the vertex set $[n]$ with an even or an odd number of edges,
respectively.  Prove that $g_{+}(n)-g_{-}(n) = (-1)^{n}(n-1)!$.

\medskip

15.  As part of the computer demonstration in class, we counted
unrooted trees by counting connected graphs with $n$ vertices and $e$
edges, then picking out the terms with $e=n-1$.  In this problem, we
outline a different method of counting unrooted trees.

\smallskip

(a) The {\em diameter} $d$ of a tree $T$ is the maximum length of a
path in $T$ (a path of length $n$ has $n$ edges and $n+1$ vertices).
Prove that if $d$ is even then all paths of length $d$ have the same
middle vertex, called the {\em center} of $T$, and if $d$ is odd, then
all paths of length $d$ have the same middle edge, called the {\em
bicenter} of $T$.

\smallskip

(b) Show that if $d$ is even, the species of labelled unrooted trees
of diameter $d$ is equivalent to the species of labelled rooted trees
of height $d/2$ with the property that at least two children of the
root are roots of subtrees of height $d/2-1$.

\smallskip

(c) Show that if $d$ is odd, the species of labelled unrooted trees of
diameter $d$ is equivalent to the species of unordered pairs of
disjoint rooted trees of height $(d-1)/2$.

\smallskip

(d) Let $T_{h}$ be the species of labelled rooted trees of height $h$,
and let $T_{\leq h} = T_{0}+\cdots +T_{h}$.  Show that these are given
by the recurrence
\[
\begin{aligned}
T_{0} & = X\\
T_{h} & = X ((E-1)\circ T_{h-1}) (E\circ T_{\leq h-2})\quad \text{for
$h>0$.}
\end{aligned}
\]

\smallskip

(e) Use (a), (b) and (c) to express the species $U_{d}$ of labelled
unrooted trees of diameter $d$ in terms the species $T_{h}$.

\smallskip

(f) Use (d) and (e) to calculate the number of labelled unrooted trees
of diameter $d$ on $n$ vertices, for $n\leq 5$ and all $d$.  Check
that your answers summed over $d$ agree with the known formula
$n^{n-2}$.

\smallskip

(g) Use (d) and (e) to calculate the number of unlabelled unrooted
trees of diameter $d$ on $n$ vertices, for $n\leq 5$ and all $d$.
Check your answers by listing the trees.

\medskip

16.  (a) Find an explicit formula for the cycle index $Z_{I}$ of the
species of involutions, $I(S) = \{\sigma \in \mathfrak{S}_{S}: \sigma
^{2} = 1 \}$.

\smallskip

(b) Evaluate $Z_{I}[x]$ and verify that it agrees with the obvious
ordinary generating function counting involutions up to conjugacy.

\medskip

17.  (a) From Cayley's tree generating function derive the identity
\[
\sum _{F}\prod _{i=1}^{n} x_{i}^{c_{F}(i)} =
\binom{n-1}{k-1}(x_{1}+\cdots x_{n})^{n-k},
\]
where the sum is over rooted forests $F$ with $k$ components on vertices
$\{1,\ldots,n \}$, and $c_{F}(i)$ denotes the number of children of
vertex $i$ in $F$.

\smallskip

(b) Deduce the identity
\[
\sum _{F}\prod _{i=1}^{n} h_{c_{F}(i)} = \binom{n-1}{k-1}\langle
\frac{x^{n-k}}{(n-k)!} \rangle H(x)^{n},
\]
where $H(x) = \sum _{m}h_{m}x^{m}/m!$ is a generic formal power series
written in exponential form and $\langle \cdot \rangle$ denotes taking
a coefficient.

\smallskip

(c) Let $H$ be the `generic species' with exponential generating
function $H(x)$, that is, the trivial species, but enumerated by
assigning weight $h_{n}$ to the one structure on any set with $n$
elements.  Let $F(x)$ be the solution of the formal functional
equation
\[
F(x) = x\, H(F(x))
\]
(that is, assuming $h_{0}$ invertible, the functional composition
inverse of $x/H(x)$).  Using (b) and the species interpretation of
$F(x)$, obtain the generalized Lagrange inversion formula
\[
\langle \frac{x^{n}}{n!} \rangle F(x)^{k}/k! = \binom{n-1}{k-1} \langle
\frac{x^{n-k}}{(n-k)!} \rangle H(x)^{n},
\]
or equivalently,
\[
\langle x^{n} \rangle F(x)^{k} = \frac{k}{n} \langle x^{n-k} \rangle
H(x)^{n}
\]
(we did the case $k=1$ in class).


\medskip

18.  Prove that the number of ordered rooted trees with $n+1$ vertices and
$j$ leaves is equal to
\[
\frac{1}{n+1} \binom{n+1}{j}\binom{n-1}{n-j}.
\]

\medskip

19.  The product $G\times H$ of two simple graphs (graphs without
loops or multiple edges) is defined to be the graph on vertex set
$V(G)\times V(H)$ with edges $\{(v,w),(v',w') \}$ for $v=v'$ and
$\{w,w'\}\in E(H)$ or $w=w'$ and $\{v,v' \}\in E(G)$.  The adjacency
matrix $A_{G}$ of a graph $G$ on $n$ vertices is the $n\times n$
matrix with rows and columns labelled by the vertices, and entries
$(A_{G})_{v,w} = 1$ if $\{v,w \}\in E(G)$, zero otherwise.  Let
$D_{G}$ be the diagonal matrix whose $(v,v)$ entry is the degree of
$v$.

\smallskip

(a) Let $f_{G}(r)$ be the number of rooted spanning forests of $G$
with $r$ roots, and let $F_{G}(z) = \sum _{r} f_{G}(r)z^{r}$ be the
corresponding generating function.  Show that $F_{G}(z) = \prod
_{i}(z+\alpha _{i})$, where the $\alpha _{i}$'s are the eigenvalues of
$D_{G}-A_{G}$.

\smallskip

(b) Show that $F_{G\times H}(z) = \prod _{i,j}(z+\alpha _{i}+\beta
_{j})$, where $F_{G}(z) = \prod _{i}(z+\alpha _{i})$ and $F_{H}(z) =
\prod _{j}(z+\beta _{j})$.  In particular, the numbers $f_{G}(r)$ and
$f_{H}(r)$ for all $r$ determine the corresponding numbers $f_{G\times
H}(r)$.

\smallskip

(c) Show that if $Q_{n}$ is the graph formed by the vertices and edges
of the $n$-cube, that is, the product of $n$ copies of the complete
graph on $2$ vertices, then
\[
F_{Q_{n}}(z) = \prod _{k=0}^{n}(z+2k)^{\binom{n}{k}}.
\]
This generalizes Stanley, Exercise 5.6.10, which follows by taking the
coefficient of $z$.

\medskip

20.  Let $f_{m}(r)$ be the number of rooted spanning forests with $r$
roots in the graph $C_{m}$, a cycle on $m$ vertices ($m>1$).  Prove
that
\[
F_{m}(z) \underset{\text{def}}{=} \sum _{r}f_{m}(r)z^{r} =
\prod_{j=0}^{m-1} (z+2-2\cos (2\pi j/m)) =
\sum_{r=1}^{m}\frac{m}{r}\binom{m+r-1}{2r-1}z^{r}.
\]


\end{document}
