A new bound on the length of the shortest string containing all r-permutations

✍ Scribed by Cai Mao-cheng

• Publisher: Elsevier Science
• Year: 1982
• Tongue: English
• Weight: 196 KB
• Volume: 39
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(82)90155-8

✦ Synopsis

The purpose of this note is to give a new upper bound of the shortest string containing all r-permutations. Thus we disprove the conjecture considered in Cl].

The terminology used in this note fullows [I]. Koutas and Nu [I] proposed the foIlowing problem of constructing a shortest string of (1, 2, . . . , n) containing aII r-permutations as its subsequences, where r s k s n -I. For example, the string ;lU44 ;X:1235] contains al': r-permutations as its subsequences provided r< k = 3. Let F(rz, k) denote the Iength of the required shortest string. Koutas and Hu proved in [I] that F(n, I) = n, F(n, 2) = 2n---1, F(n, 3) = 3n-2, F(n, 4) =4n -4, and F(rt, 5)=5n -5. Furthermore, in [I] the conjectun: is mentioned that F(n, k)=k(n-1) for 4~k~n--3. Now we prove that