Search

We enumerate the numbers $Av_n^k(1324)$ of 1324-avoiding $n$-permutations with exactly $k$ inversions for all $k$ and $n \geq (k+7)/2$. The result depends on a structural characterization of such permutations in terms of a new notion of almost-decomposability. In particular, our enumeration verifies half of a conjecture of Claesson, Jel\'inek and Steingr\'imsson, according to which $Av_n^k(1324) \leq Av_{n+1}^k(1324)$ for all $n$ and $k$. Proving also the other half would improve the best known upper bound for the exponential growth rate of the number of $1324$-avoiders from $13.5$ to approximately $13.002$., Comment: 23 pages

Let $S_n$ be the symmetric group on the set $[n]:=\{1,2,\ldots,n\}$. Given a permutation $\sigma=\sigma_1\sigma_2 \cdots \sigma_n \in S_n$, we say it has a descent at index $i$ if $\sigma_i>\sigma_{i+1}$. Let $\mathcal{D}(\sigma)$ be the set of all descents of $\sigma$ and define $\mathcal{D}(S;n)=\{\sigma\in S_n\, | \,\mathcal{D}(\sigma)=S\}$. We study the Hamming metric and $\ell_\infty$-metric on the sets $\mathcal{D}(S;n)$ for all possible nonempty $S\subset[n-1]$ to determine the maximum possible value that these metrics can achieve when restricted to these subsets., Comment: 10 pages, 2 tables

Stirling permutations are parking functions, and we investigate two parking function statistics in the context of these objects: lucky cars and displacement. Among our results, we consider two extreme cases: extremely lucky Stirling permutations (those with maximally many lucky cars) and extremely unlucky Stirling permutations (those with exactly one lucky car). We show that the number of extremely lucky Stirling permutations of order $n$ is the Catalan number $C_n$, and the number of extremely unlucky Stirling permutations is $(n-1)!$. We also give some results for luck that lies between these two extremes. Further, we establish that the displacement of any Stirling permutation of order $n$ is $n^2$, and we prove several results about displacement composition vectors. We conclude with directions for further study., Comment: 17 pages, 3 tables

For any integers $1\leq k\leq n$, we introduce a new family of parking functions called $k$-vacillating parking functions of length $n$. The parking rule for $k$-vacillating parking functions allows a car with preference $p$ to park in the first available spot in encounters among the parking spots numbered $p$, $p-k$, and $p+k$ (in that order and if those spots exists). In this way, $k$-vacillating parking functions are a modification of Naples parking functions, which allow for backwards movement of a car, and of $\ell$-interval parking functions, which allow a car to park in its preference or up to $\ell$ spots in front of its preference. Among our results, we establish a combinatorial interpretation for the numerator of the $n$th convergent of the continued fraction of $\sqrt{2}$, as the number of non-decreasing $1$-vacillating parking functions of length~$n$. Our main result gives a product formula for the enumeration of $k$-vacillating parking functions of length $n$ based on the number of $1$-vacillating parking functions of smaller length. We conclude with some directions for further research., Comment: 12 pages, 1 figure, to appear in Journal of Combinatorics

