Some Combinatorial Lemmas.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1972
- Accession Number
- AD0746189
Entities
People
- Donald Knuth
Organizations
- Stanford University