New interpretations for noncrossing partitions of classical types

We interpret noncrossing partitions of type B and type D in terms of noncrossing partitions of type A. As an application, we get type-preserving bijections between noncrossing and nonnesting partitions of type B, type C and type D which are different from those in the recent work of Fink and Giraldo. We also define Catalan tableaux of type B and type D, and find bijections between them and noncrossing partitions of type B and type D respectively.     

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.     

Linked partitions and linked cycles

The notion of noncrossing linked partition arose from the study of certain transforms in free probability theory. It is known that the number of noncrossing linked partitions of [n+1] is equal to the n-th large Schröder number r_n, which counts the number of Schröder paths. In this paper we give a bijective proof of this result. Then we introduce the structures of linked partitions and linked cycles. We present various combinatorial properties of noncrossing linked partitions, linked partitions, and linked cycles, and connect them to other combinatorial structures and results, including increasing trees, partial matchings, k-Stirling numbers of the second kind, and the symmetry between crossings and nestings over certain linear graphs.     

Folded bump diagrams for partitions of classical types

We introduce folded bump diagrams for $B_n$, $C_n$ and $D_n$ partitions. They allow us to use the type A methods to handle all other classical types simultaneously. As applications, we give uniform interpretations for two families of bijections between noncrossing and nonnesting partitions, where the first family preserves openers and closers, while the second family preserves the statistics a and μ. Here a is the increasing sequence of the minimal elements of the blocks, and μ is the sizes of these blocks. We also extend the results of Chen, Deng, Du, Stanley and Yan (2007) [5] and Kasraoui and Zeng (2006) [10] concerning the symmetry of partitions of type A to other classical types uniformly.     

Classification of partitions of all triples on ten points into copies of Fano and affine planes

We continue our study of partitions of the full set of triples chosen from a v-set into copies of the Fano plane PG(2,2) (Fano partitions) or copies of the affine plane AG(2,3) (affine partitions) or into copies of both of these planes (mixed partitions). The smallest cases for which such partitions can occur are v=8 where Fano partitions exist, v=9 where affine partitions exist, and v=10 where both affine and mixed partitions exist. The Fano partitions for v=8 and the affine partitions for v=9 and 10 have been fully classified, into 11, two and 77 isomorphism classes, respectively. Here we classify (1) the sets of i pairwise disjoint affine planes for i=1,…,7, and (2) the mixed partitions for v=10 into their 22 isomorphism classes. We consider the ways in which these partitions relate to the large sets of AG(2,3).     

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 congruences for Andrews-Paule’s broken 2-diamond partitions

We prove two conjectures of Andrews and Paule [G.E. Andrews, P. Paule, MacMahon’s partition analysis XI: Broken diamonds and modular forms, Acta Arith. 126 (2007) 281-294] on congruences of broken k-diamond partitions.     

A self-dual poset on objects counted by the Catalan numbers and a type-B analogue

We introduce two partially ordered sets, P_n^A and P_n^B, of the same cardinalities as the type-A and type-B noncrossing partition lattices. The ground sets of P_n^A and P_n^B are subsets of the symmetric and the hyperoctahedral groups, consisting of permutations which avoid certain patterns. The order relation is given by (strict) containment of the descent sets. In each case, by means of an explicit order-preserving bijection, we show that the poset of restricted permutations is an extension of the refinement order on noncrossing partitions. Several structural properties of these permutation posets follow, including self-duality and the strong Sperner property. We also discuss posets Q_n^A and Q_n^B similarly associated with noncrossing partitions, defined by means of the excedance sets of suitable pattern-avoiding subsets of the symmetric and hyperoctahedral groups.     

A skein action of the symmetric group on noncrossing partitions

We introduce and study a new action of the symmetric group \({\mathfrak {S}}_n\) on the vector space spanned by noncrossing partitions of \(\{1, 2,\ldots , n\}\) in which the adjacent transpositions \((i, i+1) \in {\mathfrak {S}}_n\) act on noncrossing partitions by means of skein relations. We characterize the isomorphism type of the resulting module and use it to obtain new representation-theoretic proofs of cyclic sieving results due to Reiner–Stanton–White and Pechenik for the action of rotation on various classes of noncrossing partitions and the action of K-promotion on two-row rectangular increasing tableaux. Our skein relations generalize the Kauffman bracket (or Ptolemy relation) and can be used to resolve any set partition as a linear combination of noncrossing partitions in a \({\mathfrak {S}}_n\)-equivariant way.     

Partitioning Sets of Triples into Small Planes