Recall that $\alpha=(a_1,a_2,\ldots,a_n)\in[n]^n$ is a parking function if its nondecreasing rearrangement $\beta=(b_1,b_2,\ldots,b_n)$ satisfies $b_i\leq i$ for all $1\leq i\leq n$. In this article, we study parking functions based on their ascents (indices at which $a_ia_{i+1}$), and ties (indices at which $a_i=a_{i+1}$). By utilizing multiset Eulerian polynomials, we give a generating function for the number of parking functions of length $n$ with $i$ descents. We present a recursive formula for the number of parking functions of length $n$ with descents at a specified subset of $[n-1]$. We establish that the number of parking functions of length $n$ with descents at $I\subset[n-1]$ and descents at $J=\{n-i:i\in I\}$ are equinumerous. As a special case, we show that the number of parking functions of length $n$ with descents at the first $k$ indices is given by $f(n, n-k-1)=\frac{1}{n}\binom{n}{k}\binom{2n-k}{n-k-1}$. We prove this by bijecting to the set of standard Young tableaux of shape $((n-k)^2,1^k)$, which are enumerated by $f(n,n-k-1)$. We also study peaks of parking functions, which are indices at which $a_{i-1}a_{i+1}$. We show that the set of parking functions with no peaks and no ties is enumerated by the Catalan numbers. We conclude our study by characterizing when a parking function is uniquely determined by their statistic encoding; a word indicating what indices in the parking function are ascents, descents, and ties. We provide open problems throughout., Comment: 17 pages, 2 figures, 5 tables, version 2 provides a new proof of Theorem 3.8

The number of 123-avoiding permutation on $\{1,2,\ldots,n\}$ with a fixed leading terms is counted by the ballot numbers. The same holds for $132$-avoiding permutations. These results were proved by Miner and Pak using the Robinson-Schensted-Knuth (RSK) correspondence to connect permutations with Dyck paths. In this paper, we first provide an alternate proof of these enumeration results via a direct counting argument. We then study the number of pattern-avoiding permutations with a fixed prefix of length $t\geq1$, generalizing the $t=1$ case. We find exact expressions for single and pairs of patterns of length three as well as the pair $3412$ and $3421$. These expressions depend on $t$, the extrema, and the order statistics. We also define $r$-Wilf equivalence for permutations with a single fixed leading term $r$, and classify the $r$-Wilf-equivalence classes for both classical and vincular patterns of length three., Comment: 23 pages, Journal of Combinatorics (forthcoming)

In this note, we prove some and conjecture other results regarding the distribution of descent top and descent bottom sets on some pattern-avoiding permutations. In particular, for 3-letter patterns, we show bijectively that the set of descent tops and the set of descent bottoms are jointly equidistributed on the avoiders of 231 and 312. We also conjecture similar equidistributions for 4-letter patterns, in particular, that the set of descent tops and the set of descent bottoms are jointly equidistributed on the avoiders of 3142, 3241, 4132., Comment: 13 pages

In this paper, we study pattern avoidance for stabilized-interval-free (SIF) permutations. These permutations are contained in the set of indecomposable permutations and in the set of derangements. We enumerate pattern-avoiding SIF permutations for classical and pairs of patterns of size 3. In particular, for the patterns 123 and 231, we rely on combinatorial arguments and the fixed-point distribution of general permutations avoiding these patterns. We briefly discuss 123-avoiding permutations with two fixed points and offer a conjecture for their enumeration by the distance between their fixed points. For the pattern 231, we also give a direct argument that uses a bijection to ordered forests., Comment: 14 pages

Recently, Hong and Li launched a systematic study of length-four pattern avoidance in inversion sequences, and in particular, they conjectured that the number of $0021$-avoiding inversion sequences can be enumerated by the OEIS entry A218225. Meanwhile, Burstein suggested that the same sequence might also count three sets of pattern restricted permutations. The objective of this paper is not only a confirmation of Hong and Li's conjecture and Burstein's first conjecture, but also two more delicate generating function identities with the $\mathsf{ides}$ statistic concerned in the restricted permutation case, and the $\mathsf{asc}$ statistic concerned in the restricted inversion sequence case, which yield a new equidistribution result., Comment: 19 pages, comments are welcome

