CSLI Publications logo
new books
catalog
series
knuth books
contact
for authors
order
search
CSLI Publications
Facebook
 
Selected Papers on Discrete Mathematics cover

Selected Papers on Discrete Mathematics

Donald E. Knuth

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

Contents

  • 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)

Prof. Knuth's page on this book including table of contents and errata

Add to Cart
View Cart

Check Out

Distributed by the
University of
Chicago Press

pubs @ csli.stanford.edu