% CHANGES TO VOLUME 1 OF THE ART OF COMPUTER PROGRAMMING % % Copyright (C) 1997,1998,1999,2000,2001,2002,2003, % 2004,2005,2006,2007,2008 by Donald E. Knuth % This file may be freely copied provided that no modifications are made. % All other rights are reserved. % % Three levels of changes to the books are distinguished here: % % "\bugonpage" introduces the correction of an error; % "\amendpage" introduces new material for future editions; % "\improvepage" introduces ameliorations of lesser importance. % % (Changes introduced by \improvepage do not appear in the hardcopy listing.) % % Also, "\planforpage" introduces some of the author's half-baked intentions. % % NOTE: TO PUT THE INDEX ON A SEPARATE PAGE, RUN THIS WITH THE COMMAND LINE % tex "\let\indexeject+ \input err1" \newif\ifall % \alltrue means show the trivial items too \relax % hook \def\vertical{|} \def\inref#1 #{\expandafter\def\csname\vertical#1\endcsname} \catcode`|=\active \let|\inref \input \jobname.ref \catcode`|=12 \input taocpmac % use the format for TAOCP, with modifications below \def\becomes{\ifmmode\ \hbox\fi{\manfnt y}\ } % wiggly arrow indicates a change \def\bugonpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt\llap{\manfnt x}% print a black triangle in left margin {\bf Page #2}\enspace #3 \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\iftrue\noindent} \def\amendpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt{\bf Page #2}\enspace #3 \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\iftrue\noindent} \def\improvepage#1.#2 #3 (#4) {\ifall \medbreak\ninepoint \line{\kern-6pt{\sl Page #2\enspace #3\/} \leaders\hrule\hfill\ \eightrm\date#4.} \nobreak\smallskip\noindent} \def\planforpage#1.#2 #3 (#4) { \medbreak\defaultpointsize \line{\kern-5pt{\bf Page #2}\enspace #3 \leaders\hbox to 5pt{\hss.\hss}\hfill\ \eightrm\date#4.} \nobreak\smallskip\begingroup\let\endchange=\endgroup\sl\noindent} \let\endchange=\fi \def\nl{\par\noindent} \def\nlh{\par\noindent\hangit} \def\hangit{\hangindent2em} \def\cutpar{{\parfillskip=0pt\par}} \def\date#1.#2.#3.{% convert "yy.mm.dd." to "dd Mon 19yy" #3 \ifcase#2\or Jan\or Feb\or Mar\or Apr\or May\or Jun\or Jul\or Aug\or Sep\or Oct\or Nov\or Dec\fi \ \ifnum #1<97 \hundred#1\else19#1\fi} \def\hundred{20} % the "century" for dates before '97 \def\ex #1. [#2]{\ninepoint \textindent{\bf#1.}[{\it#2\/}]\kern6pt} \def\EX #1. [#2]{\ninepoint \textindent{\llap{\manfnt x}\bf#1.}[{\it#2\/}]\kern6pt} \def\foottext#1{\medskip \hrule height\ruleht width5pc \kern-\ruleht \kern3pt \eightpoint \smallskip\textindent{#1}} \def\volheadline#1{\line{\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill \titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill}} \def\refin#1 {\let|\inref \input #1.ref \let|\crossref} \let\defaultpointsize=\tenpoint %%%%%%%%%%%%%% opening remarks %%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{INTRODUCTION} \let\rhead=\lhead \titlepage \volheadline{THE ART OF COMPUTER PROGRAMMING} \bigskip \volheadline{ERRATA TO VOLUME 1 (3rd edition)} \bigskip \noindent This document is a transcript of the notes that I have been making in my personal copy of {\sl The Art of Computer Programming}, Volume~1 (third edition) since it was first printed in 1997. \ifall Four levels of updates\dash---``errors,'' ``amendments,'' ``plans,'' and ``improvements''\dash---appear, indicated by four \else Three levels of updates\dash---``errors,'' ``amendments,'' and ``plans''\dash---appear, indicated by three \fi different typographic conventions: \begingroup\def\hundred{17} \bugonpage 0.666 line 1 (76.07.04) Technical or typographical errors (aka bugs) are the most critical items, so they are flagged with a `\thinspace{\manfnt x}\thinspace' preceding the page number. The date on which I first was told about the bug is shown; this is the effective date on which I paid the finder's fee. The necessary corrections are indicated in a straightforward way. If,~for example, the book says `$n$' where it should have said `$n+1$', the change is shown thus: \smallskip $n$ \becomes $n+1$ \endchange \amendpage 0.666 line 2 (89.07.14) Amendments to the text appear in the same format as bugs, but without the~`\thinspace{\manfnt x}\thinspace'. These are things I wish I had known about or thought of when I wrote the original text, so I added them later. The date is the date I drafted the new text. \endchange \def\hundred{19} \planforpage 0.666 line 3 (17.11.20) Plans for the future represent a third kind of item. In such notes I~sketched my intentions about things that I wasn't ready to flesh out further when I~wrote them down. You can identify these items because they're written in slanted type, and preceded by a bunch of dots `\hbox to 6em{\leaders\hbox to 5pt{\hss.\hss}\hfill}' leading to the date on which I recorded the plan in my files. \endchange \improvepage 0.666 line 4 (38.01.10) The fourth and final category\dash---indicated by page and line number in smaller, slanted type\dash---consists of minor corrections or improvements that most readers don't want to know about, because they are so trivial. You wouldn't even be seeing these items if you hadn't specifically chosen to print the complete errata list in all its gory details. Are you sure you wanted to do that? \endchange \endgroup \ifall\else\medskip\ninepoint My personal file of updates also includes a fourth category of items, not shown in this list. They are miscellaneous minor corrections or improvements that most readers don't want to know about, because they are so trivial. If you really want to see all of the gory details, you can download the full list from Internet webpage $$\.{http://www-cs-faculty.stanford.edu/\char`\~knuth/taocp.html}$$ by selecting the ``long form'' of the errata. \fi \medskip \tenpoint My shelves at home are bursting with preprints and reprints of significant research results that I want to digest and summarize, where appropriate, in the ultimate edition of Volume~1. I didn't do that in the third edition because I would surely have to do it over again later: New results continue to pour forth at a great rate, and I will have time to rewrite that volume only~once. Volumes 4 and~5 need to be finished first. So I've put most of my effort so far into writing up those parts of the total picture that seem to have converged to their near-final form. It follows, somewhat paradoxically, that the updates in this document are most current in the areas where there has been least activity. On the other hand I do believe that the changes listed here bring Volume~1 completely up to date in two respects: (1)~All of the research problems in the previous edition\dash---i.e., all exercises that were rated 46 and above\dash---have received new ratings of 45 or less whenever I learned of a solution; and in such cases, the answer now refers to that solution. (2)~All of the historical information about pioneering developments has been amended whenever new details have come to my attention. \beginconstruction The ultimate, glorious, future editions of Volumes 1--3 are works in progress. Please let me know of any improvements that you think I ought to make. Send your comments either by snail mail to D.~E. Knuth, Computer Science, Gates Building 4B, Stanford University, Stanford CA~94305-9045, or by email to {\tt taocp{\char`\@}cs.stanford.edu}. (Use email for book suggestions only, please\dash---all other correspondence is returned unread to the sender, or discarded, because I have no time to read ordinary email.) Although I'm working full time on Volume~4 these days, I~will try to reply to all such messages within a year of receipt. Current news about {\sl The Art of Computer Programming\/} is posted on $$\.{http://www-cs-faculty.stanford.edu/\char`~knuth/taocp.html}$$ and updated regularly. \par\endconstruction \rightline{\dash---Don Knuth, April 1997} \bigskip \bigskip {\quoteformat What happened? The subject took the bit in its teeth and ran away with it, that's what happened. I know now how Sir James Frazer felt when, after setting out to dash off a brief monograph on a single obscure rite, he found himself in the embarrassing possession of the 12 volumes of ``The Golden Bough.'' \author WAVERLEY ROOT (1974) % International Herald Tribune, 22 May 1974, p8 \vfill\eject } \def\today{\number\day\space\ifcase\month\or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \space\number\year} %%%%%%%%%%%%%%% CHANGES FOR VOLUME 1 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\lhead{CHANGES TO VOLUME 1: FUNDAMENTAL ALGORITHMS} \let\rhead=\lhead \titlepage \volheadline{FUNDAMENTAL ALGORITHMS} \bigskip \rightline{Copyright \copyright\ 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004,\qquad} \rightline{2005, 2006, 2007, 2008, Addison\with Wesley; all rights reserved} \rightline{Last updated \today} \bigskip \rightline{\sl Most of these corrections have already been made in recent printings.} \smallskip \let\defaultpointsize=\tenpoint \amendpage 1.vii line 15 (97.12.30) % this propagates to pages viii, ix, x Volume~6, {\sl The Theory of Languages\/}; Volume~7, {\sl Compilers}. \becomes Volume~6, {\sl The Theory of Languages\/} (Chapter~11); Volume~7, {\sl Compilers\/} (Chapter~12). \endchange \bugonpage 1.xii step 2 of the flowchart (97.07.16) pp.~xvii--xix \becomes pp.~xv--xvii \endchange \bugonpage 1.xviii lines 12--19 (98.07.01) 1.2.8 \becomes 1.2.8. \qquad $\cdots$ \qquad 1.3 \becomes 1.3. \endchange \bugonpage 1.1 line 11 (07.02.26) {\eightss(1844) \becomes (1843)} \endchange \improvepage 1.1 line $-5$ (01.04.10) celebrated book \becomes celebrated Arabic text \endchange \bugonpage 1.1 line $-4$ (97.08.01) {\sl Kitab al jabr} \becomes {\sl Kit\=ab al-jabr} \endchange \improvepage 1.3 line 3 after Fig.~1 (00.02.03) Step E3 \becomes step E3 \endchange \improvepage 1.4 line $-15$ (03.04.09) ${544\over 119}=4{68\over 119}$ \becomes $544/119=4+68/119$ \endchange \improvepage 1.6 lines 1 and 2 (00.03.02) set of divisors \becomes set of common divisors\quad(twice) \endchange \bugonpage 1.8 three places in {\eq(3)} (00.08.05) $f(\sigma,j)$ \becomes $f\bigl((\sigma,j)\bigr)$\qquad [twice]\nl $f(\sigma,N)$ \becomes $f\bigl((\sigma,N)\bigr)$\qquad [once] \endchange \amendpage 1.12 line $-5$ (02.08.06) 8.] \becomes 8. See also Section 7.2.1.4.] \endchange \improvepage 1.13 line $-3$ (05.05.21) $d$ and two integers $a$ and $b$,\becomes $d$, and we also compute two not-necessarily-positive integers $a$ and $b$ \endchange \bugonpage 1.15 replacement for {\eq(7)} (97.07.26) $$\vcenter{\hsize=.8\hsize\noindent \sl if an assertion attached to any arrow leading into the box is true before the operation in that box is performed, then all of the assertions on relevant arrows leading away from the box are true after the operation.}\eqno(7)$$ \endchange \bugonpage 1.16 line $-7$ (99.03.24) $m$, $n$, $c$, and $r$ \becomes $m$, $n$, $c$, $d$, and $r$ \endchange \improvepage 1.16 near the bottom (99.03.24) line $-5$: the algorithm with \becomes the method with\nl line $-2$: of the algorithm \becomes of the procedure\nl line $-1$: start the procedure with \becomes start with the values \endchange \amendpage 1.17 lines 26 and 27 (05.03.29) [See {\sl AMM\/ \bf24} \becomes [See {\sl The Penny Cyclop{\ae}dia\/ \bf11} (1838), 465--466; {\sl AMM\/ \bf 24} \endchange \improvepage 1.19 add clarification to line 3 (97.11.23) \ninepoint (A prime number is considered to be the ``product'' of a single prime, namely itself.) \endchange \amendpage 1.19 lines 11--12 (04.08.05) \ninepoint suggested to the author by R. W. Floyd, is shown in Fig.~5. \becomes suggested by Warren Lushbaugh, is shown in Fig.~5; see {\sl Math.\ Gazette\/ \bf49} (1965), 200. \endchange \improvepage 1.19 lines 18 and 20 (02.09.20) \ninepoint (1 \becomes ${}\cdot(1$ \endchange \bugonpage 1.19 in the Area part of Fig.\ 5 (97.07.30) \ninepoint $4\cdot 3\cdot 3^2+4\cdot 5\cdot5^2$ \becomes $4\cdot 3\cdot 3^2+4\cdot4\cdot4^2+4\cdot 5\cdot5^2$ \endchange \bugonpage 1.19 line 4 of exercise 13 (97.11.27) \ninepoint ``$m>0$, $n=0$, $T=0$.'' \becomes ``$m>0$, $n>0$, $T=0$.'' \endchange \bugonpage 1.22 line 8 (97.07.28) {\it $m$th root\/} of $v$, \becomes {\it $m$th root\/} of $u$, \endchange \improvepage 1.22 line 10 (97.07.28) numbers $r$ \becomes numbers $r=p/q$ \endchange \improvepage 1.22 line $-12$ (98.10.02) $1^x=1$ \becomes $b^x=1$ \endchange \improvepage 1.23 line $-1$ (02.08.08) the return \becomes the annual return \endchange \improvepage 1.25 line 1 (99.04.21) $0.0100110100010000011\ldots{}$ \becomes $(0.0100110100010000011\ldots{})_2$ \endchange \improvepage 1.26 first line of exercise 26 (01.03.20) \ninepoint Determine upper bounds on the accuracy of \becomes Find a rigorous upper bound on the error made by \endchange \improvepage 1.27 lines 9 and 10 from the bottom (01.03.20) The example in the preceding sentence \becomes A sum such as $\sum_{j\le k}{j+k\choose2j-k}$ \endchange \amendpage 1.27 new exercise to follow line 3 (03.06.28) \ninepoint\ex 30. [12] Simplify the expression $(\ln n)^{\ln n/\ln\ln n}$, assuming that $n>1$. \endchange \amendpage 1.27 on the line following {\eq(1)} (06.03.20) If $n$ is zero, the value of this summation \becomes If $n$ is zero, the value of $a_1+a_2+\cdots+a_n=\sum_{j=1}^na_j= \sum_{1\le j\le n}a_j$ \endchange \bugonpage 1.27 line 4 from the bottom (97.07.16) $\displaystyle\sum_{j=1}^\infty=$ \ \becomes \ $\displaystyle\sum_{j=1}^\infty a_j=$ \endchange \bugonpage 1.27 replacement for the bottom line (97.07.16) $$\sum_{R(j)}a_j=\biggl(\lim_{n\to \infty }\sum_{ \scriptstyle R(j)\atop\scriptstyle-n\le j<0}a_j\biggr) + \biggl(\lim_{n\to \infty }\sum_{ \scriptstyle R(j)\atop\scriptstyle0\le jb>c\ge0$. \endchange \amendpage 1.74 replacement for exercise 66 (05.11.08) \ninepoint\ex 66. [\HM30] Suppose $x$, $y$, and $z$ are real numbers satisfying $$\Bigl({x\atop n}\Bigr)=\Bigl({y\atop n}\Bigr)+\Bigl({z\atop n-1}\Bigr),$$ where $x\ge n-1$, $y\ge n-1$, $z> n-2$, and $n$ is an integer $\ge2$. Prove that $$ \vcenter{\halign{$\displaystyle#\hfil$\qquad if and only if\qquad&$#$\hfil\cr \Bigl({x\atop n-1}\Bigr)\le\Bigl({y\atop n-1}\Bigr)+\Bigl({z\atop n-2}\Bigr) & y\ge z;\cr \noalign{\smallskip} \Bigl({x\atop n+1}\Bigr)\le\Bigl({y\atop n+1}\Bigr)+\Bigl({z\atop n}\Bigr) & y\le z.\cr}}$$ \endchange \improvepage 1.74 line 1 of exercise 68 (98.03.17) \ninepoint De Moivre \becomes de Moivre \endchange \amendpage 1.75 lines 6--9 (07.05.05) (Besides $H_n$, \dots\ the harmonic series.) \becomes Besides $H_n$, \dots\ the harmonic series. Chinese bamboo strips written before 186 \BC.\ already explained how to compute $H_{10}=7381/2520$, as an exercise in arithmetic. [See C. Cullen, {\sl Historia Math.\ \bf34} (2007), 10--44.] \endchange \improvepage 1.77 the line after {\eq(10)} (00.02.25) the infinite series \becomes the infinite series 1.2.9--\eq(17) \endchange \improvepage 1.80 line 3 (97.07.26) sequence $F_n$ \becomes sequence $\langle F_n\rangle$ \endchange \improvepage 1.80 line 7 (00.07.20) Hemachandra \becomes Hemacandra \endchange \amendpage 1.80 line 10 (01.12.16) Johann Kepler \becomes Johannes Kepler \endchange \bugonpage 1.80 line 20 (06.01.04) at most $k+1$ \becomes at most $k-1$ \endchange \improvepage 1.81 line 16 (02.08.22) {\sl Paris\/ \bf1} (1680) \becomes {\sl Sci.\ \bf1} (Paris, 1680) \endchange \improvepage 1.81 line $-8$ (99.07.27) {\sl multiple of\/} $F_k$ \becomes {\sl multiple of\/} $F_n$ \endchange \improvepage 1.82 line 7 (97.07.26) sequence, $F_n$, for which statement \eq(8) holds \becomes sequence $\langle F_n\rangle$ for which statement \eq(8) holds, \endchange \bugonpage 1.83 line 18 (07.10.15) quadratic equation \becomes quadratic polynomial \endchange \amendpage 1.83 lines 2--4 after {\eq(14)} (99.09.22) by A. De Moivre \dots~essentially \becomes early in the eighteenth century. $\bigl($See D.~Bernoulli, {\sl Comment.\ Acad.\ Sci.\ Petrop.\ \bf 3} (1728), 85--100, \S7; see also A.~de Moivre, {\sl Philos.\ Trans.\ \bf32} (1722), 162--178, who showed how to solve general linear recurrences in essentially \endchange \improvepage 1.86 bottom line (04.02.07) \ninepoint (The $k$'s \becomes (See exercise 34. The $k$'s \endchange \improvepage 1.87 line 15 (98.03.17) A. De Moivre \becomes A. de Moivre \endchange \bugonpage 1.87 line 22 (97.07.27) 125--169) \becomes 125--169 \endchange \bugonpage 1.88 line $-3$ (98.02.27) $(a_0+b_0)$ \becomes $(a_0b_0)$ \endchange \improvepage 1.89 on the left side of \eq(13) (07.10.15) $\scriptstyle n\mod m=r$ \becomes $\scriptstyle n\ge0,\,n\mod m=r$ \endchange \bugonpage 1.90 in Eq.~{\eq(15)} (98.01.07) $\displaystyle\sum_{k\ge0}$ \becomes $\displaystyle\sum_{k\ge1}$ \endchange \improvepage 1.94 exercise 10 (02.08.18) \ninepoint [Change the notation from `$a_m$' to the more modern `$e_m$', throughout this exercise.] \endchange \bugonpage 1.95 line 6 of exercise 19 (97.07.17) \ninepoint$\displaystyle\Bigl({1\over n}-{1\over n+x}\bigr)$ \becomes $\displaystyle\Bigl({1\over n}-{1\over n+x}\Bigr)$ \endchange \improvepage 1.98 line $-9$ (02.08.22) {\sl Paris\/ \bf37} (1853) \becomes {\bf37} (Paris, 1853) \endchange \bugonpage 1.98 line $-2$ (97.09.12) $(n-1)P_{(n-k)k}$ \becomes $(n-1)P_{(n-1)@k}$ \endchange \amendpage 1.103 line $-12$ (05.10.04) by Thiele in 1903. \becomes by T.~N. Thiele in 1889 [see A.~Hald, {\sl International Statistical Review\/ \bf68} (2000), 137--153]. \endchange \bugonpage 1.103 in {\eq(23)} (97.07.29) $\kappa_1t^2$ \becomes $\kappa_2t^2$ \endchange \amendpage 1.104 line 2 before the exercises (08.10.30) for all $t\ge r$, \becomes for all $t\ge r$, and if $f(t)\ge0$ for all $t$ in the domain of the random variable~$X$, \endchange \improvepage 1.105 line $-7$ (06.01.01) \ninepoint probability \becomes $\Pr$ \endchange \improvepage 1.106 line 1 of exercise 14 (98.03.17) \ninepoint De Moivre \becomes de Moivre \endchange \improvepage 1.106 line 1 of exercise 18 (06.01.01) \ninepoint distinct values \becomes values \endchange \bugonpage 1.106 replacement for line 6 of exercise 18 (07.10.15) \ninepoint $$\left(k_nz\over k_n\right)\left({k_{n-1}z+k_n\over k_{n-1}+k_n}\right) \left({k_{n-2}z+k_{n-1}+k_n\over k_{n-2}+k_{n-1}+k_n}\right)\,\ldots\, \left({k_1z+k_2+\cdots +k_n\over k_1+k_2+\cdots+k_n}\right)\Big/z@,$$ \endchange \bugonpage 1.106 lines 3 and 4 of exercise 20 (01.12.24) \ninepoint $a_1,\,a_2\,\ldots\,a_n$ \becomes $a_1a_2\ldots a_n$ \endchange \amendpage 1.107 the line after {\eq(1)} (01.09.07) Oiler's constant \becomes Euler's constant [pronounced `Oiler's constant'] \endchange \bugonpage 1.108 line 3 (97.07.31) $a_1$ \becomes $a_1n$ \endchange \bugonpage 1.109 line $-7$ (98.05.22) all value \becomes all values \endchange \improvepage 1.110 line $-2$ (05.11.08) Big Theta notation \becomes Big Theta \endchange \improvepage 1.112 line $-10$ (06.03.20) introduced by Jacques Bernoulli in his \becomes introduced to European mathematicians in James Bernoulli's \endchange \improvepage 1.113 line 13 (01.11.04) (9) \becomes \eq(9) \endchange \improvepage 1.114 line 10 (02.11.10) $f^{(m)}$ \becomes $f^{(m)}(x)$ \endchange \improvepage 1.114 line 15 (02.11.28) $\pm\int_1^\infty$ \becomes $-\int_1^\infty$ \endchange \bugonpage 1.115 line 1 of exercise 3 (06.01.01) \ninepoint $\bigl((-1)^m(B_m/m!\bigr)$ \becomes $(B_m/m!)$ \endchange \improvepage 1.116 first line of exercise 8 (06.01.01) $\ln(an^2+bn)!$ \becomes $\ln\,(an^2\!+bn)!$ \endchange \bugonpage 1.116 last line of exercise 8 (98.05.03) \ninepoint $(1+\epsilon)$ \becomes $(1+\epsilon)$. \endchange \bugonpage 1.121 line 5 (00.02.08) $1\over8505$ \becomes $16\over8505$ \endchange \improvepage 1.123 the displayed equation of exercise 17 (98.03.27) \ninepoint$\displaystyle\sum_{0\le k}$ \becomes $\displaystyle\sum_{k\ge0}$ \endchange \improvepage 1.125 line 1 (04.09.17) basic unit of information \becomes basic unit of \.{MIX} data \endchange \improvepage 1.125 footnote (97.12.03) \eightpoint binary bits \becomes binary digits \endchange \bugonpage 1.126 replacement for bottom of Fig.\ 13 (98.07.15) \centerline{\epsfxsize=81mm \epsfbox{\figdir/aux.666}} \endchange \bugonpage 1.130 line 6 (99.02.14) right-hand of \becomes right-hand portion of \endchange \bugonpage 1.130 line $-15$ (99.02.14) (store X), C \becomes (store X). C \endchange \improvepage 1.131 line 13 (97.08.03) left of A \becomes left of rA \endchange \amendpage 1.131 line $-6$ (97.09.28) 10-byte number \becomes 10-byte number rAX \endchange \bugonpage 1.131 line $-2$ (97.09.28) the quotient $\pm\bigl\lfloor@\vert@\rA/\rm V\vert@\bigr\rfloor$ \becomes the quotient $\pm\bigl\lfloor@\vert@\rAX/\rm V\vert@\bigr\rfloor$\nl the remainder $\pm\bigl( \vert\rA\vert\mod\vert\rm V\vert\bigr)$ \becomes the remainder $\pm\bigl( \vert\rAX\vert\mod\vert\rm V\vert\bigr)$ \endchange \improvepage 1.133 line $-3$ (05.08.22) $C=48+i$ \becomes ${\rm C}=48+i$ \endchange \improvepage 1.134 line 14 (97.08.03) field of A \becomes field of rA \endchange \improvepage 1.135 line $-7$ (03.01.24) F = number. \becomes F = number, normally 1. \endchange \improvepage 1.135 line $-2$ (97.09.03) when the groups of locations involved overlap \becomes when there's overlap between the locations involved \endchange \improvepage 1.138 line 17 (03.04.04) 40, \dots convert \becomes 40, \dots\ convert \endchange \improvepage 1.138 line 23 (97.08.03) register A and X \becomes registers A and X \endchange \bugonpage 1.138 line $-5$ (98.10.11) unspecified. \becomes specified in Section 4.2.1. \endchange \improvepage 1.139 line $-4$ in 1st or 2nd printing (98.04.17) \ninepoint appears on \ page 133 \becomes on page 133 \endchange \bugonpage 1.139 line $-4$ in 3rd, 4th, 5th printings (99.01.10) \ninepoint appears on \ page ?? \becomes on page 133 \endchange \bugonpage 1.142 line 3 of exercise 13 (00.02.27) \ninepoint ``\.{JNOV 1001}, \becomes ``\.{JNOV 1001}'', \endchange \bugonpage 1.143 line 6 of exercise 23 (97.07.19) \ninepoint to load \becomes ability to load \endchange \bugonpage 1.144 last line of the exercise (97.09.03) \ninepoint cannot be used; \becomes instructions cannot be used; \endchange \improvepage 1.145 line $-24$ (97.08.03) ``\.{LOC OP ADDRESS}'' \becomes ``\.{LOC}'', ``\.{OP}'', and ``\.{ADDRESS}'' \endchange \bugonpage 1.145 line $-8$ (98.09.07) % in 2nd, 3rd, 4th printings only! (page 1) \becomes (page 96) \endchange \improvepage 1.147 lines 16 and 19 (04.07.18) program \becomes algorithm \qquad(twice) \endchange \improvepage 1.151 line $-8$ (07.09.21) 42, and 48. \becomes 42, 48, and 50. \endchange \bugonpage 1.154 line 5 (97.08.03) that is., \becomes that is, \endchange \bugonpage 1.155 line 4 of point 10 (97.07.19) previous defined.\ \becomes previously defined. \endchange \bugonpage 1.157 line 1 of exercise 6 (99.05.15) \ninepoint $1\le d\le\sqrt n$ \becomes $1 \.{NEWBASE[$@j$]}$ \becomes $\.{NEWBASE[$@j$]} > \.{BASE[$@j$]}$ \endchange \bugonpage 1.252 last line of exercise 5 (97.08.13) \ninepoint exercise 4(iii) \becomes exercise 4(c) \endchange \improvepage 1.253 lines 7 and 9 of exercise 12 (99.12.18) \ninepoint$\max\ (k_1,k_2)$ \becomes $\max(k_1,k_2)$ \endchange \bugonpage 1.256 replacement for line 26 (97.11.08) $$\vcenter{\baselineskip0pt\lineskip0pt \halign{#\cr \hedge\cr \vedgec\fourbytes{\.{INFO}\cb}\twobytes{\.{LINK}\cb}\cr \hedge\cr}}\punct.\eqno(3)$$ \endchange \improvepage 1.258 line $-5$ (97.08.13) 17 cycles, compared to 12 cycles \becomes 17 units of time, compared to 12 units \endchange \improvepage 1.260 replacement for line $-7$ (04.05.03) \tenpoint $$\hbox{{\sl an empty queue is represented by\/} $\.F = \Lambda$ {\sl and\/} $@@\.R = \.{LOC(F)}$.}$$ \endchange \bugonpage 1.260 line 4 (97.08.11) handle empty lists \becomes to handle empty lists \endchange \improvepage 1.264 lines 1, 3, 6, 12 (97.08.15) pairs \becomes relations \endchange \improvepage 1.265 line 1 (97.08.15) inputs pairs of relations \becomes inputs a sequence of relations \endchange \improvepage 1.265 formerly line 3, now line 4 (97.08.15) in linear order \becomes in a linear order \endchange \improvepage 1.266 line 22 (04.05.03) directly to Algorithm T. \becomes directly to Algorithm T but with slight changes for efficiency. \endchange \bugonpage 1.266 line $-20$ (99.05.25) \.{COUNT[$@j$]} \becomes \.{COUNT[$k$]} \endchange \bugonpage 1.268 line $-2$ (97.08.10) \ninepoint \.{UNDERFLOW}\kern-.5em; \ \becomes \.{UNDERFLOW}; \endchange \bugonpage 1.270 line 2 of exercise 12 (98.03.09) \ninepoint Given two \becomes Give two \endchange \improvepage 1.270 line 2 of exercise 15 (97.08.15) \ninepoint irredundant pairs of relations \becomes irredundant relations \endchange \improvepage 1.273 line $-3$ of exercise 28 (97.07.26) \ninepoint E.\ Lucas \becomes \'E.\ Lucas \endchange \amendpage 1.273 line $-1$ of exercise 28 (05.07.08) {\sl Winning Ways\/ \bf2} (Academic Press, 1982) \becomes {\sl Winning Ways\/ \bf3} (A.~K. Peters, 2003) \endchange \bugonpage 1.274 line 12 (97.11.17) ``$\.{INFO(P)}\gets\.Y''$ \becomes ``$\.{INFO(P)}\gets\.Y$'' \endchange \bugonpage 1.275 second line after {\eq(4)} (97.08.12) don't have a \becomes there is no \endchange \improvepage 1.277 lines 2 and 3 of step M2 (99.12.06) ``if $\.{ABC(P)}<0$ then~$-1$, otherwise $\.{ABC(P)}+\.{ABC(M)}$'' \becomes ``(if $\.{ABC(P)}<0$ then~$-1$, otherwise $\.{ABC(P)}+\.{ABC(M)}$)'' \endchange \bugonpage 1.279 exercise 12 (01.12.19) \ninepoint Algorithm A \becomes Program A \endchange \improvepage 1.281 lines 9 and 10 (04.05.03) {\sl \.{NODE(X)}} \becomes \.{NODE(X)}\qquad and\qquad {\sl \.X} \becomes \.X \endchange \improvepage 1.285 step E3 (97.08.20) [Open door.] \becomes [Open doors.] \endchange \improvepage 1.285 step E5 (97.08.20) [Close door.] \becomes [Close doors.] \endchange \improvepage 1.287 step D2 (97.08.20) [Should door open?] \becomes [Should doors open?] \endchange \improvepage 1.290 lines {\it047\/} and {\it049\/} (97.08.20) \ninepoint Indicates door open \becomes Indicates doors open \endchange \improvepage 1.292 program line {\it 098\/} (03.01.25) \ninepoint Compute \.{IN}, \.{OUT}, \becomes Set \.{INFLOOR}, \.{OUTFLOOR}, \endchange \bugonpage 1.292 program lines {\it 103\/} and {\it 105\/} (98.07.08) \ninepoint \.{POOLMAX} \becomes \.{POOLMAX(0:2)} \endchange \improvepage 1.293 line $-14$ (01.12.24) coroutine E \becomes Coroutine E \endchange \improvepage 1.294 program line {\it201\/} (97.08.20) \ninepoint \undertext E3. Open door.\\ \becomes \undertext E3. Open doors.\\ \endchange \improvepage 1.295 program line {\it237\/} (97.08.20) \ninepoint \undertext E5. Close door.\\ \becomes \undertext E5. Close doors.\\ \endchange \bugonpage 1.296 line 7 (98.07.08) \.{CON} \becomes \.{NOP} \endchange \bugonpage 1.296 line 20 (99.02.14) by performed \becomes be performed \endchange \improvepage 1.296 line 22 (05.10.08) {\it quasi-parallel} \becomes {\it quasiparallel} \endchange \bugonpage 1.296 line $-4$ (98.08.31) 216--218 \becomes 217--219 \endchange \improvepage 1.298 last line of exercise 11 (99.02.14) \ninepoint on the same step \becomes in the same step \endchange \improvepage 1.299 line 6 (04.06.09) an array \becomes an array like \eq(1) \endchange \bugonpage 1.301 replacement for Fig.\ 13 (97.07.21) \centerline{\epsfbox{\figdir/ch2.13}} \endchange \bugonpage 1.305 line 1 of exercise 2 (04.02.01) \ninepoint Formula \eq(6) has \becomes Formulas \eq(5) and \eq(6) have \endchange \bugonpage 1.305 line 2 of exercise 2 (01.12.24) \ninepoint $l_r\le \.I \le u_r$ \becomes $l_r\le \.I_r \le u_r$ \endchange \bugonpage 1.310 among the sons of Japheth (97.07.30) {\sixrm Meschech \ \becomes \ Meshech} \endchange \improvepage 1.311 line 3 (04.03.14) was being \becomes was first being \endchange \improvepage 1.311 lines 26 and 27 (00.12.05) represents, not a person \dots\ so-and-so.'' \becomes represents ``a person in the role of mother or father of so-and-so,'' not simply a person as an individual. \endchange \bugonpage 1.313 line 1 after Fig.~21 (97.11.29) looks very much the \becomes looks very much like the \endchange \bugonpage 1.313 line $-3$ (01.12.19) parent$(F[a,b,c,d])$ \becomes the parent of $F[a,b,c,d]$ \endchange \improvepage 1.315 line 8 before {\eq(3)} (02.09.28) {\sl list structure} \becomes {\it list structure} \endchange \improvepage 1.316 line 9 (03.02.16) lower case letters \becomes lowercase letters \endchange \improvepage 1.317 exercise 17 (01.02.13) \ninepoint If $F$ is \becomes If $Z$ stands for\nl $F[1,2,2]$ \becomes $Z[1,2,2]$ \endchange \improvepage 1.317 line 2 of exercise 19 (97.08.20) \ninepoint this list? \becomes this List? \endchange \amendpage 1.318 exercise 22 (97.10.13) \ninepoint line 1: A2, \dots~\becomes A2, \dots, A$n$, \dots \vadjust{\vskip2pt}\nl line 2: $\sqrt2$ to 1.\ \becomes $\sqrt2$ to~1 and whose areas are $2^{-n}$ square meters. \endchange \bugonpage 1.322 replacement for {\eq(7)}, has arrow $E\to G$ (97.07.15) $$\vcenter{\epsfbox{\figdir/ch2a.320}}\eqno(7)$$ \endchange \bugonpage 1.328 line $-17$ (98.08.31) $\displaystyle u_1',u_2',\ldots,u_n'$ \becomes $\displaystyle u_1',u_2',\ldots,u_{n'}'$ \endchange \bugonpage 1.328 line $-9$ (97.08.24) contents of \becomes complements of \endchange \bugonpage 1.329 equation {\eq(15)} (98.07.07) $f(u_{l+1})$ \becomes $f(u_{n_l+1})$ \endchange \improvepage 1.331 new wording for exercises 7 and 8 (05.12.04) \ninepoint \ex 7. [22] Show that if we are given the preorder and the inorder of the nodes of a binary tree, the binary tree structure may be constructed. (Assume that the nodes are distinct.) Does the same result hold true if we are given the preorder and postorder, instead of preorder and inorder? Or if we are given the inorder and postorder? \ex 8. [20] Find all binary trees whose nodes appear in exactly the same sequence in both (a) preorder and inorder; (b) preorder and postorder; (c) inorder and postorder. (As in the previous exercise, we assume that the nodes have distinct labels.) \endchange \bugonpage 1.333 line 2 of exercise 31 (06.06.21) \ninepoint the tree node \becomes the tree nodes \endchange \improvepage 1.335 line 1 (99.11.29) $45^\circ$ \becomes $45^\circ$ clockwise \endchange \amendpage 1.337 line 9 (04.03.12) tree, \becomes tree or forest, \endchange \bugonpage 1.342 line 5 (02.12.26) $\rI1\equiv\.P$ \becomes $\rI2\equiv\.P$ \endchange \bugonpage 1.345 line {\it180} of the program (04.02.01) \.{COPY2} \becomes \.{COPYP2} \endchange \bugonpage 1.346 line 1 of exercise 7 (97.07.21) \ninepoint as a , \becomes as a partial ordering, \endchange \bugonpage 1.348 line 15 from the bottom (97.07.15) LLINK in tree There are \becomes There are \endchange \bugonpage 1.349 replacement for {\eq(1)} (97.08.08) $$\bigl(A(B,C(K)),\,D(E(H),F(J),G)\bigr)\eqno(1)$$ \endchange \improvepage 1.351 line $-2$ (97.08.29) $\.P\gets\.P+1$ \becomes $\.P\gets\.P+c$ \endchange \bugonpage 1.352 lower middle (02.12.26) line $-14$: from 6 bytes to 3 \becomes from 5 bytes to 3\nl line $-12$: the latter has 60 \becomes the latter has 50 \endchange \bugonpage 1.353 replacement for the main part of Fig.\ 26 (97.08.21) \centerline{\epsfbox{\figdir/ch2.26}} \endchange \improvepage 1.354 line 1 (97.08.29) pairs of equivalences \becomes pairs of equivalent elements \endchange \bugonpage 1.355 line 7 (97.08.29) the roots to two trees \becomes the roots of two trees \endchange \improvepage 1.360 line 2 of exercise 8 (97.08.29) \ninepoint equivalences, \becomes equivalent elements, \endchange \improvepage 1.360 line 2 of exercise 9 (97.08.29) \ninepoint pairs of equivalences \becomes equivalences \endchange \improvepage 1.360 line 3 of exercise 11 (97.08.29) \ninepoint pairs of relations \becomes a set of relations \endchange \bugonpage 1.360 line 10 of exercise 11 (97.07.25) \ninepoint \.{ARRAY X[$[0@{:}@10$]} \becomes \.{ARRAY X[$0@{:}@10$]} \endchange \improvepage 1.364 line 6 (97.09.02) edge $V_{k-1}V_k$ \becomes edge $V_{k-1}\adj V_k$ \endchange \improvepage 1.364 line 14 (97.09.02) For we take an arbitrary \becomes This follows because we can find some \endchange \improvepage 1.364 lines 18 and 20 (06.06.01) a tree \becomes a free tree \endchange \improvepage 1.366 line 1 below the caption to {Fig.\ 32} (06.06.01) % aff p365 reach a subtree \becomes reach a free subtree \endchange \bugonpage 1.367 line $-2$ (99.05.14) for which $e_j$ \becomes for which $E_j$ \endchange \improvepage 1.370 replacement for line $-16$ (04.06.22) $$\vbox{\epsfbox{\figdir/ch2a.3693}}$$ \endchange \bugonpage 1.371 line 4 of exercise 10 (98.12.02) \ninepoint to that there \becomes so that there \endchange \improvepage 1.373 lines 18--25 (97.09.02) Furthermore, if \dots~{\sl an oriented\/} \becomes Furthermore, it has no cycles. For if $(V_0,V_1,\ldots,V_n)$ is an undirected cycle \dots~to the cycle $$(V_1,V_0,V_{n-1},\ldots,V_1),$$ because $V_n=V_0$. Therefore {\sl an oriented} \endchange \amendpage 1.374 and the next few pages too (04.07.15) [Starting with the 17th printing, the term `Eulerian circuit' was changed to `Eulerian trail', and `Hamiltonian circuit' was changed to `Hamiltonian cycle', in accordance with what has now become established usage. About thirty such changes were made, affecting pages 374, 375, 376, 379, 380, 581, and 584.] \endchange \improvepage 1.375 replacement for Fig.\ 36 (97.12.31) $$\vcenter{\epsfbox{\figdir/ch2.36}}$$ \endchange \improvepage 1.376 lines 4, 8, 10, and 11 (06.01.01) {\sl init\/} \becomes init\qquad(thrice)\qquad and\qquad {\sl fin\/} \becomes fin\qquad (once) \endchange \improvepage 1.376 line 3 of exercise 4 (99.09.22) \ninepoint all edges $e$ \becomes all arcs $e$ \endchange \bugonpage 1.377 line $-2$ of exercise 10 (99.05.14) \ninepoint the $F$ table \becomes the $P$ table \endchange \amendpage 1.379 in exercise 21 (01.09.06) \ninepoint line 4: $n+1$ vertices $V_0$, $V_1$, \dots, $V_n$ \becomes $n$ vertices $V_0$, $V_1$, \dots, $V_{n-1}$\nl line 5: $(n+1)m$ arcs \becomes $mn$ arcs\nl line 6: $(n+1)m$ vertices \becomes $mn$ vertices\nl line 10: $m^{(n+1)(m-1)}$ \becomes $m^{(m-1)n}$ \endchange \improvepage 1.379 line 5 of exercise 21 (02.12.26) \ninepoint the graph \becomes the digraph \endchange \bugonpage 1.381 replacement for the bottom line (06.01.01) $$x_j=\sum_{\scriptstyle{\rm init}(e)=V_i\atop\scriptstyle{\rm fin}(e)=V_j} p(e)\,x_i,\qquad \hbox{for $1\le j\le n$}.$$ \endchange \improvepage 1.387 lines $-11$, $-10$, $-9$ (03.01.25) The weight of $Y_1$ \dots we have \becomes If $Y$ is any node in the $Y_1$ subtree, its weight must be at least $n-s_1=1+s_2+\cdots +s_k$, since when $Y$ is the assumed root there are at least $n-s_1$ vertices in its subtree containing $X\!@$. Thus if $Y$ is a centroid we have \endchange \improvepage 1.387 line $-8$ (99.05.16) $\hbox{weight}\.(X)$ \becomes $\hbox{weight}\,(X)$ \endchange \improvepage 1.395 line 2 after {\eq(30)} (00.05.26) some of this function's \becomes this function's history and some of its \endchange \bugonpage 1.395 line 11 after {\eq(30)} (98.03.19) 1997 \becomes 1998 \endchange \improvepage 1.395 line 2 of exercise 1 (97.08.14) \ninepoint $\displaystyle\half A(z^2)$ \becomes $\displaystyle{\textstyle\half}A(z^2)$ \endchange \improvepage 1.396 line 9 of exercise 4 (97.08.14) \ninepoint $\displaystyle\half A(z^2)$ \becomes $\displaystyle{\textstyle\half}A(z^2)$ \endchange \improvepage 1.397 line 5 (99.02.14) \ninepoint prove there \becomes prove that there \endchange \bugonpage 1.398 line 2 of exercise 25 (99.11.27) \ninepoint $r(n,\,n-1)=n^{n-1}$ \becomes $r(n,\,n-1)=n^{n-2}$ \endchange \bugonpage 1.399 line 3 (99.11.27) \ninepoint $(x+\epsilon_1z_1+\cdots +\epsilon_nz_n)^{e_1+\cdots +e_n-1}$ $(x+\epsilon_1z_1+\cdots +\epsilon_nz_n)^{\epsilon_1+\cdots +\epsilon_n-1}$ \endchange \bugonpage 1.399 line 1 of exercise 32 (02.12.11) \ninepoint (1940) \becomes (1941) \endchange \improvepage 1.399 line 2 of exercise 32 (05.11.08) 7--12). \becomes 7--12.) \endchange \bugonpage 1.402 line $-4$ (98.09.11) (1951) \becomes (1952) \endchange \improvepage 1.403 replacement for {\eq(10)} (97.09.14) \tenpoint$$\vcenter{\epsfbox{\figdir/ch2a.4024}}\eqno(10)$$ \endchange \bugonpage 1.406 line 9 (02.08.19) \ninepoint {\sl Messenger of Math. \bf58} (1939) \becomes {\sl Messenger of Math.\ \bf58} (1929) \endchange \amendpage 1.407 lines 2--4 (05.01.29) % affects page 406 by J. von Segner \dots~it was the subject \becomes by L.~Euler, who mentioned his results in a letter to C.~Goldbach on 4~September 1751 [see J.\ von Segner and L.\ Euler, {\sl Novi Commentarii Academi\ae\ Scientiarum Petropoli\-tan\ae\ \bf 7} (1758--1759), summary~13--15, 203--210]. Euler's problem was the subject \endchange \amendpage 1.407 lines 14 and 15 (99.01.29) to appear \becomes 1999 \endchange \bugonpage 1.411 line $-6$ (97.08.28) contain a \.{TYPE} field \becomes contains a \.{TYPE} field \endchange \bugonpage 1.415 line 3 of step A2 (97.09.17) not at atom \becomes not an atom \endchange \bugonpage 1.415 line 5 of step A2 (97.09.17) $\.{K}\gets\min(\.{K1},\.{BLINK(K)})$ \becomes $\.{K1}\gets\min(\.{K1},\.{BLINK(K)})$ \endchange \improvepage 1.415 line 22 (04.05.03) {\sl ``$@$\.{NODE($\Lambda$)}''} \becomes {\sl``\/}$@@\.{NODE($\Lambda$)}\!${\sl''} \endchange \improvepage 1.418 line 3 of step E4 (97.09.17) the list \becomes the List \endchange \bugonpage 1.421 line 11 (97.09.17) garbage is \becomes total memory is \endchange \bugonpage 1.421 line $-15$ (02.01.01) 499--506 \becomes 499--507 \endchange \bugonpage 1.423 line $-4$ of exercise 11 (97.09.08) \ninepoint $\bigl( a\hbox{:}\,(b\hbox{:}\,D),b,a\hbox{:}\,E)\bigr)$ \becomes $\bigl( a\hbox{:}\,(b\hbox{:}\,D),b,a\hbox{:}\,E \bigr)$ \endchange \improvepage 1.426 line 8 (98.10.26) \.{MONTH}, \.{DAY} and \.{YEAR} \becomes \.{MONTH}, \.{DAY}, and \.{YEAR} \endchange \bugonpage 1.426 line 9 (02.12.26) \.{DAY}, \.{MONTH}, \.{YEAR} \becomes \.{MONTH}, \.{DAY}, and \.{YEAR} \endchange \bugonpage 1.428 line $-9$ (97.09.20) memory location \becomes memory allocation \endchange \bugonpage 1.430 line 6 (00.05.08) set $\.P=\.{PREV(P)}$ \becomes set $\.P\gets\.{PREV(P)}$ \endchange \bugonpage 1.430 line $-9$ (07.10.15) $0\le j0$ \endchange \bugonpage 1.470 line 3 of answer 28 (02.02.03) $x\gets1-\epsilon$ \becomes $x\gets1-\epsilon-x$ \endchange \improvepage 1.471 line 6 (97.08.13) {\sl METAFONT: The Program\/} \becomes \font\ninelogosl=logosl10 at 9pt {\sl {\ninelogosl METAFONT\/}: The Program\/} \endchange \amendpage 1.471 new answer following line 8 (03.06.28) \ans30. $n$. \endchange \amendpage 1.471 answer 19 (07.05.01) $a_n-a_{m-1}$ \becomes $(a_n-a_{m-1})@\[m\le n]$ \endchange \amendpage 1.474 new copy for the beginning of answer 40 (05.01.08) [A. de Moivre, {\sl The Doctrine of Chances}, 2nd edition (London:\ 1738), 197--199.] We have \endchange \bugonpage 1.475 lines 10 and 11 (07.10.15) are Cauchy matrices \becomes are determinants of Cauchy matrices\nl not Hilbert matrices \becomes not determinants of Hilbert matrices \endchange \amendpage 1.475 last line of answer 45 (03.01.13) 22. \becomes 22; Cauchy, {\sl \OE uvres\/ \rm(2) \bf12}, 173--182. [Beginning with the 24th printing, the latter reference was changed to: A.~Cauchy, {\sl Exercices d'analyse et de physique math\'ematique\/ \bf2} (1841), 151--159.] \endchange \bugonpage 1.475 line 10 of answer 46 (01.12.15) $\displaystyle\sum_{1\le k_1,\ldots,k_m\le m}$ \becomes $\displaystyle\sum_{1\le k_1,\ldots,k_m\le n}$ \endchange \bugonpage 1.475 bottom line (07.10.15) $n-1$ \becomes $n-2$ \endchange \amendpage 1.476 line 3 of answer 7 (05.05.13) $>1$. \becomes $>1$; that is, if and only if $(-x)\mod1+(-y)\mod1<1$. \endchange \bugonpage 1.477 line 7 of answer 34 (97.10.16) i satisfied \becomes is satisfied \endchange \bugonpage 1.478 line $-2$ of answer 37 (05.11.08) $0\le k\le n$ \becomes $0b>c>d\ge0$; the sequence begins 3210 4210 4310 4320 4321 5210 5310 5320 $\ldots\;$. We can find the combinatorial representation by a ``greedy'' method, first choosing the largest possible~$a$, then the largest possible $b$ for $n-{a\choose4}$, etc. [Section 7.2.1.3 discusses further properties of this representation.] \endchange \amendpage 1.489 replacement for first three lines of answer 58 (03.06.12) \ans58. [{\sl Systematisches Lehrbuch der Arithmetik\/} (Leipzig:\ 1811), xxix.] Use induction and $$\Bigl({n\atop k}\Bigr)_{\!q}=\Bigl({n-1\atop k}\Bigr)_{\!q}+ \Bigl({n-1\atop k-1}\Bigr)_{\!q}q^{n-k}=\Bigl({n-1\atop k}\Bigr)_{\!q}q^k+\Bigl({n-1\atop k-1}\Bigr)_{\!q}.$$ Therefore [F. Schweins, {\sl Analysis\/} (Heidelberg:\ 1820), \S151] the $q$-generalization of \eq(21) is \endchange \amendpage 1.490 replacement for lines 5--7 (03.06.12) \noindent For further information, see G. {Gasper} and M. {Rahman}, {\sl Basic Hypergeometric Series\/} (Cambridge Univ.\ Press, 1990). The $q$-nomial coefficients were introduced by Gauss in {\sl Commentationes societatis regi{\ae} scientiarum Gottingensis recentiores\/ \bf1} (1808), 147--186; see also {Cauchy} [{\sl Comptes Rendus Acad.\ Sci.\ \bf17} (Paris, 1843), 523--531], {Jacobi} [{\sl Crelle\/ \bf32} (1846), 197--204], and {Heine} [{\sl Crelle\/ \bf34} (1847), 285--328]. \endchange \bugonpage 1.491 line 2 (98.01.28) $q^{m-r+s-k)(n-k)}$ \becomes $q^{(m-r+s-k)(n-k)}$ \endchange \amendpage 1.491 replacement for answer 66 (05.11.08) \ans66. Let $X={x\choose n}$, $\underline X={x\choose n-1}={n\over x-n+1}X$, $\overline X={x\choose n+1}={x-n\over n+1}X$, with similar notations for $Y$ and~$Z$. We may assume that $y>n-1$ is fixed, so that $x$ is a function~of~$z$.\looseness=-1\par Let $F(z)=\overline X-\overline Y-\overline Z$, and suppose that $F(z)=0$ for some $z>n-2$. We will prove that $F'(z)<0$; therefore $z=y$ must be the only root $>n-2$, proving the second inequality. Since $F(z)={x-n\over n+1}(Y+Z)-{y-n\over n+1}Y-{z-n+1\over n}Z=0$ and $x>y$ and $Y,Z>0$, we must have ${x-n\over n+1}<{z-n+1\over n}$. Setting $X'=dX/dx$ and $Z'=dZ/dz=dX/dz$, we have $${X'\over X}={1\over x}+{1\over x-1}+\cdots+{1\over x-n+1} >{n\over n+1}\Bigl({1\over z}+\cdots+{1\over z-n+2}\Bigr) ={n\over n+1}{Z'\over Z},$$ since ${x-n+1\over n+1}<{z-n+2\over n}$, \dots, ${x-1\over n+1}<{z\over n}$. Thus $dx/dz=Z'/X'<{n+1\over n}(Z/X)$, and $$F'(z)={X\over n+1}@{dx\over dz}+{x-n\over n+1}@Z'-{Z\over n}-{z-n+1\over n}Z' <\Bigl({x-n\over n+1}-{z-n+1\over n}\Bigr)@Z'<0.$$\par To prove the first inequality, we may assume that $n>2$. Then if $\underline X =\underline Y+\underline Z$ for some $z>n-2$, the second inequality tells us that $z=y$.\par \em References: L.~Lov\'asz, {\sl Combinatorial Problems and Exercises}, Problem 13.31(a); R.~M. Redheffer, {\sl AMM\/ \bf103} (1996), 62--64. \endchange \bugonpage 1.493 line 2 of answer 12 (98.02.13) ${\cal F}(z)$ \becomes ${\cal G}(z)$ \endchange \amendpage 1.493 answer 14 (06.06.25) $F_{m+1}F_{n-1}+(F_{m+2}+1)F_n$ \becomes $F_{m+n+1}+F_n$ \endchange \amendpage 1.493 last line of answer 19 (07.06.21) $\sin72^\circ=\half5^{1/4}\phi^{1/2}\!@$.) \becomes $\sin72^\circ=\half5^{1/4}\phi^{1/2}\!@$. Another interesting angle is $\alpha=\arctan\phi={\pi\over4}+\half\arctan\half$, for which we have $\sin\alpha=5^{-1/4}\phi^{1/2}$, $\cos\alpha=5^{-1/4}\phi^{-1/2}$.) \endchange \amendpage 1.494 replacement for line 4 (04.01.26) \centerline{$(n+1-x^nF_{n+1})/(2x+1)$.} \endchange \amendpage 1.495 line 6 of answer 34 (05.02.05) 182]; generalizations \becomes 182]; but Section 7.2.1.7 points out that it was implicitly known in 14th-century India. Generalizations \endchange \amendpage 1.495 bottom line of answer 34 (06.10.12) exercise 5.4.2--10 \becomes exercise 5.4.2--10 and in Section 7.1.3. \endchange \bugonpage 1.495 line 7 of answer 35 (97.11.16) $m-\phi^{2n}$, \becomes $m-\phi^{-2n}$, \endchange \improvepage 1.495 line 8 of answer 35 (97.11.16) $\phi^{k-1}+\cdots+\phi^{k-2j+1}$ \becomes $\phi^{k-1}+\phi^{k-3}+\cdots+\phi^{k-2j+1}$ \endchange \improvepage 1.495 line 7 of answer 36 (02.08.23) Jean Bernoulli \becomes John Bernoulli \endchange \bugonpage 1.496 line 2 of answer 5 (06.01.01) $(n-1)!$ \becomes $\displaystyle{(n-1)!\over k!}$ \endchange \improvepage 1.496 answer 10 (02.08.18) [Change the notation from `$a_m$' to the more modern `$e_m$', throughout this exercise and also in the answer to exercise 11 on page 497.] \endchange \bugonpage 1.498 line 3 (06.01.01) $f(x)$ \becomes $\lim_{x\to1-}f(x)=f(1)$ \endchange \bugonpage 1.498 replacement for line 8 (06.01.01) $${i\over 2}+{i\over (\omega^{-p}-1)}={i\over 2}\,\Bigl({1+\omega^p\over 1-\omega^p}\Bigr)=-{i\over 2}\left({\omega^{p/2}+\omega^{-p/2}\over \omega^{p/2}-\omega^{-p/2}}\right)=-\half \cot{p\over q}\pi.$$ \endchange \bugonpage 1.498 line 2 of answer 21 (02.04.15) $E_1(x)$ \becomes $E_1(z)$ \endchange \bugonpage 1.498 line 1 of answer 23 (01.12.16) When $m=1$ \becomes (a) When $m=1$ \endchange \bugonpage 1.500 replacement for line 2 of answer 6 (97.08.01) $$\ln(q+pe^t)=\ln\Bigl(1+pt+{pt^2\over2}+{pt^3\over6}+\cdots\,\Bigr)= pt+p(1-p){t^2\over2}+p(1-p)(1-2p){t^3\over6}+\cdots{}$$ \endchange \bugonpage 1.500 line 6 of answer 6 (02.01.11) $H'(z)=e^t/(e^t-1)-1/t$ \becomes $H'(t)=e^t/(e^t-1)-1/t$ \endchange \bugonpage 1.500 line 1 of answer 8 (99.07.30) $M\falling n/\bigl((M-n)!\,M^n\bigr)$ \becomes $M\falling n/M^n$ \endchange \bugonpage 1.501 last line of answer 13 (97.08.01) $n$ and $x$.] \becomes $n$ and $x$. \endchange \improvepage 1.501 line 1 of answer 14 (97.08.01) $e^{-itpn/\hisqrt{pqn}}(q+pe^{it/\hisqrt{pqn}})^n=(qe^{-itp/\hisqrt{pqn}}+ pe^{itq/\hisqrt{pqn}})^n$ \becomes\nl $e^{-itpn/\littlehisqrt{pqn}}(q+pe^{it/\littlehisqrt{pqn}})^n=(qe^{-itp/\littlehisqrt{pqn}}+ pe^{itq/\littlehisqrt{pqn}})^n$ \endchange \bugonpage 1.501 line 2 of answer 15 (01.03.25) ${}+-t^2/2np$ \becomes $-t^2\!/(2np)$ \endchange \improvepage 1.502 line 1 of answer 21 (97.09.10) [There's slightly too much space before the word ``The''.] \endchange \bugonpage 1.502 line 2 of answer 21 (97.08.01) $\Pr(X\ge n(p+\epsilon)$ \becomes $\Pr\bigl(X\ge n(p+\epsilon)\bigr)$ \endchange \bugonpage 1.502 line 3 of answer 21 (99.07.05) $-{1\over2q}\epsilon^2$ \becomes $\epsilon -{1\over2q}\epsilon^2$ \endchange \bugonpage 1.502 line 2 of answer 22 (99.01.22) 493--509 \becomes 493--507 \endchange \bugonpage 1.502 line 4 of answer 22 (99.07.05) ${}\le e^{\delta^2\!/2}$ when $\delta\le0$ and ${}\le e^{\delta^2\!/3}$ \becomes ${}\le e^{-\delta^2\!/2}$ when $\delta\le0$ and ${}\le e^{-\delta^2\!/3}$ \endchange \improvepage 1.502 line 1 of answer 23 (97.09.10) [There's slightly too much space before the word ``Setting''.] \endchange \bugonpage 1.502 line 4 of answer 23 (98.10.27) $f(\epsilon)\le-\epsilon^2\!/(6pq)$ \becomes that $f(\epsilon)\le-\epsilon^2\!/(6pq)$ if $0\le\epsilon\le p$. \endchange \improvepage 1.503 answer 8 (98.05.26) \ninepoint the previous \becomes the method of the previous \endchange \bugonpage 1.503 line 1 of answer 9 (03.05.05) $f(x)$ \becomes $f(z)$ \endchange \bugonpage 1.503 line 2 of answer 12 (99.07.30) $O\bigl(n^k\!/(n-1)!\bigr)$ \becomes $O\bigl(n^k\!/(k-1)!\bigr)$ \endchange \bugonpage 1.503 answer 1 (97.08.01) $B_0+B_1z+B_2z^2\!/2!+\cdots{})@e^z$ \becomes $(B_0+B_1z+B_2z^2\!/2!+\cdots{})@e^z$ \endchange \improvepage 1.504 lines 2 and 3 (06.01.01) $\ln(n-1)!$ \becomes $\ln\,(n-1)!$ \endchange \amendpage 1.504 line 5 of answer 7 (05.05.20) The number $A$ is ``Glaisher's constant'' $1.2824271\ldots{}$ [{\sl Messenger} \becomes In these formulas, $A$ is the ``Kinkelin--Glaisher constant'' $1.2824271\ldots{}$ [{\sl Crelle\/ \bf57} (1860), 122--158; {\sl Messenger} \endchange \bugonpage 1.504 line 3 of answer 8 (06.01.01) ${}+\sigma$ \becomes ${}+\half\ln a+\sigma$ \endchange \improvepage 1.504 line 4 of answer 8 (06.01.01) $\ln(cn^2)!- \ln(cn^2-n)!-n\ln c-\ln n^2!+\ln(n^2-n)!$ \becomes $\ln\,(cn^2)!- \ln\,(cn^2-n)!-n\ln c-\ln n^2!+\ln\,(n^2-n)!$ \endchange \improvepage 1.504 line 1 of answer 9 (06.01.01) $\ln(2n)!$ \becomes $\ln\,(2n)!$\qquad and\qquad $\ln(n!)^2$ \becomes $\ln\,(n!)^2$ \endchange \bugonpage 1.504 line 3 of answer 9 (98.03.24) $O(n^{-3})=$ \becomes $O(n^{-3})\bigr)=$ \endchange \bugonpage 1.505 second display in answer 9 (07.10.17) $x^z$ \becomes $x^x$ \endchange \bugonpage 1.507 line 4 of answer 20 (06.01.01) $\sum_{k=1}^{m-1}c_k(2u)^{k/2-1}$ \becomes $\sum_{k=1}^{m-1}kc_k(2u)^{k/2-1}$ \endchange \improvepage 1.507 line 2 of answer 6 (98.04.20) into \ an index \becomes into an index \endchange \bugonpage 1.507 line 2 of answer 7 (02.09.28) $\vert V\vert$ \becomes $\rm \vert V\vert$ \endchange \amendpage 1.508 line 4 of answer 14 (03.03.25) \.{JSJ} \becomes \.{STJ} \.{*(0:0)}, \.{STZ} \.{*(0:0)}, and \.{STZ} \.{*(3:3)}; \.{JSJ} \endchange \improvepage 1.508 line 2 of answer 21 (98.04.20) only by \ jumping \becomes only by jumping \endchange \bugonpage 1.509 line 3 (99.05.03) a sign \becomes the sign \endchange \improvepage 1.509 line 18 (97.09.28) time${}=54u$. \becomes time${}=54u$, not counting the \.{HLT}. \endchange \improvepage 1.509 lines $-12$ through $-9$ (07.11.17) \nobreak\vskip-\baselineskip {\ansmixthree (3495)&$(-5)^{13}$\qquad\rm[This line needed only when $b>65$.]\hidewidth\cr (3496)&$(-4)^{13}$\hidewidth\cr $\ \vdots{}$\hidewidth\cr (3505)&$(+5)^{13}$\qquad\rm[This line needed only when $b>65$.]\quad\slug\hidewidth\cr\endmix} \endchange \bugonpage 1.510 line 03 of the program (98.11.21) \.{\]C\]04} \becomes \.{\]C\]O4} \endchange \bugonpage 1.510 line $-2$ (97.12.30) \.{\]\]\]B.} \becomes \.{\]J\]B.} \endchange \bugonpage 1.512 right column, line 12 of the program (02.08.25) {\tt GOOD} \becomes {\tt MEMORY} \endchange \improvepage 1.513 changes for consistency (97.10.29) line 1: {\sl Solution 1:} \becomes {\it Solution 1:}\nl line $-12$: {\sl Solution 2:} \becomes {\it Solution 2:} \endchange \bugonpage 1.513 line $-8$ (99.03.22) $R(j)\le a_{ij}$ \becomes $R(i)\le a_{ij}$ \endchange \improvepage 1.514 end of the program (99.05.18) program lines $-3$ and $-2$: interchange `\.{ENT1} \.0' with `\.{J3P} \.{3B}'\nl line 6 after the program: $540u$ \becomes $530u$ \endchange \amendpage 1.514 line $-6$ (02.08.25) we can solve \becomes and $m\ge n$, we can solve \endchange \bugonpage 1.515 line 14 (97.07.31) in 924744796234036231 our case, \becomes in our case, \endchange \amendpage 1.515 new answer (97.04.24) \ans12. M.~Hofri and P. Jacquet [{\sl Algorithmica\/ \bf22} (1998), 516--528] have analyzed the case when the $m\times n$ matrix entries are distinct and in random order. The running times of the two \MIX\ programs are then respectively $\bigl(6mn+5mH_n+8m+6+5(m+1)/(n-1)\bigr)u+ O\bigl((m+n)^2\!/{m+n\choose m}\bigr)$ and $(5mn+2nH_m+7m+7n+9H_n)u+O(1/n)+O\bigl((\log n)^2\!/m\bigr)$, as $m\to\infty$ and $n\to\infty$, assuming that $(\log n)/m\to0$. \endchange \improvepage 1.516 answer 14 (98.08.31) [Udo Wermuth has indeed squeezed out an additional $9u$, $10u$, or $12u$, depending on the year. But details are omitted here because \MIX\ will soon be replaced.] % not recorded in the MS file \endchange \amendpage 1.518 lines 18 and 19 (03.01.10) {\sl Calendrical Calculations} \dots~1997) \becomes {\sl Calendrical Calculations\/} by E.~M. Reingold and N.~Dershowitz (Cambridge Univ.\ Press, 2001) \endchange \bugonpage 1.519 line 2 of answer 17 (99.05.20) $H_n$ \becomes $H_N$ \qquad and \qquad $H_{2m}$ \becomes $2H_{2m}$ \endchange \bugonpage 1.520 line $-3$ of answer 19 (97.11.25) {\sl Soci\'ete\/} \becomes {\sl Soci\'et\'e\/} \endchange \bugonpage 1.521 replacement for line 11 (08.01.20) \noindent \.{\ \ \ \ \ \ \ LDA \ * \ \ \ \ \ }4\quad Waste $2u$ of time. \endchange \bugonpage 1.522 lines 1 and 2 of answer 6 (05.10.24) The tital time is increased \dots~name. \becomes The total time decreases by $8u$ for every blank word following a ``('', because lines 30--32 cost $4u$ while lines 26--28, 33--34, 36--38 cost $12u$. It decreases by $2u$ for every blank word following a name, because lines 68--71 cost $5u$ while 42--46 or 75--79 cost~$7u$. \endchange \improvepage 1.524 answer 17 (01.12.24) $(m/mH_n)$ \becomes $m/(mH_n)$ \endchange \bugonpage 1.524 answer 19 (99.09.15) 1/ \becomes $n!/$\quad (in three places) \endchange \bugonpage 1.524 lines 1, 3, and 9 of answer 22 (06.01.01) $\scriptstyle j\ge0$ \becomes $\scriptstyle j>0$\qquad (four times) \endchange \amendpage 1.525 lines 4 and 5 of answer 23 (03.11.04) [to appear] \becomes [Ph.D. thesis, \'Ecole Polytechnique (Paris, 1996)] \endchange \bugonpage 1.525 answer 24 (01.12.24) {\sl Proc.\ IFIP Congress (1971)} \becomes {\sl Proc.\ IFIP Congress\/} (1971) \endchange \amendpage 1.526 new sentence for answer 31 (03.04.07) When $m=2$, the $k$th man executed is number $2n+1-(2n+1-2k) @2^{\lfloor\lg(2n/(2n+1-2k))\rfloor}$. [Armin~Shams, {\sl Proc.\ Nat.\ Computer Conf.\ 2002}, English papers section, {\bf2} (Mashhad, Iran:\ Ferdowsi University, 2002), 29--33.] \endchange \amendpage 1.527 last line of answer 34 (97.10.26) efficient. \becomes efficient. [W. Fletcher and R. Silver, {\sl CACM\/ \bf9} (1966), 326.] \endchange \bugonpage 1.527 lines $-3$ and $-2$ of answer 35 (06.01.01) interchange $\gamma''$ with $\beta\gamma'$ \becomes interchange $\gamma''\beta$ with $\gamma'$ \endchange \bugonpage 1.529 lines 2--7 of answer 3 (06.07.17) But if \dots\ program.) \becomes But the comparison indicator isn't initialized; and if the final period is preceded by a replication digit, it won't be noticed. [\em Note: The most nitpickingly efficient program would probably remove lines 40, 44, and 48, and would insert ``\.{CMPA PERIOD}'' between lines 26 and 27, ``\.{CMPX PERIOD}'' between lines 59 and~60. The state of the comparison indicator should then become part of the coroutine characteristics in the program documentation.] \endchange \bugonpage 1.529 line $-4$ (97.12.28) is not to invent \becomes is not hard to invent \endchange \bugonpage 1.532 line 1 of answer 7 (98.07.16) One way \becomes One way is \endchange \bugonpage 1.534 line 7 of answer 18 (98.03.11) goint \becomes going \endchange \bugonpage 1.534 line 10 of answer 19 (01.12.24) 1339--1342 \becomes 1338--1342 \endchange \bugonpage 1.536 amendments to answer 4 (02.08.22) line 5: Andr\'e (1878): \becomes Andr\'e:\nl line 15: $2n\choose n-1$. \becomes $2n\choose n-1$. [{\sl Comptes Rendus Acad.\ Sci.\ \bf105} (Paris, 1887), 436--437.] \endchange \improvepage 1.536 line $-13$ (98.03.17) Abraham De Moivre \becomes Abraham de Moivre \endchange \bugonpage 1.537 line $-4$ (06.01.01) $A_m(n,-2)$ \becomes $A_m(n+1,-2)$ \endchange \bugonpage 1.539 answer 12 (99.11.17) line 3: We have \becomes We have, for sufficiently small $\alpha$,\nl replacement for line 7: $$\medmuskip=1.5mu (-1)^n\Bigl({k+1/2\atop n}\Bigr)=\Bigl({n-k-3/2\atop n}\Bigr)={\Gamma(n-k-1/2)\over \Gamma(n+1)@\Gamma(-k-1/2)}={(-1/2)^{\underline{k+1}}\over\sqrt\pi n} n^{\overline{-k-1/2}},$$ replacement for line 11: $$c_j\;=\;\sqrt{@1-\alpha\over\pi}\,\sum_{k=0}^j\Bigl({1/2\atop k}\Bigr) (-1/2)^{\underline{k+1}}\, \Bigl\{{j+1/2\atop k+1/2}\Bigr\}{\alpha^k\over(1-\alpha)^k}.$$ \endchange \bugonpage 1.540 line 4 of answer 3 (98.06.18) {\tt LDA 2,7:1} \becomes {\tt LDA X2,7:1} \endchange \bugonpage 1.540 answer 4 (97.08.13) (i) (ii) (iii) (iv) (v) \becomes (a) (b) (c) (d) (e) \endchange \improvepage 1.541 line 11 (99.10.05) \.N$\gets 0$ \becomes $\.N\gets0$ \endchange \bugonpage 1.542 new answer for exercise 11 (05.10.04) \ans11. Counting as before, we find that the expected number is $$E_{mnt}={1\over n^m}\,\Bigl({n\atop 2}\Bigr)\,\sum_{k=1}^m\,\sum_{r\ge t} \,(k-1)\Bigl({k-2\atop r}\Bigr)(n-1)^{k-2-r}n^{m-k}@;$$ here $r$ is the number of entries in $a_1$, $a_2$, \dots, $a_{k-1}$ that equal $a_k$. This quantity can also be expressed in the simpler form $$E_{mnt}={1\over n^m}\,\Bigl({n\atop 2}\Bigr)\,\sum_{k>t}\Bigl({m\atop k}\Bigr)(n-1)^{m-k}\Bigl(\Bigl({k\atop 2}\Bigr)-\Bigl({t+1\atop2}\Bigr)\Bigr), \quad\hbox{for }t\ge 0.$$ Is there a simpler way yet to give the answer? Apparently not, since the generating function for given $n$ and $t$ is $$\sum_mE_{mnt}z^m={n-1\over2n}{z\over(1-z)^3}\Bigl({z\over n-(n-1)z}\Bigr)^{\!t+1}\bigl(z+(1-z)@n@(t+1)\bigr).$$ \endchange \bugonpage 1.543 line 1 of answer 14 (99.11.18) $n/m+\sqrt{n}\,x_j$ \becomes $m/n+\sqrt{m}\,x_j$ \endchange \bugonpage 1.543 line $-2$ (99.11.18) $I_1=I_2/n$ \becomes $I_1=I_2/n^2$ \endchange \bugonpage 1.544 line 6 (99.11.18) $3\le j\le m$ \becomes $3\le j\le n$ \endchange \bugonpage 1.547 line 3 of answer 13 (01.05.13) $2^{2^n(n+O(1))}$ by a factor of $2^{2^n+O(n)}$ \becomes $2^{2^n(n+O(\log n))}$ by a factor of $e^{2^n+O(n)}$ \endchange \improvepage 1.549 line 12 (02.09.28) alpha. \becomes alphameric. \endchange \bugonpage 1.550 line $-14$ (97.07.26) those move \becomes those moves \endchange \improvepage 1.555 line {\it04\/} of answer 9 (97.08.20) \undertext D2. Should door open?\\ \becomes \undertext D2. Should doors open?\\ \endchange \improvepage 1.555 line {\it14\/} of answer 9 (01.07.04) are zero \becomes are zero. \endchange \improvepage 1.555 last line of answer 9 (98.08.03) subroutine. \becomes subroutine.\quad\slug \endchange \bugonpage 1.556 line 1 of answer 5 (02.09.28) {\tt A}0 \becomes {\tt A0} \endchange \bugonpage 1.557 replacement for lines 2 and 3 (97.10.25) in $\.{X[I}_{a_1}+B_1\.,\.I_{a_2}+B_2\.,\ldots\.,\.I_{a_m}+B_m\.]$, where $B_1B_2\ldots B_m$ is an inversion table for $a_1a_2\ldots a_m$ as defined in exercise 5.1.1--7.) \endchange \bugonpage 1.557 line 1 of answer 15 (01.12.24) $\rI1\equiv\.{PIVOT},J$, $\rI2\equiv\.{P0}$, $\rI3\equiv\.{Q0}$, $\rI4\equiv\.P$, $\rI5\equiv\.{P1},\.X$; \becomes $\rI1\equiv\.{PIVOT},\.J$; $\rI2\equiv\.{P0}$; $\rI3\equiv\.{Q0}$; $\rI4\equiv\.P$; $\rI5\equiv\.{P1},\.X$; \endchange \bugonpage 1.560 line 4 of answer 21 (06.01.01) $\.L_{r-1}$ \becomes $\.L_{r-1}+(\.M_r-1)^r$ \endchange \improvepage 1.561 line 1 of answer 6 (97.08.30) [There's slightly too much space before the word ``Let''.] \endchange \bugonpage 1.561 line $-2$ (01.12.19) $Z_1\cap Z_2\ne0$ \becomes $Z_1\cap Z_2\ne\emptyset$ \endchange \bugonpage 1.562 new answer 13 (07.10.15) \ans13. $\deweyperiod a_1.a_2.\cdots.a_k$, \ $\deweyperiod a_1.a_2.\cdots.a_{k-1}$, \ \dots, \ $\deweyperiod a_1.a_2$, \ $a_1$. \endchange \improvepage 1.563 answer 17 (01.02.13) $F$ \becomes $Z$ \qquad (three times) \endchange \improvepage 1.564 line 6 (98.02.03) 2-D trees \becomes 2-d trees \endchange \improvepage 1.564 line 8 of answer 5 (97.09.03) {\it level order}; \becomes {\it level order\/}; \endchange \bugonpage 1.565 line 9 of answer 11 (99.11.13) $\displaystyle {}+{11\over 24}\sqrt{{\pi\over n}}$ \becomes $\displaystyle {}-{13\over 24}\sqrt{{\pi\over n}}+{1\over2n}$ \endchange \improvepage 1.565 line 1 of answer 12 (00.01.14) between step T2 and T3 \becomes between steps T2 and T3\nl between step T4 and T2 \becomes in step T5 \endchange \improvepage 1.565 line 6 of answer 13 (01.04.20) ``Visit'' \becomes Visit \endchange \improvepage 1.568 line 6 (06.01.01) will triple traverse the tree \becomes will traverse the tree in triple order \endchange \amendpage 1.568 line 12 (04.03.21) 7.2.1 \becomes 7.2.1.6 \endchange \improvepage 1.568 line $-4$ of answer 22 (98.07.30) [insert `\thinspace\slug\thinspace' in the rightmost column, to end the program.] \endchange \bugonpage 1.568 line $-3$ (99.09.15) $\.{RLINK(P)}\gets\.Q$ \becomes $\.{RLINKT(Q)}\gets\.{RLINKT(P)}$, $\.{RLINK(P)}\gets\.Q$ \endchange \bugonpage 1.569 line 5 of answer 26 (02.12.26) $1\le j\le n$ \becomes $1\le j\le2n$. \endchange \improvepage 1.570 line 5 of answer 31 (98.07.30) $\Lambda$. \becomes $\Lambda$.\quad\slug \endchange \improvepage 1.571 lines 2 and 4 of answer 37 (02.09.28) \.{NODE(Q+1)} \becomes \.{NODE(Q${}+1$)} \endchange \bugonpage 1.572 line 2 of answer 12 (07.10.15) $\.R\gets\.{TREE(\hbox{\rm``$\uparrow$''}$\!$,TREE}$ \becomes $\.R\gets\.{TREE(\hbox{\rm``$\uparrow$''}$\!$,R,TREE}$ \endchange \improvepage 1.575 line 6 of answer 2 (97.08.29) $\.P\gets\.P-1$ \becomes $\.P\gets\.P-c$ \endchange \improvepage 1.577 line 5 of answer 17 (97.08.29) $\.P\gets\.P-1$ \becomes $\.P\gets\.P-c$ \endchange \bugonpage 1.577 line 9 of answer 18 (01.12.24) $\.{INFO2[$k$]}\gets \.{INFO[$i$]}$ \becomes $\.{INFO2[$k$]}\gets \.{INFO1[$i$]}$ \endchange \amendpage 1.579 line $-2$ of answer 8 (01.08.21) D. E. Knuth \becomes A. Nahapetian, {\sl Acta Informatica\/ \bf3} (1973), 37--41; D.~E. Knuth \endchange \improvepage 1.579 line 4 of answer 11 (99.02.14) ``common'', \becomes ``common,'' \endchange \improvepage 1.580 lines 3 and 6 of answer 13 (06.10.23) a tree \becomes a free tree \endchange \bugonpage 1.581 replacement for answer 15 (04.02.01) \ans15. True for finite graphs: If it is connected and balanced and has more than one vertex, it has an Eulerian trail that touches all the vertices. (But false in general.) \endchange \bugonpage 1.581 lines 3 and 4 of answer 16 (04.08.21) tracing out \dots~(this graph is balanced). \becomes tracing out an Eulerian trail in~$G$, because the game ends when the fourth arc to~$V_{13}$ is encountered (namely, when the fourth king turns up). \endchange \improvepage 1.581 line 3 of answer 17 (98.04.20) methods of \ Section \becomes methods of Section \endchange \improvepage 1.581 bottom line and beginning of page 582 (06.09.05) 2.3.4.4; it also \dots~direct proof: \becomes 2.3.4.4. But such a simple answer deserves a simple, direct proof, and indeed there is~one. \endchange \bugonpage 1.582 line 13 (98.12.10) See Section \becomes See \endchange \bugonpage 1.583 line 3 (97.12.28) oriented trees is \becomes oriented trees \endchange \amendpage 1.583 better answer for exercise 21 (01.09.06) Replace the last several lines on page 583, beginning with `Add the indeterminate $\lambda$~\dots', by the following new copy: \par\noindent Add the indeterminate $\lambda$ to every diagonal element of $A$ and $A^{\ast}$. If $t(G)$ and $t(G^{\ast})$ are the numbers of oriented subtrees of $G$ and $G^{\ast}$, we then have $\det A=\lambda@t(G)+O(\lambda^2)$, $\det A^\ast=\lambda@t(G^{\ast})+O(\lambda^2)$. (The number of oriented subtrees of a balanced graph is the same for any given root, by exercise 22, but we do not need that fact.) \par If we group vertices $V_{jk}$ for equal $k$ the matrix $A^{\ast}$ can be partitioned as shown above. Let $B_{kk'}$ be the submatrix of $A^{\ast}$ consisting of the rows for $V_{jk}$ and the columns for $V_{j'k'}$, for all $j$ and $j'$ such that $V_{jk}$ and $V_{j'k'}$ are in $G^{\ast}\!@$. By adding the 2nd, \dots , $m$th columns of each submatrix to the first column and then subtracting the first row of each submatrix from the 2nd, \dots , $m$th rows, the matrix $A^{\ast}$ is transformed so that $$B_{kk'}=\pmatrix{ a_{kk'}&*&\ldots&*\cr 0&0&\ldots&0\cr \vdots&\vdots&\ddots&\vdots\cr 0&0&\ldots&0\cr}\quad\hbox{for }k\ne k',\qquad B_{kk}=\pmatrix{ \lambda{+}a_{kk}&*&\ldots&*\cr 0&\lambda{+}m&\ldots&0\cr \vdots&\vdots&\ddots&\vdots\cr 0&0&\ldots&\lambda{+}m\cr}. $$ The asterisks in the top rows of the transformed submatrices turn out to be irrelevant, because the determinant of~$A^\ast$ is now seen to be $(\lambda+m)^{(m-1)n}$ times $$\det\pmatrix{ \lambda +a_{00}&a_{01}&\ldots&a_{0(n-1)}\cr a_{10}&\lambda+a_{11}&\ldots&a_{1(n-1)}\cr \vdots&\vdots&\ddots&\vdots\cr a_{(n-1)0}&a_{(n-1)1}&\ldots&\lambda+a_{(n-1)(n-1)}\cr} =\lambda t(G)+O(\lambda^2). $$ \endchange \amendpage 1.584 replacement for the top four lines (01.09.06) Notice that when $n=1$ and there are $m$ arcs from $V_0$ to itself, we find in particular that exactly $m^{m-1}$ oriented trees are possible on $m$ nodes labeled. This result will be obtained by quite different methods in Section 2.3.4.4. \endchange \bugonpage 1.584 line 8 (97.07.30) 314.) \becomes 314. \endchange \improvepage 1.584 replacement for figure at bottom left (97.12.31) $$\vcenter{\epsfbox{\figdir/ch2a.5801}}$$ \endchange \bugonpage 1.585 last line of answer 27 (99.02.14) is combination \becomes is a combination \endchange \bugonpage 1.585 in answer 28 (06.01.01) line 9: is the determinant \becomes is $(*)$ times the determinant\nlh line 17: column $j_0$ of the left section \becomes row $j_0$ of the bottom section \endchange \amendpage 1.586 last lines of answer 4 (05.10.08) (But the stated assumption \dots~set of types.) \becomes\nl [But the stated assumption \dots~set of types. On the other hand, if such a tiling does exist, there is always a tiling that is {\it quasitoroidal}, in the sense that each of its $n\times n$ blocks occurs at least once in every $f(n)\times f(n)$ block, for some function~$f$. See B.~Durand, {\sl Theoretical Computer Science\/ \bf221} (1999), 61--75.] \endchange \bugonpage 1.587 line 7 (05.07.22) $\gamma ST$ \becomes $\gamma SJ$ \endchange \bugonpage 1.590 line 1 of answer 16 (05.11.08) $1\le j\le n$ \becomes $1\le j\.P$ and $\.P\ne \Lambda$, set $\.N\gets\max(\.N,\allowbreak\.P+\.{SIZE(P)}-\.{P0})$, $\.P\gets \.{LINK(P)}$, and repeat step~B3.'' \par Step B4, for ``$\.Q+\.{SIZE(Q)}=\.{P0}$'', read ``$\.Q+\.{SIZE(Q)}\ge \.{P0}$''; and for ``$\.{SIZE(Q)}\gets \.{SIZE(Q)}+\.N$'' read ``$\.{SIZE(Q)}\gets \max(\.{SIZE(Q)}, \.{P0}+\.N-\.Q)$''. \endchange \improvepage 1.610 line $-3$ (99.02.02) $\.{LINK(P2+1)}$ \becomes $\.{LINK(P2}+1\.)$ \endchange \improvepage 1.612 program lines {\it17}, {\it18}, {\it20\/} in answer 27 (06.11.06) \.{LINKF} \becomes \.{LINKB}, \.{LINKB} \becomes \.{LINKF}, \.{AVAILF} \becomes \.{AVAILB} \quad(six changes altogether) \endchange \bugonpage 1.612 program line {\it04\/} in answer 28 (97.08.20) buddy$_{\?k}$\.{L)} \becomes buddy$_{\?k}$\.{(L)} \endchange \bugonpage 1.612 lines 12 and 13 of answer 28 (03.09.04) \par\mixfive 11&S2&LD2&0,5(LINKB)&S&\undertext S2. Combine with buddy.\\\cr 12&&LD3&0,5(LINKF)\qquad&S\cr \endmix \endchange \amendpage 1.613 new answer (02.11.10) \ans32. Steven Crain points out that the method always frees all blocks and starts afresh before 16667 units of time have elapsed; hence the stated limit certainly exists. \em Proof: Let $u_n=n+t_n$, so that $g_n=\bigl\lfloor {5\over4}\min(10000,f(u_{n-1}-n),f(u_{n-2}-n),\ldots,f(u_0-n))\bigr\rfloor$. Let $x_0=0$ and $x_1=u_0$, and $x_{k+1}=\max(u_0,\ldots,u_{x_k-1})$ for $k\ge1$. If $x_k>x_{k-1}$ then $$u_n\le n+{5\over4}f(x_k-n)={5\over4}x_k-{1\over4}n\le {5\over4}x_k-{1\over4}x_{k-1}\qquad\hbox{for $x_{k-1}\le n%% Unicode char "8cc8 \GC73:75:-4:61% G4760 <0000000780000000000000000007f0000000000000000003fe000000000000000001ff00% 0000000000000000ff0000000000000000007f0000000000007000007f800000e0000070% 00003f800001f000007000003f800003f800007000001f000007fe00007fffffffffffff% ff00007fffffffffffffff8001f000000000000fff8001f000007800000ffe0001f00000% 7e00001ff80001f007007f00001fc00007f007c07fc0001f00000ff00ff07fc0003e0000% 1ff00ff87fc0003800001ff00ff87f00003000001fe00ff07e00003000000fe00fe07e00% 0000000007c01fe07e000380000000001fc07e0007c0000000001f807e000fe000000000% 1f007e001ff0000000003e007e003ff8000000003ffffffffffc000000007ffffffffffe% 0000000078007e00000000000000f0007e00000000000000f0007e00000000000001e000% 7e00000000000001c0007e0000000000000380007e0000000000000780007e000000e000% 000f00007e000001f000001c00007e000003fc00001800007e000007fe00000800007e00% 000fff003fffffffffffffffff801fffffffffffffffff800fffffffffffffffff800000% 00fc03f000000000000000fc03f000000000000000fc03f000000000000001fc03f00000% 0000000001fc03f000000000000001fc03f000000000000001fc03f000000000000001fc% 03f000000000000001fc03f000000000000001fc03f000003000000003f803f000003000% 000003f803f000003000000007f003f000003000000007f003f00000300000000fe003f0% 0000380000000fe003f00000380000001fc003f00000380000003f8003f0000038000000% 7f0003f000007c0000007f0003f000007c000000fe0003f00000fe000001fc0003f80001% fe000003f00003f80001ff000007e00003ffffffff00001f800003ffffffff00003f0000% 01ffffffff00007c000000ffffffff0003f00000003ffffffc001fc00000000000000000% fe000000000000000000f8000000000000000000c0000000000000000000>% % Unicode char "5baa ), 53. % 9th Chinese mathematics, 53, 59, 75, 407. % 23rd Chowla, Paromita ({\bg\C112\C059\C114\C105\C109\C116\C059\ \C099\C059\C092\C108\C059} or {\dn pAroEmtA cAvlA}), 307. % 23rd Christie Mallowan, Agatha Mary Clarissa Miller, xvii. % 6th {\mc COBOL} language, 424--434, 457, 458. % 6th Combinations of $n$ objects taken $k$ at a time, 52--53, 69, 94. % 12th \sub with repetitions permitted, 73, 92, 95, 386, 388. % 12th Composition of permutations, \see Multiplication of permutations. % 21st Connected directed graph, 372. % 23rd Continued fractions, 498, 565. % 16th Convex function, 404, 596. % 6th Conway, Melvin Edward, 151, 229. % 6th Conway, John Horton, 19, 80, 273, 408, 600. % 6th Crain, Steven Paul, 613. % 12th Cullen, Christopher, 75. % 23rd Cycle, Hamiltonian, 374, 379. % 17th Cycle lemma, 593. % 16th Cyclic shift, 185. % 10th Dahl, Ole-Johan, 229, 230, 461, 462. % 10th de Moivre, Abraham, 74, 83, 87, 106, 182, 474, 536. % 19th Dershowitz, Nachum ({\heb\Hfz/\Hyy/\Hbb/\Hvv/\Hsh/\Hrr/\Hdd/ \Hfm/\Hvv/\Hkh/\Hnn/}), 518, 588, 598. % 21st Descendant, in a tree structure, 311, 348. % 16th Dickson, Leonard Eugene, 81, 484. % 13th Dijkstra, Edsger Wybe, 17, 191, 230, 231, 240, 459, 462, 545, 580, 605. % 19th d'Imperio, Mary Evelyn, 462. % 6th Durand, Bruno, 586. % 21st Dvoretzky, Aryeh ({\heb\Hyy/\Hqq/\Hts/\Hrr/\Hvv/\Hbb/\Hdd/ \Hhh/\Hyy/\Hrr/\Haa/}), 593. % 16th $e$, 23, 619--620, 626. % 6th Euler, Leonhard ({\rus Ei0lerp2, Leonardp2} = {\rus E1i0ler, Leonard}), 49, 50, 52, 57, 75, 76, 87, 111, 374, 407, 472, 496, 536, 600. % 6th \sub constant $\gamma$, 75, 107, 114, 619--620. % 6th Eulerian trails in a directed graph, 374--376, 379, 584. % 17th \sub enumeration of, 380. %17th Fibonacci, Leonardo, of Pisa (= Leonardo filio Bonacii Pisano), 79--80, 84. % 22nd Fibonomial coefficients, 85, 484, 499. % 11th Figurate numbers, 54. % 16th Flajolet, Philippe Patrick Michel, 501, 506, 543, 565. % 6th Fletcher, William, 527. % 6th Floyd, Robert W\\\\, x, 17, 20, 422, 467, 509. % 17th Forder, Henry George, 597. % 16th F\"orstemann, Wilhelm August, 490. % 10th {\mc FORTRAN} language, viii, 231, 233, 296, 360, 458, 460. % 21st Fraenkel, Aviezri S ({\heb\Hll/\Hqq/\Hnn/\Hrr/\Hpp/ \Hyy/\Hrr/\Hzz/\Hai/\Hyy/\Hbb/\Haa/}), 251. % 14th Gau{\ss} (= Gauss), Johann Friderich Carl (= Carl Friedrich), 49, 58, 95, 490. % 15th Generating functions, 82--84, 87--96, 243, 386--389, 391--392, 394--399, 539, 542. % 21st Goldbach, Christian, 49, 407, 472. % 19th Goldstine, Herman Heine, 18, 229, 231. % 10th Greek mathematics, 2, 19, 54, 593. % 10th Gustavson, Fred Gehrung, 305. % 9th Hal\=ayudha ({\dn hlAy\kern-0.4em\char0\kern.45emD}), 53. % 15th has it OK again Hald, Anders, 103. % 21st Harmonic numbers, table, 621--622. % 6th Haros, Charles, 520. % 19th Heap, 435, \see Pool of available nodes. % 12th Hemacandra, \=Ac\=arya ({\dn aA\char99A\hbox{y\kern-0.3em\hbox{\char13}} h\kern-0.8em\char3m\char99\char6\lower0.1em\hbox{\char125}\kern-0.6emd}), 80. % 9th Hindu mathematics, 53--54, 80, 495. % 19th Hipparchus of Nic{\ae}a ({\grk<'Ipparqos ek~Nika'ias}), 592. % 21st Hofri, Micha ({\heb\Hyy/\Hrr/\Hpp/\Hkh/ \Hhh/\Hcc/\Hyy/\Hmm/}), 515. % 6th Horning, James Jay, 230. % 11th Hwang, Frank Kwangming (\GC74:74:-4:61% G2738 edited by hand! <% 000003c0001e00000000% 000003f0001f80000000% 000003fc000fe0000000% 000003fc000fe0000000% 000003f8000fc00e0000% 000003f0000f801f0000% 000003f0000f803f8000% 000003f0000f807fc000% 000003f0000f80ffe000% 03fffffffffffffff000% 01fffffffffffffff800% 00f003f0000f80000000% 000003f0000f80000000% 000003f0000f80000000% 000003f0000f80000000% 000003f0000f80000000% 000003f0000f80000000% 000003ffffff80000000% 000003ffffff80000000% 000003ffffff80000000% 00000000000f80007800% 0000000000070000fc00% 0000000000000001fe00% 0000000000000003ff00% ffffffffffffffffff80% 7fffffffffffffffffc0% 7fffffffffffffffffc0% 200000007e0000000000% 000000007e0000000000% 000000007e0001c00000% 000780007e0003e00000% 0007e0007e0007f00000% 0007fffffffffff80000% 0007fffffffffffc00000007fffffffffffc00000003e0007e0003f00000% 0003e0007e0003f000000003e0007e0003f000000003e0007e0003f000000003e0007e00% 03f000000003e0007e0003f000000003e0007e0003f000000003e0007e0003f000000003% fffffffffff000000003fffffffffff000000003fffffffffff000000003e0007e0003f0% 00000003e0007e0003f000000003e0007e0003f000000003e0007e0003f000000003e000% 7e0003f000000003e0007e0003f000000007e0007e0003f000000007e0007e0003f00000% 0007fffffffffff000000007fffffffffff00000000ffffffffffff00000000fe0000000% 03f00000000fe01c000003f00000000fc07e003f83f00000000000ff003ff80000000000% 01ff800fff000000000007ffc001ffe0000000000fffc0007ff8000000003ffc00001ffe% 00000000ffe0000007ff80000001ff80000003ffc0000007fe00000000ffc000001ff800% 0000007fe00000ffe0000000001fe00007fe00000000000fe0003fe0000000000003e000% 3e00000000000001c00020000000000000004000>%% Unicode char "9ec3 \GC74:71:-3:60% G2566 <000000001c0000000000000000001f8000000000000000001fe000000000000000001fe0% 00000000000000001fe000000000000000001fe000000000000000001fc0000000000007% 00001f8000000000000380001f8001e000000001e0001f8003f800000001f0001f8003fe% 00000000f8001f8003fe000000007c001f8007fc000000003e001f8007f8000000003f00% 1f800ff0000000001f801f800fe0000000001f801f801fc0000000000fc01f801f800000% 000007e01f803f000000000007e01f803f000000000003f01f807e000000000003f01f80% 7c000000000003f01f80f8000000000003f01f80f8000000000001f01f81f00000000000% 01f01f81e0000000000001e01f83c0007800000000001f878000fc00000000001f878001% fe00000000001f8f0003ff003fffffffffffffffff800fffffffffffffffff8007ffffff% ffffffffff800000007e003f000000000000007e003f000000000000007e003f00000000% 0000007e003f000000000000007e003f000000000000007e003f000000000000007e003f% 000000000000007e003f000000000000007e003f000000000000007e003f000000000000% 007e003f000000000000007e003f000000000000007e003f000000000000007c003f0000% 00000000007c003f00000000000000f8003f00001800000000f8003f00001800000000f8% 003f00001800000000f8003f00001800000001f8003f00001800000001f8003f00001800% 000003f0003f00001800000003f0003f00001c00000007e0003f00001c0000000fe0003f% 00001e0000000fc0003f00001e0000001fc0003f00001e0000003f80003f00003f000000% 7f00003f00003f0000007e00003f00003f000000fc00003f80007f800003f000003f8000% 7f800007e000003fc001ffc0001f8000003fffffffc003ff0000001fffffffc0fffc0000% 001fffffffc0ffe00000000fffffff00ff800000000000000000>%% Unicode char "5149 \GC63:72:-9:59% G3587 <00000000700000e0000000007c0003f0000000007f0007f8000000007ffffffc00000e00% 7ffffffe78003f007ffffffe7e007f807e0001f87fffffc07e0001f07fffffe07e0001f0% 7fffffe07e0001f07e001f007e0001f07e001f007e0001f07e001f007e0001f07e001f00% 7e0001f07e001f007e0001f07e001f007e0001f07e001f007e0001f07e001f007e0001f0% 7e001f007e0001f07e001f007e0001f07e001f007e0001f07e001f007e0001f07e001f00% 7ffffff07e001f007ffffff07e001f007e0001f07fffff007e0001f07fffff007e0001f0% 7e001f007e0001f07e001f007e0001f07e001f007e0001f07e001f007e0001f07e001f00% 7e0001f07e001f007e0001f07e001f007e0001f07e001f007e0001f07e001f007e0001f0% 7e001f007e0001f07e001f007e0001f07e001f007c0001f07e001f007c0001f07e001f00% 7ffffff07e001f007ffffff07fffff007c0001f07fffff00fc0001f07fffff00fc0001f0% 7e001f00fc0001f07e001f00f80001f07e001f00f80001f07e001f00f80001f07e001f01% f80001f07e001f01f80001f07e000003f00001f0fc000003f00001f0fc000007e00001f0% f0000007e00001f00000000fc00001f00000000fc00001f00000001f800001f00000003f% 000001f00000003e000001f00000007c000001f0000000f8000003f0000001f0000003f0% 000007e000780ff000000fc0007ffff000001f00000ffff000007e000001fff00003f800% 00007ff0000ff00000003ff0003e000000001fe00030000000001fc00000000000000f00% >%% Unicode char "660e ), 405, 595. % 9th Hwang, Hsien-Kuei (\GC74:74:-4:61% G2738 edited by hand! <% 000003c0001e00000000% 000003f0001f80000000% 000003fc000fe0000000% 000003fc000fe0000000% 000003f8000fc00e0000% 000003f0000f801f0000% 000003f0000f803f8000% 000003f0000f807fc000% 000003f0000f80ffe000% 03fffffffffffffff000% 01fffffffffffffff800% 00f003f0000f80000000% 000003f0000f80000000% 000003f0000f80000000% 000003f0000f80000000% 000003f0000f80000000% 000003f0000f80000000% 000003ffffff80000000% 000003ffffff80000000% 000003ffffff80000000% 00000000000f80007800% 0000000000070000fc00% 0000000000000001fe00% 0000000000000003ff00% ffffffffffffffffff80% 7fffffffffffffffffc0% 7fffffffffffffffffc0% 200000007e0000000000% 000000007e0000000000% 000000007e0001c00000% 000780007e0003e00000% 0007e0007e0007f00000% 0007fffffffffff80000% 0007fffffffffffc00000007fffffffffffc00000003e0007e0003f00000% 0003e0007e0003f000000003e0007e0003f000000003e0007e0003f000000003e0007e00% 03f000000003e0007e0003f000000003e0007e0003f000000003e0007e0003f000000003% fffffffffff000000003fffffffffff000000003fffffffffff000000003e0007e0003f0% 00000003e0007e0003f000000003e0007e0003f000000003e0007e0003f000000003e000% 7e0003f000000003e0007e0003f000000007e0007e0003f000000007e0007e0003f00000% 0007fffffffffff000000007fffffffffff00000000ffffffffffff00000000fe0000000% 03f00000000fe01c000003f00000000fc07e003f83f00000000000ff003ff80000000000% 01ff800fff000000000007ffc001ffe0000000000fffc0007ff8000000003ffc00001ffe% 00000000ffe0000007ff80000001ff80000003ffc0000007fe00000000ffc000001ff800% 0000007fe00000ffe0000000001fe00007fe00000000000fe0003fe0000000000003e000% 3e00000000000001c00020000000000000004000>%% Unicode char "9ec3 \JC48:48:0:40% J8093 <30000600001838000f00003c3fffffbffffe3fffffdfffff3c000f801c003c000f001c00% 3c000f0018003c000f0038003fffff0c30183fffff0e603c3c000f0ffffe3c000f0fffff% 3c000f0f003e3c000f0f003c3fffff0f003c3fffff0f003c0100100f003c0180180f003c% 03c03c0ffffc0380380ffffcc70c700f003c6e06e00f003c7c07c00f003c3843840f003c% 1c71c70f003c1cf1cf0f003c0ce0ce0f003c01c01c0ffffc0180380ffffc0320320f003c% 0630630f003c0c78c38f003c19f98f8f003cff9ffccf003c7e0df0cf003c380cc0cf003c% 0000000ffffc0000000ffffc04c30c01000004618701c0000c71c381e0c00c30c1c1e070% 1838e1c3c03c3838e0c3c01e7038e007801ef018600f000fe000003c000fc00000f00007% >%% Unicode char "986f \JC48:48:0:40% J2114 <000003000000000003c00000000003e00000003003e01800003c03c03c00003ffffffe00% 003ffffffe00003c03c03c00003c03c03c00003c03c03c00003c03c03c00003ffffffc00% 003ffffffc00003c03c03c00001803c01800000003c0000c000003c0001effffffffffff% 7fffffffffff000000000000003000001800003c00003c00003ffffffe00003ffffffe00% 003c00003c00003c00003c00003c00003c00003ffffffc00003ffffffc00003c00003c00% 003c00003c00003c00003c00003ffffffc00003ffffffc00003c00003c00003c00003c00% 003c00003c00003ffffffc00003ffffffc00003c00003c000018600018000000f00fe000% 0001fc01fc000003fc007f000007f0003f80001fc0001fc0007e00000fc003e000000780% >%% Unicode char "8cb4 ), 66. % 6th Hyperfactorial, 116. % 10th Ibn al-Haytham, Ab\=u `Al{\ii} al-\d{H}asan (= Alhazen, {\arab \Afm/\Amth/\Amy/\Amh/\Ail/\Aa/ \Afn/\Aib/ \Afn/\Ams/\Amhh/\Ail/\Aa/ \Afy/\Aml/\Aiai/ \Afw/\Aib/\Aha/}), 162. % 8th {\mc ILLIAC~I} computer, 230. % 23rd {\it in situ\/} permutation, 9, 165, 185, 523. % 10th Indian mathematics, 53--54, 80, 495. % 19th Inductive assertions, 15--20. % 6th Inorder for a binary tree, 319--323, 330--332, 346. % 6th Irrational radix, 86. % 6th Islamic mathematics, 1, 162. % 10th Jacobi, Carl Gustav Jacob, 490. % 14th Jacquet, Philippe Pierre, 515. % 6th Japanese mathematics, 112, 115. % 10th Java language, 233. % 6th Jenkins, David Philip, 460. % 12th Josephus, Flavius, son of Matthias \indexbreak ({\heb\Hhh/\Hyy/\Htv/\Htv/\Hmm/ \Hfn/\Hbb/ \Hfp/\Hss/\Hvv/\Hyy/} = {\grk F\\l'abios >I'wshpos Matj'iou}), problem, 162, 184. % 6th Kahn, Arthur Bertram, 268. % 7th Kepler, Johannes, 80, 81. % 10th Kinkelin, Hermann, 504. % 19th Kramp, Christian, 49, 486. % 19th Kruskal, Joseph Bernard, Jr\period, 386, 588. % 14th Legendre (= Le Gendre), Adrien Marie, 48, 49, 51. % 19th Lexicographic order, 20, 299--300, 306, 564. % 10th Lushbaugh, Warren Arthur, 19. % 22nd Mah\=av{\ii}ra, \=Ac\=arya ({\dn mhAvFrA\char99A\hbox{y\kern-0.3em\hbox{\char13}}}), 54. % 19th Mark I computer (Manchester/Ferranti), 18. % 21st Markov (= Markoff), Andrei Andreevich ({\rus Markov, Andrei0 Andreevich}), the elder, 495. % 19th McKeeman, William Marshall, 230. % 11th Meek, Homer Vergil, 230. % 7th Mix Barrington, David Arno, 526. % 23rd Moivre, Abraham de, 74, 83, 87, 106, 182, 474, 536. % 19th Monte Carlo method: Experiments with random data, 254, 445--447. % 6th Moore School of Electrical Engineering, 230. % 6th Multilist representation, 301. % 6th Narayana, Tadepalli Venkata, 598. % 16th Nicomachus of Gerasa ({\grk Nik'omaqos ek~Ger'aswn}), 19. % 6th Nygaard, Kristen, 229, 461. % 6th Overlapping subtrees, 326, 603. % 23rd Paper sizes, 318. % 19th Paper tape, 136--137, 229, 231. % 7th Patterns in permutations, 243. % 19th Persian mathematics, 1. % 10th Pi ($\pi$), as ``random'' example, 397. % 21st Pi\:ngala, \=Ac\=arya ({\dn aA\char99A\hbox{y\kern-0.3em\hbox{\char13}} Ep\char189l}), 53. % 9th Prinz, Dietrich G\"unter, 230. % 6th Profile of a program: The number of times each instruction is performed, 145, 170, 214, 296, 528. % 6th $q$-nomial coefficients, 65, 73, 484, 491. % 11th Quasitoroidal tiling, 586. % 21st Recursion induction, 321, 565, 569. % 6th Reingold, Edward Martin ({\heb \Hdd/\Hll/\Hvv/\Hgg/\Hnn/\Hyy/\Hyy/\Hrr/},\indexbreak{\heb \Hfm/\Hyy/\Hyy/\Hkh/ \Hfn/\Hbb/ \Hhh/\Hsh/\Hmm/ \Hqq/\Hkh/\Hts/\Hyy/}), 23, 518. % 9th Remainder, 40, 160. % 7th Redheffer, Raymond Moos, 491. % 12th Reversal of a string, 185. % 10th Ribenboim, Paulo, 466. % 6th Riemann, Georg Friedrich Bernhard, zeta function $\zeta(s)$, 76, 504. % 19th Root of a number, 22, 25, 110. % 17th Root of a tree, 308, 309, 317. % 17th \sub changing, in an oriented tree, 377. % 17th Rothe, Heinrich August, 63, 71, 486. % 14th Schlesvig-Holstein-S{\o}nderborg-Gl\"ucksborg, Christian von, \see Christian~IX. % 8th Schweins, Franz Ferdinand, 489. % 14th Shams Baragh, Armin ({\arab\Aq/\Aa/\Afr/\Aib/ \Afs/\Amm/\Aish/ \Afn/\Amy/\Aim/\Ar/\Aamd/}), 526. % 12th Shared subtrees, 326, 603. % 23rd Sibling link, 334, 336, 427--433; \also \.{RLINK} in trees. % 11th Sideways addition, 131, 480. % 6th Silver, Roland Lazarus, 527. % 6th Solitaire (patience), 377--378. % 6th Spanning subtrees, 365--370, 378--379. % 17th Stirling numbers, 66--69, 71--74, 78, 99--100, 506, 582, 591. % 16th System/360 computers, 124, 189, 230. % 11th Tape, paper, 136--137, 229, 231. % 7th Taylor, Brook, series, 83, 102. % 10th \TeX, iv, xi, 193, 202, 611, 650. % 7th Trails, Eulerian, in a directed graph, 374--376, 379--380, 584. % 17th Todhunter, Isaac, 182. % 12th Toscano, Letterio, 50. % 14th Tricks versus techniques, 574--575. % 24th Unary operator: A function of one variable, 337. % 20th Vandermonde, Alexandre Th\'eophile, 59, 70, 71. % 19th von Neumann, John (= Margittai Neumann J\'anos), 18, 229, 231, 457. % 10th (+N) Yang Hui (\JC48:48:0:40% J4544 <00c000c000c000f000f000f000f800fffff800f800fffff800f000f000f000f000f000f0% 00f000f000f000f000f000f000f0c0f000f000f1e0fffff0fffff0fffff07ffff0f000f0% 00f000f000f000f000f000f000f000f000f000f000f000f000f000fffff001f000fffff0% 01fc00f000f001fe0060006001ff8000000c03f78000001e03f7cfffffff03f3c7ffffff% 07f3c03c000007f1807c001807f00078003c0ff000fffffe0ff000fffffe1ef001e79e3c% 1cf003c79e3c38f007879e3c70f00f0f1e3c60f01e0f1c3cc0f0381e3c7c80f0001e3c7c% 00f0003c387c00f00078787800f001e0f07800f007c0e07800f01e01c0f800f0000380f0% 00f0000f00f000f0003c01f000f001e07fe000f000000fe000f0000007c0006000000380% >%% Unicode char "694a \JC48:48:0:40% J2117 <000000c00000018000c0000001e000c0000c01f001c0001e00f8e1ffffff00f8f3ffffff% c0f0ffc1c00fe0f07fc1f01f70f07fc0f81c78f07fc0f8307cf07380f0007cf07000f000% 3cf063fffffc3cf0e1fffffc1cf0c000f0001cf18000f00000f300c0f07000f000e0f078% 00f030fffffc00f078fffffcfffffcf0f0f07ffffcf0f0f003cf00f0f0f003cf00f0f0f0% 03cf00fffff003cf00fffff003cf00f0f0f003cf00f0f0f003cf00f0f0f003cf00f0f0f0% 03cf00fffff003cf00fffff003cf04f0f0f0038f0c60f060078f1c00f000078f3800f000% 070f7800f00c070ff000f01e0e0fefffffff0e0fc7ffffff1c3f8000f000183f0000f000% 381e0000f000701c0000f000c0000000f000c0000000f00000000000f000000000006000% >%% Unicode char "8f1d ), 53. % 9th Warren, Don Wyman, 359. % 22nd Wegner, Peter (= Weiden, Puttilo Leonovich = {\rus Vei0den, Puttilo Leonovich}), 306. % 22nd Weierstrass (= Weierstra\ss), Karl Theodor Wilhelm, 382. % 21st Wilf, Herbert Saul, 65, 66, 93, 94, 484. % 10th Wirth, Niklaus Emil, 191, 461. % 7th Woods Berners-Lee, Mary Lee, 230. % 6th Wortman, David Barkley, 230. % 11th Zaks, Shmuel ({\heb \Hss/\Hqq/\Hzz/ \Hll/\Haa/\Hvv/\Hmm/\Hsh/}), 598. % 21st Zeckendorf, Edouard, 495. % 10th Zeta function $\zeta(s,x)$, 44, 76, 504. % 19th \vfill \enddoublecolumns \endchange \bye [The next printing will be the 24th.] Not mentioned above: The change to page 104 causes exercise 5 to move to page 105 The change to page 366 (and 365) wasn't made in the 22nd printing; make it now On page 475, I changed ref to Cauchy in answer 45; saved a line in ans 46. On page 579, better placement of the labels in the boxes in figures at top ARTICLES "TO APPEAR" THAT ARE STILL PENDING: