Search

A word w = w 1 ⋯ w n over the set of positive integers is a Motzkin word whenever w 1 = 1 , 1 ≤ w k ≤ w k − 1 + 1 , and w k − 1 ≠ w k for k = 2 , ... , n. It can be associated to a n -column Motzkin polyomino whose i -th column contains w i cells, and all columns are bottom-justified. We reveal bijective connections between Motzkin paths, restricted Catalan words, primitive Łukasiewicz paths, and Motzkin polyominoes. Using the aforementioned bijections together with classical one-to-one correspondence with Dyck paths avoiding U D U s, we provide generating functions with respect to the length, area, semiperimeter, value of the last symbol, and number of interior points of Motzkin polyominoes. We give asymptotics and closed-form expressions for the total area, total semiperimeter, sum of the last symbol values, and total number of interior points over all Motzkin polyominoes of a given length. We also present and prove an engaging trinomial relation concerning the number of cells lying at different levels and first terms of the expanded (1 + x + x 2) n. [ABSTRACT FROM AUTHOR]

We explain a discontinuous drop in the exponential growth rate for certain multivariate generating functions at a critical parameter value in even dimensions d ≤ 4. This result depends on computations in the homology of the algebraic variety where the generating function has a pole. These computations are similar to, and inspired by, a thread of research in applications of complex algebraic geometry to hyperbolic PDEs, going back to Leray, Petrowski, Atiyah, Bott and Gårding. As a consequence, we give a topological explanation for certain asymptotic phenomena appearing in the combinatorics and number theory literature. Furthermore, we show how to combine topological methods with symbolic algebraic computation to determine explicitly the dominant asymptotics for such multivariate generating functions, giving a significant new tool to attack the so-called connection problem for asymptotics of P-recursive sequences. This in turn enables the rigorous determination of integer coefficients in the Morse-Smale complex, which are difficult to determine using direct geometric methods. [ABSTRACT FROM AUTHOR]

We extend the notion of nonbacktracking walks from unweighted graphs to graphs whose edges have a nonnegative weight. Here the weight associated with a walk is taken to be the product over the weights along the individual edges. We give two ways to compute the associated generating function, and corresponding node centrality measures. One method works directly on the original graph and one uses a line graph construction followed by a projection. The first method is more efficient, but the second has the advantage of extending naturally to time-evolving graphs. Based on these generating functions, we define and study corresponding centrality measures. Illustrative computational results are also provided. [ABSTRACT FROM AUTHOR]

Consider a card guessing game with complete feedback in which a deck of n cards ordered 1 , ... , n is riffle-shuffled once. With the goal to maximize the number of correct guesses, a player guesses cards from the top of the deck one at a time under the optimal strategy until no cards remain. We provide an expression for the expected number of correct guesses with arbitrary number of terms, an accuracy improvement over the results of Liu (2021). In addition, using generating functions, we give a unified framework for systematically calculating higher-order moments. Although the extension of the framework to k ≥ 2 shuffles is not immediately straightforward, we are able to settle a long-standing McGrath's conjectured optimal strategy described in Bayer and Diaconis (1992) by showing that the optimal guessing strategy for k = 1 riffle shuffle does not necessarily apply to k ≥ 2 shuffles. [ABSTRACT FROM AUTHOR]

In this paper, we give a generalization of the Pascal triangle called the quasi s-Pascal triangle. For this, consider a set of lattice path, which is a dual approach to the definition of Ramirez and Sirvent: A Generalization of the k-bonacci Sequence from Riordan Arrays. The electronic journal of combinatorics, 22(1) (2015), 1-38. We give the recurrence relation for the sum of elements lying over finite ray of the quasi s-Pascal triangle, then, we establish a q-analogue of the coefficient of this triangle. Some identities are also given. [ABSTRACT FROM AUTHOR]

For a graph $\Gamma$ , let $K(H_{\Gamma },\,1)$ denote the Eilenberg–Mac Lane space associated with the right-angled Artin (RAA) group $H_{\Gamma }$ defined by $\Gamma$. We use the relationship between the combinatorics of $\Gamma$ and the topological complexity of $K(H_{\Gamma },\,1)$ to explain, and generalize to the higher TC realm, Dranishnikov's observation that the topological complexity of a covering space can be larger than that of the base space. In the process, for any positive integer $n$ , we construct a graph $\mathcal {O}_n$ whose TC-generating function has polynomial numerator of degree $n$. Additionally, motivated by the fact that $K(H_{\Gamma },\,1)$ can be realized as a polyhedral product, we study the LS category and topological complexity of more general polyhedral product spaces. In particular, we use the concept of a strong axial map in order to give an estimate, sharp in a number of cases, of the topological complexity of a polyhedral product whose factors are real projective spaces. Our estimate exhibits a mixed cat-TC phenomenon not present in the case of RAA groups. [ABSTRACT FROM AUTHOR]

