Let asc and desc denote respectively the statistics recording the number of ascents or descents in a sequence having non-negative integer entries. In a recent paper by Andrews and Chern, it was shown that the distribution of asc on the inversion sequence avoidance class $I_n(\geq,\neq,>)$ is the same as that of $n-1-\text{asc}$ on the class $I_n(>,\neq,\geq)$, which confirmed an earlier conjecture of Lin. In this paper, we consider some further enumerative aspects related to this equivalence and, as a consequence, provide an alternative proof of the conjecture. In particular, we find recurrence relations for the joint distribution on $I_n(\geq,\neq,>)$ of asc and desc along with two other parameters, and do the same for $n-1-\text{asc}$ and desc on $I_n(>,\neq,\geq)$. By employing a functional equation approach together with the kernel method, we are able to compute explicitly the generating function for both of the aforementioned joint distributions, which extends (and provides a new proof of) the recent result $|I_n(\geq,\neq,>)|=|I_n(>,\neq,\geq)|$. In both cases, an algorithm is formulated for computing the generating function of the asc distribution on members of each respective class having a fixed number of descents.
We provide a new succession rule (i.e. generating tree) associated with Schröder numbers, that interpolates between the known succession rules for Catalan and Baxter numbers. We define Schröder and Baxter generalizations of parallelogram polyominoes (called slicings) which grow according to these succession rules. We also exhibit Schröder subclasses of Baxter classes, namely a Schröder subset of triples of non-intersecting lattice paths, and a new Schröder subset of Baxter permutations.
James Haglund, Jeffrey B. Remmel, Andrew Timothy Wilson
We conjecture two combinatorial interpretations for the symmetric function ∆eken, where ∆f is an eigenoperator for the modified Macdonald polynomials defined by Bergeron, Garsia, Haiman, and Tesler. Both interpretations can be seen as generalizations of the Shuffle Conjecture, a statement originally conjectured by Haglund, Haiman, Remmel, Loehr, and Ulyanov and recently proved by Carlsson and Mellit. We show how previous work of the second and third authors on Tesler matrices and ordered set partitions can be used to verify several cases of our conjectures. Furthermore, we use a reciprocity identity and LLT polynomials to prove another case. Finally, we show how our conjectures inspire 4-variable generalizations of the Catalan numbers, extending work of Garsia, Haiman, and the first author.
In a rooted tree, protected nodes are neither leaves nor parents of any leaves. They have some practical motivations, e.g., in organizational schemes, security models and social-network models. Protected node profile measures the number of protected nodes with the same distance from the root in rooted trees. For no rooted tree, protected node profile has been investigated so far. Here, we present the asymptotic expectations, variances, covariance and limiting bivariate distribution of protected node profile and non-protected internal node profile in random tries, an important data structure on words in computer science. Also we investigate the fraction of these expectations asymptotically. These results are derived by the methods of analytic combinatorics such as generating functions, Mellin transform, Poissonization and depoissonization, saddle point method and singularity analysis.
A Peterson variety is a subvariety of the flag variety $G/B$ defined by certain linear conditions. Peterson varieties appear in the construction of the quantum cohomology of partial flag varieties and in applications to the Toda flows. Each Peterson variety has a one-dimensional torus $S^1$ acting on it. We give a basis of Peterson Schubert classes for $H_{S^1}^*(Pet)$ and identify the ring generators. In type A Harada-Tymoczko gave a positive Monk formula, and Bayegan-Harada gave Giambelli's formula for multiplication in the cohomology ring. This paper gives a Chevalley-Monk rule and Giambelli's formula for all Lie types.
The primary purpose of this paper is to introduce the, N-coprobabilistic normed space, coprobabilistic dual space of N-coprobabilistic normed space and give some facts that are related of them.
We show that the shapes of integer partitions chosen randomly according to Schur-Weyl measures of parameter $\alpha =1/2$ and Gelfand measures satisfy Kerov's central limit theorem. Thus, there is a gaussian process $\Delta$ such that under Plancherel, Schur-Weyl or Gelfand measures, the deviations $\Delta_n(s)=\lambda _n(\sqrt{n} s)-\sqrt{n} \lambda _{\infty}^{\ast}(s)$ converge in law towards $\Delta (s)$, up to a translation along the $x$-axis in the case of Schur-Weyl measures, and up to a factor $\sqrt{2}$ and a deterministic remainder in the case of Gelfand measures. The proofs of these results follow the one given by Ivanov and Olshanski for Plancherel measures; hence, one uses a "method of noncommutative moments''.
In this paper, we develop a new method to compute generating functions of the form $NM_τ (t,x,y) = \sum\limits_{n ≥0} {\frac{t^n} {n!}}∑_{σ ∈\mathcal{lNM_{n}(τ )}} x^{LRMin(σ)} y^{1+des(σ )}$ where $τ$ is a permutation that starts with $1, \mathcal{NM_n}(τ )$ is the set of permutations in the symmetric group $S_n$ with no $τ$ -matches, and for any permutation $σ ∈S_n$, $LRMin(σ )$ is the number of left-to-right minima of $σ$ and $des(σ )$ is the number of descents of $σ$ . Our method does not compute $NM_τ (t,x,y)$ directly, but assumes that $NM_τ (t,x,y) = \frac{1}{/ (U_τ (t,y))^x}$ where $U_τ (t,y) = \sum_{n ≥0} U_τ ,n(y) \frac{t^n}{ n!}$ so that $U_τ (t,y) = \frac{1}{ NM_τ (t,1,y)}$. We then use the so-called homomorphism method and the combinatorial interpretation of $NM_τ (t,1,y)$ to develop recursions for the coefficient of $U_τ (t,y)$.
A $k$-triangulation of the $n$-gon is a maximal set of diagonals of the $n$-gon containing no subset of $k+1$ mutually crossing diagonals. The number of $k$-triangulations of the $n$-gon, determined by Jakob Jonsson, is equal to a $k \times k$ Hankel determinant of Catalan numbers. This determinant is also equal to the number of $k$ non-crossing Dyck paths of semi-length $n-2k$. This brings up the problem of finding a combinatorial bijection between these two sets. In FPSAC 2007, Elizalde presented such a bijection for the case $k=2$. We construct another bijection for this case that is stronger and simpler that Elizalde's. The bijection preserves two sets of parameters, degrees and generalized returns. As a corollary, we generalize Jonsson's formula for $k=2$ by counting the number of $2$-triangulations of the $n$-gon with a given degree at a fixed vertex.
Let $n$ and $k$ be positive integers, $d(k)$ and $\nu_2(k)$ denote the number of ones in the binary representation of $k$ and the highest power of two dividing $k$, respectively. De Wannemacker recently proved for the Stirling numbers of the second kind that $\nu_2(S(2^n,k))=d(k)-1, 1\leq k \leq 2^n$. Here we prove that $\nu_2(S(c2^n,k))=d(k)-1, 1\leq k \leq 2^n$, for any positive integer $c$. We improve and extend this statement in some special cases. For the difference, we obtain lower bounds on $\nu_2(S(c2^{n+1}+u,k)-S(c2^n+u,k))$ for any nonnegative integer $u$, make a conjecture on the exact order and, for $u=0$, prove part of it when $k \leq 6$, or $k \geq 5$ and $d(k) \leq 2$. The proofs rely on congruential identities for power series and polynomials related to the Stirling numbers and Bell polynomials, and some divisibility properties.
Recently Postnikov gave a combinatorial description of the cells in a totally-nonnegative Grassmannian. These cells correspond to a special class of matroids called positroids. There are many interesting combinatorial objects associated to a positroid. We introduce some recent results, including the generalization and proof of the purity conjecture by Leclerc and Zelevinsky on weakly separated sets.
In this paper we solve the known V.A. Liskovets problem (1996) on the enumeration of orientable coverings over a non-orientable manifold with an arbitrary finitely generated fundamental group. As an application we obtain general formulas for the number of chiral and reflexible coverings over the manifold. As a further application, we count the chiral and reflexible maps and hypermaps on a closed orientable surface by the number of edges. Also, by this method the number of self-dual and Petri-dual maps can be determined. This will be done in forthcoming papers by authors.
Permutation tableaux are new objects that were introduced by Postnikov in the context of enumeration of the totally positive Grassmannian cells. They are known to be in bijection with permutations and recently, they have been connected to PASEP model used in statistical physics. Properties of permutation tableaux became a focus of a considerable research activity. In this paper we study properties of basic statistics defined on permutation tableaux. We present a simple and unified approach based on probabilistic techniques and use it to compute the expected values of basic statistics defined on permutation tableaux. We also provide a non―bijective and very simple proof that there are n! permutation tableaux of length n.
It is well known that many distributions that arise in the analysis of algorithms have an asymptotically fluctuating behaviour in the sense that we do not have 'full' convergence, but only convergence along suitable subsequences as the size of the input to the algorithm tends to infinity. We are interested in constructions that display such behaviour via an ordinarily convergent background process in the sense that the periodicities arise from this process by deterministic transformations, typically involving discretization as a decisive step. This leads to structural representations of the resulting family of limit distributions along subsequences, which in turn may give access to their properties, such as the tail behaviour (unsuccessful search in digital search trees) or the dependence on parameters of the algorithm (success probability in a selection algorithm).