rss_2.0Pure Mathematics and Applications FeedSciendo RSS Feed for Pure Mathematics and Applications Mathematics and Applications 's Cover of rooted 3-connected bipartite planar maps<abstract> <title style='display:none'>Abstract</title> <p>We provide the first solution to the problem of counting rooted 3-connected bipartite planar maps. Our starting point is the enumeration of bicoloured planar maps according to the number of edges and monochromatic edges, following Bernardi and Bousquet-Mélou [J. Comb. Theory Ser. B (2011)]. The decomposition of a map into 2- and 3-connected components allows us to obtain the generating functions of 2- and 3-connected bicoloured maps. Setting to zero the variable marking monochromatic edges we obtain the generating function of 3-connected bipartite maps, which is algebraic of degree 26. We deduce from it an asymptotic estimate for the number of 3-connected bipartite planar maps of the form <italic>t</italic> · <italic>n</italic><sup>−5/2</sup><italic>γ</italic><italic><sup>n</sup></italic>, where <italic>γ</italic> = <italic>ρ</italic><sup>−1</sup> ≈ 2.40958 and <italic>ρ</italic> ≈ 0.41501 is an algebraic number of degree 10.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00Preimages under a popqueue-sorting algorithm<abstract> <title style='display:none'>Abstract</title> <p>Following the footprints of what has been done with other sorting devices, we study a popqueue and define an optimal sorting algorithm, called Cons. Our results include a description of the set of all the preimages of a given permutation, an enumeration of the set of the preimages of permutations with some specific properties and, finally, the exact enumeration of permutations having 0, 1 and 2 preimages, respectively, with a characterization of permutations having 3 preimages.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00Asymptotic behaviour of -variate absorption distributions, = 1, 2<abstract> <title style='display:none'>Abstract</title> <p>In this work we study the asymptotic behavior of univariate and bivariate absorption discrete <italic>q</italic>-distributions. Specifically, the pointwise convergence of the univariate absorption distribution to a deformed Gaussian one and that of the bivariate absorption to a bivariate deformed Gaussian one, are provided.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00Finding automatic sequences with few correlations<abstract> <title style='display:none'>Abstract</title> <p>Although automatic sequences are very simple algorithmically, some of them have pseudo-random properties. In particular, some automatic sequences such as the Golay–Shapiro sequence are known to be 2-uncorrelated, meaning that they have the same correlations of order 2 as a uniform random sequence. However, the existence of <italic>ℓ</italic>-uncorrelated automatic sequences (for <italic>ℓ</italic> ⩾ 3) was left as an open question in a recent paper of Marcovici, Stoll and Tahay. We exhibit binary block-additive sequences that are 3-uncorrelated and, with the help of analytical results supplemented by an exhaustive search, we present a complete picture of the correlation properties of binary block-additive sequences of rank <italic>r</italic> ⩽ 5, and ternary sequences of rank <italic>r</italic> ⩽ 3.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00A -analogue for the Stirling numbers of the second kind of Coxeter groups of type<abstract> <title style='display:none'>Abstract</title> <p>A generalization of the Stirling numbers of the second kind of type <italic>B</italic> is given in two different directions. One generalization is via their <italic>q</italic>-analogue and the other one uses <italic>r</italic> distinguished elements. Both directions are explained and proved in a combinatorial way using generalized restricted growth words which we define here for type <italic>B</italic>. Moreover, we present their ordinary and exponential generating functions, where the exponential generating function is also used to present the <italic>r</italic>-variant as connection constants between two bases of ℝ[<italic>x</italic>].</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00Uniform generation of infinite traces<abstract> <title style='display:none'>Abstract</title> <p>We introduce an algorithm for the uniform generation of infinite traces, <italic>i.e.</italic>, infinite words up to commutation of some letters. The algorithm outputs on-the-fly approximations of a theoretical infinite trace, the latter being distributed according to the exact uniform probability measure. The average size of the approximation grows linearly with the time of execution of the algorithm, provided that some–costly–precomputations have been done.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00On the exhaustive generation of discrete figures with connectivity constraints<abstract> <title style='display:none'>Abstract</title> <p>This paper deals with a generalization of polyominoes called (<italic>a, b</italic>)<italic>-connected discrete figures</italic>, where <italic>a</italic> and <italic>b</italic> respectively denotes the connectivity of the foreground (i.e. <italic>black pixels</italic>) and background (i.e. <italic>white pixels</italic>). Formally, a finite set of pixels <italic>P</italic> is (<italic>a, b</italic>)-connected if <italic>P</italic> is <italic>a</italic>-connected and <italic>P̄</italic> is <italic>b</italic>-connected. By adapting a combinatorial structure enumeration algorithm due to Martin, we successfully generate (<italic>a, b</italic>)-connected discrete figures up to size <italic>n</italic> = 18.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00Using large random permutations to partition permutation classes<abstract> <title style='display:none'>Abstract</title> <p>Permutation classes are sets of permutations defined by the absence of certain substructures. In some cases permutation classes can be decomposed as unions of subclasses. We use combinatorial specifications automatically discovered by <italic>Combinatorial Exploration: An algorithmic framework for enumeration</italic>, Albert et al. 2022, to uniformly generate large random permutations in a permutation class, and apply clustering methods to partition them into interesting subclasses. We seek to automate as much of this process as possible.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00Foreword bit frequency in Fibonacci words<abstract> <title style='display:none'>Abstract</title> <p>It is known that binary words containing no <italic>k</italic> consecutive 1s are enumerated by <italic>k</italic>-step Fibonacci numbers. In this note we discuss the expected value of a random bit in a random word of length <italic>n</italic> having this property.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00A generating tree with a single label for permutations avoiding the vincular pattern 1−32−4<abstract> <title style='display:none'>Abstract</title> <p>We continue the study of permutations avoiding the vincular pattern 1−32−4 by constructing a generating tree with a single label for these permutations. This construction finally provides a clearer explanation of why a certain recursive formula found by Callan actually counts these permutations, since this formula was originally obtained as a consequence of a very intricate bijection with a certain class of ordered rooted trees. This responds to a theoretical issue already raised by Duchi, Guerrini and Rinaldi. As a byproduct, we also obtain an algorithm to generate all these permutations and we refine their enumeration according to a simple statistic, which is the number of right-to-left maxima to the right of 1.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00On counting Z-convex polyominoes<abstract> <title style='display:none'>Abstract</title> <p>We show a decomposition that allows to compute the number of convex polyominoes of area <italic>n</italic> and degree of convexity at most 2 (the so-called Z-convex polyominoes) in polynomial time.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00From the Fibonacci to Pell numbers and beyond via Dyck paths<abstract> <title style='display:none'>Abstract</title> <p>In <italic>From Fibonacci to Catalan permutations</italic>, Barcucci et al., 2006, a journey by pattern avoiding permutations from the Fibonacci to Catalan sequences is illustrated. In this paper we make a similar journey, but on Dyck paths.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00On the strange kinetic aesthetic of rectangular shape partitions<abstract> <title style='display:none'>Abstract</title> <p>In this paper, we focus on shape partitions. We show that for any fixed <italic>k</italic>, one can symbolically characterize the shape partition on a <italic>k</italic> × <italic>n</italic> rectangular grid by a context-free grammar. We explicitly give this grammar for <italic>k</italic> = 2 and <italic>k</italic> = 3 (for <italic>k</italic> = 1, this corresponds to compositions of integers). From these grammars, we deduce the number of shape partitions for the <italic>k</italic> × <italic>n</italic> rectangular grids for <italic>k</italic> ∈ {1, 2, 3} and every <italic>n</italic>, as well as the limiting Gaussian distribution of the number of connected components. This also enables us to randomly and uniformly generate shape partitions of large size.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00Sampling -normal linear λ-terms<abstract> <title style='display:none'>Abstract</title> <p>Leveraging our recent work on the enumeration of <italic>β</italic>-redices in closed linear λ-terms, we present an algorithm for sampling <italic>β</italic>-normal closed linear λ-terms and their corresponding maps. Such terms correspond to proofs of tautologies in implicational linear logic and their generation is of interest in various domains, including the testing of linear logic theorem provers.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00Combinatorial interpretation of Kazhdan–Lusztig basis elements indexed by 45312-avoiding permutations in 𝔖<abstract> <title style='display:none'>Abstract</title> <p>Deodhar [<italic>Geom. Dedicata</italic> 36, no. 1 (1990)] introduced the <italic>defect</italic> statistic on subexpressions of reduced expressions in the symmetric group 𝔖<italic><sub>n</sub></italic> to construct an algorithmic description of the Kazhdan–Lusztig basis of the Hecke algebra <italic>H</italic><italic><sub>n</sub></italic>(<italic>q</italic>). This led Billey–Warrington [<italic>J. Algebraic Combin.</italic> 13, no. 2 (2001)] and the second author [<italic>J. Pure Appl. Algebra</italic> 212 (2008)] to state very explicit combinatorial descriptions of the basis elements indexed by permutations avoiding certain patterns. We extend the above work by producing an exhaustive list of graphical representations of Kazhdan–Lusztig basis elements indexed by 45312-avoiding permutations <italic>w</italic> ∈𝔖<sub>5</sub>, 𝔖<sub>6</sub>.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00Optimal colorings of Max -Cut game<abstract> <title style='display:none'>Abstract</title> <p>We investigate strong Nash equilibria in the max <italic>k</italic>-cut game on an undirected and unweighted graph with a set of <italic>k</italic> colors, where vertices represent players and the edges indicate their relations. Each player <italic>v</italic> chooses one of the available colors as its own strategy, and its payoff (or utility) is the number of neighbors of <italic>v</italic> that has chosen a different color. Such games are significant since they model loads of real-worlds scenario with selfish agents and, moreover, they are related to fundamental classes of games. Few results are known concerning the existence of strong equilibria in max <italic>k</italic>-cut games in this direction. In this paper we make some progress in the understanding of the properties of strong equilibria. In particular, our main result is to show that optimal solutions are 7-strong equilibria. This means that in order a coalition of nodes is able to deviate and drive the system towards a different configuration, i.e. a different coloring, a number of nodes of the coalition strictly larger than 7 is necessary. We also conjecture that, in a generic graph with <italic>n</italic> nodes, any optimal coloring is also an <italic>n</italic>-strong equilibrium.</p> </abstract>ARTICLE2022-06-18T00:00:00.000+00:00Enumeration of S-Motzkin paths from left to right and from right to left: a kernel method approach<abstract><title style='display:none'>Abstract</title><p>The area of S-Motzkin paths (bijective to ternary trees) is calculated using the kernel method by enumerating these (partial) paths with fixed end-point resp. starting point.</p></abstract>ARTICLE2020-12-24T00:00:00.000+00:00New degenerate Bernoulli, Euler, and Genocchi polynomials<abstract><title style='display:none'>Abstract</title><p>We introduce new generalizations of the Bernoulli, Euler, and Genocchi polynomials and numbers based on the Carlitz-Tsallis degenerate exponential function. Also, we present generalizations of some familiar identities and connection between these types of Bernoulli, Euler, and Genocchi polynomials. Moreover, we establish new analogues of the Euler identity for degenerate Bernoulli polynomials and numbers.</p></abstract>ARTICLE2020-12-24T00:00:00.000+00:00Counting Stirling permutations by number of pushes<abstract><title style='display:none'>Abstract</title><p>Let 𝒯<sup>(</sup><italic><sup>k</sup></italic><sup>)</sup><italic><sub>n</sub></italic> denote the set of <italic>k</italic>-Stirling permutations having <italic>n</italic> distinct letters. Here, we consider the number of steps required (i.e., <italic>pushes</italic>) to rearrange the letters of a member of 𝒯<sup>(</sup><italic><sup>k</sup></italic><sup>)</sup><italic><sub>n</sub></italic> so that they occur in non-decreasing order. We find recurrences for the joint distribution on 𝒯<sup>(</sup><italic><sup>k</sup></italic><sup>)</sup><italic><sub>n</sub></italic> for the statistics recording the number of levels (i.e., occurrences of equal adjacent letters) and pushes. When <italic>k</italic> = 2, an explicit formula for the ordinary generating function of this distribution is also found. In order to do so, we determine the <italic>LU</italic>-decomposition of a certain infinite matrix having polynomial entries which enables one to compute explicitly the inverse matrix.</p></abstract>ARTICLE2020-12-24T00:00:00.000+00:00en-us-1