Search results for "Combinatorics"
showing 10 items of 1770 documents
Generalized Schröder permutations
2013
We give the generating function for the integer sequence enumerating a class of pattern avoiding permutations depending on two parameters: m and p. The avoided patterns are the permutations of length m with the largest element in the first position and the second largest in one of the last p positions. For particular instances of m and p we obtain pattern avoiding classes enumerated by Schroder, Catalan and central binomial coefficient numbers, and thus, the obtained two-parameter generating function gathers under one roof known generating functions and expresses new ones. This work generalizes some earlier results of Barcucci et al. (2000) [2], Kremer (2000) [5] and Kremer (2003) [6].
Unavoidable sets and circular splicing languages
2017
Circular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A, an initial set I of circular words, and a set R of rules. In this paper, we focus on the still unknown relations between regular languages and circular splicing systems with a finite initial set and a finite set R of rules represented by a pair of letters ( ( 1 , 3 ) -CSSH systems). When R = A × A , it is known that the set of all words corresponding to the splicing language belongs to the class of pure unitary languages, introduced by Ehrenfeucht, Haussler, Rozenberg in 1983. They also provided a characteriza…
Restricted 123-avoiding Baxter permutations and the Padovan numbers
2007
AbstractBaxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.
The Natural Order-Generic Collapse for ω-Representable Databases over the Rational and the Real Ordered Group
2001
We consider order-generic queries, i.e., queries which commute with every order-preserving automorphism of a structure's universe. It is well-known that first-order logic has the natural order-generic collapse over the rational and the real ordered group for the class of dense order constraint databases (also known as finitely representable databases). I.e., on this class of databases over 〈Q, <〉 or 〈R, <〉, addition does not add to the expressive power of first-order logic for defining order-generic queries. In the present paper we develop a natural generalization of the notion of finitely representable databases, where an arbitrary (i.e. possibly infinite) number of regions is allowed. We …
Combinatorial aspects of L-convex polyominoes
2007
We consider the class of L-convex polyominoes, i.e. those polyominoes in which any two cells can be connected with an ''L'' shaped path in one of its four cyclic orientations. The paper proves bijectively that the number f"n of L-convex polyominoes with perimeter 2(n+2) satisfies the linear recurrence relation f"n"+"2=4f"n"+"1-2f"n, by first establishing a recurrence of the same form for the cardinality of the ''2-compositions'' of a natural number n, a simple generalization of the ordinary compositions of n. Then, such 2-compositions are studied and bijectively related to certain words of a regular language over four letters which is in turn bijectively related to L-convex polyominoes. In …
Enumerable classes of total recursive functions: Complexity of inductive inference
1994
This paper includes some results on complexity of inductive inference for enumerable classes of total recursive functions, where enumeration is considered in more general meaning than usual recursive enumeration. The complexity is measured as the worst-case mindchange (error) number for the first n functions of the given class. Three generalizations are considered.
Periodic Groups Covered by Transitive Subgroups of Finitary Permutations or by Irreducible Subgroups of Finitary Transformations
1999
Let X be either the class of all transitive groups of finitary permutations, or the class of all periodic irreducible finitary linear groups. We show that almost primitive X-groups are countably recognizable, while totally imprimitive X-groups are in general not countably recognizable. In addition we derive a structure theorem for groups all of whose countable subsets are contained in totally imprimitive X-subgroups. It turns out that totally imprimitive p-groups in the class X are countably recognizable.
Varieties of Codes and Kraft Inequality
2005
Decipherability conditions for codes are investigated by using the approach of Guzman, who introduced in [7] the notion of variety of codes and established a connection between classes of codes and varieties of monoids. The class of Uniquely Decipherable (UD) codes is a special case of variety of codes, corresponding to the variety of all monoids. It is well known that the Kraft inequality is a necessary condition for UD codes, but it is not sufficient, in the sense that there exist codes that are not UD and that satisfy the Kraft inequality. The main result of the present paper states that, given a variety $\mathcal{V}$ of codes, if all the elements of $\mathcal{V}$ satisfy the Kraft inequ…
Some properties of vertex-oblique graphs
2016
The type t G ( v ) of a vertex v ? V ( G ) is the ordered degree-sequence ( d 1 , ? , d d G ( v ) ) of the vertices adjacent with v , where d 1 ? ? ? d d G ( v ) . A graph G is called vertex-oblique if it contains no two vertices of the same type. In this paper we show that for reals a , b the class of vertex-oblique graphs G for which | E ( G ) | ? a | V ( G ) | + b holds is finite when a ? 1 and infinite when a ? 2 . Apart from one missing interval, it solves the following problem posed by Schreyer et?al. (2007): How many graphs of bounded average degree are vertex-oblique? Furthermore we obtain the tight upper bound on the independence and clique numbers of vertex-oblique graphs as a fun…
Precise bounds for the sequential order of products of some Fréchet topologies
1998
Abstract The sequential order of a topological space is the least ordinal for which the corresponding iteration of the sequential closure is idempotent. Lower estimates for the sequential order of the product of two regular Frechet topologies and upper estimates for the sequential order of the product of two subtransverse topologies are given in terms of their fascicularity and sagittality. It is shown that for every countable ordinal α, there exists a Lasnev topology such that the sequential order of its square is equal to α.