<abstract>
<title style='display:none'>Abstract</title>
We investigate the relationship between numerical semigroups and Dyck paths discovered by Bras-Amorós and de Mier. More specifically, we consider some classes of Dyck paths and characterize those paths giving rise to numerical semigroups.
</abstract>

Classes of Dyck paths associated with numerical semigroups

<abstract><title style='display:none'>Abstract</title> We study the construction and the enumeration of bit strings, or binary words in {0, 1}*, having more 1’s than 0’s and avoiding a set of Grand Dyck patterns which form a cross-bifix-free set. We give a particular jumping and marked succession rule which describes the growth of such words according to the number of 1’s. Then, we give the enumeration of the class by means of generating function. </abstract>

A generating function for bit strings with no Grand Dyck pattern matching

<abstract><title style='display:none'>Abstract</title> The Sand Pile Model (SPM) and its generalization, the Ice Pile Model (IPM), originate from physics and have various applications in the description of the evolution of granular systems. In this article, we deal with the enumeration and the exhaustive generation of the accessible configuration of the system. Our work is based on a new recursive decomposition theorem for SPM configurations using the notion of staircase bases. Based on this theorem, we provide a recursive formula for the enumeration of SPM(n) and a constant amortized time (CAT) algorithm for the generation of all SPM(n) configurations. The extension of the same approach to the Ice Pile Model is also discussed. </abstract>

roberto.mantaci@liafa.univ-paris-diderot.fr

A recursive structure of sand pile model and its applications

<abstract><title style='display:none'>Abstract</title> Since the last two decades huge systems (such as giant graphs, big data structures, . . . ) have played a central role in computer science, and with the technology improvements, those large objects are now massively used in practice. In order to handle them we need to analyse some typical properties of models of large objects. One way to study typical behaviours consists in generating random objects to get some experimental results on their properties. A new technique has been introduced ten years ago: the Boltzmann sampling. It has been presented by Duchon et al, and is based on automatic interpretation in terms of samplers of the specification of the combinatorial objects under study.One of the core problem in Boltzmann sampling lies in the distribution of the object sizes, and the choice of some parameters in order to get the more appropriate size distribution. From this choice depends the efficiency of the sampling. Moreover some additional ideas allows to improve the efficiency, one of them is based on some anticipated rejections, the other one on the combinatorial differentiation of the specification. Anticipated rejection consists during the recursive building of a random object to kill the process as soon as we are sure to exceed the maximum target size, rather than waiting until the natural end of the process. In the original paper, while both approaches have been presented, and used on the same kind of structures, the methods are not compared. We propose in this paper a detailed comparison of both approaches, in order to understand precisely which method is the more efficient. </abstract>

Laboratoire d’Informatique de Paris-Nord CNRS UMR 7030 Université Paris-Nord 93430 Villetaneuse, France

Sorbonne Universités UPCM Univ. Paris 06, CNRS, LIP6 UMR 7606 75005 Paris, France

Pointed versus singular Boltzmann samplers: a comparative analysis

<abstract><title style='display:none'>Abstract</title> We define an order relation over Sn considering the Robinson-Schensted bijection and the dominance order over Young tableaux. This order relation makes Sn(k k - 1...3 2 1) -the set of permutations of length n that avoid the pattern k k - 1...3 2 1, k ≤ n- a principal filter in Sn. We study in detail these order relations on Sn(321) and Sn(4321), finding order-isomorphisms between these sets and sets of lattice paths. </abstract>

The dominance order for permutations

<abstract>
<title style='display:none'>Abstract</title>
The traditional criss-cross algorithm for the linear programming problem is shown to be finite when <bold>s</bold>-monotone index selection rules are used. The set of <bold>s</bold>-monotone index selection rules, among others, include the Last In First Out (LIFO) and the Most Often Selected Variable rule (MOSV). The advantage of applying the <bold>s</bold>-monotone index selection rule is the flexibility it provides in selecting the pivot element while still preserving the guarantee for finiteness. Such flexibility may be used to improve the numerical stability of the algorithm.
</abstract>

