Bijections on two variations of noncrossing partitions

We find bijections on 2-distant noncrossing partitions, 12312-avoiding partitions, 3-Motzkin paths, UH-free Schröder paths and Schröder paths without peaks at even height. We also give a direct bijection between 2-distant noncrossing partitions and 12312-avoiding partitions.     

A bijection between ordered trees and 2-Motzkin paths and its many consequences

A new bijection between ordered trees and 2-Motzkin paths is presented, together with its numerous consequences regarding ordered trees as well as other combinatorial structures such as Dyck paths, bushes, {0,1,2}-trees, Schröder paths, RNA secondary structures, noncrossing partitions, Fine paths, and Davenport-Schinzel sequences.RésuméUne nouvelle bijection entre arbres ordonnés et chemins de Motzkin bicolorés est présentée, avec ses nombreuses conséquences en ce qui concerne les arbres ordonnés ainsi que d'autres structures combinatoires telles que chemins de Dyck, buissons, arbres de type {0,1,2}, chemins de Schröder, structures secondaires de type RNA, partitions non croisées, chemins de Fine, et enfin suites de Davenport-Schinzel.     

The limiting case of Haglund's (q,t)-Schröder theorem and an involution formula

As a generalization of Haglund's statistic on Dyck paths [Conjectured statistics for the q,t-Catalan numbers, Adv. Math. 175 (2) (2003) 319–334; A positivity result in the theory of Macdonald polynomials, Proc. Nat. Acad. Sci. 98 (2001) 4313–4316], Egge et al. introduced the (q,t)-Schröder polynomial S_n,d(q,t), which evaluates to the Schröder number when q=t=1 [A Schröder generalization of Haglund's statistic on Catalan paths, Electron. J. Combin. 10 (2003) 21pp (Research Paper 16, electronic)]. In their paper, S_n,d(q,t) was conjectured to be equal to the coefficient of a hook shape on the Schur function expansion of the symmetric function e_n, which Haiman [Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, Invent. Math. 149 (2002) 371–407] has shown to have a representation-theoretic interpretation. This conjecture was recently proved by Haglund [A proof of the q,t-Schröder conjecture, Internat. Math. Res. Not. (11) (2004) 525–560]. However, because that proof makes heavy use of symmetric function identities and plethystic machinery, the combinatorics behind it is not understood. Therefore, it is worthwhile to study it combinatorially. This paper investigates the limiting case of the (q,t)-Schröder Theorem and obtains interesting results by looking at some special cases.     

A note on 2-distant noncrossing partitions and weighted Motzkin paths

We prove a conjecture of Drake and Kim: the number of 2-distant noncrossing partitions of {1,2,…,n} is equal to the sum of weights of Motzkin paths of length n, where the weight of a Motzkin path is a product of certain fractions involving Fibonacci numbers. We provide two proofs of their conjecture: one uses continued fractions and the other is combinatorial.     

Chain enumeration of k-divisible noncrossing partitions of classical types

We give combinatorial proofs of the formulas for the number of multichains in the k-divisible noncrossing partitions of classical types with certain conditions on the rank and the block size due to Krattenthaler and Müller. We also prove Armstrong's conjecture on the zeta polynomial of the poset of k-divisible noncrossing partitions of type A invariant under a 180° rotation in the cyclic representation.     

Pairs of noncrossing free Dyck paths and noncrossing partitions

Using the bijection between partitions and vacillating tableaux, we establish a correspondence between pairs of noncrossing free Dyck paths of length 2n and noncrossing partitions of [2n+1] with n+1 blocks. In terms of the number of up steps at odd positions, we find a characterization of Dyck paths constructed from pairs of noncrossing free Dyck paths by using the Labelle merging algorithm.     

Some identities on the Catalan, Motzkin and Schröder numbers

In this paper, some identities between the Catalan, Motzkin and Schröder numbers are obtained by using the Riordan group. We also present two combinatorial proofs for an identity related to the Catalan numbers with the Motzkin numbers and an identity related to the Schröder numbers with the Motzkin numbers, respectively.     

Hom-configurations and noncrossing partitions

