Search

We enumerate injectively k -colored rooted forests with a given number of vertices of each color and a given sequence of root colors. We obtain from this result some new multi-parameter distributions of Fuss–Catalan numbers. As an additional application we enumerate triangulations of regular convex polygons according to their proper 3-coloring type. [ABSTRACT FROM AUTHOR]

We view the determinant and permanent as functions on directed weighted graphs and introduce their analogues for undirected graphs. We prove that computing undirected determinants as well as permanents for planar graphs whose vertices have degree at most 4 is #P-complete. In the case of planar graphs whose vertices have degree at most 3, the computation of the undirected determinant remains #P-complete while computing the permanent can be reduced to the FKT algorithm, and therefore can be done in polynomial time. Computing the undirected permanent is a Holant problem and its complexity can be deduced from the existing literature. It is mentioned in the paper as a natural context but no new results in this direction are obtained. The concept of undirected determinant is new. Its introduction is motivated by the formal resemblance to the directed determinant, a property that may inspire generalizations of some of the many algorithms which compute the latter. For a sizable class of planar 3-regular graphs, we are able to compute the undirected determinant in polynomial time. [ABSTRACT FROM AUTHOR]

The paper deals with counting the triples of disjoint non-self-intersecting paths with nodes from a fixed set of labelled points on a circle. Some of the obtained formulae provide new properties of entries in the Online Encyclopaedia of Integer Sequences, while others generate new entries therein. [ABSTRACT FROM AUTHOR]

We investigate two fundamental questions intersecting coding theory and combinatorial geometry, with emphasis on their connections. These are the problem of computing the asymptotic density of MRD codes in the rank metric, and the Critical Problem for combinatorial geometries by Crapo and Rota. In the first part of the paper, we use methods from semifield theory to derive two lower bounds for the density function of full-rank, square MRD codes. The first bound is sharp when the matrix size is a prime number and the underlying field is sufficiently large, while the second bound applies to the binary field. We then take a new look at the Critical Problem for combinatorial geometries, approaching it from a qualitative, often asymptotic, viewpoint. We illustrate the connection between this very classical problem and that of computing the asymptotic density of MRD codes. Finally, in the third part of the paper we study the asymptotic density of some special families of codes in the rank metric, including the symmetric, alternating, and Hermitian ones. In particular, we show that the optimal codes in these three contexts are sparse. [ABSTRACT FROM AUTHOR]

An animal is a planar shape formed by attaching congruent regular polygons along their edges. Usually, these polygons are a finite subset of tiles of a regular planar tessellation. These tessellations can be parameterized using the Schläfli symbol { p , q } , where p denotes the number of sides of the regular polygon forming the tessellation and q is the number of edges or tiles meeting at each vertex. If (p - 2) (q - 2) > 4 , = 4 , or < 4 , then the tessellation corresponds to the geometry of the hyperbolic plane, the Euclidean plane, or the sphere, respectively. In 1976, Harary and Harborth studied animals defined on regular tessellations of the Euclidean plane, finding extremal values for their vertices, edges, and tiles, when any one of these parameters is fixed. They named animals attaining these extremal values as extremal animals. Here, we study hyperbolic extremal animals. For each { p , q } corresponding to a hyperbolic tessellation, we exhibit a sequence of spiral animals and prove that they attain the minimum numbers of edges and vertices within the class of animals with n tiles. We also give the first results on enumeration of extremal hyperbolic animals by finding special sequences of extremal animals that are unique extremal animals, in the sense that any animal with the same number of tiles which is distinct up to isometries cannot be extremal. [ABSTRACT FROM AUTHOR]

The Japanese braids known as Naiki, which are distinguished by their hollow interior, have a simple structure shared by many other fiber arts and crafts. The way in which this structure forms a cylindrical braid imposes a particular set of symmetries on the final product. This paper uses enumerative combinatorics, including de Bruijn's Monster Theorem, to count the number of two-color Naiki braids under equivalence by this natural set of symmetries. [ABSTRACT FROM AUTHOR]

We derive a path counting formula for a two-dimensional lattice path model with filter restrictions in the presence of long steps, source and target points of which are situated near the filters. This solves the problem of finding an explicit formula for multiplicities of modules in tensor product decomposition of T (1) ⊗ N for U q (s l 2) with divided powers, where q is a root of unity. Combinatorial treatment of this problem calls for the definition of congruence of regions in lattice path models, properties of which are explored in this paper. [ABSTRACT FROM AUTHOR]

The paper deals with counting the sets of non-self-intersecting paths whose nodes form a partitioning of the set of vertices of a given convex polygon. There turn to exist compact formulae when the magnitude of these sets is fixed. Some of these formulae provide new properties for some of the entries of the Online Encyclopedia of Integer Sequences, while others generate new entries therein. [ABSTRACT FROM AUTHOR]

We have studied self-avoiding walks contained within an L Ă— L square whose end-points can lie anywhere within, or on, the boundaries of the square. We prove that such walks behave, asymptotically, as walks crossing a square (WCAS), being those walks whose end-points lie at the south-east and north-west corners of the square. We provide numerical data, enumerating all such walks, and analyse the sequence of coefficients in order to estimate the asymptotic behaviour. We also studied a subset of these walks, those that must contain at least one edge on all four boundaries of the square. We provide compelling evidence that these two classes of walks grow identically. From our analysis we conjecture that the number of such walks C L , for both problems, behaves as C L ∼ λ L 2 + b L + c â‹... L g , where (Guttmann and Jensen 2022 J. Phys. A: Math. Theor.) λ = 1.744 5498 ± 0.000 0012, b = âˆ'0.043 54 ± 0.0005, c = âˆ'1.35 ± 0.45, and g = 3.9 ± 0.1. Finally, we also studied the equivalent problem for self-avoiding polygons, also known as cycles in a square grid. The asymptotic behaviour of cycles has the same form as walks, but with different values of the parameters c, and g. Our numerical analysis shows that λ and b have the same values as for WCAS and that c = 1.776 ± 0.002 while g = âˆ'0.500 ± 0.005 and hence probably equals âˆ' 1 2 . [ABSTRACT FROM AUTHOR]

The paper deals with counting the sets of given magnitude each consisting of non-self-intersecting paths whose nodes are vertices of a given convex polygon. Some of the obtained formulae provide new properties of entries in the On-line Encyclopaedia of Integer Sequences, while others generate new entries therein. [ABSTRACT FROM AUTHOR]

In this paper we consider doubly symmetric Dyck words , i.e. Dyck words which are fixed by two symmetry operations α and β introduced in [1]. We study combinatorial properties of doubly symmetric Dyck words, leading to the definition of two recursive algorithms to build these words. As a consequence we have a representation of doubly symmetric Dyck words as vectors of integers, called track vectors. Finally, we show some bijections between a subfamily of doubly symmetric Dyck words and a subfamily of integer partitions. The computation of the sequence f n of doubly symmetric Dyck words of semi-length n shows surprising properties giving rise to some conjectures. [ABSTRACT FROM AUTHOR]

We derive a path counting formula for a two-dimensional lattice path model with filter restrictions in the presence of long steps, source and target points of which are situated near the filters. This solves the problem of finding an explicit formula for multiplicities of modules in tensor product decomposition of T(1)⊗N for Uq(sl2) with divided powers, where q is a root of unity. Combinatorial treatment of this problem calls for the definition of congruence of regions in lattice path models, properties of which are explored in this paper.

In this article, we illustrate a method of organizing the process of discovering solutions to problems for mathematical contests. We describe the authors' experience in creating situations of learning individually, through cooperation and collaboration in pairs, and in small groups. The examples proposed for discussion can be considered mini-scientific works, which allow thorough research of the situation, but require detailed explanation and collaboration between students in order to refresh the supporting concepts and create generalizations. [ABSTRACT FROM AUTHOR]

In the past twenty years, the enumeration of lattice walks with steps taken in a prescribed set S and confined to a given cone, especially the first quadrant of the plane, has been intensely studied. As a result, the generating functions of quadrant walks are now well-understood, provided the allowed steps are small, that is, S = {-1; 0; 1}². In particular, having small steps is crucial for the definition of a certain group of bi-rational transformations of the plane. It has been proved that this group is finite if and only if the corresponding generating function is D-finite (that is, it satisfies a linear differential equation with polynomial coefficients). This group is also the key to the uniform solution of 19 of the 23 small step models possessing a finite group. In contrast, almost nothing is known for walks with arbitrary steps. In this paper, we extend the definition of the group, or rather of the associated orbit, to this general case, and generalize the above uniform solution of small step models. When this approach works, it invariably yields a D-finite generating function. We apply it to many quadrant problems, including some infinite families. After developing the general theory, we consider the 13 110 two-dimensional models with steps in f􀀀2;􀀀1; 0; 1g2 having at least one 􀀀2 coordinate. We prove that only 240 of them have a finite orbit, and solve 231 of them with our method. The nine remaining models are the counterparts of the four models of the small step case that resist the uniform solution method (and which are known to have an algebraic generating function). We conjecture D-finiteness for their generating functions, but only two of them are likely to be algebraic. We also prove non-D-finiteness for the 12 870 models with an infinite orbit, except for 16 of them. [ABSTRACT FROM AUTHOR]

We present new applications of q-binomials, also known as Gaussian binomial coefficients. Our main theorems determine cardinalities of certain error-correcting codes based on Varshamov–Tenengolts codes and prove a curious phenomenon relating to deletion spheres. [ABSTRACT FROM AUTHOR]

Given a set of species whose evolution is represented by a species tree, a gene family is a group of genes having evolved from a single ancestral gene. A gene family evolves along the branches of a species tree through various mechanisms, including—but not limited to—speciation (S ), gene duplication (D ), gene loss (L ), and horizontal gene transfer (T ). The reconstruction of a gene tree representing the evolution of a gene family constrained by a species tree is an important problem in phylogenomics. However, unlike in the multispecies coalescent evolutionary model that considers only speciation and incomplete lineage sorting events, very little is known about the search space for gene family histories accounting for gene duplication, gene loss and horizontal gene transfer (the D L T -model). In this work, we introduce the notion of evolutionary histories defined as a binary ordered rooted tree describing the evolution of a gene family, constrained by a species tree in the D L T -model. We provide formal grammars describing the set of all evolutionary histories that are compatible with a given species tree, whether it is ranked or unranked. These grammars allow us, using either analytic combinatorics or dynamic programming, to efficiently compute the number of histories of a given size, and also to generate random histories of a given size under the uniform distribution. We apply these tools to obtain exact asymptotics for the number of gene family histories for two species trees, the rooted caterpillar and complete binary tree, as well as estimates of the range of the exponential growth factor of the number of histories for random species trees of size up to 25. Our results show that including horizontal gene transfers induce a dramatic increase of the number of evolutionary histories. We also show that, within ranked species trees, the number of evolutionary histories in the D L T -model is almost independent of the species tree topology. These results establish firm foundations for the development of ensemble methods for the prediction of reconciliations. [ABSTRACT FROM AUTHOR]

In this paper we are addressing a counting problem of discrete mathematics, more precisely of digital geometry. In the Euclidean plane the shortest path between any two points is given by the straight line segment connecting the points. In discrete mathematics, the shortest path is usually not unique, e.g., in graphs there could be several shortest paths between two vertices. In this paper, a special infinite graph, the square grid, (i.e., the usual digital plane) is used. In digital geometry there are various digital, i.e., path based distance functions. A neighborhood sequence B gives the condition for each step of a B-path separately what type of neighborhood is used in that step. Therefore, the length and also the number of the shortest paths between two points depend not only on the respective positions (coordinate differences) of the points but also on the neighborhood sequence B. We give an algorithm and also closed formulae to compute the number of shortest B-paths. [ABSTRACT FROM AUTHOR]

In this paper we find recurrence relations for the asymptotic probability a vertex is k protected in all Motzkin trees. We use a similar technique to calculate the probabilities for balanced vertices of rank k. From this we calculate upper and lower bounds for the probability a vertex is balanced and upper and lower bounds for the expected rank of balanced vertices. [ABSTRACT FROM AUTHOR]

The distribution of descents in certain conjugacy classes of Sn has been previously studied, and it is shown that its moments have interesting properties. This paper provides a bijective proof of the symmetry of the descents and major indices of matchings (also known as fixed point free involutions) and uses a generating function approach to prove an asymptotic normality theorem for the number of descents in matchings. [ABSTRACT FROM AUTHOR]

This paper considers three separate matrices associated to graphs and (each dimension of) cell complexes. It relates all the coefficients of their respective characteristic polynomials to the geometric and combinatorial enumeration of three kinds of sub-objects. The matrices are: the mesh matrix for integral d-cycles, the mesh matrix for integral d-boundaries, and the Kirchhoff matrix, i.e., the combinatorial Laplacian, for integral (d-1)-chains. Trent's theorem states that the determinant of the mesh matrix on 1-cycles of a connected graph is equal to the number of spanning trees (Trent in Proc Nat Acad Sci USA 40:1004-1007, 1954; J Acoust Soc Am 27(3):500-527, 1955). Here this theorem is extended to the mesh matrix on d-cycles in an arbitrary cell complex and, new even for graphs, to enumerative combinatorial interpretation of all of the coefficients of its characteristic polynomial. This last is well defined once a basis for the integral d-cycles is chosen. Additionally, a parallel result for the mesh matrix for integral d-boundaries is proved. Kirchhoff's classical theorem on graphs (Kirchhoff in Ann Phys Chem 72:497-508, 1847) states that the product of the non-zero eigenvalues of the Kirchhoff matrix, i.e., combinatorial Laplacian, for connected graphs equals n times the number of spanning trees, with n the number of vertices. Kalai (Isr J Math 45(4): 337-351, 1983) investigated counting spanning trees in some higher dimensional settings including simplices here weighting by order of torsion homology groups entered. Lyons has generalized Kirchhoff's result on the product of the non-zero eigenvalues of the Kirchhoff or combinatorial Laplacian on (d-1)-chains to cell complexes for d>1 (Lyons in J Topol Anal 1(2), 153-175, 2009; Lyons and Peres in Probability on trees and networks. Cambridge series in statistical and probabilistic mathematics, vol 42, Cambridge University Press, New York, 2016). The present analysis extends this to all coefficients of the complete characteristic polynomial. An evaluation of the Reidemeister-Franz torsion of the cell complex with respect to its integral basis gives relations between these combinatorial invariants. [ABSTRACT FROM AUTHOR]

In this paper, we enumerate two families of pattern-avoiding permutations: those avoiding the vincular pattern 2 ... 3, which we call semi-Baxter permutations, and those avoiding the vincular patterns 2 ... 3, 3 ... 2, and 3 ... 2, which we call strong-Baxter permutations. We call semi-Baxter numbers and strong-Baxter numbers the associated enumeration sequences. We prove that the semi-Baxter numbers enumerate in addition plane permutations (avoiding 2 ... 3). The problem of counting these permutations was open and has given rise to several conjectures, which we also prove in this paper. For each family (that of semi-Baxter—or, equivalently, plane —and that of strong-Baxter permutations), we describe a generating tree, which translates into a functional equation for the generating function. For semi-Baxter permutations, it is solved using (a variant of) the kernel method: this gives an expression for the generating function while also proving its D-finiteness. From the obtained generating function, we derive closed formulas for the semi-Baxter numbers, a recurrence that they satisfy, as well as their asymptotic behavior. For strong-Baxter permutations, we show that their generating function is (a slight modification of) that of a family of walks in the quarter plane, which is known to be non–D-finite. [ABSTRACT FROM AUTHOR]

We introduce a general class of regular weight functions on finite abelian groups, and study the combinatorics, the duality theory, and the metric properties of codes endowed with such functions. The weights are obtained by composing a suitable support map with the rank function of a graded lattice satisfying certain regularity properties. A regular weight on a group canonically induces a regular weight on the character group, and invertible MacWilliams identities always hold for such a pair of weights. Moreover, the Krawtchouk coefficients of the corresponding MacWilliams transformation have a precise combinatorial significance, and can be expressed in terms of the invariants of the underlying lattice. In particular, they are easy to compute in many examples. Several weight functions traditionally studied in Coding Theory belong to the class of weights introduced in this paper. Our lattice-theory approach also offers a control on metric structures that a regular weight induces on the underlying group. In particular, it allows to show that every finite abelian group admits weight functions that, simultaneously, give rise to MacWilliams identities, and endow the underlying group with a metric space structure. We propose a general notion of extremality for (not necessarily additive) codes in groups endowed with semi-regular supports, and establish a Singleton-type bound. We then investigate the combinatorics and duality theory of extremal codes, extending classical results on the weight and distance distribution of error-correcting codes. Finally, we apply the theory of MacWilliams identities to enumerative combinatorics problems, obtaining closed formulae for the number of rectangular matrices over a finite having prescribed rank and satisfying some linear conditions. [ABSTRACT FROM AUTHOR]

The paper is concerned with subsets I of the residue group Zd in which the difference of any two elements is not relatively prime to d. The class of such subsets is denoted by U(d), the class of sets from U(d) of cardinality r is denoted by U(d, r). The present paper gives formulas for evaluation or estimation of |U(d)| and |U(d, r)|. [ABSTRACT FROM AUTHOR]

Cographs have always been a research target in areas such as coloring, graph decomposition, and spectral theory. In this work, we present an algorithm to generate all unlabeled cographs with n vertices, based on the generation of cotrees. The delay of our algorithm (time spent between two consecutive outputs) is O ( n ) . The time needed to generate the first output is also O ( n ) , which gives an overall O ( n M n ) time complexity, where M n is the number of unlabeled cographs with n vertices. The algorithm avoids the generation of duplicates (isomorphic outputs) and produces, as a by-product, a linear ordering of unlabeled cographs with n vertices. [ABSTRACT FROM AUTHOR]

