Permutations avoiding consecutive patterns, II

The generating power series for the number of permutations avoiding particular consecutive patterns are derived in a new and simple fashion.Received: 24 March 2004; revised: 28 July 2004     

Restricted 123-avoiding Baxter permutations and the Padovan numbers

Baxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.     

Generalized harmonic numbers with Riordan arrays

By observing that the infinite triangle obtained from some generalized harmonic numbers follows a Riordan array, we obtain very simple connections between the Stirling numbers of both kinds and other generalized harmonic numbers. Further, we suggest that Riordan arrays associated with such generalized harmonic numbers allow us to find new generating functions of many combinatorial sums and many generalized harmonic number identities.     

Restricted even permutations and Chebyshev polynomials

We study generating functions for the number of even (odd) permutations on n letters avoiding 132 and an arbitrary permutation τ on k letters, or containing τ exactly once. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.     

Balanced minimum covers of a finite set

In this paper a method of enumeration for n-balanced, labelled, minimum covers of a finite set of m indistinguishable elements is developed. The method is then used to tabulate the number of such covers for small values of m and n by means of a generating function.     

Eulerian quasisymmetric functions

We introduce a family of quasisymmetric functions called Eulerian quasisymmetric functions, which specialize to enumerators for the joint distribution of the permutation statistics, major index and excedance number on permutations of fixed cycle type. This family is analogous to a family of quasisymmetric functions that Gessel and Reutenauer used to study the joint distribution of major index and descent number on permutations of fixed cycle type. Our central result is a formula for the generating function for the Eulerian quasisymmetric functions, which specializes to a new and surprising q-analog of a classical formula of Euler for the exponential generating function of the Eulerian polynomials. This q-analog computes the joint distribution of excedance number and major index, the only of the four important Euler-Mahonian distributions that had not yet been computed. Our study of the Eulerian quasisymmetric functions also yields results that include the descent statistic and refine results of Gessel and Reutenauer. We also obtain q-analogs, (q,p)-analogs and quasisymmetric function analogs of classical results on the symmetry and unimodality of the Eulerian polynomials. Our Eulerian quasisymmetric functions refine symmetric functions that have occurred in various representation theoretic and enumerative contexts including MacMahon's study of multiset derangements, work of Procesi and Stanley on toric varieties of Coxeter complexes, Stanley's work on chromatic symmetric functions, and the work of the authors on the homology of a certain poset introduced by Björner and Welker.     

Counting strings in Dyck paths

This paper deals with the enumeration of Dyck paths according to the statistic “number of occurrences of τ”, for an arbitrary string τ. In this direction, the statistic “number of occurrences of τ at height j” is considered. It is shown that the corresponding generating function can be evaluated with the aid of Chebyshev polynomials of the second kind. This is applied to every string of length 4. Further results are obtained for the statistic “number of occurrences of τ at even (or odd) height”.     

On the connectivity of randomm-orientable graphs and digraphs

We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex. We analyse their almost certain connectivity and apply these results to the expected value of random minimum length spanning trees and arborescences. We also examine the relationship between our results and certain results of Erdős and Rényi.     

Counting involutory, unimodal, and alternating signed permutations

In this work we count the number of involutory, unimodal, and alternating elements of the group of signed permutations B_n, and the group of even-signed permutations D_n. Recurrence relations, generating functions, and explicit formulas of the enumerating sequences are given.     

Kernel method and linear recurrence system

Based on the kernel method, we present systematic methods to solve equation systems on generating functions of two variables. Using these methods, we get the generating functions for the number of permutations which avoid 1234 and 12k(k-1)…3$12k(k-1)\dots 3$ and permutations which avoid 1243 and 12…k$12\dots k$.     

Inversion relations, reciprocity and polyominoes

We derive self-reciprocity properties for a number of polyomino generating functions, including several families of column-convex polygons, three-choice polygons, and staircase polygons with a staircase hole. In so doing, we establish a connection between the reciprocity results known to combinatorialists and the inversion relations used by physicists to solve models in statistical mechanics. For several classes of convex polygons, the inversion (reciprocity) relation, augmented by certain symmetry and analyticity properties, completely determines the anisotropic perimeter generating function.     

Descents, inversions, and major indices in permutation groups

A multivariate generating function involving the descent, major index, and inversion statistic first given by Ira Gessel is generalized to other permutation groups. We provide generating functions for variants of these three statistics for the Weyl groups of type B and D, wreath product groups, and multiples of permutations. All of our ideas are combinatorial in nature and exploit fundamental relationships between the elementary and homogeneous symmetric functions.     

Combinatorial parameters in bargraphs

