Identities for non-crossing graphs and multigraphs

We refine an identity between the numbers of certain non-crossing graphs and multigraphs, by modifying a bijection found by P. Podbrdský [A bijective proof of an identity for noncrossing graphs, Discrete Math. 260 (2003) 249-253]. We also prove a new identity between the number of acyclic non-crossing graphs with n vertices and k edges (isolated vertices allowed and no multiple edges allowed), and the number of non-crossing connected graphs with n edges and k vertices (multiple edges allowed and no isolated vertices allowed).     

Some set partition statistics in non-crossing partitions and generating functions

In this paper we shall give the generating functions for the enumeration of non-crossing partitions according to some set partition statistics explicitly, which are based on whether a block is singleton or not and is inner or outer. Using weighted Motzkin paths, we find the continued fraction form of the generating functions. There are bijections between non-crossing partitions, Dyck paths and non-nesting partitions, hence we can find applications in the enumeration of Dyck paths and non-nesting partitions. We shall also study the integral representation of the enumerating polynomials for our statistics. As an application of integral representation, we shall give some remarks on the enumeration of inner singletons in non-crossing partitions, which is equivalent to one of udu's at high level in Dyck paths investigated in [Y. Sun, The statistic “number of udu's” in Dyck paths, Discrete Math. 284 (2004) 177-186].     

Enumeration of non-crossing pairings on bit strings

A non-crossing pairing on a bit string is a matching of 1s and 0s in the string with the property that the pairing diagram has no crossings. For an arbitrary bit-string w=p₁¹q₁⁰…pr¹qr⁰, let φ(w) be the number of such pairings. This enumeration problem arises when calculating moments in the theory of random matrices and free probability, and we are interested in determining useful formulas and asymptotic estimates for φ(w). Our main results include explicit formulas in the “symmetric” case where each pi=qi, as well as upper and lower bounds for φ(w) that are uniform across all words of fixed length and fixed r. In addition, we offer more refined conjectural expressions for the upper bounds. Our proofs follow from the construction of combinatorial mappings from the set of non-crossing pairings into certain generalized “Catalan” structures that include labeled trees and lattice paths.     

A basis for the non-crossing partition lattice top homology

We find a basis for the top homology of the non-crossing partition lattice T _n . Though T _n is not a geometric lattice, we are able to adapt techniques of Björner (A. Björner, On the homology of geometric lattices. Algebra Universalis 14 (1982), no. 1, 107–128) to find a basis with C _n?1 elements that are in bijection with binary trees. Then we analyze the action of the dihedral group on this basis.     

On certain unimodal sequences and strict partitions

Building on a bijection of Vandervelde, we enumerate certain unimodal sequences whose alternating sum equals zero. This enables us to refine the enumeration of strict partitions with respect to the number of parts and the BG-rank.     

Gray codes for non-crossing partitions and dissections of a convex polygon

In this paper we develop Gray codes for two families of geometric objects: non-crossing partitions and dissections of a convex polygon by means of non-crossing diagonals.     

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 bijection between 2-triangulations and pairs of non-crossing Dyck paths

A k-triangulation of a convex polygon is a maximal set of diagonals so that no k+1 of them mutually cross in their interiors. We present a bijection between 2-triangulations of a convex n-gon and pairs of non-crossing Dyck paths of length 2(n−4). This solves the problem of finding a bijective proof of a result of Jonsson for the case k=2. We obtain the bijection by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths.     

The bijection between plane partitions and nonnegative integer matrices

The one-to-one correspondence between the set of plane partitions withr rows andm columns and the set of matrices of nonnegative integers with the same numbers of rows and columns has been constructed. Published in Lietuvos Matematikes Rinkinys, Vol. 35, No. 2, pp. 204–210, April–June, 1995.     

Bijections between t-core partitions and t-tuples

