\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{\End}{End}
\DeclareMathOperator{\trace}{tr}
\DeclareMathOperator{\inv}{inv}

\newcommand{\PoSetf}{\operatorname{{\mathbf {PoSet}}}_{\text{fin}}}
\newcommand{\DLatf}{\operatorname{{\mathbf {DLat}}}_{\text{fin}}}

% Version to mark problems which have been used in the cumulative list
%\newcommand{\used}{* }
% Alternate version to number problems in order on a problem set.
\newcounter{problem}
\newcommand{\used}{\addtocounter{problem}{1}\theproblem. }

\begin{document}

\begin{center}
{\bf Math 249---Spring 2024}\\
{\bf Homework problems on Lectures 1--6}
\end{center}


\medskip

\used Defining the derivative $\frac{d}{dx}F(x)$ of a formal power series
term by term in the obvious way, show that the usual sum and product
rules and the chain rule hold.  Show that Taylor's formula holds if
the coefficient ring contains $\QQ $.


\medskip

\used Assume we are working in a formal power series ring $R[[x]]$ over
a coefficient ring $R$ containing $\QQ $.  Define $\exp (x)$ and $\log
(1+x)$ by their usual Taylor series.

\smallskip

(a) Given $F(x),G(x)\in R[[x]]$ such that $F(0) = 1$, show that there
is a well-defined formal power series
\[
F(x)^{G(x)} \underset{\text{def}}{=} \exp (G(x)\log F(x)).
\]

\smallskip

(b) Show that the above definition satisfies the laws of exponents
$F(x)^{G(x)+H(x)} = F(x)^{G(x)}F(x)^{H(x)}$, $F(x)^{G(x)H(x)} =
(F(x)^{G(x)})^{H(x)}$, $F(x)^{0}=1$, $F(x)^{1} = F(x)$.

\medskip

\used Generalizing the definition in the previous problem in the obvious way
to formal series in more than one variable, show that (over a
coefficient ring containing $\QQ $) the Newton binomial theorem
\[
(1+x)^{y} = \sum _{n} \binom{y}{n} x^{n}
\]
holds as a formal power series identity.


\medskip

\used Express each of the following as a binomial coefficient: (a) the
number of monomials of degree exactly $d$ in a (commutative)
polynomial ring in $n$ variables; (b) the number of monomials of
degree $\leq d$.



\medskip

\used Show that $\angbinom{n}{k} = \sum _{j=0}^{k}\angbinom{n-1}{j}$.
Using this, evaluate $\sum _{j=0}^{k}\binom{n+j}{j}$ as a single
binomial coefficient.


\medskip

\used (a) Give two proofs of the binomial coefficient identity, called the
{\em convolution formula},
\[
\sum _{j}\binom{m}{j}\binom{n}{k-j} = \binom{m+n}{k}.
\]
One proof should use generating functions, the other should be a
direct combinatorial proof.

\smallskip

(b) Discover and prove in the same two ways an analogous identity
for multiset coefficients $\angbinom{n}{k}$.


\medskip

\used Find a closed expression for the ordinary generating function in
two variables
\[
\sum _{n,k\geq 0} \binom{n}{k}x^{n}y^{k},
\]
and use it to deduce the identity
\[
\sum _{r}\binom{r}{k}x^{r} = \frac{x^{k}}{(1-x)^{k+1}}.
\]


\medskip

\used Find a closed expression for the two-variable ordinary
generating function 
\[
\sum _{n,k\geq 0} \angbinom{n}{k}x^{n}y^{k},
\]


\medskip

\used Find closed expressions for the mixed ordinary/exponential
generating functions
\[
\sum _{k,n} S(n,k) y^{k} \frac{x^{n}}{n!}\ , \qquad \sum _{k,n} c(n,k)
y^{k} \frac{x^{n}}{n!}
\]
for Stirling numbers $S(n,k)$ and signless Stirling numbers $c(n,k)$.



\medskip

\used By expanding the right hand side in partial fractions, show directly
that the generating function for Stirling numbers
\[
\sum _{n} S(n,k) x^{n} = \frac{x^{k}}{(1-x)(1-2x)\cdots (1-k\, x)}
\]
is equivalent to the explicit formula
\[
S(n,k) = \frac{1}{k!}\sum _{j}(-1)^{k-j}\binom{k}{j}j^{n}.
\]


\medskip

\used Let $m_{d}(q)$ be the number of irreducible monic polynomials
$f(x)$ of degree $d$, over the finite field $\FF (q)$ with $q$ elements.
Note that the number of {\em all} monic polynomials of degree $d$
(irreducible or not) is just $q^{d}$.

\smallskip

(a) Use unique factorization of polynomials to prove
the generating function identity
\[
\prod _{d\geq 1}\frac{1}{(1-x^{d})^{m_{d}(q)}} = \frac{1}{1-qx}.
\]

\smallskip

(b) By taking logarithms on both sides, derive the identity
\[
\sum _{d|n} dm_{d}(q) = q^{n}
\]
for all $n$, the sum ranging over the divisors of $n$.  Equivalently,
\[
m_{d}(q) = \frac{1}{d}\sum _{m|d} \mu (d/m)q^{m},
\]
where $\mu (n)$ is the M\"obius function from number theory, i.e.,
$\mu (n) = (-1)^{k}$ if $n$ is a product of $k$ distinct primes, and
$\mu (n)=0$ if $n$ is divisible by a square.

\smallskip

(c) Use (b) to prove that the product of all monic irreducible
polynomials of degree dividing $n$ is equal to $x^{q^{n}}-x$.  [Hint:
every element of $\FF (q^{n})$ is a root of $x^{q^{n}}-x$.]

\smallskip

(d) A {\em necklace} is an equivalence class of words up to rotation.
A necklace of length $n$ is {\em primitive} if the corresponding
rotation class consists of $n$ distinct words, i.e., it is not
periodic with period $d$ a proper divisor of $n$.  (Example: $1122$ is
primitive; $1212$ is not.)  Note that every word of length $n$
consists of $n/d$ repetitions of a primitive necklace of length $d$
dividing $n$.  (Example: $1212$ and $2121$ both repeat the primitive
necklace $12 = 21$.)  Let $p_{d}(q)$ be the number of primitive
necklaces of length $d$ on an alphabet of $q$ symbols.  Prove that 
\[
\sum _{d|n} dp_{d}(q) = q^{n},
\]
and hence
\[
m_{d}(q) = p_{d}(q)
\]
when $q$ is a power of a prime.

\smallskip

(e) (For those familiar with Lie algebras.)  Let $L_{q} =
L(x_{1},\ldots,x_{q})$ be the free Lie algebra with $q$ generators.
$L_{q}$ is graded if we consider each generator to be homogeneous of
degree $1$.  Let $l_{d}(q)$ be the dimension of the homogeneous part
of degree $d$ in $L_{q}$.  In other words, $l_{d}(q)$ is the number of
linearly independent expressions that can be formed by bracketing
together $d$ of the generators $x_{i}$.  The universal enveloping
algebra of $L_{q}$ is the free tensor algebra
$T(x_{1},\ldots,x_{q})$.  Using this and the Poincar\'e-Birkhoff-Witt
theorem, derive the identity
\[
\prod _{d\geq 1}\frac{1}{(1-x^{d})^{l_{d}(q)}} = \frac{1}{1-qx}.
\]
Deduce that $l_{d}(q) = p_{d}(q)$.

\smallskip

{\it Remark:} This enumerative result suggests that $L_{q}$ should
have a basis whose elements in degree $d$ are indexed in some natural
way by primitive necklaces of length $d$.  Such a basis has been
constructed by R.~Lyndon.


\medskip

\used Prove that the $q$-multinomial coefficients satisfy the
following recurrence.  A combinatorial proof is preferred.
\begin{multline*}
\binom{n}{k_{1}, k_{2},\ldots,k_{r}}_{q} = \binom{n-1}{k_{1}-1,
k_{2},\ldots,k_{r}}_{q} + q^{k_{1}}\binom{n-1}{k_{1}, k_{2}-1,\ldots,k_{r}}_{q}
\\
{}+\cdots + q^{k_{1}+\cdots +k_{r-1}}\binom{n-1}{k_{1},
k_{2},\ldots,k_{r}-1}_{q}.
\end{multline*}


