Given n and k, we consider the problem of conslructing a shortest string over the, set ~. ={1,2 ..... n} which contains every permulation of each k-element subset of ~, as a scbsequence. Let g(n, k) denote the length of a shorte,;t such string. We show by construction tic, a: g(n, k) <~ k(n -2) + 4 for 3 :g k ~ n.
1, la~od,~cfion
The r~-oblem of constructing a string over the set -~n ={1,2,..., n} which contai~ls every permutation of the string 12 โข. โข n as a subsequence (not necessarily con~;e~etive) was considered in [1], [2] and [3]. Let f(n) denote the length of a shortest ~:uch string. In all three papers it was shown constructively that
in this paper we consider a generalization of this problem: given n and k, con.~truct a string over ~, which contains every permutation of each k-element subset ~ .~ as a subsequence. Let g(n, k) be the length of a shortest such string. We wiI~i how by construction that g(n,k)<~k(n-2)+4 for 3<~k<~n.
Note lhat f(n)= g(n, n) and our result gives g(n, n)<~n(n-2)+4, which is the smaJlest known upper bound on f(rt).
A f~action F(rt, k), similar to g(rt, k), was defined by Koutas and Hu in [2].
F0~, k) is the length of a shortest string s~ over ~ with the following property: re1 1 ~ i ~< k, the string consisting of the first F(n, i) symbols of s k contains every perm~tation of each i-element subset of ,~ as a subsequence. Koutas and Hu show that
and they conjecture that F(rt, k)= k(n-1) for 4~ < k ~ n-1. By our definition of the function g(rt, k), it. must be that g(rt, k)<~F(n, k). Our result shows that for