A comprehensive treatment on compact representations for the solutions of linear difference equations with variable coefficients, of both n th and unbounded order, is presented. The equivalence between their celebrated combinatorial and determinantal representations is considered. A corresponding representation is proposed using determined nested sums of their variable coefficients. It makes explicit all the sum of products involved in the previous representations of such solutions. Some basic applications are also illustrated. [ABSTRACT FROM AUTHOR]

We introduce and study a new mathematical structure in the generalised (quantum) cohomology theory for Grassmannians. Namely, we relate the Schubert calculus to a quantum integrable system known in the physics literature as the asymmetric six-vertex model. Our approach offers a new perspective on already established and well-studied special cases, for example equivariant K-theory, and in addition allows us to formulate a conjecture on the so-far unknown case of quantum equivariant K-theory. [ABSTRACT FROM AUTHOR]

RNA sequencing (RNA-seq) has emerged as the method of choice for measuring the expression of RNAs in a given cell population. In most RNA-seq technologies, sequencing the full length of RNA molecules requires fragmentation into smaller pieces. Unfortunately, the issue of nonuniform sequencing coverage across a genomic feature has been a concern in RNA-seq and is attributed to biases for certain fragments in RNA-seq library preparation and sequencing. To investigate the expected coverage obtained from fragmentation, we develop a simple fragmentation model that is independent of bias from the experimental method and is not specific to the transcript sequence. Essentially, we enumerate all configurations for maximal placement of a given fragment length, F, on transcript length, T, to represent every possible fragmentation pattern, from which we compute the expected coverage profile across a transcript. We extend this model to incorporate general empirical attributes such as read length, fragment length distribution, and number of molecules of the transcript. We further introduce the fragment starting-point, fragment coverage, and read coverage profiles. We find that the expected profiles are not uniform and that factors such as fragment length to transcript length ratio, read length to fragment length ratio, fragment length distribution, and number of molecules influence the variability of coverage across a transcript. Finally, we explore a potential application of the model where, with simulations, we show that it is possible to correctly estimate the transcript copy number for any transcript in the RNA-seq experiment. [ABSTRACT FROM AUTHOR]

Gessel walks are lattice paths confined to the quarter plane that start at the origin and consist of unit steps going eitherWest, East, South-West or North-East. In 2001, Ira Gessel conjectured a nice closed-form expression for the number of Gessel walks ending at the origin. In 2008, Kauers, Koutschan and Zeilberger gave a computer-aided proof of this conjecture. The same year, Bostan and Kauers showed, again using computer algebra tools, that the complete generating function of Gessel walks is algebraic. In this article we propose the first "human proofs" of these results. They are derived from a new expression for the generating function of Gessel walks in terms of Weierstrass zeta functions. [ABSTRACT FROM AUTHOR]

Following Anders and Archer, we say that an unordered rooted labeled forest avoids the pattern σ ∈ S k if in each tree, each sequence of labels along the shortest path from the root to a vertex does not contain a subsequence with the same relative order as σ. For each permutation σ ∈ S k − 2 , we construct a bijection between n -vertex forests avoiding (σ) (k − 1) k ≔ σ (1) ⋯ σ (k − 2) (k − 1) k and n -vertex forests avoiding (σ) k (k − 1) ≔ σ (1) ⋯ σ (k − 2) k (k − 1) , giving a common generalization of results of West on permutations and Anders–Archer on forests. We further define a new object, the forest-Young diagram, which we use to extend the notion of shape-Wilf equivalence to forests. In particular, this allows us to generalize the above result to a bijection between forests avoiding { (σ 1) k (k − 1) , (σ 2) k (k − 1) , ... , (σ ℓ) k (k − 1) } and forests avoiding { (σ 1) (k − 1) k , (σ 2) (k − 1) k , ... , (σ ℓ) (k − 1) k } for σ 1 , ... , σ ℓ ∈ S k − 2. Furthermore, we give recurrences enumerating the forests avoiding { 123 ⋯ k } , {213}, and other sets of patterns. Finally, we extend the Goulden–Jackson cluster method to study consecutive pattern avoidance in rooted trees as defined by Anders and Archer. Using the generalized cluster method, we prove that if two length- k patterns are strong-c-forest-Wilf equivalent, then up to complementation, the two patterns must start with the same number. We also prove the surprising result that the patterns 1324 and 1423 are strong-c-forest-Wilf equivalent, even though they are not c-Wilf equivalent with respect to permutations. [ABSTRACT FROM AUTHOR]