A Fishburn permutation is a permutation which avoids the bivincular pattern $(231, \{1\}, \{1\})$, while an ascent sequence is a sequence of nonnegative integers in which each entry is less than or equal to one more than the number of ascents to its left. Fishburn permutations and ascent sequences are linked by a bijection $g$ of Bousquet-M\'elou, Claesson, Dukes, and Kitaev. We write $F_n(\sigma_1,\ldots,\sigma_k)$ to denote the set of Fishburn permutations of length $n$ which avoid each of $\sigma_1,\ldots,\sigma_k$ and we write $A_n(\alpha_1,\ldots,\alpha_k)$ to denote the set of ascent sequences which avoid each of $\alpha_1,\ldots,\alpha_k$. We settle a conjecture of Gil and Weiner by showing that $g$ restricts to a bijection between $F_n(3412)$ and $A_n(201)$. Building on work of Gil and Weiner, we use elementary techniques to enumerate $F_n(123)$ with respect to inversion number and number of left-to-right maxima, obtaining expressions in terms of $q$-binomial coefficients, and to enumerate $F_n(123,\sigma)$ for all $\sigma$. We use generating tree techniques to study the generating functions for $F_n(321, 1423)$, $F_n(321,3124)$, and $F_n(321,2143)$ with respect to inversion number and number of left-to-right maxima. We use these results to show $|F_n(321,1423)| = |F_n(321,3124)| = F_{n+2} - n - 1$, where $F_n$ is a Fibonacci number, and $|F_n(321,2143)| = 2^{n-1}$. We conclude with a variety of conjectures and open problems., Comment: 41 pages, 4 figures

A crucial permutation is a permutation that avoids a given set of prohibitions, but any of its extensions, in an allowable way, results in a prohibition being introduced. In this paper, we introduce five natural types of crucial permutations with respect to monotone patterns, notably quadrocrucial permutations that are linked most closely to Erd\H{o}s-Szekeres extremal permutations. The way we define right-crucial and bicrucial permutations is consistent with the definition of respective permutations studied in the literature in the contexts of other prohibitions. For each of the five types, we provide its characterization in terms of Young tableaux via the RSK correspondence. Moreover, we use the characterizations to prove that the number of such permutations of length $n$ is growing when $n\to\infty$, and to enumerate minimal crucial permutations in all but one case. We also provide other enumerative results.

We prove that $|Av_n(231,312,1432)|$, $|Av_n(312,321,1342)|$ $|Av_n(231,312,4321,21543)|$, and $ |Av_n(321,231,4123,21534)|$, are all equal to $F_{n+1} - 1$ where $F_n$ is the $n$-th Fibonacci number using the convention $F_0 = F_1 = 1$ and $Av_n(S)$ is the set of all permutations of length $n$ that avoid all of the patterns in the set $S$. To do this, we characterize the structures of the permutations in these sets in terms of Fibonacci permutations. Then, we further quantify the structures using statistics such as inversion number and a statistic that measures the length of Fibonacci subsequences. Finally, we encode these statistics in generating functions written in terms of the generating function for Fibonacci permutations. We use these generating functions to find analogs about recurrence relation and addition formulae of Fibonacci identities., Comment: 17 Pages, 5 figures, to be published in Minnesota Journal of Undergraduate Mathematics

In their study of cyclic pattern containment, Domagalski et al. conjecture differential equations for the generating functions of circular permutations avoiding consecutive patterns of length 3. In this note, we prove and significantly generalize these conjectures. We show that, for every consecutive pattern $\sigma$ beginning with 1, the bivariate generating function counting occurrences of $\sigma$ in circular permutations can be obtained from the generating function counting occurrences of $\sigma$ in (linear) permutations. This includes all the patterns for which the latter generating function is known.

We study the generating function of descent numbers for the permutations with descent pairs of prescribed parities, the distribution of which turns out to be a refinement of median Genocchi numbers. We prove the $\gamma$-positivity for the polynomial and derive the generating function for the $\gamma$-vectors, expressed in the form of continued fraction. We also come up with an artificial statistic that gives a $q$-analogue of the $\gamma$-positivity for the permutations with descents only allowed from an odd value to an odd value., Comment: 18 pages, 7 figures

