A partition of a positive integer \(n\) is a sequence
\(\lambda=\left(\lambda_{1}, \ldots, \lambda_{r}\right)\) of positive integers
such that \(\lambda_{1} \geq \cdots \geq \lambda_{r}\) and
\(n=\lambda_{1}+\cdots+\lambda_{r} ; r\) is the length of the partition. For
example, if \(F\) is a field and \(f \in F[x]\) of degree \(n\), then the
factorization pattern of \(f\), with the degrees of the factors in descending
order, is a partition of \(n\).
If \(\lambda=\left(\lambda_{1}, \ldots, \lambda_{r}\right)\) and
\(\mu=\left(\mu_{1}, \ldots, \mu_{s}\right)\) are two partitions of \(n\), then we
say that \(\lambda\) is finer than \(\mu\) and write \(\lambda \preccurlyeq \mu\) if
there is a surjective map \(\sigma:\\{1, \ldots, r\\} \longrightarrow\\{1,
\ldots, s\\}\) such that \(\mu_{i}=\sum_{\sigma(j)=i} \lambda_{j}\) for all \(i
\leq s\). For example, \(\lambda=(4,2,1,1)\) is finer than \(\mu=(5,3)\), as
furnished by \(\sigma(1)=\sigma(3)=1\) and \(\sigma(2)=\sigma(4)=2\). (The
function \(\sigma\) need not be unique.) In particular, \((n)\) is the coarsest
and \((1,1, \ldots, 1)\) is the finest partition of \(n\).
(i) Prove that if \(f \in \mathbb{Z}[x]\) has degree \(n\) and \(p \in \mathbb{N}\)
is prime, \(\mu\) is the factorization pattern of \(f\) in \(\mathbb{Q}[x]\), and
\(\lambda\) is the factorization pattern of \(f \bmod p\) in \(\mathbb{F}_{p}[x]\),
then \(\mu \succcurlyeq \lambda\).
(ii) Show that \(\lambda \preccurlyeq \lambda, \lambda \preccurlyeq \mu
\Longrightarrow \neg(\mu \preccurlyeq \lambda)\), and \(\lambda \preccurlyeq \mu
\preccurlyeq \nu \Longrightarrow \lambda \preccurlyeq \nu\) holds for all
partitions \(\lambda\), \(\mu, \nu\) of \(n\), so that \(\preccurlyeq\) is a partial
order on the set of all partitions of \(n\).
(iii) Enumerate all partitions of \(n=8\), and draw them in form of a directed
graph, with an edge from \(\lambda\) to \(\mu\) if \(\mu\) is a direct successor of
\(\lambda\) with respect to the order \(\preccurlyeq\), so that \(\lambda
\preccurlyeq \mu, \lambda \neq \mu\), and \(\lambda \preccurlyeq \nu
\preccurlyeq \mu \Longrightarrow \lambda=\nu\) or \(\nu=\mu\) for all partitions
\(\nu\).
(iv) Use (iii) to show that there exist partitions \(\lambda, \mu\) of 8 that do
not have a supremum with respect to \(\preccurlyeq\). (Thus the partitions do
not form a "lattice" in the sense of order theory, not to be confused with the
\(\mathbb{Z}\)-module lattices in Chapter 16.)
(v) Let \(a_{n, r}\) denote the number of partitions of \(n\) of length \(r\). Thus
\(a_{n, 1}=a_{n, n}=1\) and \(a_{n, r}=0\) for \(1 \leq n