The aim of this article is to construct some new families of generating‐type functions interpolating a certain class of higher order Bernoulli‐type, Euler‐type, Apostol‐type numbers, and polynomials. Applying the umbral calculus convention method and the shift operator to these functions, these generating functions are investigated in many different aspects such as applications related to the finite calculus, combinatorial analysis, the chordal graph, number theory, and complex analysis especially partial fraction decomposition of rational functions associated with Laurent expansion. By using the falling factorial function and the Stirling numbers of the first kind, we also construct new families of generating functions for certain classes of higher order Apostol‐type numbers and polynomials, the Bernoulli numbers and polynomials, the Fubini numbers, and others. Many different relations among these generating functions, difference equation including the Eulerian numbers, the shift operator, minimal polynomial, polynomial of the chordal graph, and other applications are given. Moreover, further remarks and comments on the results of this paper are presented. [ABSTRACT FROM AUTHOR]

We develop a complete theory for the combinatorics of walk-counting on a directed graph in the case where each backtracking step is downweighted by a given factor. By deriving expressions for the associated generating functions, we also obtain linear systems for computing centrality measures in this setting. In particular, we show that backtrack-downweighted Katz-style network centrality can be computed at the same cost as standard Katz. Studying the limit of this centrality measure at its radius of convergence also leads to a new expression for backtrack-downweighted eigenvector centrality that generalizes previous work to the case where directed edges are present. The new theory allows us to combine advantages of standard and nonbacktracking cases, avoiding localization while accounting for tree-like structures. We illustrate the behavior of the backtrack-downweighted centrality measure on both synthetic and real networks. [ABSTRACT FROM AUTHOR]

In the spirit of Göllnitz's "big" partition theorem of 1967, we present a new mod-6 partition identity. Alladi et al. provided a four-parameter refinement of Göllnitz's big theorem in 1995 via a key identity of generating functions and the method of weighted words. By means of this technique, two similar mod-6 identities of this type were discovered—one by Alladi in 1999 and one by Alladi and Andrews in 2015. We finish the picture by presenting and proving the fourth and final possible mod-6 identity in this spirit. Furthermore, we provide a complete generalization of mod-n identities of this type. Finally, we apply a similar argument to generalize an identity of Alladi et al. from 2003. [ABSTRACT FROM AUTHOR]

Phylogenetic networks generalize phylogenetic trees, and have been introduced in order to describe evolution in the case of transfer of genetic material between coexisting species. There are many classes of phylogenetic networks, which can all be modeled as families of graphs with labeled leaves. In this paper, we focus on rooted and unrooted level-k networks and provide enumeration formulas (exact and asymptotic) for rooted and unrooted level-1 and level-2 phylogenetic networks with a given number of leaves. We also prove that the distribution of some parameters of these networks (such as their number of cycles) are asymptotically normally distributed. These results are obtained by first providing a recursive description (also called combinatorial specification) of our networks, and by next applying classical methods of enumerative, symbolic and analytic combinatorics. [ABSTRACT FROM AUTHOR]

In this work we study numbers and polynomials generated by two type of composition of generating functions and get their explicit formulae. Furthermore we state an improvement of the composita formulae's given in [7, 3]. Using the new composita formula's, we construct a variety of combinatorics identities. This study go alone to define new family of generalized Bernoulli polynomials which include Hermite-Bernoulli polynomials introduced by Dattoli and al [1]. [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]

We consider the enumeration of walks on the nonnegative lattice Nd; with steps defined by a set S = f-1; 0; 1gdnf0g. Previous work in this area has established asymptotics for the number of walks in certain families of models by applying the techniques of analytic combinatorics in several variables (ACSV), where one encodes the generating function of a lattice path model as the diagonal of a multivariate rational function. Melczer and Mishna obtained asymptotics when the set of steps S is symmetric over every axis; in this setting one can always apply the methods of ACSV to a multivariate rational function whose set of singularities is a smooth manifold (the simplest case). Here we go further, providing asymptotics for models with generating functions that must be encoded by multivariate rational functions having nonsmooth singular sets. In the process, our analysis connects past work to deeper structural results in the theory of ACSV. One application is a closed form for asymptotics of models defined by step sets that are symmetric over all but one axis. As a special case, we apply our results when d = 2 to give a rigorous proof of asymptotics conjectured by Bostan and Kauers; asymptotics for walks returning to boundary axes and the origin are also given. [ABSTRACT FROM AUTHOR]