A permutation $\pi$ contains a pattern $\sigma$ if and only if there is a subsequence in $\pi$ with its letters are in the same relative order as those in $\sigma$. Partially ordered patterns (POPs) provide a convenient way to denote patterns in which the relative order of some of the letters does not matter. This paper elucidates connections between the avoidance sets of a few POPs with other combinatorial objects, directly answering five open questions posed by Gao and Kitaev \cite{gao-kitaev-2019}. This was done by thoroughly analysing the avoidance sets and developing recursive algorithms to derive these sets and their corresponding combinatorial objects in parallel, which yielded a natural bijection. We also analysed an avoidance set whose simple permutations are enumerated by the Fibonacci numbers and derived an algorithm to obtain them recursively.

The notion of a $p$-Riordan graph generalizes that of a Riordan graph, which, in turn, generalizes the notions of a Pascal graph and a Toeplitz graph. In this paper we introduce the notion of a $p$-Riordan word, and show how to encode $p$-Riordan graphs by $p$-Riordan words. For special important cases of Riordan graphs (the case $p=2$) and oriented Riordan graphs (the case $p=3$) we provide alternative encodings in terms of pattern-avoiding permutations and certain balanced words, respectively. As a bi-product of our studies, we provide an alternative proof of a known enumerative result on closed walks in the cube., Comment: To appear in Graphs and Combinatorics, 14 pages, 1 fiugure

We study the generating polynomial of the flag major index with each one-dimensional character, called signed Mahonian polynomial, over the colored permutation group, the wreath product of a cyclic group with the symmetric group. Using the insertion lemma of Han and Haglund-Loehr-Remmel and a signed extension established by Eu et al., we derive the signed Mahonian polynomial over the quotients of parabolic subgroups of the colored permutation group, for a variety of systems of coset representatives in terms of subsequence restrictions. This generalizes the related work over parabolic quotients of the symmetric group due to Caselli as well as to Eu et al. As a byproduct, we derive a product formula that generalizes Biagioli's result about the signed Mahonian on the even signed permutation groups., Comment: 21 pages

A systematic study of avoidance of mesh patterns of length 2 was conducted by Hilmarsson et al. in 2015. In a recent paper Kitaev and Zhang examined the distribution of the aforementioned patterns. The aim of this paper is to prove more equidistributions of mesh pattern and confirm Kitaev and Zhang's four conjectures by constructing two involutions on permutations., Comment: 15 pages,3 figures, comments are welcome

The study of pattern avoidance in inversion sequences recently attracts extensive research interests. In particular, Zhicong Lin and Jun Ma conjectured a formula that counts the number of inversion sequences avoiding the pattern $0012$. We will not only confirm this conjecture but also give a formula that enumerates the number of $0012$-avoiding inversion sequences in which the last entry equals $n-1$.

We present a short, direct proof of the fact that the generating function of all permutations of a fixed length $n\geq 4$ is divisible by $(1+z)^m$, where $m=\lfloor (n-2)/2 \rfloor$., Comment: 4 pages

In this paper, we enumerate Dumont permutations of the fourth kind avoiding or containing certain permutations of length 4. We also conjecture a Wilf-equivalence of two 4-letter patterns on Dumont permutations of the first kind.

Boolean nested canalizing functions (NCFs) have important applications in molecular regulatory networks, engineering and computer science. In this paper, we study their certificate complexity. For both Boolean values $b\in\{0,1\}$, we obtain a formula for $b$-certificate complexity and consequently, we develop a direct proof of the certificate complexity formula of an NCF. Symmetry is another interesting property of Boolean functions and we significantly simplify the proofs of some recent theorems about partial symmetry of NCFs. We also describe the algebraic normal form of $s$-symmetric NCFs. We obtain the general formula of the cardinality of the set of $n$-variable $s$-symmetric Boolean NCFs for $s=1,\dots,n$. In particular, we enumerate the strongly asymmetric Boolean NCFs., Comment: 14 pages