\medskip

\used Prove the following $q$-analog of the convolution formula for
binomial coefficients.  A combinatorial proof is preferred.
\[
\binom{m+n}{k}_{q} = \sum _{i+j=k} q^{(m-i)j} \binom{m}{i}_{q}
\binom{n}{j}_{q}
\]


\medskip

\used Let $\QQ(q) \langle x,y \rangle$ be the algebra of polynomials in
non-commuting variables $x,y$, over the field of rational functions
$\QQ (q)$, and let $Q_{q}[x,y] = \QQ (q)\langle x,y \rangle/J$, where
$J$ is the two-sided ideal generated by $yx-qxy$.  Thus $Q_{q}[x,y]$
is the `quantum polynomial ring' whose generators satisfy the
$q$-commutation relation $yx=qxy$.  Prove the `quantum $q$-binomial
theorem' that 
\[
(x+y)^{n} = \sum _{k}\binom{n}{k}_{q} x^{k}y^{n-k}
\]
holds as an identity in $Q_{q}[x,y]$.


\medskip

\used 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

\used 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

\used Let $k(n)$ be the number of self-conjugate partitions of $n$.  Prove
that the number of partitions of $n$ with an even number of even parts
is equal to $(p(n)+k(n))/2$.  [Stanley (2nd ed.) 1.22]


\medskip

\used From the $q$-binomial theorem
\[
\prod _{i=0}^{m-1}(1+xq^{i}) = \sum _{j=0}^{m}
\binom{m}{j}_{q}q^{\binom{j}{2}}x^{j}, 
\]
deduce
\[
\prod _{i=1}^{s}(1+x^{-1}q^{i})\prod _{i=0}^{t-1}(1+xq^{i}) = \sum
_{j=-s}^{t}\binom{s+t}{s+j}_{q} q^{\binom{j}{2}}x^{j}.
\]
By letting $s$ and $t$ go to
infinity, prove {\em Jacobi's triple product identity:}
\[
\sum _{j\in \ZZ } (-1)^{j}a^{\binom{j}{2}}x^{j} = \prod _{i\geq
0}(1-xa^{i})(1-x^{-1}a^{i+1})(1-a^{i+1})
\]


\medskip

\used 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

\used Use Durfee squares to obtain an identity analogous to part (a)
of the previous problem, but enumerating partitions with distinct
parts.  Then deduce Sylvester's identity
\[
\prod _{i\geq 1}(1-xq^{i}) = 1+\sum _{n\geq
1}(-1)^{n}x^{n}\left(q^{(3n^{2}+n)/2}\prod
_{i=1}^{n}\frac{1-xq^{i}}{1-q^{i}}+ q^{(3n^{2}-n)/2}\prod
_{i=1}^{n-1}\frac{1-xq^{i}}{1-q^{i}}\right),
\]
which generalizes Euler's pentagonal number theorem.

\medskip

\used Prove {\em Cauchy's identity:}
\[
\prod _{i\geq 0} \frac{1-axq^{i}}{1-xq^{i}} = \sum _{n\geq
0}\frac{(1-a)(1-aq)\cdots (1-aq^{n-1})}{(1-q)(1-q^{2})\cdots
(1-q^{n})}x^{n},
\]
by showing that it reduces to the $q$-binomial theorem upon setting
$a=q^{m}$ for an integer $m$ (note that you get either form of the
$q$-binomial theorem by taking $m$ positive or negative).

\medskip

\used (a) Give a direct combinatorial proof of the partition identities
\[
\prod _{i\geq 1}\frac{1}{1-xq^{i}} = \sum _{n\geq
0}\frac{x^{n}q^{n}}{(1-q)(1-q^{2})\cdots (1-q^{n})}
\]
and
\[
\prod _{i\geq 1} (1+xq^{i}) = \sum _{n\geq
0}\frac{x^{n}q^{\binom{n+1}{2}}} {(1-q)(1-q^{2})\cdots (1-q^{n})}.
\]

(b) Show that these two identities are special cases of Cauchy's
identity, above, and that they are limiting cases of the $q$-binomial
theorem.


\medskip

\used 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.

\end{document}
