Preprints of Recent Papers

Electronic approximations to most of the papers I've written since 1990 can be downloaded by clicking appropriate links below. In general, these files are in plain TeX format, and they represent the initial form of the paper before copy editing and other improvements made by the publishers.

To typeset many of these files you will need Macros for illustrations picmac.tex (2458 bytes). Sometimes you also need to generate illustrations with the MetaPost source files provided. The published papers often include illustrations that are not available in electronic form.

Of course users of these files should not violate the copyrights of the publishers.

These preprints are classified into four categories:

In each group the papers are listed in reverse chronological order. Identification numbers like P156 and Q133 refer to my list of publications, where complete bibliographic data can be found.

Refereed Papers

The following papers have been refereed:

P160 Efficient coroutine generation of constrained Gray sequences, aka ``Deconstructing coroutines'' (written with Frank Ruskey).
TeX file deco.tex; MetaPost illustrations; another illustration; Compressed PostScript
P159 Dancing links.
TeX file; MetaPost illustrations (B&W); MetaPost illustrations (color); Compressed PostScript (black-and-white version); Compressed PostScript (color version); Wassermann's beautiful solutions to the Aztec Diamond challenge
P158 Linear probing and graphs.
TeX file lpg.tex (7558 bytes)
P157 Shellsort with three increments.
TeX file swti.tex (15822 bytes)
P156 Overlapping Pfaffians.
TeX file op.tex (14020 bytes)
P154 The Knowlton-Graham partition problem.
TeX file kgpp.tex (5134 bytes)
P153 Partitioned tensor products and their spectra.
TeX file ptpats.tex (7678 bytes); MetaPost file (1465 bytes)
P152 On the inversion of y-to-the-alpha times e-to-the-y by means of associated Stirling numbers.
TeX file cr.tex (4792 bytes); TeX refs file crrefs.tex (824 bytes)
P151 Irredundant intervals.
CWEB file interval.w (17672 bytes); change file (337 bytes)
P150 Aztec diamonds, checkerboard graphs, and spanning trees.
TeX file aztec.tex (7265 bytes)
P149 An exact analysis of stable allocation.
TeX file easa.tex (10384 bytes)
P148 The sandwich theorem.
TeX file sand.tex (38988 bytes); MetaPost file (618 bytes)
P147 Leaper graphs.
TeX file lg.tex (23749 bytes)
P146 Polynomials involving the floor function.
TeX file piff.tex (7384 bytes)
P145 Two-way rounding.
TeX file twr.tex (13408 bytes)
P144 Mini-indexes for literate programs.
TeX file milp.tex (15415 bytes); CWEB file ham.w (2911 bytes); change file (524 bytes); CTWILL file system.bux (288 bytes)
P143 Bracket notation for the coefficient-of operator.
TeX file bnfc.tex (10866 bytes)
P142 Johann Faulhaber and sums of powers.
TeX file jfsp.tex (18858 bytes)
P141 Convolution polynomials.
TeX file cp.tex (21312 bytes)
P140 The birth of the giant component.
TeX file bgc.tex (113574 bytes)
P139 Context-free multilanguages.
TeX file cfm.tex (13272 bytes)
P138 Theory and practice.
TeX file tap.tex (10741 bytes)
P137 Two notes on notation.
TeX file tnn.tex (25788 bytes)
P136 A note on digitized angles.
TeX file nda.tex (8439 bytes)
P135 Textbook examples of recursion.
TeX file ter.tex (15168 bytes)
P134 Nested satisfiability.
TeX file ns.tex (5653 bytes)
P132 The problem of compatible representatives.
TeX file pcr.tex (8326 bytes)
P127 Stable husbands.
TeX file sh.tex (15411 bytes)
P123 Efficient representation of perm groups.
TeX file erpg.tex (13113 bytes)

Unrefereed Papers

The following invited papers did not benefit from the formal refereeing mechanisms:

Q241 Randomness in music
Compressed PostScript file (254K bytes)
Q204 Three Catalan bijections
Compressed PostScript file (143K bytes); PDF file tcb+.pdf (259K bytes)
Q201 Robert W Floyd, In Memoriam
Compressed PostScript file (741K bytes)
Q171 Teach Calculus with Big O (unabridged version)
TeX file ocalc.tex (7860 bytes)
Q145 Foreword to A=B by Petkovsek, Wilf, and Zeilberger.
TeX file pwz.tex (1487 bytes)
Q133 This Week's Citation Classic: Artistic programming.
TeX file artprog.tex (2390 bytes)
Q130 Icons for TeX and METAFONT.
TeX file icons.tex (7112 bytes)
Q115 Memories of Andrei Ershov.
TeX file ershov.tex (2317 bytes)
Q114 The genesis of attribute grammars.
TeX file gag.tex (17167 bytes)


The following documents are essentially notes to myself and a few colleagues; I don't intend to polish them for publication, although they might form the nucleus of later work. I suggest that you download them only if you haven't been able to find anything more exciting to read on the World Wide Web.

Bipermutations (96.06.28)
TeX file biperm.tex (5785 bytes)
Squared differences of uniform deviates (95.07.18)
TeX file sdud.tex (1588 bytes)
An interesting bijection (95.05.17)
TeX file ib.tex (5047 bytes)
Solution to AMM problem 10430 (95.02.24)
TeX file 10430.tex (2145 bytes)
Solution to AMM problem 10424 (95.02.24)
TeX file 10424.tex (744 bytes)
Labeled bipartite trees (94.04.05)
TeX file lbt.tex (1543 bytes)
Nonattacking kings on a chessboard (94.02.23)
TeX file nkc.tex (2674 bytes)
Combinatorial matrices (93.01.07)
TeX file cm.tex (6621 bytes)
A bilinear identity (91.23.08)
TeX file abi.tex (1847 bytes)
An integer programming problem unsolved for 35 years (99.03.06)
TeX file prob.tex (4069 bytes); data file (4781 bytes)
A curious sequence of sets (08.01.17)
Compressed PostScript file (266328 bytes)
Diamonds and dragons: Notes on generalized dragon curves (10.09.24)
Compressed PostScript file (75351 bytes)
Comments on JRM problem 2680 (11.01.10)
TeX file JRM2680.tex (7731 bytes);    PDF (82032 bytes)
Problems that Philippe would have loved (14.06.16)
PDF (405217 bytes)
Conjectures about set partitions and generating functions (18.01.06)
text file (3K bytes)
A conjecture about noncrossing partitions (19.02.06)
PDF (83041 bytes)
A computational proof of Huang's degree theorem (19.07.27)
PDF (74334 bytes)
Culinary arts and Computer Science (19.09.28)
PDF (54107 bytes)
Plausible but bad probabilistic reasoning (19.12.30)
PDF (47971 bytes)
Asymptotic size of search trees for Fibonacci matchings (20.02.04)
PDF (126828 bytes)
Signed skeletons (20.04.24)
PDF (133792 bytes)
Whirlpool permutations (20.05.17)
PDF (124838 bytes)
Coups de grâceful graphs (20.11.16)
PDF (109721 bytes)
Amazing grace (21.01.01)
PDF (149072 bytes)
Von Neumann's 1945 manuscript on sorting (21.04.10)
PDF (158454392 bytes)
Baxter matrices (21.09.05)
PDF (107937 bytes)
Xqueens and Xqueenons (21.10.06)
PDF (124067 bytes)
Ambidextrous numbers (22.09.07)
PDF (241670 bytes)
The CVM algorithm for estimating distinct elements in streams (23.05.25)
PDF (232859 bytes)
Parades and poly-Bernoulli bijections (24.03.14)
PDF (330869 bytes)


Q167 O Calculus: A letter about calculus reform
TeX file ocalc.tex (7853 bytes)
R47 Stanford's CS204 Problem Seminar 1985, edited by Ramsey Haddad
PDF file (4.9MB)

Complete list of all Knuth's papers

Don Knuth's home page

Valid HTML 4.01 Transitional