Runs statistics have found many applications in various fields and have attracted attentions of many researchers. Traditional methods used to investigate run-related distributions are ad hoc and not easy to generalize. The problems often become tedious because of the combinatorial complexity involved. Several unified methods have been devised to overcome the combinatorial difficulties. One of them is the finite Markov chain imbedding approach. Recently we used a different systematic approach that is inspired by methods in statistical physics. In this approach the study of runs distributions is decoupled into two easy independent steps. In the first step, elements of each of the same object are considered in isolation without regards of elements of the other objects. By considering only one kind of object each time the complexity involved is reduced considerably. In the second step, general formulas in matrix or explicit forms combine the results from the first step into a whole multi-object system with potential nearest neighbor interactions. The method reduces the complicated combinatorics to simple mechanical manipulations of binomial and multinomial coefficients, which can be carried out automatically by the Gosper-Zeilberger method. Many commonly studied run and pattern distributions, such as exact length runs, runs of Type I, II, III, the longest runs, rises and falls, among others, can be handled by the method. Novel run-related distributions have been derived using the method. We'll discuss the general framework of the method and use some examples to illustrate its application to distributions of runs, including the derivation of the m th longest runs distributions of multivariate random sequences. [ABSTRACT FROM AUTHOR]

We introduce a new generating function based method to compute the Banzhaf, Deegan–Packel, Public Good (a.k.a. the Holler power index) and Shapley–Shubik power indices in the presence of incompatibility among players. More precisely, given a graph G = V , E with V the set of players and E the edge set, our extension involves multiple weighted voting games (MWVG's) and incompatible players, i.e., pairs of players belonging to E are not allowed to cooperate. The route to obtain the aforementioned generating functions comprises the use of a key lemma characterizing the set of minimal winning coalitions of the game with incompatibility due to Alonso-Meijide et al. (Appl Math Comput 252(1):377–387, 2015), a tool from combinatorial analysis, namely, the Omega calculus in partition analysis, and basic tools borrowed from commutative algebra involving the computation of certain quotients of polynomial rings module polynomial ideals. Using partition analysis, we obtain new generating functions to compute the Deegan–Packel and Public Good power indices with incompatibility leading to lower time complexity than previous results of Chessa (TOP 22(2):658–673, 2014) and some results of Alonso-Meijide et al. (Appl Math Comput 219(8):3395–3402, 2012). Using a conjunction of partition analysis and commutative algebra, we extend to MWVG's the generating function approach to compute the Banzhaf and Shapley–Shubik power indices in the presence of incompatibility. Finally, an example taken from the real-world, i.e., the European Union under the Lisbon Treaty, is used to illustrate the usefulness of the Omega package, a symbolic computational package that implements the Omega calculus in Mathematica, due to Andrews et al. (Eur J Comb 22(7):887–904, 2001) in the context of MWVG's by computing the PG power index of the associated voting game. [ABSTRACT FROM AUTHOR]

We define a generalized vector partition function and derive an identity for the generating series of such functions associated with solutions to basic recurrence relations of combinatorial analysis. As a consequence we obtain the generating function of the number of generalized lattice paths and a new version of the Chaundy-Bullard identity for the vector partition function. [ABSTRACT FROM AUTHOR]

The combinatorics of walks on a graph is a key topic in network science. Here we study a special class of walks on directed graphs. We combine two features that have previously been considered in isolation. We consider alternating walks, which form the basis of algorithms for hub/authority detection and for discovering directed bipartite substructure. Within this class, we restrict to non-backtracking walks, since this constraint has been seen to offer advantages in related contexts. We derive a recursive formula for counting the total number of non-backtracking alternating walks of a given length, leading to an expression for any associated power series expansion. We discuss computational issues for the widely used cases of resolvent and exponential series, showing that non-backtracking can be incorporated at very little extra cost. We also derive an appropriate asymptotic limit which gives a parameter-free, spectral analogue. We perform tests on an artificial data set in order to quantify the advantages of the new methodology. We also show that the removal of backtracking allows us to identify larger bipartite subgraphs within an anatomical connectivity network from neuroscience. [ABSTRACT FROM AUTHOR]

Stirling numbers of the second kind, S(n, r), denote the number of partitions of a finite set of size n into r disjoint nonempty subsets. The aim of this short article is to shed some light on the generating functions of these numbers by deriving them probabilistically. We do this by linking them to Markov chains related to the classical coupon collector problem; coupons are collected in discrete time (ordinary generating function) or in continuous time (exponential generating function). We also review the shortest possible combinatorial derivations of these generating functions. [ABSTRACT FROM AUTHOR]

In this paper, we consider an extension of the tribonacci polynomial, which we will refer to as the generalized (p; q; r)-tribonacci polynomial, denoted by Tn;m(x).We find an explicit formula for Tn;m(x), which we use to introduce the incomplete generalized (p; q; r)-tribonacci polynomials and derive several properties. An explicit formula for the generating function of the incomplete generalized polynomials is determined and a combinatorial interpretation is provided yielding further identities. [ABSTRACT FROM AUTHOR]

John Tromp introduced the so-called ‘binary lambda calculus’ as a way to encode lambda terms in terms of 0–1-strings using the de Bruijn representation along with a weighting scheme. Later, Grygiel and Lescanne conjectured that the number of binary lambda terms with m free indices and of size n (encoded as binary words of length n and according to Tromp’s weights) is o ( n − 3 ∕ 2 τ − n ) for τ ≈ 1 . 963448 … . We generalize the proposed notion of size and show that for several classes of lambda terms, including binary lambda terms with m free indices, the number of terms of size n is Θ n − 3 ∕ 2 ρ − n with some class dependent constant ρ , which in particular disproves the above mentioned conjecture. The methodology used is setting up the generating functions for the classes of lambda terms. These are infinitely nested radicals which are investigated then by a singularity analysis. We show further how some properties of random lambda terms can be analyzed and present a way to sample lambda terms uniformly at random in a very efficient way. This allows to generate terms of size more than one million within a reasonable time, which is significantly better than the samplers presented in the literature so far. [ABSTRACT FROM AUTHOR]

Let ( a n ) n ≥ 0 be a sequence of the Catalan-like numbers. We evaluate Hankel determinants det [ λ a i + j + μ a i + j + 1 ] 0 ≤ i , j ≤ n and det [ λ a i + j + 1 + μ a i + j + 2 ] 0 ≤ i , j ≤ n for arbitrary coefficients λ and μ . Our results unify many known results of Hankel determinant evaluations for classic combinatorial counting coefficients, including the Catalan, Motzkin and Schröder numbers. [ABSTRACT FROM AUTHOR]

In this paper we introduce restricted r-Stirling numbers of the first kind. Together with restricted r-Stirling numbers of the second kind and the associated r-Stirling numbers of both kinds, by giving more arithmetical and combinatorial properties, we introduce a new generalization of incomplete poly-Cauchy numbers of both kinds and incomplete poly-Bernoulli numbers. [ABSTRACT FROM AUTHOR]

In this work we consider two different aspects of weighted walks in cones. To begin we examine a particular weighted model, known as the Gouyou-Beauchamps model. Using the theory of analytic combinatorics in several variables we obtain the asymptotic expansion of the total number of Gouyou-Beauchamps walks confined to the quarter plane. Our formulas are parametrized by weights and starting point, and we identify six different asymptotic regimes (called universality classes) which arise according to the values of the weights. The weights allowed in this model satisfy natural algebraic identities permitting an expression of the weighted generating function in terms of the generating function of unweighted walks on the same steps. The second part of this article explains these identities combinatorially for walks in arbitrary cones and dimensions, and provides a characterization of universality classes for general weighted walks. Furthermore, we describe an infinite set of models with non-D-finite generating function. [ABSTRACT FROM AUTHOR]

We introduce themulti-poly-Bernoulli numbers and polynomialswith a q parameter, which are generalizations of the poly-Bernoulli numbers and polynomials with a q parameter, respectively.We give several combinatorial identities and properties of these new numbers and polynomials. [ABSTRACT FROM AUTHOR]

Using a combinatorial approach, we introduce the t-successive associated Stirling numbers and we give the recurrence relation and the generating function. We also establish the unimodality of sequence ... lying over a ray of the second kind's Stirling triangle. Some combinatorial identities are given. [ABSTRACT FROM AUTHOR]

This article presents a methodology that automatically derives a combinatorial specification for a permutation class C , given its basis B of excluded patterns and the set of simple permutations in C , when these sets are both finite. This is achieved considering both pattern avoidance and pattern containment constraints in permutations. The obtained specification yields a system of equations satisfied by the generating function of C , this system being always positive and algebraic. It also yields a uniform random sampler of permutations in C . The method presented is fully algorithmic. [ABSTRACT FROM AUTHOR]

In a recent work, Andrews introduced the new combinatorial objects called singular overpartitions. He proved that these singular overpartitions can be enumerated by the partition function which denotes the number of overpartitions of in which no part is divisible by and only parts may be overlined. In this paper, we consider the function from an arithmetical point of view. We establish a number of Ramanujan-like congruences and a congruence relation modulo for by employing some generating function dissection techniques. With the aid of these congruences and the relation, we obtain two new infinite families of congruences modulo satisfied by . [ABSTRACT FROM AUTHOR]

Based on a combinatorial approach to quantum gravity and random matrix theory, we show a central limit theorem that gives important insight into causally triangulated 3 D quantum gravity. [ABSTRACT FROM AUTHOR]