% CHANGES TO FASCICLE V4F3 OF THE ART OF COMPUTER PROGRAMMING
%
% Copyright (C) 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 err4f3"

\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{\hss\cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill
       \titlefont\ #1\ \cleaders\hbox{\raise3pt\hbox{\manfnt\char'36}}\hfill\hss}}
\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 4 FASCICLE 3}
\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~4,
Fascicle~3, since it was first printed in 2005.

\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
\beginconstruction
The ultimate, glorious, future editions of Volumes 1--5 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, June 2005}

\bigskip
\bigskip
{\quoteformat
For a work of such scope as this,
the first word of the author should be an apology
for what is doubtless the too ambitious effort
of a single writer.
\author EDWARD W. BYRN (1900)
% The Progress of Invention in the Nineteenth Century, page i
\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 4 FASCICLE 3 %%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\lhead{\kern-12ptCHANGES TO V4F3: GENERATING ALL COMBINATIONS AND PARTITIONS}
\def\rhead{CHANGES TO V4F3: GENERATING ALL COMBINATIONS AND PARTITIONS\kern-12pt}
\titlepage
\volheadline{GENERATING ALL COMBINATIONS AND PARTITIONS} % the fascicle title
\bigskip
\rightline{Copyright \copyright\ 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

\improvepage 4f3.iv line $-12$ (05.12.04)
indices \becomes indexes
\endchange

\amendpage 4f3.0 replacement for lines 3 and 4 (07.06.13)
\beginconstruction The opening sections of this chapter will appear in
Volume~4, Fascicle~0, and
Volume~4, Fascicle~1, planned for publication in 2007 and 2008.\par\endgroup
\endchange

\improvepage 4f3.1 line $-8$ (08.04.21)
The latter representation \becomes The string representation
\endchange

\bugonpage 4f3.2 in the running headline {(also on pages 4, 6, 8,
   \dots!)} (05.09.07)
\eightpoint (F2) \becomes (F3)
\endchange

\amendpage 4f3.4 line 10 (06.10.18)
7.1--00 \becomes 7.1.3--20
\endchange

\improvepage 4f3.4 line $-7$ (05.09.17)
repeat until $c_j+1\ne c_{j+1}$. \becomes
eventually the condition $c_j+1\ne c_{j+1}$ will occur.
\endchange

\bugonpage 4f3.7 in {\eq(23)} (06.07.31)
$w_1\ge w_0;$ \becomes $w_1\ge w_0\ge0@;$
\endchange

\amendpage 4f3.8 lines $-13$ and $-12$ (06.03.24)
discovered by D.~T. Tang \becomes
discovered by J.~E. Miller in her Ph.D. thesis (Columbia University, 1971),
then independently by D.~T. Tang
\endchange

\improvepage 4f3.8 near the bottom (06.10.23)
lines $-3$ and $-1$: increasing \becomes nondecreasing\nl
line $-2$: {\it decreasing} \becomes non{\it increasing}
\endchange

\improvepage 4f3.13 in steps C4 and C6 (08.04.21)
$r=j>1$ \becomes $r=j$ and $j>1$
\endchange

\bugonpage 4f3.17 {(and throughout the fascicle!)} (08.04.04)
\ninepoint{\bf Fig.\ 26} \becomes {\bf Fig.\ 46} [and all figure
numbers need to increased by 20]
\endchange

\improvepage 4f3.20 line $-2$ (05.08.07)
in cross order \becomes in increasing cross order
\endchange

\amendpage 4f3.27 exercise 21 (06.03.24)
\ninepoint Prove \becomes (Joan E. Miller, 1971.) Prove
\endchange

\bugonpage 4f3.35 in the running headline (05.10.25)
{\eightrm PARTITIONS \becomes COMBINATIONS}
\endchange

\bugonpage 4f3.35 line 3 (06.03.07)
$11001000,\,11001001$ \becomes $11001000,\,11001010,\,11001001$
\endchange

\amendpage 4f3.35 new exercise (06.08.09)
\ninepoint{\advance\parindent by4pt
\EX111. [M26] (P. Erd\H{o}s, C. Ko, and R. Rado.)
Suppose $A$ is a set of $r$-combinations of an $n$-set, with $\alpha\cap\beta
\ne\emptyset$ whenever $\alpha,\beta\in A$. Show that $\vert A\vert\le
{n-1\choose r-1}$, if $r\le n/2$. \em Hint: Consider $\del^{n-2r}B$, where
$B$ is the set of complements of~$A$.
\par}
\endchange

\amendpage 4f3.36 line 4 (07.08.21)
(see Table 1). All twelve of Stanley's \becomes \nl
(see Table 1), based on a series of lectures by
Gian-Carlo Rota. All twelve of these
\endchange

\amendpage 4f3.37 bottom line (05.10.24)
52]: \becomes
52], and pad the array with 1s
as suggested by A.~Zoghbi and I.~Stojmenovi\'c [{\sl International
Journal of Computer Math.\ \bf70} (1998), 319--332]:
\endchange

