
Accession Number : AD0746189
Title : Some Combinatorial Lemmas.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Personal Author(s) : Knuth,Donald E.
Report Date : JUN 1972
Pagination or Media Count : 24
Abstract : The report consists of the following short papers: (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 FordJohnson algorithm, is described. (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+t1). and at most (s+t)./(max(s,t)+1) < 2(s+t1). ways such that the partial sum x(1)+...+x(j) are nonnegative for 1<or= j <or= s+t. (Author)
Descriptors : (*COMBINATORIAL ANALYSIS, REPORTS), GRAPHICS, TOPOLOGY, SET THEORY, PERMUTATIONS, ALGORITHMS, COMPUTER PROGRAMMING
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE