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.     

Asymptotic behaviour of the containment of certain mesh patterns

We present some results on the proportion of permutations of length n containing certain mesh patterns as n grows large, and give exact enumeration results in some cases. In particular, we focus on mesh patterns where entire rows and columns are shaded. We prove some general results which apply to mesh patterns of any length, and then consider mesh patterns of length four. An important consequence of these results is to show that the proportion of permutations containing a mesh pattern can take a wide range of values between 0 and 1.     

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.     

明安图与Catalan数

中国数学家明安图在其《割圜密率捷法》中最先应用了Catalan数,取得优秀的研究成果.本文简介明安图的计数成就和Catalan数,综述国内外对明安图应用该数的研究.特别地,近两年来英国的Larcombe发表了5篇文章,对明安图的成果——包含Catalan数的sin（2pa）展开式,加以推广,并给出明安图确定Catalan 数的第二种方法的严格代数证明.     

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.     

A brief history of partitions of numbers,partition functions and their modern applications

‘Number rules the universe.’

The Pythagoras     

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.     

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.