Finiteness of the criss-cross algorithm for the linear programming problem with s-monotone index selection rules

<abstract>
<title style='display:none'>Abstract</title>
Let <italic>π</italic><italic>n</italic> be a uniformly chosen random permutation on [<italic>n</italic>]. Using an analysis of the probability that two overlapping consecutive <italic>k</italic>-permutations are order isomorphic, we show that the expected number of distinct consecutive patterns of all lengths <italic>k</italic> ∈ {1, 2,…, <italic>n</italic>} in <italic>π</italic><italic>n</italic> is <inline-formula>
<alternatives>
<inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_puma-2022-0031_eq_001.png"/>
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mrow><mml:mfrac><mml:mrow><mml:msup><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msup></mml:mrow><mml:mn>2</mml:mn></mml:mfrac><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mn>1</mml:mn><mml:mo>-</mml:mo><mml:mi>o</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math>
<tex-math>{{{n^2}} \over 2}\left( {1 - o\left( 1 \right)} \right)</tex-math>
</alternatives>
</inline-formula> as <italic>n</italic> → ∞. This exhibits the fact that random permutations pack consecutive patterns near-perfectly.
</abstract>

The expected number of distinct consecutive patterns in a random permutation

<abstract>
<title style='display:none'>Abstract</title>
In this note, we study the mean length of the longest increasing subsequence of a uniformly sampled involution that avoids the pattern 3412 and another pattern.
</abstract>

The longest increasing subsequence in involutions avoiding 3412 and another pattern

<abstract>
<title style='display:none'>Abstract</title>
This is a <italic>selected overview</italic> of a research line initiated and mostly developed by the three authors over the last three decades. Applying the state space paradigm of Mathematical Systems Theory, monitoring means that from the observation (a transform) of an unknown state process, the latter should be recovered. Since most of the dynamic models of population biology are nonlinear, for solving the monitoring problem, tools of nonlinear analysis are applied in different contexts. This approach to monitoring has found different applications ranging from population ecology to radiotherapy, from stock estimation in fisheries to monitoring of solar thermal heating systems.
</abstract>

Monitoring of population systems

<abstract>
<title style='display:none'>Abstract</title>
We consider several concepts of computability (recursiveness) for sets in Euclidean space. A list of four ideal properties for such sets is proposed and it is shown in a very elementary way that no notion can satisfy all four desiderata. Most notions introduced here are essentially based on separability of ℝ<italic>n</italic> and this is natural when thinking about operations on an actual digital computer where, in fact, rational numbers are the basis of everything. We enumerate some properties of some naïve but practical notions of recursive sets and contrast these with others, including the widely used and accepted notion of <italic>computable</italic> set developed by Weihrauch, Brattka and others which is based on the “Polish school” notion of a computable real function. We also offer a conjecture about the Mandelbrot set.
</abstract>

Computability of sets in Euclidean space

<abstract>
<title style='display:none'>Abstract</title>
The paper investigates an one-product reverse logistics system. The aim is to analyze the functioning of such a system with continuous time and linear cost structure. The costs consist of linear holding costs for both warehouse, and the linear remanufacturing, manufacturing, and disposal costs. The demand and return rates are known deterministic parameters. The problem is solved with the Pontyagin’s maximum principle. Solving the control problem, it is corrected an earlier paper [1].
</abstract>

Production-inventory strategies for a linear reverse logistics system

<abstract>
<title style='display:none'>Abstract</title>
A special oligopoly model is considered when the firms compete on the factor market, and the used factor volumes determine their outputs. In the <italic>N</italic>firm case conditions are given for the existence of the Nash equilibrium, and in the cooperative case, sufficient conditions are derived for the existence and uniqueness of the joint profit maximizer. In the case of a linear duopoly the dynamic extensions are introduced in both cases based on gradient adjustments. Conditions are given for the local asymptotic stability of the equilibrium and the joint profit maximizer without and with information delays.
</abstract>

Some notes on dynamic oligopsonies

