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 Ford-Johnson 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+t-1). and at most (s+t)./(max(s,t)+1) < 2(s+t-1). ways such that the partial sum x(1)+...+x(j) are non-negative 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