Maximal continuants and the Fine-Wilf theorem

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:111

Article

Ramharter, G

关键词: combinatorial inequalities;    balanced words;    partially ordered sets;    euclidean type algorithm;    beatty sequences;    semiregular continued fraction;    backward continued fraction;   

DOI  :  10.1016/j.jcta.2004.11.008

来源: Elsevier

【 摘 要 】

The following problem was posed by C.A. Nicol: given any finite sequence of positive integers, find the permutation for which the continuant (i.e. the continued fraction denominator) having these entries is maximal, resp. minimal. The extremal arrangements are known for the regular continued fraction expansion. For the singular expansion induced by the backward shift [1/x] - 1/x the problem is still open in the case of maximal continuants. We present the explicit solutions for sequences with pairwise different entries and for sequences made up of any pair of digits occurring with any given (fixed) multiplicities. Here the arrangements are uniquely described by a certain generalized continued fraction. We derive this from a purely combinatorial result concerning the partial order structure of the set of permutations of a linearly ordered vector. This set has unique extremal elements which provide the desired extremal arrangements. We also prove that the palindromic maximal continuants are in a simple one-to-one correspondence with the Fine and Wilf words with two coprime periods which gives a new analytic and combinatorial characterization of this class of words. (c) 2005 Elsevier Inc. All rights reserved.

【 授权许可】

Free