We study maximal Hom-free sets in the τ[2]-orbit category C(Q) of the bounded derived category for the path algebra associated to a Dynkin quiver Q, where τ denotes the Auslander–Reiten translation and [2] denotes the square of the shift functor. We prove that these sets are in bijection with periodic combinatorial configurations, as introduced by Riedtmann, certain Hom _≤0-configurations, studied by Buan, Reiten and Thomas, and noncrossing partitions of the Coxeter group associated to Q which are not contained in any proper standard parabolic subgroup. Note that Reading has proved that these noncrossing partitions are in bijection with positive clusters in the associated cluster algebra. Finally, we give a definition of mutation of maximal Hom-free sets in C(Q)\mathcal {C}(Q) and prove that the graph of these mutations is connected.     

A Distributive Lattice Structure Connecting Dyck Paths,Noncrossing Partitions and 312-avoiding Permutations

In [Ferrari, L. and Pinzani, R.: Lattices of lattice paths. J. Stat. Plan. Inference 135 (2005), 77–92] a natural order on Dyck paths of any fixed length inducing a distributive lattice structure is defined. We transfer this order to noncrossing partitions along a well-known bijection [Simion, R.: Noncrossing partitions. Discrete Math. 217 (2000), 367–409], thus showing that noncrossing partitions can be endowed with a distributive lattice structure having some combinatorial relevance. Finally we prove that our lattices are isomorphic to the posets of 312-avoiding permutations with the order induced by the strong Bruhat order of the symmetric group.     

Restricted partitions and q-Pell numbers

In this paper, we provide new combinatorial interpretations for the Pell numbers p _n in terms of finite set partitions. In particular, we identify six classes of partitions of size n, each avoiding a set of three classical patterns of length four, all of which have cardinality given by p _n . By restricting the statistic recording the number of inversions to one of these classes, and taking it jointly with the statistic recording the number of blocks, we obtain a new polynomial generalization of p _n . Similar considerations using the comajor index statistic yields a further generalization of the q-Pell number studied by Santos and Sills.     

Universal cycles of -partitions of an -set

In 1992 Chung, Diaconis and Graham generalized de Bruijn cycles to other combinatorial families with universal cycles. Universal cycles have been investigated for permutations, partitions, k-partitions and k-subsets. In 1990 Hurlbert proved that there exists at least one Ucycle of n−1-partitions of an n-set when n is odd and conjectured that when n is even, they do not exist. Herein we prove Hurlbert’s conjecture by establishing algebraic necessary and sufficient conditions for the existence of these Ucycles. We enumerate all such Ucycles for n≤13 and give a lower bound on the total number for all n. Additionally we give ranking and unranking formulae. Finally we discuss the structures of the various solutions.     

Counting partitions on the abacus

In 2003, Maróti showed that one could use the machinery of ℓ-cores and ℓ-quotients of partitions to establish lower bounds for p(n), the number of partitions of n. In this paper we explore these ideas in the case ℓ=2, using them to give a largely combinatorial proof of an effective upper bound on p(n), and to prove asymptotic formulae for the number of self-conjugate partitions, and the number of partitions with distinct parts. In a further application we give a combinatorial proof of an identity originally due to Gauss. Dedicated to the memory of Dr. Manfred Schocker (1970–2006)     

Analytic proof of the partition identity A 5,3,3(n)=B 5,3,3 0 (n)

In this paper we give an analytic proof of the identity A _5,3,3(n)=B _5,3,3⁰(n), where A _5,3,3(n) counts the number of partitions of n subject to certain restrictions on their parts, and B _5,3,3⁰(n) counts the number of partitions of n subject to certain other restrictions on their parts, both too long to be stated in the abstract. Our proof establishes actually a refinement of that partition identity. The original identity was first discovered by the first author jointly with M. Ruby Salestina and S.R. Sudarshan in [Proceedings of the International Conference on Analytic Number Theory with Special Emphasis on L-functions, Ramanujan Math. Soc., Mysore, 2005, pp. 57–70], where it was also given a combinatorial proof, thus answering a question of Andrews. Research partially supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe.”     

Total variation asymptotics for independent process approximations of logarithmic multisets and selections