In 2017 Davis, Nelson, Petersen, and Tenner pioneered the study of pinnacle sets of permutations and asked whether there exists a class of operations, which applied to a permutation in $\mathfrak{S}_n$, can produce any other permutation with the same pinnacle set and no others. In this paper, we adapt a group action defined by Foata and Strehl to provide a way to generate all permutations with a given pinnacle set. From this we give a closed non-recursive formula enumerating permutations with a given pinnacle set. Thus answering a question posed by Davis, Nelson, Petersen, and Tenner., Comment: 17 pages, 1 figure, 3 tables

Two permutation classes, the X-class and subpermutations of the increasing oscillation are shown to exhibit an exponential Wilf-collapse. This means that the number of distinct enumerations of principal subclasses of each of these classes grows much more slowly than the class itself whereas a priori, based only on symmetries of the class, there is no reason to expect this. The underlying cause of the collapse in both cases is the ability to apply some form of local symmetry which, combined with a greedy algorithm for detecting patterns in these classes, yields a Wilf-collapse., Comment: Final version as accepted by DMTCS. Formatting changes only

Defant, Engen, and Miller defined a permutation to be uniquely sorted if it has exactly one preimage under West's stack-sorting map. We enumerate classes of uniquely sorted permutations that avoid a pattern of length three and a pattern of length four by establishing bijections between these classes and various lattice paths. This allows us to prove nine conjectures of Defant., Comment: 23 pages, 18 figures; reformatted for Discrete Mathematics & Theoretical Computer Science

Recently, B\'ona and Smith defined strong pattern avoidance, saying that a permutation $\pi$ strongly avoids a pattern $\tau$ if $\pi$ and $\pi^2$ both avoid $\tau$. They conjectured that for every positive integer $k$, there is a permutation in $S_{k^3}$ that strongly avoids $123\cdots (k+1)$. We use the Robinson--Schensted--Knuth correspondence to settle this conjecture, showing that the number of such permutations is at least $k^{k^3/2+O(k^3/\log k)}$ and at most $k^{2k^3+O(k^3/\log k)}$. We enumerate $231$-avoiding permutations of order $3$, and we give two further enumerative results concerning strong pattern avoidance. We also consider permutations whose powers all avoid a pattern $\tau$. Finally, we study subgroups of symmetric groups whose elements all avoid certain patterns. This leads to several new open problems connecting the group structures of symmetric groups with pattern avoidance., Comment: 16 pages, 1 figure

Let $\sigma$ be a permutation on $n$ letters. We say that a permutation $\tau$ is an even (resp. odd) $k$th root of $\sigma$ if $\tau^k=\sigma$ and $\tau$ is an even (resp. odd) permutation. In this article, we obtain generating functions for the number of even and odd $k$th roots of permutations. Our result implies know generating functions of Moser and Wyman and also some generating functions for sequences in The On-line Encyclopedia of Integer Sequences (OEIS)., Comment: Second version, 11 pages

In this paper, we first consider a generalization of the David-Barton identity which relate the alternating run polynomials to Eulerian polynomials. By using context-free grammars, we then present a combinatorial interpretation of a family of q-alternating run polynomials. Furthermore, we introduce the definition of semi-gamma-positive polynomial and we show the semi-gamma-positivity of the alternating run polynomials of dual Stirling permutations. A connection between the up-down run polynomials of permutations and the alternating run polynomials of dual Stirling permutations is established., Comment: 14 pages