Bargraphs are non-intersecting lattice paths in with 3 allowed types of steps; up (0, 1), down (0, ?1) and horizontal (1, 0). They start at the origin with an up step and terminate immediately upon return to the x-axis. We unify the study of integer compositions (ordered partitions) with that of bargraph lattice paths by obtaining a single generating function for both these structures. We also obtain the asymptotic expected size of the underlying composition associated with an arbitrary bargraph as the semiperimeter tends to infinity (equivalently the expected value for the total area under the bargraph). In addition, the number of descents, the number of up steps and the number of level steps are found together with their asymptotic expressions for large semiperimeter.     

Restricted colored permutations and Chebyshev polynomials

Several authors have examined connections between restricted permutations and Chebyshev polynomials of the second kind. In this paper we prove analogues of these results for colored permutations. First we define a distinguished set of length two and length three patterns, which contains only 312 when just one color is used. Then we give a recursive procedure for computing the generating function for the colored permutations which avoid this distinguished set and any set of additional patterns, which we use to find a new set of signed permutations counted by the Catalan numbers and a new set of signed permutations counted by the large Schröder numbers. We go on to use this result to compute the generating functions for colored permutations which avoid our distinguished set and any layered permutation with three or fewer layers. We express these generating functions in terms of Chebyshev polynomials of the second kind and we show that they are special cases of generating functions for involutions which avoid 3412 and a layered permutation.     

The butterfly decomposition of plane trees

We introduce the notion of doubly rooted plane trees and give a decomposition of these trees, called the butterfly decomposition, which turns out to have many applications. From the butterfly decomposition we obtain a one-to-one correspondence between doubly rooted plane trees and free Dyck paths, which implies a simple derivation of a relation between the Catalan numbers and the central binomial coefficients. We also establish a one-to-one correspondence between leaf-colored doubly rooted plane trees and free Schröder paths. The classical Chung-Feller theorem as well as some generalizations and variations follow quickly from the butterfly decomposition. We next obtain two involutions on free Dyck paths and free Schröder paths, leading to parity results and combinatorial identities. We also use the butterfly decomposition to give a combinatorial treatment of Klazar's generating function for the number of chains in plane trees. Finally we study the total size of chains in plane trees with n edges and show that the average size of such chains tends asymptotically to (n+9)/6.     

Longest alternating subsequences of k-ary words

Recently, Stanley [Longest alternating subsequences of permutations, preprint, arXiv/0511419v1] studied the length of the longest alternating subsequence of a permutation in the symmetric group, where a sequence a,b,c,d,… is alternating if a>b<c>d<?. In this paper, we extend this result to the case of k-ary words. More precisely, we find an explicit formula for the generating function of the number of k-ary words of length n according to the length of the longest alternating subsequence.     

Enumeration of k-poles

Ak-pole in this paper is a regular planar map withk vertices. Poles with even degrees were first enumerated by Tutte [9] in 1962 where he obtained a very simple and elegant expression. Using Brown's quadratic method, Bender and Canfield [2] derived two algebraic equations for the generating function of the poles. But the equations seem to be quite complicated for the odd degree case, and so far no progress has been seen in utilizing these equations to derive any result for the number of poles with odd degree. In this paper, we use hypergeometric functions to enumerate poles. We will show that the odd degree case is indeed very different from, and much more complicated than, the even degree case. Research supported by NSERC.     

Effective scalar products of D-finite symmetric functions

Many combinatorial generating functions can be expressed as combinations of symmetric functions, or extracted as sub-series and specializations from such combinations. Gessel has outlined a large class of symmetric functions for which the resulting generating functions are D-finite. We extend Gessel's work by providing algorithms that compute differential equations, these generating functions satisfy in the case they are given as a scalar product of symmetric functions in Gessel's class. Examples of applications to k-regular graphs and Young tableaux with repeated entries are given. Asymptotic estimates are a natural application of our method, which we illustrate on the same model of Young tableaux. We also derive a seemingly new formula for the Kronecker product of the sum of Schur functions with itself.     

Eulerian quasisymmetric functions for the type B Coxeter group and other wreath product groups

Eulerian quasisymmetric functions were introduced by Shareshian and Wachs in order to obtain a q-analog of Euler?s exponential generating function formula for the Eulerian numbers (Shareshian and Wachs, 2010 [17]). They are defined via the symmetric group, and applying the stable and nonstable principal specializations yields formulas for joint distributions of permutation statistics. We consider the wreath product of the cyclic group with the symmetric group, also known as the group of colored permutations. We use this group to introduce colored Eulerian quasisymmetric functions, which are a generalization of Eulerian quasisymmetric functions. We derive a formula for the generating function of these colored Eulerian quasisymmetric functions, which reduces to a formula of Shareshian and Wachs for the Eulerian quasisymmetric functions. We show that applying the stable and nonstable principal specializations yields formulas for joint distributions of colored permutation statistics, which generalize the Shareshian–Wachs q-analog of Euler?s formula, formulas of Foata and Han, and a formula of Chow and Gessel.