A Tableau Formula of Double Grothendieck Polynomials for 321-Avoiding Permutations

Annals of Combinatorics - In this article, we prove a tableau formula for the double Grothendieck polynomials associated to 321-avoiding permutations. The proof is based on the compatibility of the...     

Combinatorial proof of the inversion formula on the Kazhdan–Lusztig R-polynomials

In this paper, we present a combinatorial proof of the inversion formula on the Kazhdan–Lusztig \(R\) -polynomials. This problem was raised by Brenti. As a consequence, we obtain a combinatorial interpretation of the equidistribution property due to Verma stating that any nontrivial interval of a Coxeter group in the Bruhat order has as many elements of even length as elements of odd length. The same argument leads to a combinatorial proof of an extension of Verma’s equidistribution to the parabolic quotients of a Coxeter group obtained by Deodhar. As another application, we derive a refinement of the inversion formula for the symmetric group by restricting the summation to permutations ending with a given element.     

Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three

We consider the problem of enumerating the permutations containing exactly k occurrences of a pattern of length 3. This enumeration has received a lot of interest recently, and there are a lot of known results. This paper presents an alternative approach to the problem, which yields a proof for a formula which so far only was conjectured (by Noonan and Zeilberger). This approach is based on bijections from permutations to certain lattice paths with “jumps,” which were first considered by Krattenthaler.     

A combinatorial proof of a result of Gessel and Greene

A combinatorial proof is given of a result of Gessel and Greene relating the sizes of two classes of permutations. A natural map from one class to the other is described in terms of a shared recursive structure.     

Permutations and riemann surfaces

Another combinatorial proof of a theorem of Ree's on permutations is offered. This proof makes use of the notion of the genus of pair of permutations.     

On a theorem of Rimhak Ree about permutations

A simple graph-theoretic proof is given for a theorem about permutations which was obtained by R. Ree with the aid of Riemann surfaces. With an additional hypothesis, we also improve Ree's inequality.     

Cyclic subsemigroups of symmetric inverse semigroups

A generalization of the cycle notation for permutations is introduced for partial one-one transformations (charts). Notational representation theorems for charts that generalize those of permutations are given. Notational multiplication of charts is developed and then applied to yield a transparent proof of Frobenius' result which bounds the idempotent in the cyclic subsemigroup. Lastly, the well known result that the structure of the cyclic subgroups of the finite symmetric groups is determined from combinations of disjoint cycles is generalized to the cyclic subsemigroups of the finite symmetric inverse semigroups.     

一个易错概率题的分析及发现

分堆问题是排列组合中常遇到的难题之一.通过一个易错概率题的分析,推广了分堆问题,定义相同结构,并对相同结构下的排列组合进行研究,给出了相同结构下的计算公式,并利用离散型随机变量的性质加以验证.此外,还发现了一个符号运算的恒等式,并进行了证明.     

Baxter permutations

Chung et al. (1978) have proved that the number of Baxter permutations on [n] is

Viennot (1981) has then given a combinatorial proof of this formula, showing this sum corresponds to the distribution of these permutations according to their number of rises.

Cori et al. (1986), by making a correspondence between two families of planar maps, have shown that the number of alternating Baxter permutations on [2n+δ] is c_n+δc_n where c_n = (2n)!/(n + 1)!n! is the nth Catalan number.

In this paper, we establish a new one-to-one correspondence between Baxter permutations and three non-intersecting paths, which unifies Viennot (1981) and Cori et al. (1986). Moreover, we obtain more precise results for the enumeration of (alternating or not) Baxter permutations according to various parameters. So, we give a combinatorial interpretation of Mallows's formula (1979).     

Teaching about combinations without permutations

In an elementary statistics course, the topic of combinations may be desired for computing the binomial probabilities, but the topic of permutations may be unnecessary. It is possible to explain combinations thoroughly without discussing permutations. The formula for the binomial coefficient is proved for successively larger samples by augmenting the samples of a given size, using the induction principle. For small sample sizes, it is easy to avoid mentioning factorials.     