We give three applications of a recently-proven "Decomposition Lemma," which allows one to count preimages of certain sets of permutations under West's stack-sorting map $s$. We first enumerate the permutation class $s^{-1}(\text{Av}(231,321))=\text{Av}(2341,3241,45231)$, finding a new example of an unbalanced Wilf equivalence. This result is equivalent to the enumeration of permutations sortable by ${\bf B}\circ s$, where ${\bf B}$ is the bubble sort map. We then prove that the sets $s^{-1}(\text{Av}(231,312))$, $s^{-1}(\text{Av}(132,231))=\text{Av}(2341,1342,\underline{32}41,\underline{31}42)$, and $s^{-1}(\text{Av}(132,312))=\text{Av}(1342,3142,3412,34\underline{21})$ are counted by the so-called "Boolean-Catalan numbers," settling a conjecture of the current author and another conjecture of Hossain. This completes the enumerations of all sets of the form $s^{-1}(\text{Av}(\tau^{(1)},\ldots,\tau^{(r)}))$ for $\{\tau^{(1)},\ldots,\tau^{(r)}\}\subseteq S_3$ with the exception of the set $\{321\}$. We also find an explicit formula for $|s^{-1}(\text{Av}_{n,k}(231,312,321))|$, where $\text{Av}_{n,k}(231,312,321)$ is the set of permutations in $\text{Av}_n(231,312,321)$ with $k$ descents. This allows us to prove a conjectured identity involving Catalan numbers and order ideals in Young's lattice., Comment: 20 pages, 4 figures. arXiv admin note: text overlap with arXiv:1903.09138

A systematic study of avoidance of mesh patterns of length 2 was conducted by Hilmarsson et al., where 25 out of 65 non-equivalent cases were solved. In this paper, we give 27 distribution results for these patterns including 14 distributions for which avoidance was not known. Moreover, for the unsolved cases, we prove an equidistribution result (out of 6 equidistribution results we prove in total), and conjecture 6 more equidistributions. Finally, we find seemingly unknown distribution of the well known permutation statistic ``strict fixed point'', which plays a key role in many of our enumerative results. This paper is the first systematic study of distributions of mesh patterns. Our techniques to obtain the results include, but are not limited to, obtaining functional relations for generating functions, and finding recurrence relations and bijections., Comment: Advances in Applied Mathematics 110 (2019) 1-32; there is a mistake in the proof of Theorem 5.1 in version 1 of the paper; its statement is now a conjecture

We offer a new proof that a certain q-analogue of multinomial coeffi- cients furnishes a q-counting of the set of permutations of an associated multiset of positive integers, according to the number of inversions in such arrangements. Our proof uses the fact that such q-multinomial coefficients enumerate certain classes of chains of subspaces of a fnite dimensional vector space over a fnite field of cardinality q. Additionally, we investigate the function that counts the number of permutations of a multiset having a fixed number of inversions.

The Legendre-Stirling numbers of the second kind were introduced by Everitt et al. in the spectral theory of powers of the Legendre differential expressions. In this paper, we provide a combinatorial code for Legendre-Stirling set partitions. As an application, we obtain combinatorial expansions of the Legendre-Stirling numbers of both kinds. Moreover, we present grammatical descriptions of the Jacobi-Stirling numbers of both kinds., Comment: 11 pages

We show how to enumerate words in $1^{m_1} \dots n^{m_n}$ that avoid the increasing consecutive pattern $12 \dots r$ for any $r \geq 2$. Our approach yields an $O(n^{s+1})$ algorithm to enumerate words in $1^s \dots n^s$, avoiding the consecutive pattern $1\dots r$, for any $s$, and any $r$. This enables us to supply many more terms to quite a few OEIS sequences, and create new ones. We also treat the more general case of counting words with a specified number of the pattern of interest (the avoiding case corresponding to zero appearances). This article is accompanied by three Maple packages implementing our algorithms., Comment: After the first version of the current paper was posted, Justin Troyka pointed out that our Theorem 1 is not new and it goes back to Ira Gessel. Thus we have this second version

We define a variation of Stirling permutations, called quasi-Stirling permutations, to be permutations on the multiset $\{1,1,2,2,\ldots, n,n\}$ that avoid the patterns 1212 and 2121. Their study is motivated by a known relationship between Stirling permutations and increasing ordered rooted labeled trees. We construct a bijection between quasi-Stirling permutations and the set of ordered rooted labeled trees and investigate pattern avoidance for these permutations.

