Abstract :

An extremal problem considering sequences related to Davenport-Schinzel sequences is investigated in this paper. We prove that f(x_1^i x_2^i... x_k^ix_1^i x_2^i... x_k^i, n)=O(n) where the quantity on the left side is defined as the maximum length m of the sequence u=a_1a_2..a_m of integers such that 1) 1<= a_r <= n, 2) a_r=a_s, r differs from s, implies |r-s| >= k and 3) u contains no subsequence of the type x_1^i...  x_k^i x_1^i...x_k^i (x^i stands for xx..x i-times).