Minimum range sequences of all k-subsets of a set

✍ Scribed by F.K. Hwang; J.C. Lagarias

• Publisher: Elsevier Science
• Year: 1977
• Tongue: English
• Weight: 703 KB
• Volume: 19
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(77)90105-4

✦ Synopsis

The purpose of this paper is to find sequential orderings of the class S, of at, k -element subsets of the u element set V = (1,2.. . . ~ u} with certain mirlimizmg properties. A sequential ordering of Sa is just a numbering of the (l) k -element subsets of V, where the first one is sI. the second sz and so on. Let f(s) denote the position oE the k-element subset s in the ordering. For each element e of V the range R,(e) of e in the sequence f is given by The total range R, of ;a sequence f is R, = c I, SEV and the bottleneck range E3, of a sequence f is Let F denote the set of all sequences (for fixed values of v and k ), In this qaper we show there exist sequences f that simultaneously minimize R, and B,, give a cf~nstructi(;,L of such sequences for arbitrary o and k, and give exact formulae for minfafi R, and minpcFBI as iJnc?ions of u and k.

These problems arise in experimental &signs involving human subjects an4 in the linking between two stages of switches in multistage switching networks. _