BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-72-291
       ENTRY:: October 16, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Some combinatorial lemmas.
        TYPE:: Technical Report
      AUTHOR:: Knuth, Donald E.
        DATE:: June 1972
       PAGES:: 22
    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$.
       NOTES:: [Adminitrivia V1/Prg/19951016]
         END:: STAN//CS-TR-72-291