We study partitions of the set of all ₃ ^v triples chosen from a v-set intopairwise disjoint planes with three points per line. Our partitions may contain copies of PG(2,2) only (Fano partitions) or copies of AG(2, 3) only (affine partitions)or copies of some planes of each type (mixed partitions).We find necessary conditions for Fano or affine partitions to exist. Such partitions are already known in severalcases: Fano partitions for v = 8 and affine partitions for v = 9 or 10. We constructsuch partitions for several sporadic orders, namely, Fano partitions for v = 14, 16, 22, 23, 28, andan affine partition for v = 18. Using these as starter partitions, we prove that Fano partitionsexist for v = 7 ⁿ + 1, 13 ⁿ + 1,27 ⁿ + 1, and affine partitions for v = 8 ⁿ + 1,9 ⁿ + 1, 17 ⁿ + 1. In particular, both Fano and affine partitionsexist for v = 3⁶ⁿ + 1. Using properties of 3-wise balanced designs, weextend these results to show that affine partitions also exist for v = 3²ⁿ .Similarly, mixed partitions are shown to exist for v = 8 ⁿ ,9 ⁿ , 11 ⁿ + 1.     

On the Combinatorics of Lecture Hall Partitions

A lecture hall partition of length n is an integer sequence satisfying Bousquet-Mélou and Eriksson showed that the number of lecture hall partitions of length n of a positive integer N whose alternating sum is k equals the number of partitions of N into k odd parts less than 2n. We prove the fact by a natural combinatorial bijection. This bijection, though defined differently, is essentially the same as one of the bijections found by Bousquet-Mélou and Eriksson.     

On the weighted enumeration of alternating sign matrices and descending plane partitions

We prove a conjecture of Mills, Robbins and Rumsey [Alternating sign matrices and descending plane partitions, J. Combin. Theory Ser. A 34 (3) (1983) 340-359] that, for any n, k, m and p, the number of n×n alternating sign matrices (ASMs) for which the 1 of the first row is in column k+1 and there are exactly m −1?s and m+p inversions is equal to the number of descending plane partitions (DPPs) for which each part is at most n and there are exactly k parts equal to n, m special parts and p nonspecial parts. The proof involves expressing the associated generating functions for ASMs and DPPs with fixed n as determinants of n×n matrices, and using elementary transformations to show that these determinants are equal. The determinants themselves are obtained by standard methods: for ASMs this involves using the Izergin-Korepin formula for the partition function of the six-vertex model with domain-wall boundary conditions, together with a bijection between ASMs and configurations of this model, and for DPPs it involves using the Lindström-Gessel-Viennot theorem, together with a bijection between DPPs and certain sets of nonintersecting lattice paths.     

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.     

Counting Dyck Paths by Area and Rank

The set of Dyck paths of length 2n inherits a lattice structure from a bijection with the set of noncrossing partitions with the usual partial order. In this paper, we study the joint distribution of two statistics for Dyck paths: area (the area under the path) and rank (the rank in the lattice). While area for Dyck paths has been studied, pairing it with this rank function seems new, and we get an interesting (q, t)-refinement of the Catalan numbers. We present two decompositions of the corresponding generating function: One refines an identity of Carlitz and Riordan; the other refines the notion of γ-nonnegativity, and is based on a decomposition of the lattice of noncrossing partitions due to Simion and Ullman. Further, Biane’s correspondence and a result of Stump allow us to conclude that the joint distribution of area and rank for Dyck paths equals the joint distribution of length and reflection length for the permutations lying below the n-cycle (12· · ·n) in the absolute order on the symmetric group.     

Tamari lattices and noncrossing partitions in type B

The usual, or type A_n, Tamari lattice is a partial order on , the triangulations of an (n+3)-gon. We define a partial order on , the set of centrally symmetric triangulations of a (2n+2)-gon. We show that it is a lattice, and that it shares certain other nice properties of the A_n Tamari lattice, and therefore that it deserves to be considered the B_n Tamari lattice. We also define a bijection between and the noncrossing partitions of type B_n defined by Reiner.     

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.     

A theorem on the cores of partitions

If s and t are relatively prime positive integers we show that the s-core of a t-core partition is again a t-core partition. A similar result is proved for bar partitions under the additional assumption that s and t are both odd.     

Shellability of noncrossing partition lattices

We give a case-free proof that the lattice of noncrossing partitions associated to any finite real reflection group is EL-shellable. Shellability of these lattices was open for the groups of type and those of exceptional type and rank at least three.