\amendpage 4f3.38 line 3 (06.05.29)
$n\ge1$. \becomes
$n\ge1$. The value of $a_0$ is also set to zero.
\endchange

\amendpage 4f3.38 replacement for step P1 (05.10.24)
\algindentset{P1}%
\algstep P1. [Initialize.] Set $a_m\gets1$ for $n\ge m>1$. Then set $m\gets1$
and $a_0\gets0$.
\endchange

\amendpage 4f3.38 replacement for step P4 (05.10.24)
\algstep P4. [Change 2 to $1{+}1$.] Set $a_q\gets1$, $q\gets q-1$, $m\gets
m+1$, and return to P3. (At this point we have $a_k=1$ for $q<k\le n$.)
\endchange

\amendpage 4f3.40 line 3 before {\eq(13)} (07.08.25)
{\it representation}. \becomes
{\it representation} [see S. Com\'et, {\sl Numer.\ Math.\ \bf1} (1959),
90--109].
\endchange

\improvepage 4f3.45 line 3 before {\eq(40)} (06.04.18)
by considering \becomes by transposing
\endchange

\improvepage 1.406 line 2 below Table 2 (08.03.24)
Erd\H{o}s \becomes Erd\"os \qquad[to agree with the English spelling
in the paper cited]
\endchange

\bugonpage 4f3.53 bottom line (06.12.08)
\ninepoint $l_2$, $l_4$, $l_5$, $l_7$ \becomes
$l_2$, $l_4$, $l_5$, $l_6$, $l_7$
\endchange