This note introduces some bijections relating core partitions and tuples of integers. We apply these bijections to count the number of cores with various types of restriction, including fixed number of parts, limited size of parts, parts divisible by some integer, and distinct parts. For example, we prove that the number of $2t$-core partitions into $l$ even parts equals the number of $t$-core partitions into $l$ parts. We also generalize one expression for simultaneous cores, which was given by Baek, Nam and Yu, recently. Subsequently, we use this expression to obtain recurrence satisfied by numbers of $(s,s+1,\dots ,s+r)-$core partitions for $s\ge 1$.     

A direct bijection between descending plane partitions with no special parts and permutation matrices

We present a direct bijection between descending plane partitions with no special parts and permutation matrices. This bijection has the desirable property that the number of parts of the descending plane partition corresponds to the inversion number of the permutation. Additionally, the number of maximum parts in the descending plane partition corresponds to the position of the one in the last column of the permutation matrix. We also discuss the possible extension of this approach to finding a bijection between descending plane partitions and alternating sign matrices.     

Partitions of a set satisfying certain set of conditions

In this paper we present a new combinatorial class enumerated by Catalan numbers. More precisely, we establish a bijection between the set of partitions π₁π₂?π_n of [n] such that π_i+1−π_i≤1 for all i=,1,2…,n−1, and the set of Dyck paths of semilength n. Moreover, we find an explicit formula for the generating function for the number of partitions π₁π₂?π_n of [n] such that either π_i+?−π_i≤1 for all i=1,2,…,n−?, or π_i+1−π_i≤m for all i=1,2,…,n−1.     

Nodal domains and spectral minimal partitions

We consider two-dimensional Schrödinger operators in bounded domains. We analyze relations between the nodal domains of eigenfunctions, spectral minimal partitions and spectral properties of the corresponding operator. The main results concern the existence and regularity of the minimal partitions and the characterization of the minimal partitions associated with nodal sets as the nodal domains of Courant-sharp eigenfunctions.     

Enumeration and limit laws of dissections on a cylinder

We compute the generating function for triangulations on a cylinder, with the restriction that all vertices belong to its boundary and that the intersection of a pair of different faces is either empty, a vertex or an edge. We generalize these results to maps with either constant ({k}-dissections) or unrestricted (unrestricted dissections) face degree. We apply singularity analysis to the resulting generating functions to obtain asymptotic estimates for their coefficients, as well as limit distributions for natural parameters.     

On zero-sum partitions and anti-magic trees

We study zero-sum partitions of subsets in abelian groups, and apply the results to the study of anti-magic trees. Extension to the nonabelian case is also given.     

Set partitions and moments of random variables

It is well known that the sequence of Bell numbers (Bn)_n?0 (Bn being the number of partitions of the set [n]) is the sequence of moments of a mean 1 Poisson random variable τ (a fact expressed in the Dobiński formula), and the shifted sequence (Bn+1)_n?0 is the sequence of moments of 1+τ. In this paper, we generalize these results by showing that both and (where is the number of m-partitions of [n], as they are defined in the paper) are moment sequences of certain random variables. Moreover, such sequences also are sequences of falling factorial moments of related random variables. Similar results are obtained when is replaced by the number of ordered m-partitions of [n]. In all cases, the respective random variables are constructed from sequences of independent standard Poisson processes.     

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.     

Sequences of Ordered Sets and Catalan Numbers

We define the down sets (lower covers, respectively) sequence of an ordered set. We show that the number of down set sequences of an n-ordered set is equal to the n-th Catalan Number. We give a characterization of down sets sequences of an ordered set and another characterization of lower covers sequences of an ordered set.     

A simple bijection for enhanced,classical, and 2-distant k-noncrossing partitions

In this note, we give a simple extension map from partitions of subsets of $\left[n\right]$ to partitions of $[n+1]$, which sends $\delta$-distant $k$-crossings to $(\delta +1)$-distant $k$-crossings (and similarly for nestings). This map provides a combinatorial proof of the fact that the numbers of enhanced, classical, and 2-distant $k$-noncrossing partitions are each related to the next via the binomial transform. Our work resolves a recent conjecture of Zhicong Lin and generalizes earlier reduction identities for partitions.