A characterization of permutations via skew-hooks

A characterization of permutations is given using skew-hooks, such that the r-descents of the permutation are reflected in the structure of the skew-hook. The characterization yields a combinatorial proof of Foulkes' skew-hook rule for computing Eulerian numbers.     

Signed excedance enumeration via determinants

We show a simple connection between determinants and signed-excedance enumeration of permutations. This gives us an alternate proof of a result of Mantaci about enumerating signed excedances in permutations. The connection also gives an alternate proof of a result of Mantaci and Rakotondrajao about enumerating signed excedances over derangements.Motivated by this connection, we define several excedance-like statistics on permutations and show interesting values for their signed enumerator. In some cases, we also obtain the signed excedance-like statistic enumerator with respect to positive integral weights.     

On the Numbers of Orbits of Permutations under an Operator Related to Eulerian Numbers

In two previous papers an operator on permutations was introduced and its applications to Eulerian numbers were discussed by means of periods and orbits under the operator. In this paper, observing particular subsequences of permutations, an explicit formula for the number of orbits is given for each period. Several identities concerning the number of orbits and its related numbers are also derived.AMS Subject Classification: 05A05, 05A10.     

Riffle shuffles,cycles, and descents

We derive closed form expressions and limiting formulae for a variety of functions of a permutation resulting from repeated riffle shuffles. The results allow new formulae and approximations for the number of permutations inS _n with given cycle type and number of descents. The theorems are derived from a bijection discovered by Gessel. A self-contained proof of Gessel's result is given.     

Permutations, parenthesis words, and Schröder numbers

A different proof for the following result due to West is given: the Schröder number s[inn−1] equals the number of permutations on [1,2,] …, nþat avoid the pattern (3,1,4,2) and its dual (2,4,1,3).     

Hypermaps versus bipartite maps

A hypermap was defined by R. Cori to be a pair of permutations σ and α on a finite set B, such that the group generated by σ and α is transitive on B. The genus of a hypermap was defined according to a formula of A. Jacques for the genus of a pair of permutations. This paper presents a one-to-one correspondence between the set of hypermaps of a given genus and the set of 2-colored bipartite maps of the same genus.     

Indecomposable permutations, hypermaps and labeled Dyck paths

Hypermaps were introduced as an algebraic tool for the representation of embeddings of graphs on an orientable surface. Recently a bijection was given between hypermaps and indecomposable permutations; this sheds new light on the subject by connecting a hypermap to a simpler object. In this paper, a bijection between indecomposable permutations and labeled Dyck paths is proposed, from which a few enumerative results concerning hypermaps and maps follow. We obtain for instance an inductive formula for the number of hypermaps with n darts, p vertices and q hyperedges; the latter is also the number of indecomposable permutations of Sn with p cycles and q left-to-right maxima. The distribution of these parameters among all permutations is also considered.     

An integral characterization of random permutations. A point process approach

We consider random finite permutations and prove the following version of Thoma’s theorem in [8]: Random finite permutations which are class functions satisfy a new integration by parts formula if and only if they are given by a certain Ewens-Sütö process. The main source of inspiration for the results in this note is the fundamental work of Andras Sütö [7], from which some results are reestablished here again in the present point process approach.     

Separable d-Permutations and Guillotine Partitions

We characterize separable multidimensional permutations in terms of forbidden patterns and enumerate them by means of generating function, recursive formula, and explicit formula. We find a connection between multidimensional permutations and guillotine partitions of a box. In particular, a bijection between separable d-dimensional permutations and guillotine partitions of a 2 ^d-1-dimensional box is constructed. We also study enumerating problems related to guillotine partitions under certain restrictions revealing connections to other combinatorial structures. This allows us to obtain several results on patterns in permutations.     

Pattern Avoidance in Multiset Permutations: Bijective Proof

It is well-known that the number of permutations of n letters that avoid a pattern τ of 3 letters is independent of τ. In this note we provide bijective proof that the same result holds for permutations of a multiset. Received August 16, 2006