Selected Papers on Discrete Mathematics

This is the sixth in a series of eight volumes that contain archival forms of my published papers, together with new material. (The first book in the series was Literate Programming; the second was Selected Papers on Computer Science; the third was Digital Typography; the fourth was Selected Papers on Analysis of Algorithms; the fifth was Selected Papers on Computer Languages.) The Discrete Mathematics volume is characterized by the following remarks quoted from its preface.

This book brings together almost everything that I've written about mathematical topics during the past four decades. I'm grateful for this opportunity to put the materials into a consistent format, and to correct errors in the original publications that have come to my attention. If any of this work deserves to be remembered, it is now in the form that I most wish people to remember it.

Some of these papers were written purely as expositions in which I tried to introduce important work of other people and to explain it as well as I could. Other papers contain ideas that were novel when I wrote them down; but even in such cases I did not address the papers to specialists. I tried to make every paper self-contained, so that readers with a general mathematical background would be able to understand the details. My tendency has always been not to emphasize the theorems on the “bottom line,” but rather to tell a story of how various results fit together in harmonious patterns.

... Although the present book is by no means a text on discrete math, readers will find just about every basic aspect of that subject in here somewhere: permutations, partitions, identities, recurrences, and combinatorial designs; matrix theory, number theory, graph theory, probability theory, and a bit of algebra. Therefore I hope this book will be of interest to students and teachers of mathematics, as well as to everyone else who has become seduced by the deep pleasures of this subject.

... And then the preface continues by describing the various chapters, which can be summarized more succinctly by quoting from the hype on the back cover:

More than forty of Knuth's classic papers on the subject are collected in this book, brought up to date with extensive revisions and dozens of pages of new material. The papers emphasize general techniques that apply to many different kinds of problems, together with the joy of discovery associated with beautiful mathematical patterns. His prize-winning expositions of mathematical notation, his accounts of fascinating episodes in the history of mathematics, and his fundamental papers on tableaux and random graphs all are found here, accompanied by 50 newly created illustrations.

Here's the table of contents:

1. Combinatorial analysis and computers [P19]
2. Two notes on notation [P137]
3. Bracket notation for the `coefficient-of' operator [P143]
4. Johann Faulhaber and sums of powers [P142]
5. Notes on Thomas Harriot [excerpted from Q68]
6. A permanent inequality [P102]
7. Overlapping Pfaffians [P156]
8. The Sandwich Theorem [P148]
9. Combinatorial matrices [previously unpublished]
10. Aztec diamonds, checkerboard graphs, and spanning trees [P150]
11. Partitioned tensor products and their spectra [P153]
12. Oriented subtrees of an arc digraph [P26]
13. Another enumeration of trees [P33]
14. Abel identities and inverse relations [Q25]
15. Convolution polynomials [P141]
16. Polynomials involving the floor function [P146]
17. Construction of a random sequence [P24]
18. An imaginary number system [P3]
19. Tables of finite fields [P20]
20. Finite semifields and projective planes [P21]
21. A class of projective planes [P22]
22. Notes on central groupoids [P36]
23. Huffman's algorithm via algebra [P101]
24. Wheels within wheels [P61]
25. Complements and transitive closures [P50]
26. Random matroids [P72]
27. The asymptotic number of geometries [P62]
28. Permutations with nonnegative partial sums [P57]
29. Efficient balanced codes [P114]
30. The Knowlton--Graham partition problem [P154]
31. Permutations, matrices, and generalized Young tableaux [P38]
32. Enumeration of plane partitions [P49]
33. A note on solid partitions [P39]
34. Identities from partition involutions [P87]
35. Subspaces, subsets, and partitions [P43]
36. The power of a prime that divides a generalized binomial coefficient [P121]
37. An almost linear recurrence [P25]
38. Recurrence relations based on minimization [P66]
39. A recurrence related to trees [P120]
40. The first cycles in an evolving graph [P122]
41. The birth of the giant component [P140]

(Numbers like P19 and Q68 in this list refer to the corresponding papers in my list of publications.)

This book can be ordered from the publisher (CSLI), and also from the distributor (University of Chicago Press).

... a real gem. Knuth writes well, and his papers are always interesting. ... non-specialists will enjoy this book. Most of the papers include addenda on further developments, so that in fact the book is not just a historical artifact but also a useful source of up-to-date information. ... As one might expect, the book is very well produced ... in terms of book design and typography. This one you want to have. -- Fernando Q. Gouvêa, MAA Reviews (October 2003)

Knuth again (as in so many of his previous publications) manages to draw the reader into the subject. ... All of these papers are beautifully written. ... The scope of these contributions covers the majority of topics in discrete mathematics.
-- F. Winkler, in Computing Reviews (September 2004)

Most of the papers are followed by “Addenda” with today's remarks about the current state of events concerning the problems under discussion. ... The list [of topics in the author's preface] is, of course, not exhaustive. Not pretending to give one either, we would add the following items: history of mathematics ... dug up for us readers and scattered throughout the whole volume; discussion of various types of notation; and also enumerative combinatorics, uniformly distributed sequences, algorithms, asymptotics, and numerous other subjects.
-- Alexander Zvonkin, in Mathematical Reviews (March 2005)

It is greatly rewarding to read this book as a way of learning how to write good papers.
--Carlos A. S. Oliviera, in SIGACT News (December 2004)

As with all of Knuth's books, this book is written authoritatively and eloquently ... a testament to clean, formal writing. ... The notation and typography are beautiful and succinct. As mentioned above, some of the chapters even explicitly focus on which notation is the most clear and useful. I found it a delight to read.
-- Daniel Apon, in SIGACT News (June 2014)

Errata

As usual, I promise to deposit 0x$1.00 ($2.56) to the account of the first person who finds and reports anything that remains technically, historically, typographically, or politically incorrect.

Here is a list of all nits that have been picked so far in the first printing (2003); an asterisk (*) marks technical errors that are not merely typographical:

page iv, line 9 (02 Aug 09)

change "Selected Papers in" to "Selected Papers on"

page xiii, line 4 (11 Dec 04)

change "Structures and" to "Structures &"

page xiv, line 20 (16 Dec 03)

change "permissionof" to "permission of"

page xv, line 17 (14 Feb 04)

change "pp. 355" to "p. 355"

page 11, line 3 from the bottom (25 Oct 11)

change "84" to "83"

page 12, line 2 (25 Oct 11)

change "82" to "81"

*page 21, lines 8 and 9 (29 Mar 23)

change "[x divides k] - [x divides k - 1] for all k > 0" to "[x divides k - 1] - [x divides k] for all k > 0 and x > 0"

page 23, line 13 (13 May 14)

change "p" to "P" (twice)

*page 30, line 7 (26 Jan 07)

the displayed formula should actually be $$C_2(n)=3{n+1\choose4}+2{n+1\choose3};\qquad \Gamma_2(n)=3{n+2\choose4}+{n+2\choose3}.$$

page 39, line 20 (26 Feb 24)

change "Stirling subset number" to "Stirling partition number"

page 41, line 11 (09 Dec 04)

change "Oxford," to "Oxford:"

page 44, line 19 from the bottom (29 Mar 23)

change Probaba- to Proba-

page 52, line 2 (26 Jan 07)

change "because w" to "because z"

page 66, line 6 from the bottom

change $g_{r,2m=1}$ to $g_{r,2m-1}$

page 76, line 8 (08 Aug 12)

change "6048000" to "604800"

page 81, line 10 (17 Apr 05)

change "u^{-k/2-j/2}\Bigr)" to "\Bigr)u^{-k/2-j/2}"

page 86, line 13 from the bottom (11 Aug 22)

change "pound" to "ounce" (twice); also change "lb" to "oz" three times in the preceding lines

page 88, new material for bottom of page (09 Jan 04)

Addendum
I thank David Fowler for pointing out that John Wallis exhibited “Stirling numbers of the first kind” in several formulas for figurate numbers, for example on page 162 of his Arithmetica Infinitorum (1655).

page 92, line 4 (17 Apr 05)

change "from 0 to 1" to "from $0$ to $1$"

page 93, line 15 from the bottom (23 Apr 05)

change "\sum_i" to "\sum_j"

page 93, line 14 from the bottom (17 Apr 05)

change $\per_j(a_1,\ldots,b,b)$ to $\per_j(a_1,\ldots,a_{n-3},b,b)$

page 94, line 12 from the bottom (29 Oct 20)

change "Buseman's" to "Busemann's"

page 100, in the displayed equations (4.6) (23 Apr 05)

change "=" to " = " (twice)

*page 100, line 10 from the bottom (17 Apr 05)

change $[i\prec j]-[i\prec\jhat]$ to $[i\prec\ihat]-[i\prec\jhat]$

page 103, reference [3] (29 Oct 20)

change 'Buseman" to "Busemann"

*page 126, line 5 from the bottom (24 Apr 07)

change "whenever" to "whenever $u\ne v$ and" (twice)

*pages 135 and 136 (11 Oct 14)

A major error in the original version of these pages (and also page 176) has been corrected: See the replacement pages

*page 143, line 15 (17 Apr 05)

change "{c(a_{v_\max})\over\vartheta}" to just "c(a_{v_\max})" in this displayed equation

*page 145, second line of display (19.4) (17 Apr 05)

change \sqrt{w_{v'}} to \sqrt{w'_v} and change \sqrt{w_{v''}} to \sqrt{w''_v}

page 151, below the $\sum$ sign in (22.15) (30 Jan 07)

change $0\le j<n$ to $j=0$

page 154, line 18 (24 Apr 07)

change "mal feasible" to "mum feasible"

page 163, line 13 from the bottom (18 Sep 05)

change "{\sl for all $z\in z$}" to "for all $z\in Z$"

*page 165, last line of (33.3) (12 Feb 07)

change $u\not\adj v$ to $u\adj v$

page 168, lines 3 and 4 from the bottom (12 Mar 07)

change "not necessarily optimum" to "not necessarily satisfying (12.2)"

page 176, new paragraph (20 Sep 03)

Problem P6 has been solved when $p=1/2$ by Uriel Feige and Robert Krauthgamer, “The probable value of the Lovász--Schrijver relaxations for maximum independent set,” SIAM Journal on Computing 32 (2003), 345--370.

*page 176, replacement page (11 Oct 14)

See the note above for pages 135 and 136

page 183, line 4 from the bottom (12 Mar 07)

change u to v

page 185, line 12 (17 Apr 05)

change "linearly independent" to "linearly independent eigenvectors"

page 191, in reference [2]

change 'Čulik' to 'Čulík'

page 197, line 4 from the bottom (12 Mar 07)

change $(\sigma a)$ to $\sigma\ a)$

page 208, new copy at end of page (03 May 17)

Addendum
A nice “combinatorial construction” has indeed been found, by Hoda Bidkhori and Shaunak Kishore, “A bijective proof of a theorem of Knuth,” Combinatorics, Probability and Computing 20 (2011), 11–25.

page 237, line 19 (12 Mar 07)

change n to j in the formula (four changes)

*page 247, line 13 (29 May 05)

change $\sum_{k=0}^n$ to $\sum_{n\ge0}$

page 247, line 16 (29 May 05)

change $H_n(x)$ to $H_n^{(t)}(x)$

page 260, line 7 (12 Mar 07)

change zd to d (three chnages)

*page 262, in the lower part of the definition of $y_j$ in line 17 (12 Mar 07)

change $-q$ to $+q$

*page 262, line 18 (24 Apr 07)

change $k-2$ to $k-1$ (two changes)

page 283, left side of (11)

change $\pi^j+\pi^k$ to ind$(\pi^j+\pi^k)$

page 301, two lines after the tables (16 Jun 05)

change $b_1t_3+t_6=1$ to $b_1t_3+t_6\equiv1$

*page 314, lines 2 and 3 (12 Mar 07)

interchange $\star_1$ with $\star_2$ and $\square_1$ with $\square_2$

*page 314, line 1 of Theorem 3.2.3 (12 Mar 07)

change {\sl elements} to {\sl nonzero elements}

*page 322, line 4 from the bottom (16 Jun 05)

change $C(AB)T$ to $C(AB^T)$

*page 330, line 1 (27 Mar 07)

insert ", $u\ne 0$"

page 335, line 1 (01 Oct 03)

change "Theorem 6.1." to "Theorem 6.1.1."

*page 337, line 16 (27 Mar 07)

change $\lambda c^2 e$ to $\delta c^2 e$

page 337, line 7 from the bottom (01 Oct 03)

change "Theorem 6.1" to "Theorem 6.1.1"

page 344, new paragraph to precede the last three lines (16 Jul 06)

I learned in 1967 that several of the three-dimensional results in Section 4 had been anticipated in an unpublished work of R. L. McFarland, “Cubic matrices and finite dimensional algebras,” Research Foundation Project 646, Technical Report No. 4 (Columbus, Ohio: The Ohio State University, November 1961), 62 pp.

page 352, line 1 (27 Mar 07)

change {\sl automorphism} to {\sl autotopism}

page 355, line 4 from the bottom (22 Dec 03)

change "(to appear)" to "270 (2003), 96--114"

*page 355, line 2 from the bottom (25 Jul 04)

change "semifield planes of order $2^n$" to "planes of order $2^n$ that are coordinatized by commutative semifields"

page 372, in reference [2]

change "1969" to "1970"

page 373, line 3 from the bottom (16 Jun 05)

change $g(m,v)$ to $g(m,b)$

page 375, line 4 (16 Jun 05)

change $x'\not\to y$ to $x'\not\to y'$

page 375, line 13 from the bottom (26 Oct 03)

change "Dan" to "Daniel"

page 375, lines 10, 11, and 12 from the bottom (26 Oct 03)

change "preprint ... (February 2003)" to "Journal of Combinatorial Theory A105 (2004), 35--50"

page 395, line 13 from the bottom (16 Jun 05)

change $bR+a$ to $bR^+a$

page 403, line 5 (06 Jan 22)

change "Theorem 4" to "Theorem 5"

page 412, lines 17 and 18 (16 Jun 05)

change $\cal F$ to $\cal F'$ (twice)

page 438, line 7 (16 Jun 05)

change $\nu(v)$ to $\nu(u)$

page 438, replacement for reference [1] (03 Mar 09)

[1] J. Aebly, “Démonstration du problème du scrutin par des considérations géométriques,” L'Enseignement Mathématique 23 (1923), 185--186.

page 458, line 4 (27 Mar 07)

change "from tableau $P$" to "from the dual tableau $P$"

page 460, line 14 from the bottom (16 Jun 05)

change "Theorem 4" to "Theorem 5"

page 461, line 12 from the bottom (16 Jun 05)

change "Theorem 2" to "Theorem 3"

page 461, line 3 from the bottom (16 Jun 05)

change "§4" to "§5"

page 462, line 8 (16 Jun 05)

change "leader" to "reader"

page 463, line 12 (16 Jun 05)

change $Y_{i1}\ldots Y_{ip_i}$ to $y_{i1}\ldots y_{ip_i}$

page 470, line 17 (27 Mar 07)

change $n_{23}$ to $n_{33}$

*page 488, insert missing line after line 14 (24 Jul 05)

for k:=1 step 1 until n do d[k]:=0;

*page 488, line 13 from the bottom (24 Oct 05)

change "rr[pp] := rr[pp] + 1" to "rr[p] := rr[p] + 1"

page 489, line 6 (24 Oct 05)

change "$d_2(n)$ and $e_2(n)$ are defined similarly" to "$c_2(n)$ and $e_2(n)$ are obtained from $d_2(n)$ in a similar way"

page 510, lines 7--9 from the bottom (24 Jul 05)

change "15" to "16" (twice), "16" to "17", and "14" to "15"

page 510, bottom two lines (19 Sep 05)

change "preprint ... 2003)." to "Journal of Combinatorial Theory A105 (2004), 63--77."

page 513, line 3 from the bottom (30 Mar 04)

change "Grassman" to "Grassmann"

page 582, in reference [3] (25 Feb 09)

change "SIAM Journal of Discrete" to "SIAM Journal on Discrete"

page 597, in (4.1) (12 Mar 07)

move the $\lambda$ into the denominator of the integrand

page 602, line 16 (12 Mar 07)

change $h'(1)\approx0$ to $h'(1)=0$

*page 603, line 9 (12 Mar 07)

change $+{1\over2}\mu^k$ to $-{1\over2}(-\mu)^k$

*page 631, line 7 (24 Jul 05)

change $2l_{p_l}$ to $2lp_l$ and $2l_{\hat p_l}$ to $2l\hat p_l$

*page 635, in (A.9) (12 Mar 07)

change $(3x)^k$ to $(3^{1/3}x)^k$

*page 639, bottom line (12 Mar 07)

change $v^{2m+1}$ to $v^{2m+2}$

page 643, line 5 (11 Dec 04)

change "Structures and" to "Structures &"

page 647, bottom line (24 Oct 11)

change G to M

page 651, line 12 (13 Aug 05)

change $\widehat F$ to $F$

page 653, line 5 from the bottom (13 Aug 05)

change "Lemma 2 and (3.16)" to "Lemma 2"

page 662, line 5 from the bottom (13 Aug 05)

change $\widehat E_r$ to $\widehat E_r(z)$

page 682, first line of (9.12) (13 Aug 05)

change $n_{\vert\sigma(j)\vert}$ to $n_{\vert\sigma j\vert}$

*page 683, line 3 (13 Aug 05)

change $\sigma_j$ to $\sigma j$

*page 683, line 2 from the bottom (13 Aug 05)

change $n'_{\vert\sigma j\vert}$ to $n_{\vert\sigma j\vert}$

page 699, lines 5 and 6 (13 Aug 05)

change "Corollary 9" to "Corollary 8"

*page 713, line 4 (18 Sep 05)

change "{\sl The expected}" to "{\sl Let $\mu_0>0$. The expected}"

*page 713, line 7 (18 Sep 05)

change $\mu\ge\delta>0$ to $\mu\ge\mu_0$

page 734, line 8 from the bottom (13 Aug 05)

change "(19.6)" to "(19.16)"

page 788, line 10 from the bottom (11 Dec 04)

change "Structures and" to "Structures &"

page 790, lines 4, 23, and 26 (11 Dec 04)

change "Structures and" to "Structures &"

page 793, right column (03 Mar 09)

change "André, Antoine Désiré" to "Aebly, Jakob" (and re-alphabetize)

page 794, left column (24 Dec 06)

new entry "association schemes, 186."

page 794, right column (03 May 17)

new entry "Bidkhori, Hoda, 208."

page 795, right column (28 Apr 11)

Brun, Viggo, 42.

page 795, right column (10 Feb 23)

change 'Burnside, William Snow' to 'Burnside, William'

page 795, right column (29 Oct 20)

change 'Buseman' to 'Busemann'

page 795, Cantor entry in the right column (26 Jun 05)

change 'Philip' to 'Philipp'

page 797, left column, Coxeter entry

change 'Macdonald' to 'MacDonald'

page 797, right column, Desargues entry (20 Jun 05)

change "Gérard" to "Girard"

page 797, right column, Désarménien entry (17 Mar 11)

change "Jeanésarménien" to "Jean"

page 797, right column (11 Oct 14)

DeCorte, Philip Evan Bigras, 176.

page 797, right column, Dijkstra entry (28 Mar 05)

change "Wijbe" to "Wybe"

page 798, left column (20 Sep 03)

Feige, Uriel, 176.

page 798, left column (09 Jan 04)

figurate numbers, 88.

page 799, left column (29 Oct 20)

change 'Fano, Robert Mano' to "Fano, Robert Mario'

page 799, right column (09 Jan 04)

Fowler, David H., 88.

page 800, left column, Hagen entry (29 Oct 20)

change 'George' to 'Georg'

page 800, right column (30 Mar 04)

Grassmann, Hermann Günther, 513.

page 802, right column (03 May 17)

new entry "Kishore, Shaunak, 208."

page 802, right column (20 Sep 03)

Krauthgamer, Robert, 176.

page 804, right column (18 Mar 11)

delete the entry for Markov the younger, and put pages 646--647 into the entry for Markov the elder

page 805, left column (16 Jul 06)

McFarland, Robert Lee, 344.

page 806, left column, Padberg entry (29 Oct 20)

change 'William' to 'Wilhelm'

page 807, polytope entry (12 Mar 07)

polytopes, 162, 168

page 809, left column (28 Apr 11)

Skolem, Thoralf Albert, 42.

page 809, right column, Stirling entry (09 Jan 04)

numbers, history, x, 29--35, 87--88.

page 809, right column, Stirling entry (26 Feb 24)

change "subset numbers" to "partition numbers"

page 811, right column (21 May 04)

Viennot, Gérard Michel François Xavier, 78--79, 84.

page 811, right column (09 Jan 04)

Wallis, John, 88.

page 812, Zariski entry (13 Apr 2024)

change "Zaristky, Asher" to "Zaritsky, Osher Betsalelovich"

I hope the book is otherwise error-free; but (sigh) it probably isn't, because each page presented me with hundreds of opportunities to make mistakes. Please send suggested corrections to knuth-bug@cs.stanford.edu, or send snail mail to Prof. D. Knuth, Computer Science Department, Gates Building 1B, Stanford University, Stanford, CA 94305-9015 USA. In either case please include your postal address, so that I can mail an official certificate of deposit as a token of thanks for any improvements to which you have contributed.

I may not be able to read your message until many months have gone by, because I'm working intensively on The Art of Computer Programming. However, I promise to reply in due time.

DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS! And if you do report an error via email, please do not include attachments of any kind; your message should be readable on brand-X operating systems for all values of X.

Don Knuth's home page

Don Knuth's other books