\bugonpage 4f3.54 new wording for exercise 13 (05.08.27)
\ninepoint
\EX 13. [M22] (F. Franklin, 1882.)
Find a one-to-one correspondence between
partitions of~$n$ that have exactly $k$~even parts and partitions of~$n$
in which we can form $k$ pairs of equal parts. (For example, $k=4$
in the partition 8666433211111, because of the pairs 66, 33, 11, and~11.
The case $k=0$ corresponds to Euler's result.)
\endchange

\amendpage 4f3.57 in exercise 47 (07.02.23)
\ninepoint line 1 of step N4: 1, 2, \dots, $n$ \becomes 1, 2, \dots,\nl
line $-1$ (the displayed equation): $\displaystyle \sum_{j=1}^m$
\becomes $\displaystyle \sum_{j=1}^\infty$
\endchange

\amendpage 4f3.59 the rating of exercise 56 (07.01.21)
\ninepoint [{\it M27\/}] \becomes [{\it M32\/}]
\endchange

\bugonpage 4f3.60 line 2 of exercise 59 (06.10.26)
\ninepoint same as conjugate \becomes same as the conjugate
\endchange

\improvepage 4f3.62 line 18 (05.10.30)
in which we have \becomes of nonnegative integers in which we have
\endchange

\amendpage 4f3.63 an explanatory sentence to follow \eq(9) (08.02.09)
(In other words, we begin with either $A\losub{(m-1)n}(m{-}1)$ or
$A'_{(m-1)n}(m{-}1)$ and then use either
$A_{mn}^R@j$ or $A\losub{mn}@j$, alternately, as $j$ decreases from
$m-1$ to~0.)
\endchange

\bugonpage 4f3.67 line 14 (05.08.23)
$O\Bigl({e^{n-n^{-2\epsilon}\!/2}\over n^n}\Bigr)$ \becomes
$O\Bigl({e^{n-n^{2\epsilon}\!/2}\over n^n}\Bigr)$
\endchange

\improvepage 4f3.68 on the line following {\eq(23)} (05.09.17)
saddle point now occurs \becomes saddle point for the new integrand occurs
\endchange

\improvepage 4f3.75 line 22 (08.02.08)
simple \becomes fairly simple
\endchange

\bugonpage 4f3.75 replacement for {\eq(57)} (07.01.18)
$$\openup1\jot
\def\\#1#2{\llap{\smash{\special{ps: .5 setgray}\vrule height 95pt
           \special{ps: 0 setgray}\kern8pt}}%
       \setbox0=\hbox{\ninepoint$f_{#1}=#2$}\hbox to.5em{\hss\rotl0\hss}}
\vcenter{\halign{&\hskip1.5em\hfil$#$\cr
j  &0&1&2&3&4&5&6&7&8&9&\hidewidth10\hidewidth&\hidewidth11\hidewidth\cr
c_j&1&2&1&2&1&2&1&2&1&2&2&2\cr
u_j&9&9&6&8&4&6&2&6&1&5&4&1\cr
v_j&3&1&2&2&2&0&1&1&1&1&3&1\cr
&\\00&&\\12&&\\24&&\\36&&\\48&&\\5{10\ }&\\6{11}&\\7{12}\cr}}\eqno(57)$$
\endchange

\bugonpage 4f3.75 line $-2$ (07.01.18)
$f_0f_1\ldots f_n$, $c_0c_1\ldots c_{n}$,
$u_0u_1\ldots u_{n}$, and $v_0v_1\ldots v_{n}$ \becomes\nl
$f_0f_1\ldots f_n$, $c_0c_1\ldots c_{mn}$,
$u_0u_1\ldots u_{mn}$, and $v_0v_1\ldots v_{mn}$
\endchange

\amendpage 4f3.76 restatement of step M2 (08.02.09)
Set $j\gets a$ and \dots\ until $j=b$. \becomes
Set $j\gets a$,
$k\gets b$, and $x\gets0$. Then while $j<b$ do the following:
Set $u_k\gets u_j-v_j$.
If $u_k=0$, just set $x\gets1$ and $j\gets j+1$.
Otherwise if $x=0$, set $c_k\gets c_j$, $v_k\gets\min(v_j,u_k)$,
$x\gets\[u_k<v_j]$, $k\gets k+1$, $j\gets j+1$.
Otherwise set $c_k\gets c_j$, $v_k\gets u_k$, $k\gets
k+1$, $j\gets j+1$. (Notice that $x=\[\hbox{$v$ has changed}]$.)
\endchange

\amendpage 4f3.76 line 25 (07.01.18)
every component. \becomes every component. (See exercise 68.)
\endchange

\bugonpage 4f3.85 line 3 of exercise 63 (06.07.01)
\ninepoint $(1@{+}@p_n(1{-}z)$ \becomes $(1@{+}@p_n(z{-}1)$
\endchange

\amendpage 4f3.85 line 1 of exercise 68 (07.01.18)
\ninepoint
[{\it 20\/}] How large can the stack get in Algorithm M, when it \becomes
[{\it 21\/}] How large can variables $l$ and $b$ get in Algorithm M,
when that algorithm
\endchange

\amendpage 4f3.85 line 1 of exercise 69 (08.02.09)
\ninepoint [{\it 21\/}] \becomes [{\it 22\/}]
\endchange

\bugonpage 4f3.86 replacement for dominoes in exercise 82 (05.09.17)
\font\dom=domino scaled 700
$$\chardef\2="B2 \chardef\3="B3 \chardef\6="B6
\def\\#1#2{\vcenter{\offinterlineskip\hbox{\dom#1}\hbox{\dom#2}}}
\\1\2+\\1\3+\\41+\\15+\\1\6\;=\;
\\\2\3+\\4\2+\\\25+\\4\3+\\45\;=\;
\\\2\6+\\5\3+\\\3\6+\\\64+\\\65$$
\endchange

\let\defaultpointsize=\ninepoint % get ready for answer pages

\bugonpage 4f3.87 last line of answer 5 (06.07.31)
$(\delta_t,\ldots,\delta_1)$ \becomes $(\delta_t,\ldots,\delta_0)$
\endchange

\bugonpage 4f3.90 replacement for answer 19  (06.03.18)
\ans 19. It is the binary representation of post(1000000), where
post$(2^{k+1}-1)=2^k$, and
post$(n)=2^k+{\rm post}(n-2^k+1)$ if $2^k\le n<2^{k+1}-1$,
for $k\ge0$. So it is 11110100001001000100.\tighten
\endchange

\amendpage 4f3.90 addendum to answer 19 (06.10.02)
\noindent [Incidentally, the left-child/right-sibling representation of
$T_\infty$ is the sideways heap.]
\endchange

\bugonpage 4f3.91 line 13 of answer 25 (06.04.26)
$\{b_s,\ldots,b_1,c_t\ldots,c_1\}$ \becomes $\{b_s,\ldots,b_1,c_t,\ldots,c_1\}$
\endchange

\amendpage 4f3.95 addendum to answer 43 (06.12.08)
(Incidentally, $s(x)=f(x)\xor1$ and $p(x)=f(x\xor1)$,
where $f(x)=(x\dotminus1)+((x\band1)\lsh1)$.)
\endchange

\bugonpage 4f3.97 line 1 of answer 55 (05.09.06)
[Solution \becomes (a) [Solution
\endchange

\bugonpage 4f3.97 line 4 of answer 55 (05.12.03)
$t\le i\le n$ \becomes $t\le j\le n$
\endchange

\bugonpage 4f3.98 line 4 of answer 60 (08.02.07)
$x=t$ \becomes $x\gets t$.
\endchange

\improvepage 4f3.99 line $-5$ of answer 62 (05.09.06)
[This line, the beginning of part (e), should be indented.]
\endchange

\bugonpage 4f3.108 line 2 of answer 107 (06.08.09)
3-combinations \becomes 2-combinations
\endchange

\amendpage 4f3.109 new answer (06.08.09)
{\advance\parindent by4pt
\ans 111. $\del^{n-2r}B$ is the set of all $r$-subsets of $B$; these subsets
must not be in~$A$. If $\vert A\vert=\break\vert B\vert=
{x\choose n-r}$ for some real $x>n-1$,
we would have ${n\choose r}\ge\vert A\vert+\vert\del^{n-2r}B\vert\ge
{x\choose n-r}+{x\choose r}>{n-1\choose n-r}+{n-1\choose r}={n\choose r}$,
by exercise 80. [See {\sl Quart.\ J. Math.\ Oxford\/ \bf12} (1961),
313--320.]
\par}
\endchange

\bugonpage 4f3.110 in the running headline (05.08.27)
7.2.1.3 \becomes 7.2.1.4
\endchange

\improvepage 4f3.111 improved wording for answer 13 (05.09.17)
\ans13. Map the partition $c_1{\cdot}1+c_2{\cdot}2+c_3{\cdot}3+\cdots{}$ into
$r_1{\cdot}1+\lfloor c_1/2\rfloor{\cdot}2+
 r_3{\cdot}3+\lfloor c_2/2\rfloor{\cdot}4+
 r_5{\cdot}5+\lfloor c_3/2\rfloor{\cdot}6+\cdots{}$,
where $r_m=(c_m\mod2)+2(c_{2m}\mod2)+4(c_{4m}\mod2)+
8(c_{8m}\mod2)+\cdots{}$. [{\sl Johns Hopkins University Circular\/ \bf2}
(1882), 72.]
\endchange

\amendpage 4f3.112 line 10 of answer 17 (06.10.23)
``Partition bijections, a survey,'' to appear in {\sl The Ramanujan Journal}.
\becomes
{\sl The Ramanujan Journal\/ \bf12} (2006), 5--75.
\endchange

\bugonpage 4f3.112 line $-3$ of answer 17 (06.07.31)
$b_1<t$).\ \becomes $b_1<t$.
\endchange

\bugonpage 4f3.116 last line of answer 37 (06.08.26)
{\sl de Scienze Economiche e Commerciale\/} \becomes
{\sl di Scienze Economiche e Commerciali\/}
\endchange

\bugonpage 4f3.118 last line of answer 53 (07.02.07)
$20~8~8~8~6~5~4~3~3~3~3~2~$1^{19}$ \becomes
$20~8~8~8~8~6~5~4~3~3~3~3~2~$1^{19}$
\endchange

\bugonpage 4f3.118 part {(b)} of answer 54 (05.11.05)
$n-kl$ \becomes $n+kl$\qquad\qquad(three changes)
\endchange

\bugonpage 4f3.118 the end of answer 54{(c)} (05.11.05)
$0\le\cdots\le c_{k+1}\le\cdots c_k$ \becomes
$0\le\min(a_{k+1},b_{k+1})\le
     \min(a_{k+1},b_{k+1}+b_1+\cdots+b_k-a_1-\cdots-a_k)
=c_{k+1}\le a_{k+1}\le a_k=c_k+(c_1+\cdots+c_{k-1})
-(a_1+\cdots+a_{k-1})\le c_k$.
\endchange

\amendpage 4f3.124 line 1 of answer 72 (07.08.21)
Swap \becomes [R. ^{Stanley}, 1972 (unpublished).] Swap
\endchange

\amendpage 4f3.125 line 4 of answer 7 (07.04.25)
``Partially ordered \dots~to appear \becomes
{\sl Discrete Math.\ \bf298} (2005), 212--229
\endchange

\amendpage 4f3.131 lines 5--7 (07.04.25)
in the paper ``Crossings \dots~partitions'' \becomes in a paper\nl
(preprint, 2005) \becomes
[{\sl Transactions of the Amer.\ Math.\ Soc.\ \bf359} (2007), 1555--1575]
\endchange

\amendpage 4f3.131 line $-2$ of answer 27 (05.11.05)
S. Fomin, \becomes
A.~Berele, {\sl J. Combinatorial Theory\/ \bf A43} (1986), 320--328;
S.~Fomin,
\endchange

\bugonpage 4f3.132 line 23 of answer 29 (06.06.27)
[The formula \becomes \em Notes: The formula
\endchange

\amendpage 4f3.141 lines 2 and 3 of answer 68 (07.01.18)
The maximum level is also equal to~$n$. \becomes
Then the values of $l+1=n$ and $b=mn_1+(m-1)n_2+\cdots+n_m$ 
reach their maximum.
[Thus it's best to choose names of the multiset elements
so that $n_1\le n_2\le\cdots\le n_m$.]
\endchange

\bugonpage 4f3.143 replacement for domino displays in answer 82 (05.09.17)
\begingroup\chardef\2="B2 \chardef\3="B3 \chardef\6="B6
\font\dom=domino scaled 500
\def\\#1#2{\vcenter{\offinterlineskip\hbox{\dom#1}\hbox{\dom#2}}}%
$$\thickmuskip=8mu
\\1\2\equiv\\\24\equiv\\\3\6\,,\quad
\\1\3\equiv\\\2\6\,,\quad
\\\2\3\equiv\\4\6\,.$$
$$\\\21+\\15+\\4\2+\\5\3+\\\6\3\;=\;
\\1\3+\\\61+\\\25+\\\2\6+\\45\;=\;
\\41+\\\2\3+\\4\3+\\4\6+\\\65$$
\medskip
\endgroup
\endchange

\expandafter\ifx\csname indexeject\endcsname\relax\else\vfill\eject\fi
\amendpage 4f3.144 and following (05.06.23)
Miscellaneous changes to the existing index of Volume~4 Fascicle~3
are collected here,
including corrections and amendments to the old entries as well as new entries
that are occasioned by the new material. Thus, the lines of the full index
that have changed serve also as an index to the present document. However,
when a correction or amendment has caused an old index entry to be deleted,
the deletion is usually not indicated.

\input exotic
\begindoublecolumns
\indexformat
\gdef\Uni1.08:{\bitmap24:1.08:}
\hangindent2em
Berele, Allan, 131. % 2nd
Bitstring notation: Data represented as a string of $0@$s and~1s, 1--2, 26, 28. % 2nd
Bitwise operations, 4, 95, 109. % 2nd
Com\'et, Stig, 40. % 2nd
Dominance order, \see Majorization. % 2nd
Erd\H{o}s, P\'al (= Paul), 19, 35, 46, 57. % 2nd
$f$-vectors, \see Size vectors. % 2nd
Fibonacci, Leonardo, of Pisa (= Leonardo filio Bonacii Pisano), recurrence, 42. % 2nd
Hickey, Michael, 16, 97. % 2nd
Ko, Chao (= Ke Zhao, \GC74:74:-3:61% G3134
<001e0000000000000000001fc000000000000000000ff000000000000000000ff0000000%
 00000000000ff000000000000000000ff000000000000000000f8000000000001c00000f%
 8000000000003e00000f8000000000007f00000f807fffffffffff80000f803fffffffff%
 ffc0000f801fffffffffffc0000f80060000001f8000000f80000000001f8000000f8000%
 0000001f8000000f81c00000001f8000000f83e00000001f8000000f87f00000001f8000%
 fffffff80000001f80007ffffffc0000001f80003ffffffc0000001f8000080f80038001%
 c01f8000000f8003c003e01f8000000f8003f007f01f8000001f8003fffff81f8000001f%
 8003fffffc1f8000001f8003f003e01f8000001f8001f003e01f8000001f8001f003e01f%
 8000001f8001f003e01f8000003f8001f003f01f8000003ff001f003f01f8000007ffe01%
 f003f01f8000007fff81f003f01f8000007fffc1f003f01f800000ff9fe1f003f01f8000%
 00ff8ff1f003f01f800000ff87f1f003f01f800001ef83f9f003f01f800001ef81f9f003%
 f01f800003cf80f9f003f01f800003cf80f9f003f01f8000078f8079f003f01f8000078f%
 8021f003f01f80000f0f8001f003f01f80000f0f8001f003f01f80001e0f8001fffff01f%
 80001e0f8001fffff01f80003c0f8001f003f01f80007c0f8003f003f01f8000780f8003%
 f003f01f8000e00f8003f003f01f8000c00f8003f003e01f8000800f8003f000001f8000%
 800f8003f000001f8000000f8003f000001f8000000f80000000001f8000000f80000000%
 001f8000000f80000000001f8000000f80000000001f8000000f80000000001f8000000f%
 80000000001f8000000f80000000001f8000000f80000000001f8000000f80000000001f%
 8000000f80000000ffff8000001f80000000ffff8000001f800000001fff8000001f8000%
 000007ff0000001f8000000003ff0000001f8000000001ff0000001f8000000000fe0000%
 001f0000000000fe0000001f0000000000f00000>%% Unicode char "67ef
\GC68:72:-5:59% G5357
<000000000000000e00000000000000003f00000000000000007f801fffffffffffffffc0%
 0fffffffffffffffe007fffffffffffffff00200001fc000003ff00000001fc000003fc0%
 0000001f8000003f000000003f8000003f000000003f8000003f000000003f8000003f00%
 0000003f8000003f000000003f8000007f000000003f0000007f000000003f0000007f00%
 0000007f0000007e000000007e0000007e00000000fe000000fe00000000fc000000fe00%
 000001fc000001fe00000001f8000001fc00000003f8000001fc00000003f0000001f800%
 000007f001f803f80000000fe001ff83f00000000fc0001ffff00000001f800007ffe000%
 00003f800003ffe00000007f000001ffc00000007e000000ff80000000fc000000ff0000%
 0001fc0000007e00000003f80000004000000007f0000000000000000fe000000000e000%
 001ffc00000001f800003e7f00000003fc00007c7ffffffffffe0001f07ffffffffffe00%
 07e07ffffffffffe000f007e00000001f8003c007e00000001f800e0007e00000001f800%
 c0007e00000001f80000007e00000001f80000007e00000001f80000007e00000001f800%
 00007e00000001f80000007e00000001f80000007e00000001f80000007e00000001f800%
 00007e00000001f80000007e00000001f80000007e00000001f80000007e00000001f800%
 00007e00000001f80000007e00000001f80000007e00000001f80000007e00000001f800%
 00007ffffffffff80000007ffffffffff80000007ffffffffff80000007e00000001f800%
 00007e00000001f80000007e00000001f80000007e00000001f80000007e00000001f800%
 00007e00000001f8000000fe00000001f8000000fc00000001f8000000fc00000001f000%
 >%%  Unicode char "53ec
), 35. % 2nd
Left-child/right-sibling links, 90. % 2nd
Lenin, Vladimir Ilyich ({\rus Lenin, Vladimir Ilp1ich}), 11. % 2nd
Littlewood, Dudley Ernest, 120. % 2nd
Littlewood, John Edensor, 121. % 2nd
Miller, Joan Elizabeth, 8, 27. % 2nd
Notational conventions:\indexnoperiod % 2nd
\sub $\Gamma^R$ (reversal), 8. % 2nd
\sub ${n\parts m}^{\mathstrut}_{\mathstrut}$ (the number of partitions of~$n$ into exactly $m$~parts), 38. % 2nd
Rado, Richard, 35. % 2nd
Rota, Gian-Carlo, 36. % 2nd
Seth, Vikram ({\dn Evk\kern-.6em\hbox{\char2}\kern.6emm s\kern-0.8em\char3W}), ii, 83. % 2nd
Sideways heap, 90. % 2nd
Stojmenovi\'c, Ivan Dan\v{c}a ({\rus Stojmenovits1, Ivan Dancha}), 37. % 2nd
Ulyanov, Vladimir Ilyich ({\rus Ulp1yanov, Vladimir Ilp1ich}), 11. % 2nd
Zoghbi, Antoine Chaiban \indexbreak
 ({\arab\Afy/\Amb/\Aigh/\Afz/\Ail/\Aa/ \An/\Afa/\Amb/\Amy/\Aish/ \An/\Afw/\Amtt/\Ain/\Aha/}), 37. % 2nd

\vfill
\enddoublecolumns
\endchange

\bye

******** I'm not sure yet about the Figure renumbering constant! **********
******** (needs to be fixed also in err4f2 and err4f4) ********************

[The next printing will be the 2nd.]
not listed above:
page iii, The Stanford -> the Stanford
page 2, new paragraph break near the bottom
page 31, more complete list in lines 7 and 10 of exercise 62
page 35, improved wording in exercise 110
page 46, improved wording after (43), with reference to exercise 35
page 58, better wording in ex 55 line 2
pages 34, 35, 106--109: parindent is a tad too big on ex numbers > 99
page 96, "To" -> "Go to" in steps CB7, CB8
page 97, avoided clashes between lines in answer 49
I moved a line from page 99 to page 100
page 112, improved wording in answer 17(b)
page 120, commas in step M5
Index entries for pi as random ex, shadow of binary string move from 35 to 34

check |gosper-hack|=20 in 7.1.3.ref, regarding page 4f3.4

ARTICLES "TO APPEAR" THAT ARE STILL PENDING:
7.2.1.4, Colthurst--Kleber paper on binary partitions
 [as of April 2007, Kleber's home page says it is still a work in progress]