Search results for "FIBONACCI"
showing 10 items of 38 documents
A trace partitioned Gray code forq-ary generalized Fibonacci strings
2015
AbstractWe provide a trace partitioned Gray code for the set of q-ary strings avoiding a pattern constituted by k consecutive equal symbols. The definition of this Gray code is based on two different constructions, according to the parity of q. This result generalizes, and is based on, a Gray code for binary strings avoiding k consecutive 0's.
Minimal Forbidden Factors of Circular Words
2017
Minimal forbidden factors are a useful tool for investigating properties of words and languages. Two factorial languages are distinct if and only if they have different (antifactorial) sets of minimal forbidden factors. There exist algorithms for computing the minimal forbidden factors of a word, as well as of a regular factorial language. Conversely, Crochemore et al.ÃÂ [IPL, 1998] gave an algorithm that, given the trie recognizing a finite antifactorial language M, computes a DFA of the language having M as set of minimal forbidden factors. In the same paper, they showed that the obtained DFA is minimal if the input trie recognizes the minimal forbidden factors of a single word. We gener…
Exhaustive generation for permutations avoiding (colored) regular sets of patterns
2019
Abstract Despite the fact that the field of pattern avoiding permutations has been skyrocketing over the last two decades, there are very few exhaustive generating algorithms for such classes of permutations. In this paper we introduce the notions of regular and colored regular set of forbidden patterns, which are particular cases of right-justified sets of forbidden patterns. We show the (colored) regularity of several sets of forbidden patterns (some of them involving variable length patterns) and we derive a general framework for the efficient generation of permutations avoiding them. The obtained generating algorithms are based on succession functions, a notion which is a byproduct of t…
Combinatorial Gray codes for classes of pattern avoiding permutations
2007
The past decade has seen a flurry of research into pattern avoiding permutations but little of it is concerned with their exhaustive generation. Many applications call for exhaustive generation of permutations subject to various constraints or imposing a particular generating order. In this paper we present generating algorithms and combinatorial Gray codes for several families of pattern avoiding permutations. Among the families under consideration are those counted by Catalan, Schr\"oder, Pell, even index Fibonacci numbers and the central binomial coefficients. Consequently, this provides Gray codes for $\s_n(\tau)$ for all $\tau\in \s_3$ and the obtained Gray codes have distances 4 and 5.
Construction of a fundamental set of solutions of an arbitrary homogeneous linear difference equation
2002
Abstract The detailed construction of a prefixed fundamental set of solutions of a linear homogeneous difference equation of any order with arbitrarily variable coefficients is reported. The usefulness of the resulting resolutive formula is illustrated by simple applications to the Hermite polynomials and to the Fibonacci sequence.
Avoiding patterns in irreducible permutations
2016
We explore the classical pattern avoidance question in the case of irreducible permutations, <i>i.e.</i>, those in which there is no index $i$ such that $\sigma (i+1) - \sigma (i)=1$. The problem is addressed completely in the case of avoiding one or two patterns of length three, and several well known sequences are encountered in the process, such as Catalan, Motzkin, Fibonacci, Tribonacci, Padovan and Binary numbers. Also, we present constructive bijections between the set of Motzkin paths of length $n-1$ and the sets of irreducible permutations of length $n$ (respectively fixed point free irreducible involutions of length $2n$) avoiding a pattern $\alpha$ for $\alpha \in \{13…
A programming guide for tensor networks with global SU(2) symmetry
2020
Abstract This paper is a manual with tips and tricks for programming tensor network algorithms with global S U ( 2 ) symmetry. We focus on practical details that are many times overlooked when it comes to implementing the basic building blocks of codes, such as useful data structures to store the tensors, practical ways of manipulating them, and adapting typical functions for symmetric tensors. Here we do not restrict ourselves to any specific tensor network method, but keep always in mind that the implementation should scale well for simulations of higher-dimensional systems using, e.g., Projected Entangled Pair States, where tensors with many indices may show up. To this end, the structur…
m-bonacci metamaterial multilayers: location of the zero-average index bandgap edges
2009
We examine quasiperiodic multilayers arranged in m-bonacci sequences, which combine ordinary positiveindex materials and dispersive metamaterials with negative index in a certain frequency range. When the volume-averaged refractive index of the nonperiodic multilayer equals zero, the structure does not propagate light radiation and exhibits a forbidden band. We identify some analytical expressions to determine the upper and lower limits of the above zero-average refractive-index bandgap. We recognize that these limits are not explicitly dependent on the geometrical parameters of the stack of layers. © 2009 Optical Society of America. Fil: Monsoriu, J.A.. Universidad Politécnica de Valencia;…
Diffractive m-bonacci lenses.
2017
[EN] Fibonacci zone plates are proving to be promising candidates in image forming devices. In this letter we show that the set of Fibonacci zone plates are a particular member of a new family of diffractive lenses which can be designed on the basis of a given m-bonacci sequence. These lenses produce twin axial foci whose separation depends on the m-golden mean. Therefore, with this generalization, bifocal systems can be freely designed under the requirement at particular focal planes. Experimental results support our proposal. (C) 2017 Optical Society of America
Considerations on correlations in shift-register pseudorandom number generators and their removal
1997
Abstract We present a simple calculation quantitatively explaining the triplet correlations in the popular shift-register random number generator “R250”, which were recently observed numerically by Schmid and Wilding, and are known from general analysis of this type of generator. Starting from these considerations, we discuss various methods to remove these correlations by combining different shift-register generators. We implement and test a particularly simple and fast version, based on an XOR combination of two independent shift-register generators with different time lags. The results indicate that this generator has much better statistical properties than R250, while being only a facto…