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. Kaehler.) 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\ s+t$.