tailieunhanh - Báo cáo toán học: "Counting Abelian Squares"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Counting Abelian Squares. | Counting Abelian Squares L. B. Richmond Department of Combinatorics and Optimization University of Waterloo Waterloo ON N2L 3G1 Canada lbrichmo@ Jeffrey Shallit School of Computer Science University of Waterloo Waterloo ON N2L 3G1 Canada shallit@ Submitted Jan 5 2009 Accepted Jun 8 2009 Published Jun 19 2009 Mathematics Subject Classification 68R15 05A16 Abstract An abelian square is a nonempty string of length 2n where the last n symbols form a permutation of the first n symbols. Similarly an abelian r th power is a concatenation of r blocks each of length n where each block is a permutation of the first n symbols. In this note we point out that some familiar combinatorial identities can be interpreted in terms of abelian powers. We count the number of abelian squares and give an asymptotic estimate of this quantity. 1 Introduction An abelian square of length 2n is a nonempty string of the form xx where x x n 0 and x is a permutation of x. Two abelian squares in English are reappear and intestines. Of course the permutation can be the identity so ordinary squares such as murmur and hotshots are also considered to be abelian squares. Similarly an abelian r th power is a concatenation of r blocks each of length n where each block is a permutation of the first n symbols. For example deeded is an abelian cube. Abelian squares were introduced by Erdos 10 p. 240 and since then have been extensively studied in the combinatorics on words literature see for example 1 p. 37 . THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R72 1 In this note we point out that some familiar combinatorial identities can be interpreted in terms of counting abelian powers. We discuss enumerating the abelian squares over an alphabet of size k and give an asymptotic estimate for this quantity. 2 Preliminaries Let fk n be the number of abelian squares of length 2n over an alphabet E with k letters. Without loss of generality we assume that E 1 2 . k . Given a string