TAILIEUCHUNG - Báo cáo toán học: " How Many Squares Must a Binary Sequence Contain"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: How Many Squares Must a Binary Sequence Contain? | How Many Squares Must a Binary Sequence Contain Aviezri S. Fraenkel1 and R. Jamie Simpson2 Submitted November 16 1994 Accepted December 11 1994 Abstract. Let g n be the length of a longest binary string containing at most n distinct squares two identical adjacent substrings . Then g 0 3 010 is such a string g 1 7 0001000 and g 2 18 010011000111001101 . How does the sequence g n behave We give a complete answer. 1. Introduction A binary word or string containing no square a pair of identical adjacent subwords has maximum length 3 in fact the only squarefree words of length 3 are 010 and its 1-complement 101. A computer disclosed that a binary word containing at most 1 square has maximum length 7 the only words of length 7 with only 1 square are 0001000 0100010 0111011 and their 1-complements and the reverse of 0111011 and its 1-complement. Further a binary word containing at most 2 distinct squares has maximum length 18 the only words of length 18 which contain only 2 distinct squares are 010011000111001101 and its 1-complement which is also its reverse . In general let g k denote the length of a longest binary word containing at most k distinct squares. Distinct means that the squares are of different shape not just translates of each other. We have seen that g 0 3 g 1 7 g 2 18. This data raises the following natural questions. 1 Department of Applied Mathematics Computer Science The Weizmann Institute of Science Rehovot 76100 Israel. Email fraenkel@ . Work done while visiting Curtin University. 2 School of Mathematics Curtin University Perth WA 6001 Australia. Email tsimpsonr@ THE ELECTRONIC JOURNAL OF COMBINATORICS 2 1995 R2 2 1. Is the set of values of the sequence S g k k 0 1 . J- inhnite or hnite 2. What s the value of g 3 Regarding the hrst of these questions Entringer Jackson and Schatz 1974 considered the conjecture that S is inhnite citing a reference which. seems to say that this conjecture. is true . They then go on .

TÀI LIỆU LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.