Selected Papers on Discrete Mathematics

Donald Knuth's influence in computer science ranges from the invention of methods for translating and defining programming languages to the mathematical analysis of algorithms and the creation of the TEX typesetting system. His award-winning textbooks have become classics that are often given credit for shaping the field; his scientific papers are widely referenced and stand as milestones of development over a wide range of topics. The present volume, which is the sixth in a series of his collected papers, is devoted to his purely mathematical work, which spans the entire range of discrete mathematics: permutations, partitions, identities, recurrences, and combinatorial designs; matrix theory, number theory, graph theory, probability theory, and a bit of algebra.

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. Knuth's 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. Everyone who enjoys mathematics will take pleasure in this unusually readable collection.

9/1/2003

1. Combinatorial Analysis and Computers 1
2. Two Notes on Notation 15
3. Bracket Notation for the ‘Coefficient-Of’ Operator 45
4. Johann Faulhaber and Sums of Powers 61
5. Notes on Thomas Harriot 85
6. A Permanent Inequality 89
7. Overlapping Pfaffians 105
8. The Sandwich Theorem 123
9. Combinatorial Matrices 177
10. Aztec Diamonds, Checkerboard Graphs, and Spanning Trees 187
11. Partitioned tensor products and their spectra 193
12. Oriented Subtrees of an Arc Digraph 203
13. Another Enumeration of Trees 209
14. Abel Identities and Inverse Relations 221
15. Convolution Polynomials 225
16. Polynomials Involving the Floor Function 257
17. Construction of a Random Sequence 265
18. An Imaginary Number System 271
19. Tables of Finite Fields 277
20. Finite Semifields and Projective Planes 305
21. A Class of Projective Planes 345
22. Notes on Central Groupoids 357
23. Huffman's Algorithm via Algebra 377
24. Wheels Within Wheels 387
25. Complements and Transitive Closures 393
26. Random Matroids 405
27. The Asymptotic Number of Geometries 425
28. Permutations with Nonnegative Partial Sums 429
29. Efficient Balanced Codes 433
30. The Knowlton—Graham Partition Problem 439
31. Permutations, Matrices, and Generalized Young Tableaux 445
32. Enumeration of plane partitions 465
33. A Note on Solid Partitions 483
34. Identities from Partition Involutions 493
35. Subspaces, Subsets, and Partitions 511
36. The Power of a Prime that Divides a Generalized Binomial Coefficient 515
37. An Almost Linear Recurrence 525
38. Recurrence Relations Based on Minimization 537
39. A Recurrence Related to Trees 565
40. The First Cycles in an Evolving Graph 585
41. The Birth of the Giant Component 643
42. Index 793

ISBN (Paperback): 1575862484 (9781575862484)
ISBN (Cloth): 1575862492 (9781575862491)

Selected Papers on Discrete Mathematics

Contents