Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: On a Strange Recursion of Golomb

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:c. | A SYMMETRIC FUNCTIONS APPROACH TO STOCKHAUSEN S PROBLEM Luy Yen Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario N2L 3G1 Canada lyen@j eeves.uwaterloo.ca Submitted July 9 1995. Accepted February 5 1996. Abstract. We consider problems in sequence enumeration suggested by Stockhausen s problem and derive a generating series for the number of sequences of length k on n available symbols such that adjacent symbols are distinct the terminal symbol occurs exactly r times and all other symbols occur at most r 1 times. The analysis makes extensive use of techniques from the theory of symmetric functions. Each algebraic step is examined to obtain information for formulating a direct combinatorial construction for such sequences. 1. Introduction The score of the piano work nr. 7 Klavierstuck XI by Karlheinz Stockhausen 1957 S consists of 19 fragments of music. The performer is instructed to choose at random one of these fragments and play it then to choose another different fragment and play that and so on. If a fragment is chosen that has already been played twice the performance ends. We can state a more general problem as follows Denote each fragment of music by a symbol. Then an r-Stockhausen sequence on n symbols is a sequence such that 1 adjacent symbols are distinct 2 the terminal symbol occurs exactly r times 3 no symbol occurs more than r times 4 exactly one symbol occurs r times 5 the symbol alphabet is Nn 1 2 . ng. The original problem posed by Stockhausen is then the case when r 3 and n 19. We shall refer to 3-Stockhausen sequences simply as Stockhausen sequences. We let cr n k be the number of r-Stockhausen sequences of length k on n symbols and r 1 n 1 Sr n Cr n k k 2r 1 The research for this paper was supported by the Natural Sciences and Engineering Research Council of Canada under a postdoctoral fellowship. Typeset by A S-T .X 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 3 1996 R7 2 for the minimum resp. maximum length of an