Report Number: CS-TR-72-291
Institution: Stanford University, Department of Computer Science
Title: Some combinatorial lemmas.
Author: Knuth, Donald E.
Date: June 1972
Abstract: This report consists of several short papers which are
completely independent of each other:
1. "Wheels Within Wheels." Every finite strongly connected
digraph is either a single point or a set of n smaller
strongly connected digraphs joined by an oriented cycle of
length n. This result is proved in somewhat stronger form,
and two applications are given.
2. "An Experiment in Optimal Sorting." An unsuccessful
attempt, to sort 13 or 14 elements in less comparisons than
the Ford-Johnson algorithm, is described. (Coauthor: E.B.
3. "Permutations With Nonnegative Partial Sums." A sequence
of s positive and t negative real numbers, whose sum is zero,
can be arranged in at least (s+t-1)! and at most
(s+t)!/(max(s,t)+1) < 2(s+t-1)! ways such that the partial
sums $x_1 + ... + x_j$ are nonnegative for $1 \leq\ j \leq\