% Comments and corrections to Nicholas A. Loehr, Combinatorics, 2nd ed. \documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage{amsmath,amssymb,mathtools} \usepackage{enumitem} \usepackage[hidelinks]{hyperref} \usepackage{tikz} \usepackage{ytableau} \usepackage[margin=1in]{geometry} \newcommand{\book}{\textit{Combinatorics}, 2nd edition 2018} \newcommand{\corr}[2]{\item[\textbf{#1}.] #2} \newcommand{\CC}{\mathbb{C}} \newcommand{\RR}{\mathbb{R}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\KK}{\mathbb{K}} \newcommand{\xx}{\mathbf{x}} \newcommand{\uu}{\mathbf{u}} \newcommand{\vv}{\mathbf{v}} \newcommand{\ww}{\mathbf{w}} \newcommand{\id}{\operatorname{id}} \newcommand{\ch}{\operatorname{ch}} \newcommand{\GF}{\operatorname{GF}} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\rev}{\operatorname{rev}} \newcommand{\Par}{\operatorname{Par}} \newcommand{\Asc}{\operatorname{Asc}} \newcommand{\Des}{\operatorname{Des}} \newcommand{\SPf}{\operatorname{SPf}} \newcommand{\Comp}{\operatorname{Comp}} \newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\tup}[1]{\left( #1 \right)} \newcommand{\ive}[1]{\left[ #1 \right]} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \title{Comments and Corrections to Nicholas A.\ Loehr, \book} \author{GPT-5.6 Sol, edited and proofread by Darij Grinberg} \date{\today} \begin{document} \maketitle \noindent The following are specific comments and corrections found in chapter-by-chapter proofreading passes through Nicholas A.\ Loehr's \book. They are intended especially for course use: the emphasis is on points that could trip up an instructor or students. I (GPT 5.6 Sol) have separated definite errors from places where the text is essentially correct but would benefit from supplementary explanation. I (Darij) have proofread these errata, removing spurious errors and streamlining the wording in many of the others. I do not agree with all of GPT's priorities regarding exposition and notations, but I consider them to be legitimate opinions (with a few exceptions that I have removed from this list). \tableofcontents \section{Definite corrections} \begin{description}[style=nextline,leftmargin=0pt,labelsep=0.5em] \corr{Page 23, after Definition 1.65} If \(P(A)>0\), the text says that independence of \(A\) and \(D\) is equivalent to \[ P(D\mid A)=P(A). \] This should be \[ P(D\mid A)=P(D). \] \corr{Page 29, Example 1.84(c)} In the proof that the map \[ w_i\longmapsto w_i+i-1 \] takes weakly increasing words to strictly increasing words, replace \[ 1 \leq w_1 + 0 < w_2 + 1 < w_3 + 2 \leq \cdots < w_k + k - 1 \leq n + k - 1 \] by \[ 1 \leq w_1 + 0 < w_2 + 1 < w_3 + 2 < \cdots < w_k + k - 1 \leq n + k - 1. \] \corr{Page 30, Theorem 1.88 (Multiset Rule)} The statement needs the hypothesis \(n>0\). As written, for an \(n\)-letter alphabet it gives \[ \binom{k+n-1}{k,n-1}=\frac{(k+n-1)!}{k!(n-1)!}. \] For \(n=0\), the right-hand side is not defined, whereas the empty alphabet has one \(0\)-element multiset and no \(k\)-element multisets for \(k>0\). \corr{Page 31, Theorem 1.89(b) (Integer Equation Rule)} The theorem begins with \(n>0\) and \(k\geq0\), and then says that the number of positive integer solutions of $y_1+\cdots+y_n=k$ is $\dbinom{k-1}{n-1}$. There are two edge-case problems. First, when \(k=0\), the displayed binomial coefficient has upper index \(-1\), which is not defined by Definition 1.28. Even if the usual definition of binomial coefficients is applied, the equality is wrong (when $k=0$, the number of positive integer solutions is $0$, but $\dbinom{k-1}{n-1}=\dbinom{-1}{n-1}=(-1)^{n-1} \neq 0$). Second, the proof replaces \(k\) by \(k-n\) in part (a); this is only legitimate when \(k\geq n\). This is only a problem for the proof; the claim itself is true in the case $k0$ in Theorem 1.89(b), and to add a sentence about the $k0\), the text says that the identity also holds when one (but not both) of \(a,b\) is zero. Under Definition 1.36, however, a multinomial coefficient is only defined when all lower entries are nonnegative. Thus, for example, when \(a=0\), the displayed right side contains \[ \binom{b-1}{-1,b}, \] which is not defined by the book's conventions. One can either omit the boundary-case remark, or explicitly extend multinomial coefficients by the convention that they are \(0\) when any lower entry is negative. The latter remedy is probably the best one, as the same convention is needed to make Exercise 2-13 and Exercise 12-3 valid in the respective boundary cases. \corr{Page 65, after the multiset recursion in 2.22} The text says that \[ M(n,k)=\binom{k+n-1}{k,n-1} \] for all \(n,k\geq0\). This is not literally meaningful when \(n=0\), since the right side then has a lower entry \(-1\) (and the factorial form contains \((-1)!\)). The formula should be stated for \[ n>0,\qquad k\geq0. \] The already stated initial conditions handle the empty alphabet separately: \[ M(0,0)=1,\qquad M(0,k)=0\quad(k>0). \] \corr{Page 76, Theorem 2.38 (recursion for integer partitions)} The theorem is stated for all positive integers \(n,k\): \[ p(n,k)=p(n-1,k-1)+p(n-k,k). \] But \(p(r,k)\) was only defined for nonnegative \(r\). If \(k>n\), the term \(p(n-k,k)\) therefore lies outside the stated domain. A clean repair is either to state the recursion only for \[ n\geq k>0, \] using \(p(n,k)=0\) for \(k>n\) as a boundary condition, or to extend the convention by setting \(p(r,k)=0\) whenever \(r<0\). The proof given in the text works verbatim with either of the two repairs. \corr{Page 76, Proposition 2.40} The proposition says that \(p(n,k)\) equals the number of integer partitions of \(n\) whose first part is \(k\), without specifying a range for \(n,k\). The statement should exclude the empty partition. For example, \(p(0,0)=1\), but the empty partition has no first part. A clean formulation is: for positive integers \(n,k\), the number of partitions of \(n\) into \(k\) parts equals the number of partitions of \(n\) with first part \(k\). \corr{Page 82, Theorem 2.49 (balls in nonempty boxes)} The theorem does not state a range for \(a,b\). Its formula in part (b), \[ \binom{a-1}{b-1}, \] is not defined under the book's conventions when \(a=0\). The theorem should simply assume that \(a,b\) are positive integers, or else the zero-ball/zero-box cases should be stated separately. \corr{Page 84, proof of Theorem 2.55} In constructing a placement in \(A_1\), the text says to use a placement from \(C\) to fill ``the bottom \(n-1\) rows of \(\Delta_n\).'' But \[ \Delta_n=(n-1,n-2,\ldots,1) \] has only \(n-1\) rows altogether, and after reserving its top row the remaining board \(\Delta_{n-1}\) has \(n-2\) rows. Thus ``the bottom \(n-1\) rows'' should be \[ \text{``the remaining bottom \(n-2\) rows''} \] (or simply ``the copy of \(\Delta_{n-1}\) below the top row''). The counting argument itself is otherwise correct. \corr{Page 86, proof of Theorem 2.58} Replace ``the remaining $n-1$ columns of $\Delta_n$'' by ``the remaining $n-2$ columns of $\Delta_n$'' (since $\Delta_n$ itself has just $n-1$ columns, and we are removing the leftmost one). Also, replace ``in the first row'' by ``in the first column''. % There are two slips in the construction of a placement in \(A_1\). After placing a file rook % in the leftmost column of \(\Delta_n\), the text says to use a placement from \(C\) to fill % ``the remaining \(n-1\) columns of \(\Delta_n\).'' Since \(\Delta_n\) has \(n-1\) columns % in total, only % \[ % n-2 % \] % columns remain; these form a copy of \(\Delta_{n-1}\). % The following sentence says that these file rooks ``do not attack the file rook in the first % row.'' The distinguished rook was placed in the \emph{leftmost column}, not necessarily % the first row. The relevant observation is simply that all the other file rooks lie in % different columns, so they cannot attack it. \corr{Page 88, combinatorial proof of Theorem 2.59} The $n=0$ case cannot be handwaved away with the ``polynomials in $x$'' argument. It is trivial, of course, but that should be said before assuming $x,n\in\ZZ_{>0}$. It would also make more sense to have the sum in \[ |A|=\sum_{k=1}^n S(n,k)x(x-1)\cdots(x-k+1) \] start at $k=1$, not at $k=0$, since you have explicitly mentioned the set $A_0$ in the same sentence (and since the theorem itself has ``$k=0$'' under the summation sign). If you do this, then the $n=0$ case need not be treated separately (i.e., you need not assume that $n\in\ZZ_{>0}$). \corr{Page 89, proof of Theorem 2.62} Replace ``in these rows'' by ``in these columns'' (since the whole proof classifies file-rook placements according to the \emph{columns} that contain rooks). % The proof classifies file-rook placements according to the \emph{columns} of lengths % \(i_1,\ldots,i_{n-k}\) that contain rooks. The sentence % \[ % \text{``the number of placements of file rooks in these rows is \(i_1\cdots i_{n-k}\)''} % \] % should therefore say % \[ % \text{``in these columns.''} % \] \corr{Page 92, Exercise 2.68} In the sentence \[ \text{``The general (complex) solution is }x=s(3+4i)^n+t(3-4i)^n\text{'',} \] replace ``$x$'' by ``$x_n$''. \corr{Page 94, Chapter 2 Summary} There are two index/variable slips in the Multinomial Theorems item. First, the commutative formula begins with variables \(z_1,\ldots,z_s\), but its monomial on the right is printed using \(x_1,\ldots,x_s\). It should be \[ (z_1+z_2+\cdots+z_s)^n = \sum_{n_1+n_2+\cdots+n_s=n} \binom{n}{n_1,n_2,\ldots,n_s} z_1^{n_1} z_2^{n_2} \cdots z_s^{n_s}. \] Second, in the noncommutative formula the final factor is printed as \(Z_{w_s}\). It should be \[ Z_{w_n}, \] since \(w=w_1\cdots w_n\) has length \(n\). \corr{Page 96, Exercise 2-13} The multinomial version of Pascal's identity contains terms with \(n_i-1\). Unless all \(n_i>0\), some of these lower entries are negative, and such multinomial coefficients are not defined by Definition 1.36. Thus the exercise should either assume all \(n_i>0\), or (better) explicitly adopt the convention that a multinomial coefficient is \(0\) whenever one of its lower entries is negative. \corr{Page 100, Exercise 2-79(f)} No hypotheses are stated on \(a,b,n\), but the summand contains \(F_{b-k}\) for \(0\leq k\leq a\). With the book's Fibonacci numbers indexed only by nonnegative integers, the formula is not even defined when \(b0$, but not for $n=0$. \corr{Page 101, Exercises 2-92 and 2-93} In each of the two exercises, replace ``the set of'' by ``the number of''. % Each exercise says ``Let \(p_d(n,k)\) [respectively \(p_o(n,k)\)] be the \emph{set} of integer % partitions \(\ldots\),'' and then asks for a recursion and initial conditions for the quantity % \(p_d(n,k)\) or \(p_o(n,k)\). The intended word is % \[ % \text{``number''}, % \] % not ``set.'' % \corr{Page 109, Example 3.23} % For % \[ % B=\begin{bmatrix} % 0&x&y\\ % 0&0&z\\ % 0&0&0 % \end{bmatrix}, % \qquad % B^2=\begin{bmatrix} % 0&0&xz\\ % 0&0&0\\ % 0&0&0 % \end{bmatrix}, % \qquad B^3=0, % \] % the text says that this gives matrices ``nilpotent of index \(3\).'' The index is only % \emph{at most} \(3\) in general. It is exactly \(3\) when \(xz\neq0\); if \(xz=0\), the % index may be \(1\) or \(2\). \corr{Page 126, Theorem 3.74} The theorem allows \(d_1,\ldots,d_n\geq0\) and, when \[ d_1+\cdots+d_n=2n-2, \] states the formula \[ \binom{n-2}{d_1-1,\ldots,d_n-1} = \frac{(n-2)!}{\prod_j(d_j-1)!}. \] If some \(d_j=0\), however, the right-hand side contains a negative lower multinomial entry (or \((-1)!\)), which is not defined by the book's conventions. The proof later says that the formula is zero ``by convention,'' but this convention has not been introduced. A clean formulation is: if all \(d_j\geq1\) and \(\sum_j d_j=2n-2\), the displayed multinomial gives the number of trees; in every other case the number is \(0\). \corr{Page 127, Corollary 3.75} When summing over degree sequences of trees, the displayed condition is \(d_i\geq 0\). For \(n\geq 2\), it should be \[ d_i\geq 1. \] This is also required by the summand, which contains \((d_i-1)!\), and by the corrected formulation of Theorem 3.74. \corr{Pages 129--130, proof of Theorem 3.80} In the implication ``no odd cycle \(\Rightarrow\) no odd closed walk,'' the proof chooses a shortest odd closed walk and says that, if it is not a cycle, then there must be an interior return to the starting vertex: \[ v_0=v_i=v_s \qquad(00\), the terms with lower index \(-1\) are indeed \(0\) by Definition 1.28.) The clean repair is to state part (b) for \[ p\geq0,\qquad j>0. \] Then its right side may simply be written \(\chi(p\geq j)\). \corr{Page 174, Example 4.30} The phrase \[ \text{``first choosing which of the \(j\) inputs will be fixed %(there are \(\binom{n}{j}\) possibilities) ''} \] should read \[ \text{``first choosing which \(j\) of the \(n\) inputs will be fixed.''} \] \corr{Page 174, Definition 4.31} Replace ``distint'' by ``distinct''. % In the prime factorization used to define the number-theoretic M\"obius function, % ``the \(p_i\)'s are distint primes'' should read % \[ % \text{``the \(p_i\)'s are distinct primes.''} % \] \corr{Page 177, Example 4.41} Replace ``prime power'' by ``prime power or $1$'', unless you count $1$ as a prime power. % For the divisibility poset consisting of the positive divisors of \(n\), the text says: % \[ % \text{``This poset is a totally ordered set iff \(n\) is a prime power.''} % \] % There is an endpoint exception: when \(n=1\), the divisor poset has the single element % \(1\) and is certainly totally ordered, although \(1\) is not normally called a prime power % (with positive exponent). % Thus one should say that the divisor poset is totally ordered iff % \[ % n=1\quad\text{or}\quad n\text{ is a prime power}. % \] \corr{Page 181, Theorem 4.58} The theorem on the M\"obius function of a product poset should assume that the factor posets are finite. The book has defined the poset M\"obius function only for finite posets, and the proof explicitly uses finite matrices \(Z_i,M_i,Z,M\). Thus the opening should read, for example: \[ \text{``Let \((X,\leq)\) be the product of finite posets \((X_i,\leq_i)\), \(1\leq i\leq k\).''} \] (One can extend the theorem to locally finite posets, but that theory has not been introduced here.) \corr{Page 182, Theorem 4.60} For the same reason, the isomorphism-invariance theorem for M\"obius functions should explicitly concern finite posets (or else locally finite posets in a more general treatment). As written, \(\mu_{(X,\leq)}\) has not been defined for an arbitrary infinite poset. \corr{Page 182, Example 4.61} Replace ``divisibility poset'' by ``Boolean poset''. % The heading correctly concerns a Boolean poset, but the first sentence calls % \[ % X=(\mathcal P([n]),\subseteq) % \] % ``the divisibility poset.'' Replace this by % \[ % \text{``the Boolean poset.''} % \] \corr{Page 186, Exercise 4-48} The phrase \[ \text{``Find the probability that none of the events \(S_i\) occurs first by using inclusion-exclusion, and then \(\ldots\)''} \] is a bit of a crash blossom: it can be read as though ``occurs first'' were an event. The intended wording is \[ \text{``Find the probability that none of the events \(S_i\) occurs, first by using inclusion-exclusion, and then \(\ldots\)''} \] \corr{Page 187, Exercise 4-53} The Catalan identity is stated without a range for \(n\): \[ C_n= \sum_{1\leq k\leq (n+1)/2} (-1)^{k-1}C_{n-k}\binom{n+1-k}{k}. \] It is false at \(n=0\): the sum is empty, while \(C_0=1\). The exercise should assume \[ n\geq1. \] \corr{Page 189, Exercise 4-87} The exercise says: ``Consider an \(n\times n\) lower-triangular matrix \(A\) such that \(A(n,k)\) is the number of Dyck paths ending with exactly \(k\) east steps.'' This specifies only the last row of an \(n\times n\) matrix. The intended definition is presumably \[ A(i,k)=\#\{\text{Dyck paths of order \(i\) ending with exactly \(k\) east steps}\} \qquad \text{(for all $k$ and $i$)}, \] i.e., \(A(i,k)=C_{i,k}\) in the notation of Exercise 2-81. \corr{Page 189, Exercise 4-93(c)} Part (c) is false as written. It claims that every interval \([P,Q]\) in the partition lattice \(X_n\) is isomorphic to \(X_k\) for some \(k\). In general an interval is a \emph{product} of partition lattices, not a single partition lattice. For a concrete counterexample, let \[ P=\{\{1\},\{2\},\{3\},\{4\}\},\qquad Q=\{\{1,2\},\{3,4\}\}. \] Then \([P,Q]\) has four elements and is isomorphic to \(X_2\times X_2\); it is not isomorphic to any \(X_k\) (whose first sizes are \(1,2,5,\ldots\)). The standard corrected statement is this. For each block \(B\) of \(Q\), let \(r_B\) be the number of blocks of \(P\) contained in \(B\). Then \[ [P,Q]\cong\prod_{B\in Q} X_{r_B}. \] Consequently part (d) gives \[ \mu_{X_n}(P,Q) = \prod_{B\in Q}(-1)^{r_B-1}(r_B-1)! \qquad \text{ whenever } P\preceq Q. \] \corr{Page 189, Exercise 4-98} Replace ``$n$ is even'' by ``$m$ is even''. % The parity hypothesis is wrong. The exercise states that if \(n\) is even and % \(00\) is even, the \(k\) and \(-k\) terms are equal and the \(k=0\) term is zero, so the desired positive-half sum $\sum_{k=1}^{n}(-1)^k \binom{2n}{n+k}k^m$ is zero. On the other hand, requiring $n$ to be even when $m$ is not is insufficient; for instance, if $n=2$ and $m=1$, the sum is $-2$. \corr{Page 189, Exercise 4-100} Replace ``$n\geq 0$'' by ``$n\geq 1$''. Indeed, at $n=0$ the sum contains the summand $\binom{2n-2k-1}{n-1}=\binom{-1}{-1}$ which is not defined by the book's conventions. \corr{Page 194, Example 5.8(a)} The example takes \(b\in\mathbb C\) arbitrary and computes the radius of convergence of $\sum_{n\geq0} b^n z^n$ using $\lim_{n\to\infty}\left|{b^n}/{b^{n+1}}\right|=1/{|b|}$. This ratio calculation is not defined when \(b=0\). The conclusion is still correct if the zero case is separated: when \(b=0\), the series is just \(1\), so its radius of convergence is \(\infty\). \corr{Page 194, Example 5.8(d)} The Ratio Test calculation is said to work ``for any \(z\in\mathbb C\),'' but when \(z=0\) all the terms \(c_k\) are zero and \(c_{k+1}/c_k\) is undefined. One should perform the ratio calculation for \(z\neq0\) and note separately that convergence at \(z=0\) is immediate. \corr{Page 196, Example 5.11} When the ordinary Binomial Theorem is recalled, the displayed formula ends with \(z^m\): \[ (1+z)^m=\sum_{n=0}^m \binom{m}{n}z^m. \] The exponent should be the summation index: \[ (1+z)^m=\sum_{n=0}^m \binom{m}{n}z^n. \] \corr{Page 209, Example 5.29} The displayed expansion of $(1-4z)^{1/2}$ contains the term \[ -10^4. \] It should be \[ -10z^4. \] Thus the beginning of the expansion is \[ (1-4z)^{1/2} = 1-2z-2z^2-4z^3-10z^4-28z^5-\cdots. \] \corr{Pages 216--217, derivation in \S5.13} The last displayed equation on page 216 contains the expressions $(n-1)!$ and $(n-2)!$ in certain sums that start at $n=0$. But these expressions are undefined for $n=0$ and for $n=1$. This can be fixed by discarding the $n=0$ addend of the sum back before these expressions appear, and also discarding the $n=1$ addend of the second sum at the point where it still has a $\dfrac{(n-1)c(n-1,k)}{(n-1)!}$ factor. Corresponding changes are also needed in the first paragraph of page 217. % In deriving the differential equation for the generating function of the signless Stirling % numbers of the first kind, the text rewrites terms using % \[ % \frac{1}{(n-1)!} % \qquad\text{and}\qquad % \frac{1}{(n-2)!} % \] % while the displayed sums still begin at \(n=0\). After reindexing the second sum, it similarly % writes \(1/(m-1)!\) while displaying \(m=0\). % The terms that were discarded are zero before the factorial cancellation, so the intended % calculation is valid, but the rewritten expressions are literally undefined at these boundary % indices. The clean fix is to start the first transformed sum at \(n=1\), the second at % \(n=2\), and after reindexing the latter to start at \(m=1\). The resulting differential % equation % \[ % (1-z)\frac{\partial F}{\partial z}=tF % \] % is unchanged. \corr{Page 220, Theorem 5.46} The identity \[ \sum_{\mu\in\Par} t^{\ell(\mu)}z^{|\mu|} = \prod_{i=1}^\infty \frac1{1-tz^i} = \sum_{\mu\in\Par} t^{\mu_1}z^{|\mu|} \] includes the empty partition. But under the book's definition of an integer partition, the empty partition has no first part, so \(\mu_1\) is undefined for this one summand. The best way to repair this is by explicitly introducing the convention that if $\mu$ is a partition of length $k$, then $\mu_i$ means $0$ for all $i>k$. (Thus, $\mu_1 = 0$ when $\mu$ is the empty partition.) This convention is also introduced in Chapter 9, but it is equally useful outside of symmetric polynomial theory. \corr{Page 222, Figure 5.3} The intended L-shaped pieces in Sylvester's bijection are not visibly drawn inside the partition diagram in this printing, although the surrounding text and the labels ``piece 1,'' ``piece 2,'' etc.\ refer to them. A corrected version of the figure is needed if this construction is used in class. Here is a TikZ replacement figure with the ten L-shaped pieces color-coded: \begin{center} \begin{tikzpicture}[scale=1.2,x=0.38cm,y=0.38cm,line join=round,font=\small,>=latex] \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-6.5,0.5) rectangle (-5.5,-0.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-5.5,0.5) rectangle (-4.5,-0.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-4.5,0.5) rectangle (-3.5,-0.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-3.5,0.5) rectangle (-2.5,-0.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-2.5,0.5) rectangle (-1.5,-0.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,0.5) rectangle (-0.5,-0.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,0.5) rectangle (0.5,-0.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (0.5,0.5) rectangle (1.5,-0.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (1.5,0.5) rectangle (2.5,-0.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (2.5,0.5) rectangle (3.5,-0.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (3.5,0.5) rectangle (4.5,-0.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (4.5,0.5) rectangle (5.5,-0.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (5.5,0.5) rectangle (6.5,-0.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-6.5,-0.5) rectangle (-5.5,-1.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-5.5,-0.5) rectangle (-4.5,-1.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-4.5,-0.5) rectangle (-3.5,-1.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-3.5,-0.5) rectangle (-2.5,-1.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-2.5,-0.5) rectangle (-1.5,-1.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,-0.5) rectangle (-0.5,-1.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-0.5) rectangle (0.5,-1.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (0.5,-0.5) rectangle (1.5,-1.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (1.5,-0.5) rectangle (2.5,-1.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (2.5,-0.5) rectangle (3.5,-1.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (3.5,-0.5) rectangle (4.5,-1.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (4.5,-0.5) rectangle (5.5,-1.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (5.5,-0.5) rectangle (6.5,-1.5); \filldraw[fill=violet!18,draw=black,line width=0.25pt] (-5.5,-1.5) rectangle (-4.5,-2.5); \filldraw[fill=violet!18,draw=black,line width=0.25pt] (-4.5,-1.5) rectangle (-3.5,-2.5); \filldraw[fill=violet!18,draw=black,line width=0.25pt] (-3.5,-1.5) rectangle (-2.5,-2.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-2.5,-1.5) rectangle (-1.5,-2.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,-1.5) rectangle (-0.5,-2.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-1.5) rectangle (0.5,-2.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (0.5,-1.5) rectangle (1.5,-2.5); \filldraw[fill=green!22,draw=black,line width=0.25pt] (1.5,-1.5) rectangle (2.5,-2.5); \filldraw[fill=green!22,draw=black,line width=0.25pt] (2.5,-1.5) rectangle (3.5,-2.5); \filldraw[fill=green!22,draw=black,line width=0.25pt] (3.5,-1.5) rectangle (4.5,-2.5); \filldraw[fill=green!22,draw=black,line width=0.25pt] (4.5,-1.5) rectangle (5.5,-2.5); \filldraw[fill=magenta!16,draw=black,line width=0.25pt] (-5.5,-2.5) rectangle (-4.5,-3.5); \filldraw[fill=magenta!16,draw=black,line width=0.25pt] (-4.5,-2.5) rectangle (-3.5,-3.5); \filldraw[fill=violet!18,draw=black,line width=0.25pt] (-3.5,-2.5) rectangle (-2.5,-3.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-2.5,-2.5) rectangle (-1.5,-3.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,-2.5) rectangle (-0.5,-3.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-2.5) rectangle (0.5,-3.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (0.5,-2.5) rectangle (1.5,-3.5); \filldraw[fill=green!22,draw=black,line width=0.25pt] (1.5,-2.5) rectangle (2.5,-3.5); \filldraw[fill=cyan!22,draw=black,line width=0.25pt] (2.5,-2.5) rectangle (3.5,-3.5); \filldraw[fill=cyan!22,draw=black,line width=0.25pt] (3.5,-2.5) rectangle (4.5,-3.5); \filldraw[fill=cyan!22,draw=black,line width=0.25pt] (4.5,-2.5) rectangle (5.5,-3.5); \filldraw[fill=brown!20,draw=black,line width=0.25pt] (-5.5,-3.5) rectangle (-4.5,-4.5); \filldraw[fill=magenta!16,draw=black,line width=0.25pt] (-4.5,-3.5) rectangle (-3.5,-4.5); \filldraw[fill=violet!18,draw=black,line width=0.25pt] (-3.5,-3.5) rectangle (-2.5,-4.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-2.5,-3.5) rectangle (-1.5,-4.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,-3.5) rectangle (-0.5,-4.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-3.5) rectangle (0.5,-4.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (0.5,-3.5) rectangle (1.5,-4.5); \filldraw[fill=green!22,draw=black,line width=0.25pt] (1.5,-3.5) rectangle (2.5,-4.5); \filldraw[fill=cyan!22,draw=black,line width=0.25pt] (2.5,-3.5) rectangle (3.5,-4.5); \filldraw[fill=yellow!30,draw=black,line width=0.25pt] (3.5,-3.5) rectangle (4.5,-4.5); \filldraw[fill=yellow!30,draw=black,line width=0.25pt] (4.5,-3.5) rectangle (5.5,-4.5); \filldraw[fill=violet!18,draw=black,line width=0.25pt] (-3.5,-4.5) rectangle (-2.5,-5.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-2.5,-4.5) rectangle (-1.5,-5.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,-4.5) rectangle (-0.5,-5.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-4.5) rectangle (0.5,-5.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (0.5,-4.5) rectangle (1.5,-5.5); \filldraw[fill=green!22,draw=black,line width=0.25pt] (1.5,-4.5) rectangle (2.5,-5.5); \filldraw[fill=cyan!22,draw=black,line width=0.25pt] (2.5,-4.5) rectangle (3.5,-5.5); \filldraw[fill=violet!18,draw=black,line width=0.25pt] (-3.5,-5.5) rectangle (-2.5,-6.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-2.5,-5.5) rectangle (-1.5,-6.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,-5.5) rectangle (-0.5,-6.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-5.5) rectangle (0.5,-6.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (0.5,-5.5) rectangle (1.5,-6.5); \filldraw[fill=green!22,draw=black,line width=0.25pt] (1.5,-5.5) rectangle (2.5,-6.5); \filldraw[fill=cyan!22,draw=black,line width=0.25pt] (2.5,-5.5) rectangle (3.5,-6.5); \filldraw[fill=violet!18,draw=black,line width=0.25pt] (-3.5,-6.5) rectangle (-2.5,-7.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-2.5,-6.5) rectangle (-1.5,-7.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,-6.5) rectangle (-0.5,-7.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-6.5) rectangle (0.5,-7.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (0.5,-6.5) rectangle (1.5,-7.5); \filldraw[fill=green!22,draw=black,line width=0.25pt] (1.5,-6.5) rectangle (2.5,-7.5); \filldraw[fill=cyan!22,draw=black,line width=0.25pt] (2.5,-6.5) rectangle (3.5,-7.5); \filldraw[fill=violet!18,draw=black,line width=0.25pt] (-3.5,-7.5) rectangle (-2.5,-8.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-2.5,-7.5) rectangle (-1.5,-8.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,-7.5) rectangle (-0.5,-8.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-7.5) rectangle (0.5,-8.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (0.5,-7.5) rectangle (1.5,-8.5); \filldraw[fill=green!22,draw=black,line width=0.25pt] (1.5,-7.5) rectangle (2.5,-8.5); \filldraw[fill=cyan!22,draw=black,line width=0.25pt] (2.5,-7.5) rectangle (3.5,-8.5); \filldraw[fill=red!18,draw=black,line width=0.25pt] (-2.5,-8.5) rectangle (-1.5,-9.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,-8.5) rectangle (-0.5,-9.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-8.5) rectangle (0.5,-9.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (0.5,-8.5) rectangle (1.5,-9.5); \filldraw[fill=green!22,draw=black,line width=0.25pt] (1.5,-8.5) rectangle (2.5,-9.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,-9.5) rectangle (-0.5,-10.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-9.5) rectangle (0.5,-10.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (0.5,-9.5) rectangle (1.5,-10.5); \filldraw[fill=orange!25,draw=black,line width=0.25pt] (-1.5,-10.5) rectangle (-0.5,-11.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-10.5) rectangle (0.5,-11.5); \filldraw[fill=teal!22,draw=black,line width=0.25pt] (0.5,-10.5) rectangle (1.5,-11.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-11.5) rectangle (0.5,-12.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-12.5) rectangle (0.5,-13.5); \filldraw[fill=blue!20,draw=black,line width=0.25pt] (-0.5,-13.5) rectangle (0.5,-14.5); \draw[->,line width=0.4pt] (-9.1,0) -- (-6.55,0); \node[left] at (-9.1,0) {piece 2}; \draw[->,line width=0.4pt] (-9.1,-1) -- (-6.55,-1); \node[left] at (-9.1,-1) {piece 4}; \draw[->,line width=0.4pt] (-9.1,-2) -- (-5.55,-2); \node[left] at (-9.1,-2) {piece 6}; \draw[->,line width=0.4pt] (-9.1,-3) -- (-5.55,-3); \node[left] at (-9.1,-3) {piece 8}; \draw[->,line width=0.4pt] (-9.1,-4) -- (-5.55,-4); \node[left] at (-9.1,-4) {piece 10}; \draw[->,line width=0.4pt] (9.1,0) -- (6.55,0); \node[right] at (9.1,0) {piece 1}; \draw[->,line width=0.4pt] (9.1,-1) -- (6.55,-1); \node[right] at (9.1,-1) {piece 3}; \draw[->,line width=0.4pt] (9.1,-2) -- (5.55,-2); \node[right] at (9.1,-2) {piece 5}; \draw[->,line width=0.4pt] (9.1,-3) -- (5.55,-3); \node[right] at (9.1,-3) {piece 7}; \draw[->,line width=0.4pt] (9.1,-4) -- (5.55,-4); \node[right] at (9.1,-4) {piece 9}; \end{tikzpicture} \par\smallskip \( F((13,13,11,11,11,7,7,7,7,5,3,3,1,1,1))=(21,17,16,13,11,9,8,3,2,1). \) \end{center} \corr{Page 223, inverse of Sylvester's bijection} After \(y_0\) has already been defined as the number of cells in column \(0\), the text says: ``For all \(i\geq0\), let \(y_i\) be the number of cells in the vertical portion of the \(2i\)th L-shaped piece.'' Replace ``$i\geq 0$'' by ``$i\geq 1$'' here, since $y_0$ has already been defined and since there is no \(0\)th L-shaped piece. \corr{Page 230, Exercise 5-10} The new weight is defined by \[ \operatorname{wt}'(u)=a\,\operatorname{wt}(u)+b \qquad(a,b\in\mathbb Z_{\geq0}). \] If \(a>0\), the expected answer is \(z^bG(z^a)\). But the case \(a=0\) requires separate treatment: if the original weighted set \(S\) is infinite, then every object receives the same new weight \(b\), so the weight-\(b\) fiber is infinite and \((S,\operatorname{wt}')\) is no longer a weighted set in the sense of \S5.1. Thus the exercise should either assume \(a>0\), or explicitly discuss the exceptional case \(a=0\) (which is harmless only when \(S\) is finite). \corr{Page 230, Exercise 5-12(b),(d)} Both displayed series begin at \(n=0\), but their \(n=0\) terms are undefined: part (b) contains division by \(n\), and part (d) contains \(1/n\). Both sums should begin at $n=1$. \corr{Page 230, Exercise 5-13(b),(d)} The same endpoint problem occurs here. Part (b) contains ${z^n}/({n^2 4^n})$, and part (d) contains $\left(z/n\right)^n$, while both sums are printed as starting at \(n=0\). They should start at $n=1$. \corr{Page 236, Exercise 5-109(a)} The statement is false as written. It assumes two sequences of distinct nonzero partitions \(\{\mu^i:i\geq1\}\) and \(\{\nu^i:i\geq1\}\) such that, for every finite \(S\subseteq\mathbb Z_{>0}\), \[ \sum_{i\in S}|\mu^i|=\sum_{i\in S}|\nu^i|, \] and asks one to prove that the numbers of partitions avoiding all the \(\mu^i\)'s and all the \(\nu^i\)'s are equal. For a counterexample, take \[ \mu^1=(2,2),\qquad \mu^2=(2,1,1), \] and \[ \nu^1=(4),\qquad \nu^2=(3,1). \] All four partitions have area \(4\), so the stated hypothesis holds for every finite subset of \(\{1,2\}\). For \(n=6\), however, there are \(8\) partitions avoiding both \(\mu^1,\mu^2\), but only \(7\) partitions avoiding both \(\nu^1,\nu^2\). The issue is that an intersection of extension conditions is controlled by the \emph{multiset union} (componentwise maximum of multiplicities), not by the sum of the areas of the individual forbidden partitions. A sufficient corrected hypothesis is that for every finite \(S\), \[ \left|\bigvee_{i\in S}\mu^i\right| = \left|\bigvee_{i\in S}\nu^i\right|, \] where \(\bigvee\) denotes the partition whose multiplicity of each part \(r\) is the maximum of the multiplicities of \(r\) among the partitions indexed by \(S\). Then inclusion--exclusion gives the desired conclusion. \corr{Page 237, Exercise 5-125} The divide-and-conquer setup assumes only \(a,b,c,d>0\), but it needs at least \[ b>1. \] If \(b=1\), the subproblem size \(n/b\) does not decrease and the expression \(\log_b a\) appearing in the claimed asymptotic bound is undefined. In the algorithmic interpretation one would normally assume that \(a\) and \(b\) are positive integers with \(b\geq2\). \corr{Page 239, Definition 6.1} The notation \[ \mathopen{[\![}n\mathclose{]\!]}=\{0,1,\ldots,n-1\} \] is defined only for positive integers \(n\). Later in the chapter, however, ranking maps for empty combinatorial classes arise naturally (for example, impossible set-partition or anagram parameter choices), and the Bijective Sum Rule also allows finite component sets that may be empty. These situations require a rank set of cardinality \(0\). Thus, the above definition of $\mathopen{[\![}n\mathclose{]\!]}$ should be extended to all \textbf{nonnegative} integers $n$. This boils down to setting \[ \mathopen{[\![}0\mathclose{]\!]}=\varnothing. \] % This also makes the phrase ``the only % possible map'' for empty ranking classes literally meaningful. \corr{Page 242, proof of Lemma 6.4} % In the proof of the product-map lemma, the text says % \[ % \text{``Since \(S\times T\) is the union of the pairwise disjoint sets % \(S_0,\ldots,S_{n-1}\), \(\ldots\)''} % \] % but no sets \(S\) and \(T\) have been defined in this lemma. The domain under discussion is Replace ``\(S\times T\)'' by ``$\mathopen{[\![}n\mathclose{]\!]}\times\mathopen{[\![}m\mathclose{]\!]}$''. \corr{Page 247, Example 6.15} The text introduces a three-letter word as \[ w=w_1w_2w_2\in S. \] This should be \[ w=w_1w_2w_3\in S. \] \corr{Pages 252--253, ranking anagrams} The text writes \[ C(n;n_1,\ldots,n_k) = \sum_{i=1}^k C(n-1;n_1,\ldots,n_i-1,\ldots,n_k) \] without any restrictions on $n, n_1, \ldots, n_k$. In truth, this only holds for $n > 0$. Furthermore, the definition \[ M={(n_1+\cdots+n_k)!}/({n_1!\cdots n_k!}) \] makes sense only if $n_1, n_2, \ldots, n_k$ are nonnegative. If some \(n_i<0\), then $M$ must be defined as $0$. The recursive definition of the ranking function $r_{n_1,\ldots,n_k}$ also requires $n>0$ (otherwise, there is no ``first letter''). \corr{Page 256, Section 6.11 (Ranking Trees)} The section opens by saying that there are \[ n^{\,n-2} \] rooted trees on \(\{1,\ldots,n\}\) rooted at \(1\), and then encodes them by words of length \(n-2\). This construction requires \[ n\geq2. \] For \(n=1\), there is indeed one rooted tree, but \(n-2=-1\), so neither the word model nor the displayed power should be used literally. The \(n=1\) case should be separated. \corr{Page 257, Rule 6.31 (Successor Sum Rule)} The rule permits some of the sets \(S_i\) to be empty and its pseudocode explicitly skips empty components. But it simultaneously assumes that ``we already know successor algorithms for each \(S_i\).'' Under the definition in \S6.1, an empty set has no successor algorithm (since a successor algorithm includes subroutines \texttt{first} and \texttt{last}, but an empty set has no minimum and maximum elements). The hypothesis should instead say that we can detect which \(S_i\)'s are empty and that successor algorithms are known for every \emph{nonempty} \(S_i\). The pseudocode then works exactly as intended. \corr{Page 258, Section 6.13} ``rearrangemenets'' should read {``rearrangements''}. \corr{Page 259, Figure 6.6 (Anagram Successor Algorithm)} The base case in both \texttt{first} and \texttt{last} is incorrect. The pseudocode says \[ \texttt{if (k==0) then return the empty word;} \] where \(k\) is the size of the fixed alphabet. But recursive calls decrease the multiplicities \(n[i]\), not \(k\). Consequently, when all multiplicities have reached \(0\) but \(k>0\), the subsequent loop \[ \texttt{while (n[i]==0)} \] runs past the end of the array. The base case should be \[ \texttt{if (all n[i] are 0) then return the empty word;} \] (or equivalently, ``if all \(n[i]=0\)''). This is a genuine algorithmic bug in the printed pseudocode. \corr{Pages 263--264, Section 6.16 (Successor Algorithms for Dyck Paths)} The text repeatedly applies the subroutines \(\texttt{first}\), \(\texttt{last}\), and \(\texttt{next}\) to \(C_n\), although \(C_n\) is the \emph{number} of Dyck paths. The underlying set is \(DP(n)\). Thus, for example, \[ \texttt{first}(C_n) \quad\text{and}\quad \texttt{last}(C_n) \] should be \[ \texttt{first}(DP(n)) \quad\text{and}\quad \texttt{last}(DP(n)). \] Also, after ``We use three cases to define $\pi^* = \texttt{next}(\pi, DP(n))$'', add ``when $\pi \neq \texttt{last}(DP(n))$''. % There is also a missing hypothesis in the three-case definition of \(\texttt{next}\). % It begins ``To compute \(\texttt{next}(\pi)\) for \(\pi\in C_n\),'' but the successor % subroutine is only defined when \(\pi\) is not the last object. For the last path % \[ % \pi=N^nE^n, % \] % Case 3 would formally ask for % \[ % \texttt{first}(DP(-1)). % \] % The sentence should therefore say: for % \[ % \pi\in DP(n),\qquad % \pi\neq\texttt{last}(DP(n)), % \] % compute \(\texttt{next}(\pi)\) by the three cases that follow. \corr{Page 265, Chapter 6 Summary: ranking anagrams} Again, the expression \[ \frac{(n_1+\cdots+n_k-1)!} {n_1!\cdots(n_j-1)!\cdots n_k!} \] only makes sense if $n_j \neq 0$, since otherwise this has a $(-1)!$ in the denominator. The sum should run only over \[ j0, \] or else the text should explicitly use the convention that a fraction with a $(-1)!$ in its denominator must be $0$. \corr{Page 272, Exercise 6-123} The phrase \[ \text{``Describe a successor algorithm for ranking rooted trees \(\ldots\)''} \] should read simply \[ \text{``Describe a successor algorithm for rooted trees \(\ldots\)''} \] (or ``for generating rooted trees''). A successor algorithm does not itself rank the trees. \corr{Page 282, Definition 7.18} This defines $k$-cycles only for $k>1$, but the (arguably trivial) concept of a $1$-cycle is used in several places below (explicitly in the proofs of Theorems 7.33, 7.113 and 7.115, for example, but already in Remark 7.19 you are writing ``$(9)$'' and treating it as a permutation). The best remedy is to replace ``$k>1$'' by ``$k\geq 1$'' in Definition 7.18; thus, $1$-cycles are put on the same footing as all the other cycles, despite their triviality. % \corr{Page 287, Theorem 7.33 and the use of \(1\)-cycles} % Definition 7.18 defines a \(k\)-cycle only for \(k>1\), but Theorem 7.33 says that the % result is ``already known for \(k=1\) and \(k=2\),'' and Theorem 7.34 subsequently treats % the \(1\)-cycles in a complete cycle decomposition on the same footing as the other cycles. % The intended mathematics is clear: a cycle of length \(1\) contributes sign \(+1\). % For consistency, Theorem 7.33 can simply be stated for \(k>1\), with the \(1\)-cycle % case handled separately when Theorem 7.34 is applied. \corr{Page 288, Example 7.38} In ``The set $J=\{(1)(2)(3),(1,3),(2,3),(1,3)\}$'', replace one of the two ``$(1,3)$''s by ``$(1,2)$''. % lists \((1,3)\) twice. Presumably one of these repeated entries was intended to be % \((1,2)\), so that \(J\) consists of the identity together with the three transpositions % in \(S_3\). The stated conclusion that \(J\) is not a subgroup is correct either way, % since % \[ % (1,3)\circ(2,3)=(1,3,2)\notin J. % \] \corr{Page 299, Definition 7.73} Replace ``\textit{left multiplication by $G$}'' by ``\textit{left multiplication by $g$}'', since the map being defined is given by \(L_g(x)=g\ast x\). \corr{Page 311, proof of Theorem 7.118 (Lucas)} In Step 3, the displayed formula at the end starts with \[ \binom{n}{p}. \] It must start with \[ \binom{n}{k}. \] Indeed, the next line applies Step 2 using \(n=ap+n_0\) and \(k=cp+k_0\), and the remainder of the computation proves Lucas's formula for \(\binom nk\). % There is \emph{no} problem with the negative lower indices that occur earlier in the proof: % Definition 1.28 already sets \(\binom{r}{s}=0\) for \(r\geq0\) and \(s<0\). \corr{Page 319, Chapter 7 Summary} In the discussion of the center of a finite \(p\)-group, the summary says \[ \text{``(Exercise 7-92) groups \(G\) of size \(p^n\) \ldots have \(|Z(G)|>1\).''} \] Exercise 7-92 is the Class Equation. The exercise that explicitly asks the reader to deduce the nontriviality of the center of a \(p\)-group is \textbf{Exercise 7-93}. \corr{Page 322, Exercise 7-45} The hypercube \(Q_k\) is declared to be a \emph{simple graph}, but its edge set is written using ordered pairs: \[ E=\{(v,w)\in V:\ v,w\text{ differ in exactly one position}\}. \] For a simple undirected graph, the edges should be unordered pairs: \[ E=\bigl\{\{v,w\}:v,w\in V,\ v,w\text{ differ in exactly one position}\bigr\}. \] \corr{Page 325, Exercise 7-87(b)} This should assume $n \geq 2$, since the transposition \((1,2)\) does not exist in \(S_1\). \corr{Page 333, inversion tables after Example 8.22} The displayed formula defining \(k_r\) is missing cardinality bars: \[ k_r=\{(i,j):1\leq iw_j\}. \] The left side is a number, whereas the right side as printed is a set. It should be \[ k_r= \left|\{(i,j):1\leq iw_j\}\right|. \] This agrees with the sentence immediately following the display, which says that \(k_r\) \emph{counts} such inversion pairs. \corr{Page 333, Example 8.23} Replace ``$G(w) = (5,5,1,2,3,0,1,0)$'' by ``$G(w) = (5,5,1,2,3,1,0,0)$''. Moreover, replace ``since $k_0 = k_1 = 0$'' by ``since $k_2 = k_1 = 0$''. % While reconstructing a permutation from the inversion table % \[ % (5,5,1,2,3,1,0,0)=(k_8,k_7,\ldots,k_1), % \] % the text says that inserting \(2\) at the right end gives \(12\) ``since % \(k_0=k_1=0\).'' There is no \(k_0\) in the inversion table. This should read % \[ % k_2=k_1=0 % \] % (or simply ``since \(k_2=0\)''). \corr{Page 337, proof of Corollary 8.33} The induction proof of polynomiality applies the first recursion of Theorem 8.32 with \(a=k\) and \(b=n-k\) for every \(0\leq k\leq n\). But Theorem 8.32 states that recursion only for \[ a,b>0. \] Thus the displayed recursion does not apply when \(k=0\) or \(k=n\). The repair is immediate but should be stated: handle the boundary cases separately using \[ \begin{bmatrix}n\\0\end{bmatrix}_q = \begin{bmatrix}n\\n\end{bmatrix}_q =1, \] and apply the recursion only for \(00$, but not for $n=0$. \corr{Page 357, Exercise 8-67} The definition of \[ G_n=\{(g_0,g_1,\ldots,g_{n-1}):g_0=0,\ \ldots\} \] requires \(n\geq1\), since \(g_0\) does not exist when \(n=0\). The exercise should explicitly assume \[ n\geq1. \] \corr{Pages 365, 385, and 387: scope of \(h_\alpha,e_\alpha,p_\alpha\) and Kostka numbers} There are two related scope inconsistencies in the notation. First, Definition 9.20 defines \[ e_\alpha,\quad h_\alpha,\quad p_\alpha \] only when \(\alpha=(\alpha_1,\ldots,\alpha_s)\) is a sequence of \emph{positive} integers. Theorems 9.64 and 9.69 later allow \(\alpha\) to have zero entries. This is harmless for \(e_\alpha\) and \(h_\alpha\), since \(e_0=h_0=1\), but it is formally outside Definition 9.20. One should extend the definition of \(e_\alpha,h_\alpha\) to finite weak compositions by allowing zero entries (which simply contribute factors \(e_0=h_0=1\)). It is better \emph{not} to make the analogous extension for \(p_\alpha\), since \(p_0\) has not been defined. Second, Definition 9.25 defines \(K_{\mu,\alpha}\) only for \(\mu\in\Par_N\) and \(\alpha\in\mathbb Z_{\geq0}^N\). Later statements use Kostka numbers outside this range: for example, Theorem 9.41 writes \(K_{\lambda,\lambda}\) for arbitrary partitions, and Theorems 9.64 and 9.69 use an arbitrary finite sequence \(\alpha=(\alpha_1,\ldots,\alpha_s)\), with no requirement \(s=N\); Theorem 9.69 may also involve \(K_{\lambda',\alpha}\) when \(\lambda'\) has more than \(N\) parts. The standard clean convention is to define \(K_{\lambda,\alpha}\), independently of an ambient number \(N\) of variables, for every partition \(\lambda\) and every finite weak composition \(\alpha\): it is the number of semistandard tableaux of shape \(\lambda\) having \(\alpha_i\) copies of the letter \(i\). With this convention the later theorems are well-formed exactly as intended. \corr{Page 388, Definition 9.73} The definition begins with a list \(z_1,\ldots,z_m\), but the displayed monomials are written \[ z_1^{\alpha_1}z_2^{\alpha_2}\cdots z_N^{\alpha_N}, \qquad \alpha\in\mathbb Z_{\geq0}^N. \] The \(N\)'s should be \(m\)'s: \[ z_1^{\alpha_1}z_2^{\alpha_2}\cdots z_m^{\alpha_m}, \qquad \alpha\in\mathbb Z_{\geq0}^m. \] \corr{Page 389, beginning of \S9.15} The recalled definition of \(p_\alpha\) is written \[ p_\alpha(x_1,\ldots,x_N)=\prod_{j\geq1}p_{\alpha_j}(x_1,\ldots,x_N). \] For the finite sequence \(\alpha=(\alpha_1,\ldots,\alpha_s)\), this should be \[ p_\alpha(x_1,\ldots,x_N)=\prod_{j=1}^{s}p_{\alpha_j}(x_1,\ldots,x_N). \] Otherwise \(\alpha_j\) is not defined for \(j>s\); padding by zeros would not fix the issue, since \(p_0\) has not been defined. \corr{Page 389, Theorem 9.76} There are two minor mistakes in the last paragraph of this proof. First, ``$\dfrac{\partial g}{\partial y_k}(g_1, \ldots, g_N)$ is nonzero in $\RR[y_1,\ldots,y_N]$'' should be ``$\dfrac{\partial g}{\partial y_k}(g_1, \ldots, g_N)$ is nonzero in $\RR[x_1,\ldots,x_N]$''. % an evaluated derivative is said to lie in % \(\mathbb R[y_1,\ldots,y_N]\), whereas after evaluation it lies in % \[ % \mathbb R[x_1,\ldots,x_N]. % \] Furthermore, the argument that ``$\mathbf{A}\mathbf{v} = \mathbf{0}$ forces $\mathbf{A}$ to be non-invertible, so that $J = \det(\mathbf{A}) = 0$ by a theorem of linear algebra'' does not work over the ring $\RR[x_1,\ldots,x_N]$ but only works over its fraction field $\RR(x_1,\ldots,x_N)$. Indeed, a square matrix over $\RR[x_1,\ldots,x_N]$ can be non-invertible without its determinant being $0$ (for instance, the \(1\times1\) matrix \([x_1]\) is not invertible but has nonzero determinant). To repair this, regard $\mathbf{A}$ and $\mathbf{v}$ as a matrix and vector over the fraction field $\RR(x_1,\ldots,x_N)$. % The proof constructs a nonzero polynomial vector \(v\) satisfying % \[ % Av=0 % \] % and concludes that \(A\) is noninvertible and hence \(\det A=0\). Over % \(\mathbb R[x_1,\ldots,x_N]\), noninvertibility by itself does not imply zero determinant % (for instance, the \(1\times1\) matrix \([x_1]\) is not invertible but has nonzero determinant). % A clean repair is to regard \(A\) and \(v\) as a matrix and vector over the fraction field % \[ % \mathbb R(x_1,\ldots,x_N). % \] % Then \(v\neq 0\) and \(Av=0\) imply that \(A\) is singular over a field, hence % \(\det A=0\). \corr{Page 393, proof of Theorem 9.86} In the displayed formula, replace ``$\sum\limits_{k=0}^n$'' by ``$\sum\limits_{k=0}^N$''. % After substituting \(t=1/X\) and \(x_i=-r_i\) in the generating-function identity, the % first displayed sum is written with upper limit \(n\): % \[ % X^N\sum_{k=0}^{n} e_k(-r_1,\ldots,-r_N)X^{-k}. % \] % The letter \(n\) is not defined here. The upper limit should be % \[ % N. % \] % The next displayed sum already has the correct upper limit \(N\). \corr{Pages 398 (last paragraph), 417 (``We can define evaluation homomorphisms \ldots''), and 421 (``Symmetric functions'' bullet point in Summary)} The text (and later the Chapter 9 summary) says that a polynomial algebra such as \[ \Lambda_N=\mathbb R[p_1,\ldots,p_N] \qquad\text{or}\qquad \Lambda=K[p_1,p_2,\ldots] \] admits an evaluation homomorphism sending the generators to arbitrary elements of an arbitrary algebra \(B\). If \(B\) is noncommutative, this is false unless the chosen images commute pairwise. Thus one should either assume that \(B\) is commutative, or require the chosen images of the generators to commute pairwise. \corr{Page 399, Definition 9.94} The definition \[ \omega(p_j)=(-1)^{j-1}p_j \] is said to hold ``for \(j\) between \(1\) and \(n\).'' The upper index should be \[ N, \] not \(n\). \corr{Page 411, proof of Theorem 9.121} In ``where $j$ is a fixed index between $1$ and $n$'', replace ``$n$'' by ``$N$''. % In the first Cauchy-identity calculation, the text says to replace \(t\) by \(y_j\), where % \(j\) is ``between \(1\) and \(n\).'' The \(y\)-variables are % \(y_1,\ldots,y_N\), so this should read % \[ % 1\leq j\leq N. % \] \corr{Page 414, Definition 9.130} A filling of a skew shape is allowed to take arbitrary integer values, \[ T:\mu/\nu\longrightarrow\mathbb Z, \] but the text then defines the content monomial of \emph{any} such filling by \[ \xx^T=\prod_{(i,j)\in\mu/\nu}x_{T(i,j)}. \] The variables \(x_0,x_{-1},\ldots\) have not been introduced. The content monomial should be defined only for fillings with values in \(\mathbb Z_{>0}\) (and, for a polynomial in \(N\) variables, for values in \([N]\)), just as in Definition 9.6 for straight shapes. \corr{Page 416, Theorem 9.136} The skew Pieri formulas contain \(K_{\lambda/\mu,\alpha}\) while summing over all \(\lambda\in\Par_N\). But \(\lambda/\mu\) is a skew shape only when \(\mu\subseteq\lambda\); no convention assigning zero to the other terms has been stated. One should either restrict the first sum to \(\lambda\supseteq\mu\) (and the second accordingly), or explicitly declare the corresponding skew Kostka number to be \(0\) when the containment fails. There is also the same Kostka-indexing issue noted above: the theorem allows \(\alpha\in\mathbb Z_{\geq0}^s\), whereas the preceding definition of skew Kostka numbers uses \(\alpha\in\mathbb Z_{\geq0}^N\). Defining (skew) Kostka numbers for arbitrary finite weak compositions resolves this uniformly. \corr{Page 416, scalar-product identity after Theorem 9.136} The finite-variable statement \[ \langle s_{\mu/\nu},f\rangle=\langle s_\mu,s_\nu f\rangle \] is asserted for a skew shape \(\mu/\nu\) with \(k\) cells, \(f\in\Lambda_N^k\), and \(N\geq k\). This hypothesis is not sufficient for the right-hand side to be defined under Definition 9.122: the right side lies in homogeneous degree \[ |\mu|=|\nu|+k, \] whereas the Hall scalar product on \(\Lambda_N^d\) was defined there only when \(N\geq d\). A sufficient finite-variable hypothesis is \[ N\geq|\mu|. \] More naturally, this adjointness identity can be stated in the abstract symmetric-function algebra \(\Lambda\), where there is no finite-variable degree restriction. \corr{Page 417, \S9.28} After introducing a finite sequence \(\alpha=(\alpha_1,\ldots,\alpha_s)\), the abstract symmetric functions are written \[ h_\alpha=\prod_{i\geq1}h_{\alpha_i}, \qquad e_\alpha=\prod_{i\geq1}e_{\alpha_i}. \] The products should run over \[ 1\leq i\leq s, \] unless one explicitly declares \(\alpha_i=0\) for \(i>s\). \corr{Page 420, Chapter 9 Summary} The displayed generating function for the complete homogeneous symmetric polynomials is incorrectly stated as \[ H_N(t)=\prod_{i=1}^N(1-x_it)^{-1} =\sum_{k=0}^{N}h_k(x_1,\ldots,x_N)t^k. \] The ``$\sum\limits_{k=0}^{N}$'' sign here should be ``$\sum\limits_{k=0}^{\infty}$'', as in Theorem 9.87. % Unlike \(e_k\), the complete homogeneous polynomial \(h_k\) does not vanish for \(k>N\). % The correct formula, as in Theorem 9.87, is % \[ % H_N(t)=\sum_{k=0}^{\infty}h_k(x_1,\ldots,x_N)t^k. % \] \corr{Page 420, Table 9.2} The finite-variable monomial expansions in Table 9.2 are written as sums over all partitions of the relevant degree, for example \[ s_\lambda=\sum_{\mu\in\Par(|\lambda|)} K_{\lambda,\mu}m_\mu. \] But \(m_\mu(x_1,\ldots,x_N)\) was defined only when \(\ell(\mu)\leq N\) (Remark 9.24). Unless \(N\) is known to be at least the degree, these sums should use \[ \Par_N(|\lambda|) \] (and similarly \(\Par_N(|\mu/\nu|)\) for the skew Schur expansion), or the table should explicitly impose the stable-range hypothesis \(N\geq\) degree. \corr{Page 420, Chapter 9 Summary: action of \(\omega\)} The summary states, without a degree restriction, that the finite-variable involution \[ \omega:\Lambda_N\longrightarrow\Lambda_N \] satisfies \(\omega(s_\mu)=s_{\mu'}\). Theorem 9.96 proved this only in the stable range \[ |\mu|\leq N, \] and the unrestricted finite-variable statement is false. For example, when \(N=1\), \(\Lambda_1=\mathbb R[p_1]\) and \(\omega\) is the identity, so \[ \omega(s_{(2)}(x_1))=x_1^2, \qquad s_{(1,1)}(x_1)=0. \] The unrestricted identity is valid in the abstract symmetric-function algebra \(\Lambda\); in \(\Lambda_N\) the stable-range hypothesis should be retained. \corr{Page 421, Chapter 9 Summary, ``Symmetric Functions'' bullet point} The summary repeats the claim that one may define an evaluation homomorphism on the abstract symmetric-function algebra by sending each \(p_n\) to ``any element'' of a \(K\)-algebra. As on pages 398 and 417, this is correct for a commutative target algebra; for a noncommutative target, the chosen images must commute pairwise. \corr{Page 423, Exercise 9-55} Replace ``$x_n$'' by ``$x_N$''. % The exercise asks for the coefficient of % \[ % m_\lambda(x_1,\ldots,x_n) % \] % but the rest of the exercise uses \(N\) variables and \(s\times N\) matrices. The final % variable should be % \[ % x_N, % \] % not \(x_n\). \corr{Page 424, Exercise 9-72} The displayed recursion is claimed for \(k,N\geq 1\), but when \(N=1\) its right-hand side contains symmetric polynomials in the empty list of variables, such as \(e_k(x_1,\ldots,x_{N-1})=e_k()\), which have not been defined in the text. One can either state the recursion for \(N\geq2\) and take the \(N=1\) formulas as initial conditions, or extend the definitions by \[ e_0()=h_0()=1,\qquad \text{ and } \qquad e_r()=h_r()=0\quad\text{for } r \neq 0. \] With this extension (which is standard in the literature) the stated recursion is valid also for \(N=1\). \corr{Page 424, Exercise 9-73} The ranges of \(n\) and \(k\) should be specified. As written, the formulas can contain negative subscripts when \(k>n\), while \(k=0\) leads to symmetric polynomials in zero variables. Without introducing additional conventions, the exercise holds for $1\leq k\leq n$. If the boundary cases are desired as well, one can use \[ e_0()=h_0()=1,\qquad \text{ and } \qquad e_r()=h_r()=0\quad\text{for } r \neq 0. \] together with the usual zero conventions for Stirling numbers. \corr{Page 426, Exercise 9-94} As written, ``an algebra isomorphism of \(\Lambda_N\) sending each \(p_i\) to \(-p_i\)'' is ambiguous and is false if ``each'' means every \(i\geq1\). For example, in one variable \(p_2=p_1^2\), so a homomorphism with \(p_1\mapsto-p_1\) must send \[ p_2=p_1^2\longmapsto p_1^2=p_2, \] not to \(-p_2\). The finite-variable version should say that the isomorphism should send \[ p_i\longmapsto-p_i\qquad \text{ for all } 1\leq i\leq N. \] With this interpretation, the simple formulas \[ h_n\longmapsto(-1)^n e_n,\qquad e_n\longmapsto(-1)^n h_n \] hold for \(n\leq N\). Alternatively, the exercise can be stated in the abstract symmetric-function algebra \(\Lambda\), where all \(p_i\) are independent generators and the formulas hold for every \(n\). \corr{Page 426, Exercise 9-95} The exercise asks: \[ \text{``In the proof of Theorem 9.95(b), where is the assumption \(n\leq N\) needed?''} \] Part (b) has no such variable \(n\) or hypothesis. The intended reference is almost certainly \textbf{Theorem 9.95(c)}, whose proof explicitly begins ``For \(1\leq n\leq N\)'' and uses part (b) on all partitions of \(n\). \corr{Page 439, proof of Theorem 10.22} In the second-to-last sentence of the proof, replace ``$m_i=|\rho^i|$'' by ``$m_i=|\nu^i|$. %where \(\nu^i\) is the \(i\)-th \(k\)-quotient. \corr{Page 440, Definition 10.23} In the last sentence of the definition, replace ``$c_k(z)\equiv r\pmod{k}$'' by ``$c(z)\equiv r\pmod{k}$''. % The \(k\)-content of an object \(z\) is defined as the unique % \(r\in\{0,1,\ldots,k-1\}\) satisfying % \[ % c_k(z)\equiv r\pmod{k}. % \] % This is circular: \(c_k(z)\) is the quantity being defined. The congruence should use the % ordinary content: % \[ % \boxed{\,c(z)\equiv r\pmod{k}\,}. % \] \corr{Page 440, construction immediately after Figure 10.1} In constructing the zeroth \(3\)-quotient, the text says to mark the cells whose associated frontier steps ``both have content zero.'' The construction is based on residue classes modulo \(3\), so this should read \[ \text{``both have \(3\)-content zero.''} \] \corr{Page 442, Remark 10.26} In ``$t_i\mathbin{\bullet} f=\sgn(t_i)f$ for all $i$ between $1$ and $N-1$'', replace ``$N-1$'' by ``$k$''. Indeed, the $t_i$ are the factors of the given factorization $w=t_1t_2\cdots t_k$, so there is no reason why there should be exactly $N-1$ of them. % After writing a permutation as a product of basic transpositions % \[ % w=t_1t_2\cdots t_k, % \] % the proof says that it suffices to have checked % \[ % t_i\mathbin{\bullet} f=\sgn(t_i)f % \quad\text{``for all \(i\) between \(1\) and \(N-1\).''} % \] % Here \(i\) indexes the factors \(t_1,\ldots,t_k\), not the possible adjacent % transpositions. The phrase should be % \[ % \text{``for all \(1\leq i\leq k\),''} % \] % or, more cleanly, one should first say that every basic transposition acts on \(f\) by % \(-1\), and then apply this to each factor in a chosen expression for \(w\). \corr{Page 449, proof of Theorem 10.39} The proof says that \[ \sgn(v^*)\text{ differs from }\sgn(v) \text{ by }\sgn(R)=(-1)^{\operatorname{spin}(R)}, \] ``which is the number of beads that bead \(i\) passes over when it moves''. Of course, this is not literally true: The sign \((-1)^{\operatorname{spin}(R)}\) is not a number of beads. What the preceding example established is \[ \operatorname{spin}(R) = \#\{\text{beads passed over by bead \(i\)}\}, \] and hence the resulting sign change is \((-1)^{\operatorname{spin}(R)}\). \corr{Pages 455--456, Definition 10.48 and Theorem 10.50} Definition 10.48 allows a weak composition \(\alpha\in\mathbb Z_{\geq0}^s\) and requires \(\nu_i/\nu_{i-1}\) to be an \(\alpha_i\)-ribbon. But Definition 10.7 defines a ribbon as a nonempty skew shape, so an \(\alpha_i=0\) stage has not been defined. Later Definition 10.63 explicitly speaks of ``nonzero rim-hooks,'' confirming that zero stages are intended. For rim-hook tableaux it would be natural to adopt the convention that a \(0\)-ribbon is the empty skew shape, contributes no change of partition, and has sign \(+1\). There is a separate but related issue in Theorem 10.50. It is stated for arbitrary \(\alpha\in\mathbb Z_{\geq0}^t\), but the polynomial \(p_\alpha\) was defined only for sequences of positive integers; in particular \(p_0\) has not been defined. Thus the theorem should either assume \[ \alpha_i>0\qquad\text{ for all }1\leq i\leq t, \] or explicitly declare that zero entries of \(\alpha\) are to be deleted before forming \(p_\alpha\) and the corresponding rim-hook tableau: \[ p_\alpha := \prod_{\substack{1\leq i\leq t;\\ \alpha_i>0}} p_{\alpha_i} \qquad \text{ for all } \alpha = (\alpha_1, \alpha_2, \ldots, \alpha_t) \in \ZZ_{\geq 0}^t. \] The latter is the best option for Definition 10.63, since regarding a partition in $\Par_N$ as an $N$-tuple often causes it to contain zeroes. \corr{Page 458, beginning of \S10.13} The set \(X\) is defined to consist of pairs \((v,T)\), where \(v\) is a justified labeled abacus and \(T\) is merely said to be ``a semistandard tableau using letters in \(\{1,\ldots,N\}\).'' The shape of \(T\) is missing. Since the next displayed generating function is \[ a_{\delta(N)}s_\lambda, \] the intended definition is \[ T\in\operatorname{SSYT}_N(\lambda) \] (with semistandardness interpreted relative to the ordering \(<_v\)). \corr{Page 461, proof of Theorem 10.58} Replace ``take the scalar product of both sides with a given partition \(\lambda\)'' by ``take the scalar product of both sides with $s_\lambda$ for a given partition \(\lambda\)''. % After expanding \(s_\mu p_\nu\), the proof says: % \[ % \text{``Now take the scalar product of both sides with a given partition \(\lambda\).''} % \] % A partition is not an element of the scalar-product space. This should read % \[ % \text{``take the scalar product of both sides with \(s_\lambda\).''} % \] \corr{Pages 465--466, proof of Theorem 10.61} The proof of the Second Jacobi--Trudi Formula has a genuine finite-variable scope problem. The theorem assumes only \[ \lambda_1=n\leq N, \] and then says to obtain the result by applying the finite-variable involution \(\omega\) to the First Jacobi--Trudi Formula for \(\lambda'/\mu'\). However, Theorem 10.59 established \[ \omega(s_{\alpha/\beta})=s_{\alpha'/\beta'} \] in \(N\) variables only under the stronger stable-range hypothesis \(N\geq|\alpha|\). Outside that range the corresponding finite-variable assertion is false. For example, in one variable \(\omega\) is the identity, so \[ \omega(s_{(2)}(x_1))=x_1^2 \quad\text{whereas}\quad s_{(1,1)}(x_1)=0. \] Thus the stated Second Jacobi--Trudi Formula is standard and correct, but the printed proof does not establish it under the stated hypothesis. A clean repair is to apply \(\omega\) in the \emph{abstract} symmetric-function algebra, where \(\omega(s_{\alpha/\beta})=s_{\alpha'/\beta'}\) holds without a finite-variable restriction, prove the determinant identity there, and then specialize to \(N\) variables. Alternatively, the printed argument works after imposing the unnecessarily stronger assumption \(N\geq|\lambda|\). \corr{Page 466, beginning of \S10.16} The vector identity \[ \mathbf e=\mathbf K^{\operatorname{tr}}\omega(\mathbf s) \] is potentially incorrect if \(\omega(\mathbf s)\) means applying the finite-variable involution $\omega$ entrywise to the vector of all Schur polynomials indexed by \(\Par_N\). The identity \(\omega(s_\lambda)=s_{\lambda'}\) is only valid when $\lambda$ has size $\leq N$, whereas this paragraph ranges over all degrees. The intended relation is better written \[ \mathbf e=\mathbf K^{\operatorname{tr}}\mathbf s^\vee, \qquad \text{ where } \mathbf s^\vee=(s_{\lambda'}:\lambda\in\Par_N), \] with the Kostka matrices understood degree by degree. The subsequent explicit inverse formulas remain meaningful with this interpretation. \corr{Page 467, proof of Theorem 10.64} In the paragraph where you cancel the colliding-beads addends, replace ``and switching $e(i)$ and $e(j)$ in the exponent vector'' by ``and leaving $e$ unchanged''. In fact, there is no need to change $e$ in order to preserve the weight, since an object has signed weight \[ \sgn(w) \prod_{r=1}^N x_{w(r)}^{\,N-r+e(r)}, \] which is symmetric in $x_{w(i)}$ and $x_{w(j)}$ if the beads $w(i)$ and $w(j)$ collide (indeed, the beads $w(i)$ and $w(j)$ collide if and only if $N-i+e(i)=N-j+e(j)$). However, if you do switch $e(i)$ and $e(j)$, then the factors $x_{w(i)}^{N-i+e(i)}$ and $x_{w(j)}^{N-j+e(j)}$ become $x_{w(j)}^{N-i+e(j)}$ and $x_{w(i)}^{N-j+e(i)}$, which does not preserve the weight. % For example, take \(N=2\), \(e=(1,2)\), and the identity labeling % \(w(1)=1,w(2)=2\). The two beads land at the same position \(2\), and the original % monomial weight is % \[ % x_1^2x_2^2. % \] % Swapping only the labels preserves this weight and reverses the sign. Swapping % \(e(1)\) and \(e(2)\) as well instead destroys weight preservation. \corr{Page 469, Theorem 10.66} The Littlewood--Richardson rule is stated ``for all partitions \(\lambda,\mu,\nu\),'' but its right side counts tableaux of skew shape \(\lambda/\nu\). That skew shape has only been defined when \[ \nu\subseteq\lambda. \] Moreover, the content \(\mu\) must have the same size as the skew shape: \[ |\mu|=|\lambda|-|\nu|. \] Thus these hypotheses should either be included explicitly, or the coefficient \(c^\lambda_{\nu,\mu}\) should first be extended by the convention that it is \(0\) outside these containment and degree conditions. The latter remedy is better, since it is consistent with later use of $c^\lambda_{\nu,\mu}$. (For instance, in Theorem 10.72, you don't presuppose anything about the sizes and containment relations of $\lambda,\mu,\nu$.) \corr{Page 470, Example 10.67} ``parentheis string'' should read {``parenthesis string.''} \corr{Page 470, proof of Theorem 10.66} In the construction of the involution, the sentence ``One may verify that the new word is the word of a tableau \(T'\in\operatorname{SSYT}_N(\lambda/\nu)\), relative to the ordering \(<_{v'}\)'' hides a nontrivial verification. Here is the missing argument. The beads \(i>_v j\) are adjacent, and \(v'\) is obtained from \(v\) by interchanging them. Hence \(<_{v'}\) differs from \(<_v\) only by reversing the order of \(i\) and \(j\); all comparisons involving any third letter are unchanged. It therefore suffices to check adjacent row and column comparisons in which both entries belong to \(\{i,j\}\). For the rows, use the parenthesis matching from the proof. Since \(i<_{v'}j\), a failure of weak increase in a row of \(T'\) involving these two letters would mean that some \(j\) occurs in a cell strictly to the left of some \(i\) in the same row. In the parenthesis encoding appropriate to \((v',T')\), the \(j\)'s are left parentheses and the \(i\)'s are right parentheses. Thus this row contains a left parenthesis somewhere before a right parenthesis, so the matching contains a matched pair entirely within this row. The construction preserves which parenthesis positions are matched; hence, this matched pair must have already been matched in $T$. In the original tableau \(T\), the two cells of this matched pair contain an \(i\) to the left of a \(j\). But \(j<_v i\), contradicting the weak increase of that row of \(T\). For the columns, suppose two vertically adjacent cells of \(T'\) each contain \(i\) or \(j\). Let us call these two cells $(r,c)$ and $(r+1,c)$. We must prove that $T'(r,c) = i$ and $T'(r+1,c) = j$. Clearly, each of $T(r,c)$ and $T(r+1,c)$ must be either $i$ or $j$, since the transformation of $T$ into $T'$ changes no letters other than $i$ and $j$. % We must prove that these two cells must contain the entries $i$ and $j$, with the $i$ being in the top cell and the $j$ being in the bottom cell. % We know that the corresponding cells of \(T\) also each contain % \(i\) or \(j\), since the construction changes no other letters. Because \(T\) is column-strict and \(j<_v i\), we thus have $T(r,c) = j$ and $T(r+1,c) = i$. In the word of $T$, these entries $j$ and $i$ become a right and a left parenthesis, respectively. We shall now show that both of these parentheses are matched (though not necessarily to each other). % We consider the tableau $T$. % Let the \(j\) be in cell \((r,c)\) and the \(i\) directly below it in cell \((r+1,c)\). First consider the \(j\). Consider any $j$ in row $r$ that lies in column $c$ or further left. % Say that this $j$ is the $p$-th $j$ in row $r$ counted from the left. % Hence, each of the leftmost $p$ many $j$'s in this row % lies weakly to the left of column $c$, and therefore Then, this $j$ has a cell directly below it (since skew rows are intervals, the lower row starts weakly to the left of the upper row, and it extends at least through column \(c\)). The entry in this latter cell is strictly larger than \(j\) (since $T$ is column-strict) and less than or equal to \(i\) (since $T$ is weakly increasing along rows, and there is an $i$ to the right of this entry). Since \(j\) and \(i\) are adjacent in the alphabet, this entails that this entry is $i$. Thus, we have shown that each $j$ in row $r$ that lies in column $c$ or further left must have an $i$ directly below it (in row $r+1$). Similarly, we can show that each $i$ in row $r+1$ that lies in column $c$ or further right must have a $j$ directly above it (in row $r$). Therefore, rows $r$ and $r+1$ of $T$ look as follows: \begin{align} \ytableausetup{notabloids} \begin{ytableau} \none & \none & *(yellow)\cdots & *(yellow)u_2 & *(yellow)u_1 & *(green)j & *(green)j & *(green)\cdots & *(green)j & \ast & \ast & \ast & \ast & \ast \\ \ast & \ast & \ast & \ast & \ast & *(green)i & *(green)i & *(green)\cdots & *(green)i & *(yellow)v_1 & *(yellow)v_2 & *(yellow)\cdots \end{ytableau} , \end{align} where $v_1, v_2, v_3, \ldots$ satisfy $v_\ell>_v i$, whereas $u_1, u_2, u_3, \ldots$ satisfy $u_\ell<_v j$, and where the asterisks denote entries that we are not interested in (they can include $i$'s and $j$'s, but they might also not exist). Note that the columns that have a $j$ in row $r$ and an $i$ in row $r+1$ simultaneously are highlighted in green, whereas the cells of row $r$ that lie to their left as well as the cells of row $r+1$ that lie to their right are highlighted in yellow. In particular, the $i$ in cell $(r+1,c)$ and the $j$ in cell $(r,c)$ are green. Now, in the reading word $w(T)$, the green and yellow entries form a contiguous block \[ i i \cdots i v_1 v_2 \cdots \cdots u_2 u_1 j j \cdots j. \] All the $i$'s in this block are left parentheses, and all the $j$'s in this block are right parentheses. Since the intermediate entries $v_1 v_2 \cdots \cdots u_2 u_1$ are not parentheses (because $v_\ell>_v i$ and $u_\ell<_v j$), and since there are equally many $i$'s and $j$'s in this block, we conclude that the left parentheses in this block are matched bijectively with the right parentheses in this block, entirely within the block. In particular, the $i$ in cell $(r+1,c)$ and the $j$ in cell $(r,c)$ are both matched positions (although they need not be matched with each other). Now, the parenthesis modification in the construction of $T'$ leaves the parenthesis symbols at all matched positions unchanged. When the resulting parenthesis string is decoded for $T'$, however, left parentheses represent $j$ and right parentheses represent $i$, rather than $i$ and $j$ as they did for $T$. Thus, any $i$ in a matched position of $T$ becomes a $j$ in $T'$, and vice versa. Hence, the $i$ in cell $(r+1,c)$ of $T$ and the $j$ in cell $(r,c)$ of $T$ become $j$ and $i$ in $T'$, respectively. This is exactly the strict order required by \(<_{v'}\) to ensure that the entries are strictly increasing in column $c$. Comparisons with third letters remain valid because \(i\) and \(j\) are adjacent. Therefore \(T'\) is indeed semistandard relative to \(<_{v'}\). Example 10.67 sketches the row and column checks in a particular case, but the general verification is omitted from the proof itself. \corr{Page 474, Theorem 10.72} % There are two missing hypotheses in the alternate formula for Littlewood--Richardson % coefficients. The tableau content is stated to be % \[ % \lambda-\nu=(\lambda_i-\nu_i:1\leq i\leq N). % \] % For this to be a weak composition one needs % \[ % \nu\subseteq\lambda. % \] % Also, because the tableau has shape \(\mu\), one needs the homogeneous-degree condition % \[ % |\lambda|=|\mu|+|\nu|. % \] % Without these conditions, ``content \(\lambda-\nu\)'' need not even be defined in the sense % used in the book. As with Theorem 10.66, one can instead explicitly extend the % Littlewood--Richardson coefficients by zero outside the natural range. There is a typographical error in the statement: ``coefficent'' should read ``coefficient.'' \corr{Page 475, Table 10.1} Two finite-variable formulas in the summary table have lost the hypotheses under which they were proved. First, \[ \langle s_{\lambda/\mu},f\rangle = \langle s_\lambda,s_\mu f\rangle \] is written merely ``for \(f\in\Lambda_N\).'' Theorem 10.57 assumes \[ k=|\lambda|-|\mu|,\qquad f\in\Lambda_N^k,\qquad N\geq|\lambda|. \] The degree condition is also needed for the two scalar products to live in the homogeneous spaces on which the finite-variable Hall scalar product was defined. Second, the table writes \[ \omega(s_{\lambda/\mu})=s_{\lambda'/\mu'} \] without a stable-range restriction. Theorem 10.59 assumes \(N\geq|\lambda|\); without such a condition the finite-variable statement is false. The unrestricted formula belongs naturally to the abstract symmetric-function algebra. % \corr{Page 478, Exercise 10-23} % The integer $n$ in $\mathcal A_N^n$ is not quantified in the exercise. It should say, for % example, ``For each $n\in\ZZ_{\geq0}$, verify that $\mathcal A_N$ and % $\mathcal A_N^n$ are subspaces of $\RR[x_1,\ldots,x_N]$.'' Strictly speaking, the same % minor omission already occurs in Definition 10.31 on page 443, where $\mathcal A_N^n$ is % introduced without first quantifying $n$. \corr{Page 479, Exercise 10-46} The exercise asks the reader to explain why \[ \omega(h_\mu)=e_\mu,\qquad \omega(e_\mu)=h_\mu \] are special cases of Theorem 10.59, but no finite-variable range is specified. As an unrestricted assertion in \(\Lambda_N\), this is false: for \(N=1\) and \(\mu=(2)\), \[ \omega(h_2)=h_2=x_1^2,\qquad e_2=0. \] A clean version is to work in the abstract symmetric-function algebra, or to impose a stable-range hypothesis such as \(N\geq|\mu|\) before applying Theorem 10.59. \corr{Pages 479--480, Exercise 10-57} The first sentence asks for $I(v^0,T)$, consistently with the notation $v^0$ used in the proof of Theorem 10.66 for the standard justified abacus. But the displayed definition immediately below writes \[ v_0=5432100\cdots . \] Replace $v_0$ by $v^0$. \corr{Page 483, proof of Theorem 11.7(b)} Replace ``$\prod_{n=0}^\infty F_n$'' by ``$\prod_{n=0}^\infty (1+F_n)$''. Replace ``$\prod_{n=0}^m F_n$'' by ``$\prod_{n=0}^m (1+F_n)$''. Replace ``of the factors $F_n$'' by ``of the factors $1+F_n$''. % The theorem concerns % \[ % \prod_n (1+F_n), % \] % but the proof twice changes this to \(\prod_n F_n\). Both occurrences should be % \[ % \prod_n (1+F_n). % \] % The recurrence immediately afterward, % \[ % P_{m+1}=P_m(1+F_{m+1}), % \] % already has the correct form. \corr{Page 484, Theorem 11.10} There are two small domain/indexing issues in the Infinite Product Rule for Weighted Sets. First, the hypothesis uses \[ \operatorname{minwt}(S_k-\{o_k\}), \] but it is possible that \(S_k=\{o_k\}\), in which case the minimum of the empty set has not been defined. This should be remedied by adopting the natural convention \[ \operatorname{minwt}(\varnothing)=+\infty. \] Second, in the weight-additivity hypothesis, replace ``\(u\) is constructed from $(u_k:k\geq0)$'' by ``\(u\) is constructed from $(u_k:k\geq1)$''. The same ``\(k\geq0\)'' typo is repeated in the Chapter 11 Summary (page 507). \corr{Page 491, justification of Method 2.70 after Theorem 11.21} Let \(k\) be the order of the recurrence. The text writes \[ \chi(z)=\prod_{i=1}^{k}(z-r_i)^{m_i} \] and subsequently sums over \(i=1,\ldots,k\). This indexing is wrong when the characteristic polynomial has repeated roots: there need not be \(k\) distinct roots. One should introduce, say, \(\ell\) distinct roots \(r_1,\ldots,r_\ell\), with multiplicities \(m_1,\ldots,m_\ell\) satisfying \[ m_1+\cdots+m_\ell=k, \] and write \[ \chi(z)=\prod_{i=1}^{\ell}(z-r_i)^{m_i}, \qquad P(z)=\prod_{i=1}^{\ell}(1-r_i z)^{m_i}. \] All subsequent outer sums in this argument should likewise run from \(1\) to \(\ell\). There is one further tacit step in this application of Theorem 11.18. That theorem allows a polynomial part \(h\) in the partial fraction decomposition, and its coefficient formula accordingly contains the extra term \(h|_{z^n}\). But the uniqueness proof of Theorem 11.18 identifies \(h\) as the quotient obtained when the numerator is divided by the denominator. Thus one has the useful porism \[ \deg f<\deg g \quad\Longrightarrow\quad h=0. \] In the present application, \(\deg G 0$. Indeed, in the case $n = 0$ (which is explicitly allowed in Definitions 11.41 and 11.42), the one-letter word $w = 1$ satisfies the weight conditions of Theorem 11.43, but is not a list of $0$ terms (since that list would be the empty word). % The Weight Characterization of Lists of Terms is false for the allowed boundary case % \(n=0\). Definitions 11.41 and 11.42 explicitly allow \(n=0\), but the one-letter word % \[ % w=1 % \] % has % \[ % \operatorname{wt}(w)=0=-n % \] % and has no nonempty proper prefixes, so it satisfies the two displayed weight conditions. % It is nevertheless not a list of zero terms; the unique list of zero terms is the empty word. The proof also silently fails at \(n=0\): it prefixes the symbol \(n\) to \(w\) and claims that \(nw\) satisfies the term criterion, but when \(n=0\) its first symbol already has weight \(-1\). % The clean fix is to state Theorem 11.43 for % $n>0$ and handle \(n=0\) separately. The corresponding characterization in the Chapter 11 (page 509) Summary needs the same qualification. \corr{Page 505, proof of Theorem 11.47} ``which satsifies'' should read {``which satisfies.''} \corr{Page 507, Chapter 11 Summary: symmetric function formula for $1/F$} Part (d) of the ``Multiplicative Inverses of Formal Series'' bullet points needs the requirement $a_0 = 1$ (not just the $a_0 \neq 0$ requirement of the whole bullet point). Arguably, this may be implicit in ``the homomorphism sending $e_n$ to $a_n$'', provided that the $n$ is understood to range over $\ZZ_{\geq 0}$ (since this implies, in particular, that the homomorphism sends $e_0 = 1$ to $a_0$, and thus $a_0 = 1$ follows); but a reader might just as well understand $n$ to range over $\ZZ_{>0}$, and then this requirement is nowhere to be seen. % The summary begins its multiplicative-inverse discussion with an arbitrary invertible % \[ % F(z)=\sum_{n\geq0}a_nz^n, % \qquad a_0\neq0, % \] % but part (d) then says that, if % \[ % \phi:\Lambda\longrightarrow K,\qquad \phi(e_n)=a_n, % \] % then the inverse coefficients satisfy % \[ % u_n=\phi((-1)^n h_n). % \] % The derivation in \S11.3 assumed instead that % \[ % F(z)=1+\sum_{n\geq1}a_nz^n, % \] % so \(a_0=1\). Without this normalization the summary formula is already wrong at % \(n=0\), since its right side is \(1\) whereas \(u_0=a_0^{-1}\). % Thus part (d) should assume \(a_0=1\). For general \(a_0\neq0\), first normalize % \(F/a_0\), apply the symmetric-function formula to that series, and multiply the resulting % inverse by \(a_0^{-1}\). \corr{Page 509, Chapter 11 Summary} There are two definite typographical errors near the end of the summary. In the Cycle Lemma item, the number of lists using \(k_i\) copies of \(i\) for \(0\leq i\leq t\) is printed with the multinomial coefficient \[ \binom{s}{k_0,k_1,\ldots,k_s}. \] The final lower index should be \[ k_t, \] not \(k_s\). In the ``Compositional Inverses of Formal Series'' item, replace ``$F=x/R$'' by ``$F=z/R$''. % the text says % \[ % F=x/R. % \] % The formal variable throughout the chapter is \(z\), so this should be % \[ % F=z/R. % \] \corr{Page 509, Exercise 11-13} There is a small edge case in the instruction to ``let $(F_{k_n})$ be the subsequence of nonzero terms of $(F_n)$.'' If $(F_n)$ has only finitely many nonzero terms, there is no infinite subsequence $(F_{k_n}:n\geq0)$ to which the displayed infinite sum or product can refer. One should either assume that there are infinitely many nonzero terms, or allow $(F_{k_n})$ to be a finite list and handle that case separately (where convergence is immediate). The same qualification applies to the remark following Theorem 11.7 that one may ``always'' drop zero summands or factors equal to $1$ in order to arrange that all terms are nonzero. \corr{Page 510, Exercise 11-17} This exercise asks the reader to check convergence of the infinite products at the end of \S9.28, but those products live in the rings \[ K[[t,x_1,x_2,\ldots]] \quad\text{and}\quad K[[t,x_1,x_2,\ldots,y_1,y_2,\ldots]], \] whereas Chapter 11 has only defined convergence for sequences in the one-variable ring $K[[z]]$. In particular, Theorem 11.7 cannot simply be applied using $t$-adic order: for example, every factor $1+t x_i$ differs from $1$ in $t$-degree $1$. The intended statement is correct after extending the definition of convergence coefficientwise to these infinite-variable formal power series rings. Then each fixed monomial is affected by only finitely many of the factors. For instance, the coefficient of a given monomial in \[ \prod_{i\geq1}(1+t x_i) \] stabilizes once all variables occurring in that monomial have appeared; the same local-finiteness argument works for the doubly indexed Cauchy product \[ \prod_{i,j\geq1}(1-tx_i y_j)^{-1}. \] Thus the exercise needs a brief extension of the formal convergence framework before it is literally well-posed. \corr{Page 511, Exercise 11-47} Replace ``$g:B\to C$'' by ``$q:B\to C$''. % The exercise introduces functions % \[ % p:A\longrightarrow B % \qquad\text{and}\qquad % g:B\longrightarrow C, % \] % but both parts then refer to \(p,q\) and \(q\circ p\). Either the second function should % have been named % \[ % q:B\longrightarrow C, % \] % or every subsequent \(q\) should be replaced by \(g\). \corr{Page 513, Exercise 11-64(g)} Part (g) is false because the exponent \(r\) is itself allowed to be a formal power series. The exercise defines \[ F^r=\exp(r\log F) \qquad \text{(where }F(0)=1,\ r\in K[[z]]\text{)}, \] and then claims \[ \frac{d}{dz}F^r=rF^{r-1}F'. \] This omits the derivative of \(r\). The correct formula is \[ \boxed{ \frac{d}{dz}F^r = F^r\left(r'\log F+r\frac{F'}F\right) = F^r r'\log F+rF^{r-1}F'. } \] The printed formula is valid when \(r\) is a constant scalar in \(K\), but not for general \(r\in K[[z]]\). For instance, taking \(F=1+z\) and \(r=z\) produces a nonzero extra term \((1+z)^z\log(1+z)\). \corr{Page 514, Exercises 11-82 and 11-83} Both exercises should specify $n\geq1$. Every term is a nonempty word, so this is the natural range; without it, the case $n=0$ asks for binary trees with $-1$ nodes in Exercise 11-82 and for lattice paths ending at $(-1,-1)$ in Exercise 11-83. \corr{Page 514, Exercise 11-86(c)} ``a given sequence \(F\in V\)'' should be ``a given formal series \(F\in V\)''. % The exercise asks for a procedure for expressing ``a given sequence \(F\in V\)'' % as a linear combination of basis elements. Since \(V\) was defined as a vector space of % formal power series, ``sequence'' should read % \[ % \text{``formal series.''} % \] \corr{Page 518, proof of Theorem 12.4 (Chung--Feller)} The integer \(k\) has already been fixed as the desired number of flaws, but the construction of \(\phi_k\) reuses \(k\) as the position of the first step at which the newly constructed path goes below the diagonal: \[ %c_1=a_1,\ c_2=a_2,\ldots,\quad \text{``until we reach a horizontal step \(c_k=a_k\)''}. \] These two $k$'s need not be equal. Indeed, in the displayed example \(k=6\), while the first switch occurs after transferring the five steps \(J,K,L,M,N\). The stopping index should be given a new name, say \(\ell\): \[ c_1=a_1,\ c_2=a_2,\ \ldots,\ c_\ell=a_\ell, \] followed by \[ c_{\ell+1}=b_1,\ c_{\ell+2}=b_2, \ \ldots,\ c_{\ell+m}=b_m, \qquad c_{\ell+m+1}=a_{\ell+1},\ \ldots . \] The rest of the construction is unchanged. \corr{Page 525, Remark 12.17} In the discussion of linear probing for hashing, when \(h(i)\) is occupied, item \(i\) is said to be put in ``the earliest position after position \(i\).'' It should be put in \[ \text{the earliest position after position \(h(i)\).} \] Otherwise the stated correspondence with parking functions is not correct. \corr{Page 531, proof of Theorem 12.30 and Exercise 12-39(b)} The proof of the irreducible-polynomial counting formula begins by taking a finite extension field \[ K\supseteq F,\qquad |K|=q^n, \] and later uses that \(K\) is a splitting field for \(x^{q^n}-x\). Existence of such a field (or extension of \(F\)) is therefore an input to the printed proof. This creates a logical dependency problem with Exercise 12-39(b), which asks the reader to \emph{use Theorem 12.30} to prove that a field exists for every prime-power cardinality. If finite-field existence is among the field-theory facts being imported before Theorem 12.30, then Exercise 12-39(b) is circular as a purported proof of that existence theorem. One should either state explicitly before Theorem 12.30 that the existence of the extension \(K/F\) of degree \(n\) is being assumed from field theory, and not present Exercise 12-39(b) as an independent proof; or else give a proof of Theorem 12.30 that does not presuppose finite-field existence in the degree being constructed. There is also a small omitted case inside the proof. The argument for an irreducible \(g\) of degree \(d\) starts with a nonzero root \(z\). When \(g=x\) (the degree-\(1\) irreducible with root \(0\)), this does not apply. That case is immediate and should be separated before assuming \(z\neq0\). \corr{Pages 542--543, Theorems 12.51--12.53} The Laplace expansion is stated for every \(A\in M_n(\mathbb R)\), but for \(n=1\) the minor \(A[1\mid1]\) is a \(0\times0\) matrix. Definition 12.39 defines \(M_n(\mathbb R)\) only for positive \(n\), and no determinant of the empty matrix has been defined. Definition 12.52 of the classical adjoint has the same issue for a \(1\times1\) matrix. The standard clean convention is to allow the unique \(0\times0\) matrix and define its determinant by \[ \det(\varnothing)=1. \] With this convention the Laplace formula and the adjoint formula include \(n=1\) exactly as written (and all the other standard properties of determinants are true). Alternatively, one must state the Laplace theorem for \(n\ge2\) and treat the \(1\times1\) cases separately. \corr{Page 551, proof of Lemma 12.72} There are two boundary/notation problems in the induction. First, after the initial cell \(c_1=(i_1,j_1)\), the proof says that each possible \(c_2\) is chosen with probability \[ 1/({h(c)-1})=1/({h(i_1,j_1)-1}). \] Since \(c=(r,s)\) is the \emph{terminal corner}, \(h(c)=1\), so the first denominator is zero. The intended expression is \[ \boxed{1/({h(c_1)-1})=1/({h(i_1,j_1)-1})}. \] Second, the two possible next cells are written \[ c_2=(i_1,j_2)\qquad\text{or}\qquad c_2=(i_2,j_1). \] But \(j_2\) is undefined when \(J=\{j_1\}\), and \(i_2\) is undefined when \(I=\{i_1\}\). The intended argument becomes uniform if, after writing \[ I=\{i_1<\cdots1\). When \(j=1\), the symbol \(u_{j-1}=u_0\) does not exist. The \(j=1\) case is actually easier: after the preceding slides, one has already reached \[ u_1\,w_k\,u_2\cdots u_{k-1}, \] which is exactly the reading word of the tableau obtained when \(w_k\) bumps \(u_1\) into the second row. Thus one should simply separate \(j=1\) before invoking the displayed inequality. \corr{Pages 555--557, Definition 12.82 and Theorem 12.84} There is a small but real terminological imprecision in the definition of \(\operatorname{inc}_k\) and \(\operatorname{dec}_k\). A ``set of \(k\) disjoint increasing subsequences'' is literally written as \(\{I_1,\ldots,I_k\}\). If the word has length \(n\), then for sufficiently large \(k\) no such set exists (and allowing the empty subsequence does not fix the literal set notation, since a set cannot contain several copies of \(\varnothing\)). Nevertheless \(\operatorname{inc}_k\) and \(\operatorname{dec}_k\) are defined for every \(k\geq1\), and Theorem 12.84 is stated for every such \(k\). A clean repair is to use a \(k\)-tuple \((I_1,\ldots,I_k)\) of pairwise disjoint subsequences, allowing empty subsequences; equivalently, maximize over collections of \emph{at most} \(k\) pairwise disjoint nonempty subsequences. One should also adopt the usual zero-padding convention \[ \lambda_i=0\quad\text{ for all }i>\ell(\lambda), \qquad \text{ as well as } \lambda'_i=0\quad\text{ for all }i>\ell(\lambda'). \] With these conventions, the formulas \[ \operatorname{inc}_k(w)=\lambda_1+\cdots+\lambda_k, \qquad \operatorname{dec}_k(w)=\lambda'_1+\cdots+\lambda'_k \] make literal sense for all \(k\geq1\), and the proof is unchanged after padding the chosen families by empty subsequences when necessary. \corr{Page 556, proof of Theorem 12.83} In the exceptional case of the increasing-subsequence argument, the proof writes quantities such as \[ v_{j_r},\quad v_{j_{r+1}},\quad v_{k_s},\quad v_{k_{s+1}} \] to compare values immediately before and after the three affected positions. These symbols need not all exist: for example, an increasing subsequence may have no selected position before \(i+1\), or none after \(i+2\). The construction of the replacement subsequences still works; the missing endpoint inequalities should simply be treated as vacuous. For instance, the inequality ``$v_{j_r} \leq x$'' should be treated as vacuously true if $v_{j_r}$ does not exist (i.e., if $r=0$). % For a completely literal proof, separate % the four endpoint cases (or introduce \(-\infty,+\infty\) sentinel values). \corr{Page 557, proof of Theorem 12.85} The proof concludes, ``for all \(k\ge1\),'' \[ \lambda_k = \operatorname{inc}_k(\vv)-\operatorname{inc}_{k-1}(\vv) = \operatorname{inc}_k(\ww)-\operatorname{inc}_{k-1}(\ww) = \mu_k. \] But Definition 12.82 defines \(\operatorname{inc}_k\) only for \(k\ge1\), so \(\operatorname{inc}_0\) is undefined when \(k=1\). Add the natural convention \[ \operatorname{inc}_0(\uu)=0 \qquad (\text{and, if desired, }\operatorname{dec}_0(\uu)=0) \] for every word $\uu$, or handle the case \(k=1\) separately. \corr{Pages 559--562, Section 12.14 on Quasisymmetric Polynomials} In Definition 1.90, compositions of $k$ were only defined for $k>0$. When working with quasisymmetric functions, it is essentially unavoidable to extend this definition to the case $k=0$. The definition is precisely the same; the only composition of $0$ is, of course, the empty sequence $()$. Of course, this means that the Composition Rule 1.92 (a) does not hold for $k = 0$ (but this wasn't claimed either). Likewise, it is worth clarifying that $[k-1] = \set{1,2,\ldots,k-1}$ is to be understood as the empty set when $k = 0$ (just as it is when $k = 1$). The maps $\operatorname{sub}$ and $\operatorname{comp}$ for $k = 0$ are the obvious bijections between the $1$-element sets $\Comp(0)$ and $\mathcal{P}([0-1]) = \mathcal{P}(\varnothing)$. In Theorem 12.94, the claim $|\operatorname{Comp}(k)|=2^{k-1}$ only holds for $k \geq 1$. % The section allows \(k=0\) in several statements, although the composition/subset indexing % has only been set up for positive \(k\). % Definition 12.92 takes \(\alpha\in\operatorname{Comp}_N(k)\) for \(k\ge0\), even though % compositions have just been recalled as sequences of positive integers and the Composition % Rule is stated only for \(k\ge1\). Theorem 12.94 then says, for \(N\ge k\), % \[ % \dim Q_N^k=|\operatorname{Comp}(k)|=2^{k-1}. % \] % At \(k=0\), however, \(Q_N^0\) is the one-dimensional space of constants whereas % \(2^{k-1}=1/2\). % Definitions/Theorems 12.95, 12.97, and 12.98 also use subsets of % \([k-1]\), which becomes \([-1]\) at \(k=0\). % The cleanest repair is to state the composition- and subset-indexed results for \(k\ge1\) % and add separately % \[ % Q_N^0=\mathbb R\cdot1. % \] % Alternatively, introduce the empty composition as the unique composition of \(0\), set % \(M_{\varnothing}=FQ_{0,\varnothing}=1\), and formulate an explicit degree-\(0\) convention % for the subset notation. \corr{Page 561, proof of Theorem 12.97} There are two small points worth making explicit in the proof. First, in the sentence following (12.14), replace ``the sum of all monomials whose exponent sequences are shifts of \(\xx^\alpha\)'' by ``the sum of all monomials whose exponent sequences are shifts of \(\alpha\)''. The shift relation was defined for exponent sequences, whereas \(\xx^\alpha\) is a monomial. Second, when the proof replaces the sum over subsets \(T\subseteq[k-1]\) by a sum over \(\alpha\in\Comp_N(k)\), it silently omits those \(T\) for which \(\operatorname{comp}(T)\) has more than \(N\) parts. This omission is valid: such a \(T\) has at least \(N\) elements, and thus the corresponding inner sum \[ \sum_{I\in\mathcal{I} : \ T = \Asc(I)} \xx_I \] will be zero (since a weakly increasing sequence \[ I = (i_1\leq\cdots\leq i_k) \qquad \text{ with each $i_j$ in $[N]$} \] can have at most \(N-1\) strict increases, i.e., its ascent set $\Asc(I)$ must have size $\leq N-1$, so it cannot equal the set $T$ which has at least $N$ elements). \corr{Page 563, proof of Theorem 12.99} In the last paragraph of the proof, the sentence ``Since $\Des(U) \subseteq \Asc(I)$, we see (as in the previous paragraph) that every run of equal values in $I$ is used to relabel a horizontal strip of cells in $dg(\lambda)$'' hides a non-completely-trivial argument worth spelling out. Suppose \[ i_a=i_{a+1}=\cdots=i_b \] is a maximal run of equal values in \(I\). Then none of \(a,a+1,\ldots,b-1\) lies in \(\operatorname{Asc}(I)\). Since \(\operatorname{Des}(U)\subseteq\operatorname{Asc}(I)\), none of these indices is a descent of \(U\). Thus, as the labels \(a,a+1,\ldots,b\) increase, their cells move weakly upward through the rows of \(U\). In particular, two of these cells cannot lie in the same column, because entries of a standard tableau strictly increase down a column. Hence the cells form a horizontal strip. Moreover, consecutive labels in this run occur strictly from left to right: the cell containing \(j+1\) is weakly above the cell containing \(j\), and it cannot be weakly to its left, since then it would lie weakly northwest of \(j\) while containing the larger entry. Consequently, standardizing \(G(U,I)\) from left to right recovers \(U\). This supplies the detail behind ``as in the previous paragraph''. \corr{Page 564, Theorem 12.105} The Pfaffian expansion is stated for every positive even \(N\). At \(N=2\), however, \(A[[1,2]]\) is a \(0\times0\) skew-symmetric matrix, while neither \(\SPf_0\) nor the Pfaffian of the empty matrix has been defined. The standard convention \[ \SPf_0=\{\text{empty permutation}\}, \qquad \operatorname{Pf}(\varnothing)=1 \] makes the recursion valid at \(N=2\). Otherwise, state Theorem 12.105 for \(N\ge4\) and give \(N=2\) as the base case. The same convention is also needed for the recursive Pfaffian formula repeated in the Chapter 12 Summary on page 578. \corr{Pages 567--568, proof of Theorem 12.112} The claimed bijection between even-cycle permutations and pairs of perfect matchings is not literally correct with ordinary simple graphs. For a \(2\)-cycle \((a,b)\), the two directed edges \[ a\longrightarrow b,\qquad b\longrightarrow a \] become the \emph{same} undirected edge \(\{a,b\}\). Thus, after the proof says to view \(G(w)\) as an undirected graph, ``take all the edges not used in \(M_1\)'' does not produce a second perfect matching on this component. The inverse description has the same problem: the ordinary set-theoretic union of two perfect matchings need not be a disjoint union of even cycles when the matchings share an edge. Exercise 12-107(c), where \(u=v\), is an explicit instance in which every matching edge is shared. The repair is to retain the two matching \emph{occurrences} (or colors). Equivalently, form a two-edge-colored multigraph from \(M_1\) and \(M_2\), counting an edge twice when it belongs to both. Every vertex then has one edge of each color, so every component is an alternating even cycle; a doubled edge is a \(2\)-cycle. The orientation is recovered by declaring the \(M_1\)-colored edge at the minimum vertex to be the outgoing edge. With this interpretation, the intended bijection and the remainder of the proof work. \corr{Page 574, Lemma 12.118} Replace ``$[U_k(1,b),U_k(2,b),\ldots,U_k(a,b)]^{\operatorname{tr}}$'' by ``$[U_k(1,b),U_k(2,b),\ldots,U_k(k,b)]^{\operatorname{tr}}$''. (This should be a vector with $k$ entries, as it is claimed to be an eigenvector of the \(k\times k\) matrix \(Q_k\).) % The displayed eigenvector of \(Q_k\) is written % \[ % [U_k(1,b),U_k(2,b),\ldots,U_k(a,b)]^{\operatorname{tr}}. % \] % The running index \(a\) should reach \(k\), since an eigenvector of the \(k\times k\) matrix % \(Q_k\) has \(k\) coordinates: % \[ % \boxed{ % [U_k(1,b),U_k(2,b),\ldots,U_k(k,b)]^{\operatorname{tr}}. % } % \] \corr{Page 578, Chapter 12 Summary: description of \(\SPf_N\)} The ``Pfaffians'' bullet point of the summary says that ``\(w\in \SPf_N\) iff $w \in S_N$, $w_i0\}, \] one can replace the product by \[ \prod_{k=1}^{K} \binom{a_{k-1}+a_k-1}{a_{k-1}-1,a_k}. \] These factors are all defined: writing \(d_i=N-i-\mu_i\), we have \(d_N=0\) and \(d_{i+1}-d_i=\mu_i-\mu_{i+1}-1\geq-1\), so if the value \(k>0\) occurs among the \(d_i\), then the value \(k-1\) occurs as well. Hence \(a_k>0\) implies \(a_{k-1}>0\). (Equivalently, one can take the product only over \(k\geq1\) with \(a_k>0\).) \corr{Page 580, Exercises 12-23 and 12-24} Parking functions were defined in Definition 12.12 only for positive order. However, both recursions on this page use the order-zero quantities: the terms with \(m=1\) and \(m=n\) contain \(p_0\) in Exercise 12-23 and \(P_0(q)\) in Exercise 12-24. The natural convention is that there is one empty parking function of order \(0\), so that \[ p_0=1 \qquad\text{and}\qquad P_0(q)=1. \] This convention should be stated before the two recursions; or, better, Definition 12.12 should be extended to \(n=0\) (no changes to the definition are needed aside of this). \corr{Page 581, Exercise 12-31} Replace ``finite subgroups of the field \(\mathbb C\)'' by ``finite subgroups of the multiplicative group \(\mathbb C^\times\)''. A field is not itself a group until an operation is specified, and the multiplicative interpretation is the one intended by the immediately preceding Theorem 12.29. \corr{Page 582, Exercise 12-57} In the two displays defining the \(q\)-tangent and \(q\)-secant numbers, the summation index is printed as \(k\), while the summands use \(n\): \[ \tan_q x=\sum_{k=0}^{\infty}\frac{t_n}{(q;q)_n}x^n; \qquad \sec_q x=\sum_{k=0}^{\infty}\frac{s_n}{(q;q)_n}x^n. \] Thus \(n\) is unbound and \(k\) is unused. In both sums, replace the lower limit ``\(k=0\)'' by ``\(n=0\)'' (or, equivalently, replace every \(n\) in the summand by \(k\)). \corr{Page 585, Exercise 12-98} Replace ``$\operatorname{FQ}_{n,S}$'' by ``$\operatorname{FQ}_{k,S}$''. % The exercise asks to expand \(M_\alpha\), where \(|\alpha|=k\), in the basis % \[ % \{FQ_{n,S}:S\subseteq[k-1]\}. % \] % The degree parameter \(n\) is not defined here and should be % \[ % \boxed{k}. % \] % Thus the basis is \(\{FQ_{k,S}:S\subseteq[k-1]\}\). \corr{Page 585, Exercise 12-99} The $f_y$ are not well-defined polynomials for an arbitrary surjection $G:\mathbb Z_{\ge0}^N\longrightarrow Y$. Indeed, the exercise defines \(f_y\in\mathbb R[x_1,\ldots,x_N]\) to be the sum of \emph{all} monomials \(x^\alpha\) with \(G(\alpha)=y\). A fiber \(G^{-1}(y)\) can be infinite, in which case this sum is not a polynomial. For example, if \(Y\) is a singleton and \(G\) is constant, then \(f_y\) would be the sum of every monomial in \(N\) variables. A sufficient correction is to assume \[ |G^{-1}(y)|<\infty \qquad\text{for every }y\in Y. \] Under this finite-fiber hypothesis, each \(f_y\) is a polynomial, the disjoint monomial supports give linear independence, and every \(G\)-symmetric polynomial is a finite linear combination of the \(f_y\)'s. The maps underlying Theorems 9.23 and 12.94 do have finite fibers, so the intended special cases remain valid. Alternatively, without any such assumptions, the $f_y$ are still well-defined as formal power series in $\RR[[x_1,\ldots,x_N]]$. However, they only form a topological basis (not a literal, linear-algebraic basis) of the topological vector space of all $G$-symmetric power series; thus, the claim of Exercise 12-99 (b) does not literally hold for them. \corr{Page 591, Appendix: algebra over a commutative ring} % The sentence % \[ % \text{``We can also consider algebras where the field \(F\) of scalars is a replaced by % any commutative ring \(R\).''} % \] % has an extra article. It should read % \[ % \text{``We can also consider algebras where the field \(F\) of scalars is replaced by % any commutative ring \(R\).''} % \] ``is a replaced'' should be ``is replaced''. \corr{Page 591, Appendix: definition of a graded algebra} The appendix defines a graded algebra as \[ A=\bigoplus_{n\geq0} A_n \] where the \(A_n\) are \emph{subalgebras}. This is incorrect. The \(A_n\) should be vector subspaces (or, in a more general base-ring setting, submodules) satisfying $A_n\bullet A_m\subseteq A_{n+m}$. The book's own example of homogeneous polynomials contradicts the printed definition, since homogeneous polynomials of a fixed positive degree are not closed under multiplication and do not contain \(1\). \corr{Page 591, Appendix} The formula \[ \Lambda=K[p_m:m\geq0] \] should read \[ \Lambda=K[p_m:m\geq1]. \] \corr{Page 592, Appendix} As on pages 398 and 417, arbitrary elements \(c_1,\ldots,c_k\) of an arbitrary algebra \(B\) do not necessarily determine ``a unique algebra homomorphism $E : F[z_1,\ldots,z_k]\longrightarrow B$''. The \(c_i\) must commute pairwise, or \(B\) should be assumed commutative. Later on the same page, the phrase \[ \text{``If \(E\) consists of zero alone''} \] should read \[ \text{``If \(\ker E\) consists of zero alone.''} \] \corr{Page 607, Index} The entry \[ \text{``connected graphs and OGFs, 499''} \] should read \[ \text{``connected graphs and EGFs, 499.''} \] Example 11.33 counts labeled graphs with the Exponential Formula and explicitly uses coefficients \(z^n/n!\), hence an exponential generating function. \end{description} \section{Places where supplementary explanation would help} The following are not necessarily errors, but they are points at which a self-learner or student may reasonably feel that a proof has skipped a nontrivial step, or where the wording leaves a convention implicit. (DG: Not all of these comments are particularly useful or to-the-point, but I have removed only those that I have found definitely irrelevant. Brace yourself for some pedantism.) \begin{description}[style=nextline,leftmargin=0pt,labelsep=0.5em] \corr{Page 23, Definition 1.66} The definition of independence of a collection of events says that the product formula holds ``for all choices of indices \(1\leq i_1<\cdots0\). The missing cases are harmless but should be checked separately: \(n=1\) for the sum of squares, and \(n=1,2\) for the sum of cubes. In the general case, the easiest way to go is to argue that (2.2) holds not only for $n \geq p$ but also for all $n \geq 0$ if you rewrite the left hand side as $\dbinom{0}{p}+\dbinom{1}{p}+\cdots+\dbinom{n}{p}$ (because if $0 \leq n < p$, then this equality boils down to $0 = 0$). \corr{Pages 88--89, combinatorial proof of Theorem 2.60} The theorem asserts a polynomial identity for every real \(x\), but the combinatorial proof explicitly fixes an integer \(x\geq0\) and concludes after proving the identity only for those values. One final sentence should be added: for fixed \(n\), both sides are polynomials in \(x\), so equality for infinitely many nonnegative integers \(x\) implies equality for all real \(x\), by Remark 2.7. The case \(n=0\) may be checked separately if desired. \corr{Page 99, Exercise 2-67} The statement that rhyme schemes using \(k\) different rhyme syllables are counted by \(S(n,k)\) implicitly treats the rhyme classes as \emph{unlabeled}. If the actual \(k\) syllables were regarded as prescribed/distinguishable labels, the count would instead be \(k!S(n,k)\). For students, it would be clearer to say that rhyme schemes are considered up to relabeling of the rhyme symbols, or equivalently that one is partitioning the \(n\) lines into \(k\) rhyme classes. \corr{Page 125, Theorem 3.71} The Tree Rule is stated for all \(n\geq1\), whereas the Rooted Tree Rule 3.47 used to deduce it is stated only for \(n>1\). The missing case \(n=1\) is of course immediate: there is exactly one tree on a one-element vertex set. It is worth saying this explicitly, rather than leaving the endpoint case to the formal expression \(1^{\, -1}=1\). \corr{Page 144, proof of Theorem 3.120} In the proof of existence of closed Eulerian tours, after constructing a maximal trail \(W\), the text says that, if some edge $e$ is not used by $W$, then ``we can find such an edge that is incident to one of the vertices $v_i$ visited by $W$''. This is true, but not quite immediate in a digraph. One way to justify it is to take a directed path from a visited vertex to the tail of an unused edge and choose the first edge of this path that has not already appeared in \(W\); its initial vertex is already visited. This fills a small logical gap in the maximality argument. (\textit{Remark:} We could replace ``directed path'' by ``undirected path'' in the above argument, and the argument would still work; this shows that Theorem 3.120 holds even if $G$ is assumed to be weakly connected rather than connected.\footnote{That said, it is not hard to show (independently of Theorem 3.120) that a weakly connected balanced digraph is automatically strongly connected.}) % \corr{Pages 171--172, proof of Lemma 4.27(b)} % The involution in part (b) is correct, but its definition is slightly compressed. The % instruction to toggle the rightmost nonzero symbol applies only when the resulting word % remains in \(Y\). The exceptional word % \[ % 2^{\,p-j}0^j % \] % is then declared fixed. Stating the map explicitly in these two cases would make the % involution easier to verify on a first reading. % \corr{Chapter 4, notation \(\tau\)} % The number-theoretic divisor-counting function \(\tau(m)\) introduced in Definition 4.34 % reuses the symbol \(\tau\) that Chapter 3 used for the number of spanning trees % \(\tau(G)\). The arguments are different enough that this causes no mathematical % ambiguity, but it is worth warning students when the two chapters are taught consecutively. \corr{Page 212, tree bijection \(g\)} The map \(g:T\to U\) from full binary trees to ordered trees is announced as a bijection and its recursive construction is given, but the text checks only the weight relation. The inverse map is postponed to Exercise 5-87. If this section is used as the promised bijective proof of the Catalan equinumeracy, it would be better to describe the inverse at once. It has the simple recursion \[ g^{-1}((0))=(\bullet,\varnothing,\varnothing), \] and, for an ordered tree \(u=(k,u_1,\ldots,u_k)\) with \(k\geq1\), \[ g^{-1}(u) = \bigl(\bullet, g^{-1}((k-1,u_1,\ldots,u_{k-1})), g^{-1}(u_k)\bigr). \] (When \(k=1\), the first argument on the right is the ordered tree \((0)\).) This directly shows that the displayed recursion for \(g\) is bijective. \corr{Page 223, proof of Sylvester's bijection} After solving (5.12) for the integers \(x_i,y_i\), the text says that ``we can fit the pieces together to recover the centered diagram of \(\mu=G(\nu)\in\operatorname{OddPar}\)'' and then concludes bijectivity from uniqueness of the solution of (5.12). There is a small geometric verification hidden here: one should check that the reconstructed pieces really do form a centered Ferrers diagram, and hence that \(F(G(\nu))=\nu\). Here is one way to make this explicit. Number the rows \(1,2,\ldots\) from top to bottom, and number the centered columns by the integers $\ldots,-2,-1,0,1,2,\ldots$. For \(i\geq1\), define the prospective \((2i-1)\)st and \(2i\)th pieces by \[ \begin{split} P_{2i-1} ={}& \{(r,i-1):i\leq r0\), the mirror cell \((r,-c)\) satisfies the same criterion. Hence every row is symmetric about column \(0\). The rows have no gaps (i.e., each row is a contiguous block of cells). To prove this, we fix a row $r$. Suppose first that \(0\leq d0\). Repeated use of \[ y_{j-1}>y_j\qquad\text{whenever }y_{j-1}>0 \] gives \[ y_d\geq y_c+(c-d)\geq r-d \qquad \left(\text{since $y_c \geq r-c$}\right), \] and therefore \((r,d)\in D\). Thus the cells of $D$ in row $r$ and columns $0,1,\ldots,r-1$, if there are any, form an initial segment $0,1,\ldots,t$. Together with their mirror cells, they form a contiguous block about column $0$; we call this the \emph{central block}. On the other hand, the cells with \(c\geq r\) form, by (*) alone, the consecutive block \[ r,r+1,\ldots,r+x_r-1. \] If this block is nonempty, then \(x_r>0\), so that $\nu_{2r}>0$ (since otherwise, all $\nu_i$ with $i\geq 2r$ would be $0$, and thus their alternating sum $x_r$ would be $0$ as well), therefore $\nu_{2r-1}>\nu_{2r}$ and thus $\nu_{2r-1}-\nu_{2r} > 0$; consequently \[ y_{r-1}-y_r = \nu_{2r-1}-\nu_{2r} > 0, \] whence \(y_{r-1}>0\), so we have \((r,r-1)\in D\), and this block joins the central block. By symmetry, the same holds on the left side of column $0$. The rows are weakly decreasing in length. To prove this, it is enough, by symmetry, to show that whenever \((r+1,c)\in D\) with \(c\geq0\), then \((r,c)\in D\). We prove this case-by-case depending on whether $cr$ or $c=r$: \begin{itemize} \item If \(cr\), then $c\geq r+1$, so that \((r+1,c)\in D\) yields \(c-r\leq x_{r+1}\). Since $c-r\geq1$, this implies $x_{r+1}>0$, and hence $\nu_{2r+2}>0$ (otherwise all parts $\nu_j$ with $j\geq2r+2$ would vanish, forcing $x_{r+1}=0$). Thus $\nu_{2r+1}>0$ as well, so the distinctness of the positive parts of $\nu$ gives $\nu_{2r}>\nu_{2r+1}$. From the alternating-sum formulas, \[ x_r-x_{r+1}=\nu_{2r}-\nu_{2r+1}>0. \] Therefore \(x_r\geq x_{r+1}+1\); in conjunction with $c-r\leq x_{r+1}$, this yields \[ c-r+1\leq x_r, \] so that $(r, c) \in D$. \item Finally, if \(c=r\), then \((r+1,r)\in D\) means \(y_r>0\). Hence $\nu_{2r+1}>0$ (otherwise all later parts of $\nu$ would vanish and $y_r$ would be $0$), so $\nu_{2r}>\nu_{2r+1}$ by distinctness of the positive parts of $\nu$. Using again \[ x_r-x_{r+1}=\nu_{2r}-\nu_{2r+1}>0 \] and $x_{r+1}\geq0$, we get $x_r>0$, and hence \((r,r)\in D\). \end{itemize} Thus every cell of $D$ (except those in the first row) has a cell directly above it. In other words, the rows of $D$ are weakly decreasing in length. Since \(x_i=y_i=0\) for all sufficiently large \(i\), the set \(D\) is finite. We have therefore shown that every nonempty row of \(D\) is an interval symmetric about column \(0\), and that the rows weakly decrease in length. Thus \(D\) is the centered Ferrers diagram of a partition \(G(\nu)\) into odd parts. Moreover, the sets \(P_j\) are pairwise disjoint: on the right half of the diagram a cell \((r,c)\), \(c\geq0\), belongs to the vertical part of \(P_{2c+1}\) when \(c