<abstract><title style='display:none'>Abstract</title> Two well known results on semigroups, one of them clue to Calais, the other to Lajos, are generalized in case of hypersemigroups in the way indicated in the present paper. We prove that a nonempty subset B of a regular hypersemigroup H is a bi-ideal of H if and only if it is represented in the form B = A * C where A is a right ideal and C a left ideal of H. We also show that an hyper semigroup H is regular if and only if the right and the left ideals of H are idempotent, and for every right ideal A and every left ideal B of H, the product A * B is a quasi-ideal of H. </abstract>

On hypersemigroups

<abstract><title style='display:none'>Abstract</title> We enumerate permutations avoiding 1243, 2134, and a third 4-letter pattern τ, a step toward the goal of enumerating avoiders for all triples of 4-letter patterns. The enumeration is already known for all but three patterns τ, which are treated in this paper. </abstract>

On permutations avoiding 1243, 2134, and another 4-letter pattern

<abstract><title style='display:none'>Abstract</title> We enumerate permutations avoiding 1324, 2143, and a third 4-letter pattern τ a step toward the goal of enumerating avoiders for all triples of 4-letter patterns. The enumeration is already known for all but five patterns τ, which are treated in this paper.</abstract>

On permutations avoiding 1324, 2143, and another 4-letter pattern

<abstract><title style='display:none'>Abstract</title>This paper is one of a series whose goal is to enumerate the avoiders, in the sense of classical pattern avoidance, for each triple of 4-letter patterns. There are 317 symmetry classes of triples of 4-letter patterns, avoiders of 267 of which have already been enumerated. Here we enumerate avoiders for all small Wilf classes that have a representative triple containing the pattern 1342, giving 40 new enumerations and leaving only 13 classes still to be enumerated. In all but one case, we obtain an explicit algebraic generating function that is rational or of degree 2. The remaining one is shown to be algebraic of degree 3. We use standard methods, usually involving detailed consideration of the left to right maxima, and sometimes the initial letters, to obtain an algebraic or functional equation for the generating function.</abstract>

Enumeration of small Wilf classes avoiding 1342 and two other 4-letter patterns

<abstract><title style='display:none'>Abstract</title> A permutation of length n may be represented, equivalently, by a sequence a1a2 • • • an satisfying 0 &lt; ai &lt; i for all z, which is called an inversion sequence. In analogy to the usual case for permutations, the pattern avoidance question is addressed for inversion sequences. In particular, explicit formulas and/or generating functions are derived which count the inversion sequences of a given length that avoid a single pattern of length three. Among the sequences encountered are the Fibonacci numbers, the Schröder numbers, and entry A200753 in OEIS. We make use of both algebraic and combinatorial methods to establish our results. An explicit Injection is given between two of the avoidance classes, and in three cases, the kernel method is used to solve a functional equation satisfied by the generating function enumerating the class in question. </abstract>

Department of Mathematics University of Haifa 31905 Haifa, Israel

Department of Mathematics University of Tennessee Knoxville, TN 37996 USA

Pattern avoidance in inversion sequences

<abstract><title style='display:none'>Abstract</title>Recently, it has been determined that there are 242 Wilf classes of triples of 4-letter permutation patterns by showing that there are 32 non-singleton Wilf classes. Moreover, the generating function for each triple lying in a non-singleton Wilf class has been explicitly determined. In this paper, toward the goal of enumerating avoiders for the singleton Wilf classes, we obtain the generating function for all but one of the triples containing 1324. (The exceptional triple is conjectured to be intractable.) Our methods are both combinatorial and analytic, including generating trees, recurrence relations, and decompositions by left-right maxima. Sometimes this leads to an algebraic equation for the generating function, sometimes to a functional equation or a multi-index recurrence amenable to the kernel method.</abstract>

Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns

Editorial Policy

Instructions for Authors

Open Access License

Pure Mathematics and Applications

 Pure Mathematics and Applications - section Algebra and Theoretical Computer Science - publishes original high quality articles of international relevance in the...

 Pure Mathematics and Applications - section Algebra and Theoretical Computer Science - publishes original high quality...

Pure Mathematics and Applications

Alle Bände und Hefte dieser Zeitschrift