We enumerate permutations in the two permutation classes $\text{Av}_n(312, 4321)$ and $\text{Av}_n(321, 4123)$ by the number of cycles each permutation admits. We also refine this enumeration with respect to several statistics.

This paper analyzes relations between pattern avoidance of certain permutations and graphs on staircase grids and boundary grids, and proves two conjectures posed by Bean, Tannock, and Ulfarsson (2015). More specifically, this paper enumerates a certain family of staircase encodings and proves that the downcore graph, a certain graph established on the boundary grid, is pure if and only if the permutation corresponding to the boundary grid avoids the classical patterns 123 and 2143., Comment: 14 pages, 7 figures

In this paper, we study gamma-positivity of descent-type polynomials by introducing the change of context-free grammars method. We first present grammatical proofs of the gamma-positivity of the Eulerian polynomials, type B Eulerian polynomials, derangement polynomials, Narayana polynomials and type B Narayana polynomials. We then provide partial gamma-positive expansions for several multivariate polynomials associated to Stirling permutations, Legendre-Stirling permutations, Jacobi-Stirling permutations and type B derangements, and the recurrences for the partial gamma-coefficients of these expansions are also obtained. Moreover, we define variants of the Foata-Strehl group action which are used to give combinatorial interpretations for the coefficients of most of these partial gamma-positive expansions., Comment: 31 pages

In this paper, several variants of the ascent-plateau statistic are introduced, including flag ascent-plateau, double ascent and descent-plateau. We first study the flag ascent-plateau statistic on Stirling permutations by using context-free grammars. We then present a unified refinement of the ascent polynomials and the ascent-plateau polynomials. In particular, by using Foata and Strehl's group action, we prove two bistatistics over the set of Stirling permutations of order n are equidistributed., Comment: 15 pages

Enumeration problems related to words avoiding patterns as well as permutations that contain the pattern $123$ exactly once have been studied in great detail. However, the problem of enumerating words that contain the pattern $123$ exactly once is new and will be the focus of this paper. Previously, Doron Zeilberger provided a shortened version of Alexander Burstein's combinatorial proof of John Noonan's theorem that the number of permutations with exactly one $321$ pattern is equal to $\frac{3}{n} \binom{2n}{n+3}$. Surprisingly, a similar method can be directly adapted to words. We are able to use this method to find a formula enumerating the words with exactly one $123$ pattern. Further inspired by Nathaniel Shar and Zeilberger's paper on generating functions enumerating 123-avoiding words with $r$ occurrences of each letter, we examine the algebraic equations for generating functions for words with $r$ occurrences of each letter and with exactly one $123$ pattern., Comment: 12 pages

An open conjecture in pattern avoidance theory is that the distribution of the major index among 321-avoiding permutations is distributed unimodally. We construct a formula for this distribution, and in the case of 2 descents prove unimodality, with unimodality for 3 through 5 descents likely being little more complicated. The formula refines the $q$-analogue of the Frame-Robinson-Thrall hooklength formula for two-rowed partitions, and in the latter part of the paper we discuss another theorem of the same type, and further exploration toward this question. We also give observations on the analogous behaviors for other permutation patterns of length 3., Comment: v1: 14 pages. Partially presented at CANT 2017. Comments welcome. v2: Conjecture on (m,k,1) now a theorem; this line of investigation to be pursued further

In a rooted tree, we call a vertex {\em balanced} if it is at equal distance from all its descendant leaves. We count balanced vertices in three different tree varieties. For decreasing binary trees, we can prove that the probability that a vertex chosen uniformly at random from the set of all trees of a given size is balanced is monotone decreasing., Comment: 16 pages, 3 figures