Many natural unlabeled combinatorial structures, such as random partitions of the integer n, or random monic polynomials over a finite field of degree n, or unlabeled mapping patterns on n points may be described as multisets. In the usual statistical language, a multiset is an unordered sample in which number of items is variable, but the sum is a fixed value n. For these structures, the process counting the number of components of various sizes is equal in distribution to a process of independent, but not identically distributed random variables, conditioned on the value of a weighted sum. By restricting to the first b coordinates, it is possible to compare the combinatorial process directly to the independent process, and to estimate the total variation distance d_b(n) between these distributions. For a broad class of examples similar to the Ewens sampling formula we give asymptotics for d_b(n) which are valid for b=o(n/log n). The polynomial and random mapping pattern examples are covered by this result, but not the example of partitions. Similar results for selections, which are multisets with no repeated parts, such as square free polynomials, are also derived. The proofs of these results use large deviations bounds and singularity analysis of generating functions. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 51–80, 1997     

The Fine numbers refined

We give a short combinatorial proof of a Fine number generating function identity and then explore some of the ramifications in terms of random walks, friendly walkers, and ordered trees. The results are also generalized to obtain similar results including those in Motzkin and Schröder settings.     

Some combinatorial interpretations ofq-analogs of Schröder numbers

We introduce two definitions of Schröder numberq-analogs and show some combinatorial interpretations of theseq-numbers. We use the following combinatorial objects for these interpretations: Schröder paths, 1-colored parallelogram polyominoes and permutations with forbidden subsequences (4231, 4132). We enumerate these objects according to various parameters by means of a recentq-counting technique. We prove that the firstq-Schröder number enumerates of Schröder paths with respect to area and the number of permutation inversions, while the second one counts the 1-colored parallelogram polyominoes according to their width and area. Finally, we illustrate some relations among the parameters characterizing the combinatorial objects.     

Ramsey-Type Results for Geometric Graphs, II

We show that for any two-coloring of the segments determined by n points in the plane, one of the color classes contains noncrossing cycles of lengths . This result is tight up to a multiplicative constant. Under the same assumptions, we also prove that there is a noncrossing path of length Ω(n ^2/3 ) , all of whose edges are of the same color. In the special case when the n points are in convex position, we find longer monochromatic noncrossing paths, of length . This bound cannot be improved. We also discuss some related problems and generalizations. In particular, we give sharp estimates for the largest number of disjoint monochromatic triangles that can always be selected from our segments. Received March 25, 1997, and in revised form March 5, 1998.     

Gray Codes,Loopless Algorithm and Partitions

The generation of efficient Gray codes and combinatorial algorithms that list all the members of a combinatorial object has received a lot of attention in the last few years. Knuth gave a code for the set of all partitions of [n] = {1,2,...,n}. Ruskey presented a modified version of Knuth’s algorithm with distance 2. Ehrlich introduced a looplees algorithm for the set of the partitions of [n]; Ruskey and Savage generalized Ehrlich’s results and introduced two Gray codes for the set of partitions of [n]. In this paper, we give another combinatorial Gray code for the set of the partitions of [n] which differs from the aforementioned Gray codes. Also, we construct a different loopless algorithm for generating the set of all partitions of [n] which gives a constant time between successive partitions in the construction process.      

Dissecting the Stanley partition function

Let p(n) denote the number of unrestricted partitions of n. For i=0, 2, let p_i(n) denote the number of partitions π of n such that . Here denotes the number of odd parts of the partition π and π^′ is the conjugate of π. Stanley [Amer. Math. Monthly 109 (2002) 760; Adv. Appl. Math., to appear] derived an infinite product representation for the generating function of p₀(n)-p₂(n). Recently, Swisher [The Andrews–Stanley partition function and p(n), preprint, submitted for publication] employed the circle method to show that

(i)

and that for sufficiently large n

(ii)

In this paper we study the even/odd dissection of the Stanley product, and show how to use it to prove (i) and (ii) with no restriction on n. Moreover, we establish the following new result:

Two proofs of this surprising inequality are given. The first one uses the Göllnitz–Gordon partition theorem. The second one is an immediate corollary of a new partition inequality, which we prove in a combinatorial manner. Our methods are elementary. We use only Jacobi's triple product identity and some naive upper bound estimates.