Two mesh patterns are coincident if they are avoided by the same set of permutations, and are Wilf-equivalent if they have the same number of avoiders of each length. We provide sufficient conditions for coincidence of mesh patterns, when only permutations also avoiding a longer classical pattern are considered. Using these conditions we completely classify coincidences between families containing a mesh pattern of length 2 and a classical pattern of length 3. Furthermore, we completely Wilf-classify mesh patterns of length 2 inside the class of 231-avoiding permutations.

In this paper, we present grammatical descriptions of several polynomials associated with Eulerian polynomials, including q-Eulerian polynomials, alternating run polynomials and derangement polynomials. As applications, we get several convolution formulas involving these polynomials., Comment: 14 pages

A grid class consists of permutations whose pictorial depiction can be partitioned into increasing and decreasing parts as determined by a given matrix. In this paper, we introduce a method for enumerating cyclic permutations in vector grid classes by establishing a bijective relationship with certain necklaces. We use this method to complete the enumeration of cyclic permutations in the length 3 vector grid classes. In addition, we define an analog of Wilf-equivalence between these sets. We conclude by discussing cyclic permutations in alternating grid classes.

Comtet introduced the notion of indecomposable permutations in 1972. A permutation is indecomposable if and only if it has no proper prefix which is itself a permutation. Indecomposable permutations were studied in the literature in various contexts. In particular, this notion has been proven to be useful in obtaining non-trivial enumeration and equidistribution results on permutations. In this paper, we give a complete classification of indecomposable permutations avoiding a classical pattern of length 3 or 4, and of indecomposable permutations avoiding a non-consecutive vincular pattern of length 3. Further, we provide a recursive formula for enumerating $12\cdots k$-avoiding indecomposable permutations for $k\geq 3$. Several of our results involve the descent statistic. We also provide a bijective proof of a fact relevant to our studies., Comment: 22 pages; The reference [14] is added and is mentioned in the text after Theorems 3.5 and 3.7

In this paper we study the generating polynomials obtained by enumerating signed simsun permutations by number of the descents. Properties of the polynomials, including the recurrence relations and generating functions are studied., Comment: 10 pages

In this paper, we study the relationship among left peaks, interior peaks and up-down runs of simsun permutations. Properties of the generating polynomials, including the recurrence relation, generating function and real-rootedness are studied. Moreover, we introduce and study simsun permutations of the second kind., Comment: 13 pages

Vincular and covincular patterns are generalizations of classical patterns allowing restrictions on the indices and values of the occurrences in a permutation. In this paper we study the integer sequences arising as the enumerations of permutations simultaneously avoiding a vincular and a covincular pattern, both of length 3, with at most one restriction. We see familiar sequences, such as the Catalan and Motzkin numbers, but also some previously unknown sequences which have close links to other combinatorial objects such as lattice paths and integer partitions. Where possible we include a generating function for the enumeration. One of the cases considered settles a conjecture by Pudwell (2010) on the Wilf-equivalence of barred patterns. We also give an alternative proof of the classic result that permutations avoiding 123 are counted by the Catalan numbers., Comment: 24 pages, 11 figures, 2 tables

Caffrey, Egge, Michel, Rubin and Ver Steegh recently introduced snow leopard permutations, which are the anti-Baxter permutations that are compatible with the doubly alternating Baxter permutations. Among other things, they showed that these permutations preserve parity, and that the number of snow leopard permutations of length $2n-1$ is the Catalan number $C_n$. In this paper we investigate the permutations that the snow leopard permutations induce on their even and odd entries; we call these the even threads and the odd threads, respectively. We give recursive bijections between these permutations and certain families of Catalan paths. We characterize the odd (resp. even) threads which form the other half of a snow leopard permutation whose even (resp. odd) thread is layered in terms of pattern avoidance, and we give a constructive bijection between the set of permutations of length $n$ which are both even threads and odd threads and the set of peakless Motzkin paths of length $n+1$., Comment: 25 pages, 6 figures. Version 3 is modified to use standard Discrete Mathematics and Theoretical Computer Science but is otherwise unchanged