Multiple partitions, lattice paths and a Burge-Bressoud-type correspondence

A bijection is presented between (1): partitions with conditions f_j+f_j+1≤k−1 and f₁≤i−1, where f_j is the frequency of the part j in the partition, and (2): sets of k−1 ordered partitions (n⁽¹⁾,n⁽²⁾,…,n^(k−1)) such that and , where m_j is the number of parts in n^(j). This bijection entails an elementary and constructive proof of the Andrews multiple-sum enumerating partitions with frequency conditions. A very natural relation between the k−1 ordered partitions and restricted paths is also presented, which reveals our bijection to be a modification of Bressoud’s version of the Burge correspondence.     

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.     

Rank partitions and covering numbers under small perturbations of an element

We investigate how the rank partitions and the covering number of the elements can change with arbitrarily small perturbations of a fixed element.     

Lattice paths and the q-ballot polynomials

Two statistics with respect to “upper-corners” and “lower-corners” are introduced for lattice paths. The corresponding refined generating functions are shown to be closely related to the q-ballot polynomials that extend the well-known Narayana polynomials and Catalan numbers.     

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].     

Reconfiguration of subspace partitions

Let $q$ be a fixed prime power and let $V\left(n,q\right)$ denote a vector space of dimension $n$ over the Galois field with $q$ elements. A subspace partition (also called “vector space partition”) of $V\left(n,q\right)$ is a collection of subspaces of $V\left(n,q\right)$ with the property that every nonzero element of $V\left(n,q\right)$ appears in exactly one of these subspaces. Given positive integers $a,b,n$ such that $1\le a<b<n$, we say a subspace partition of $V\left(n,q\right)$ has type $a^x{b}^y$ if it is composed of $x$ subspaces of dimension $a$ and $y$ subspaces of dimension $b$. Let $c=\text{gcd}\left(a,b\right)$. In this paper, we prove that if $b$ divides $n$, then one can (algebraically) construct every possible subspace partition of $V\left(n,q\right)$ of type $a^x{b}^y$ whenever $y\ge \left(q^e?1\right)∕\left(q^b?1\right)$, where $0\le e<ab∕c$ and $n\equiv e\left(\mathrm{mod}ab∕c\right)$. Our construction allows us to sequentially reconfigure batches of $\left(q^a?1\right)∕\left(q^c?1\right)$ subspaces of dimension $b$ into batches of $\left(q^b?1\right)∕\left(q^c?1\right)$ subspaces of dimension $a$. In particular, this accounts for all numerically allowed subspace partition types $a^x{b}^y$ of $V\left(n,q\right)$ under some additional conditions, for example, when $e=b$.     

Rainbow paths

A k-rainbow path in a graph with colored edges is a path of length k where each edge has a different color. In this note, we settle the problem of obtaining a constructive k-coloring of the edges of K_n in which one may find, between any pair of vertices, a large number of internally disjoint k-rainbow paths. In fact, our construction obtains the largest possible number of paths. This problem was considered in a less general setting by Chartrand et al. (2007) [6].     

Lattice paths and generalized cluster complexes

In this paper we propose a variant of the generalized Schröder paths and generalized Delannoy paths by giving a restriction on the positions of certain steps. This generalization turns out to be reasonable, as attested by the connection with the faces of generalized cluster complexes of types A and B. As a result, we derive Krattenthaler's F-triangles for these two types by a combinatorial approach in terms of lattice paths.     

Self-conjugate partitions with the same disparity

We give a bijection between the set of ordinary partitions and that of self-conjugate partitions with some restrictions. Also, we show the relationship between hook lengths of a self-conjugate partition and its corresponding partition via the bijection. As a corollary, we give new combinatorial interpretations for the Catalan number and the Motzkin number in terms of self-conjugate simultaneous core partitions.     

Monochromatic square-cycle and square-path partitions

The square of a path P is the graph obtained from P by joining every pair of vertices with distance 2 in P. We show that in every 2-colored complete graph on sufficiently many vertices the vertex set can be partitioned by at most 65 vertex disjoint monochromatic square-paths.     

Irreducible partitions and the construction of quasi-measures

A quasi-measure is a non-subadditive measure defined on only open or closed subsets of a compact Hausdorf space. We investigate the nature of irreducible partitions as defined by Aarnes and use the results to construct quasi-measures when . The cohomology ring is an important tool for this investigation.

     

Walks and paths in trees

Recently Csikvári [Combinatorica 30(2) 2010, 125–137] proved a conjecture of Nikiforov concerning the number of closed walks on trees. Our aim is to extend this theorem to all walks. In addition, we give a simpler proof of Csikvári's result and answer one of his questions in the negative. Finally we consider an analogous question for paths rather than walks. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Counting humps and peaks in generalized Motzkin paths

Let us call a lattice path in $\mathbb{Z}\times \mathbb{Z}$ from $(0,0)$ to $(n,0)$ using $U=(1,k)$, $D=(1,?1)$, and $H=(a,0)$ steps and never going below the $x$-axis, a $(k,a)$-path (of order $n$). A super   $(k,a)$-path is a $(k,a)$-path which is permitted to go below the $x$-axis. We relate the total number of humps in all of the $(k,a)$-paths of order $n$ to the number of super $(k,a)$-paths, where a hump is defined to be a sequence of steps of the form $U{H}^{i}D$, $i\ge 0$. This generalizes recent results concerning the cases when $k=1$ and $a=1$ or $a=\infty$. A similar relation may be given involving peaks (consecutive steps of the form $UD$).     

Relations between two types of polarized partitions

It is shown that close links exist between two important types of polarized partition relations of higher dimensions. Project supported by a South-South Fellowship of the Third World Academy of Sciences and by the National Natural Science Foundation of China (Grant No. 19671061).     

Random partitions with restricted part sizes

For a subset of positive integers let Ω(n, ) be the set of partitions of n into summands that are elements of . For every λ ∈ Ω(n, ), let M _n(λ) be the number of parts, with multiplicity, that λ has. Put a uniform probability distribution on Ω(n, ), and regard M _n as a random variable. In this paper the limiting density of the (suitably normalized) random variable M _n is determined for sets that are sufficiently regular. In particular, our results cover the case = {Q(k) : k ≥ 1}, where Q(x) is a fixed polynomial of degree d ≥ 2. For specific choices of Q, the limiting density has appeared before in rather different contexts such as Kingman's coalescent, and processes associated with the maxima of Brownian bridge and Brownian meander processes. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On pattern avoiding flattened set partitions

Let Π = B_1/B_2/… /B_k be any set partition of[n]= {1,2,...,n} satisfying that entries are increasing in each block and blocks are arranged in increasing order of their first entries.Then Callan defined the flattened Π to be the permutation of[n]obtained by erasing the divers between its blocks,and Callan also enumerated the number of set partitions of[n]whose flattening avoids a single3-letter pattern.Mansour posed the question of counting set partitions of[n]whose flattening avoids a pattern of length 4.In this paper,we present the number of set partitions of[n]whose flattening avoids one of the patterns:1234,1243,1324,1342,1423,1432,3142 and 4132.     

Exchange relations, Dyck paths and copolymer adsorption

We consider a lattice model of fully directed copolymer adsorption equivalent to the enumeration of vertex-coloured Dyck paths. For two infinite families of periodic colourings we are able to solve the model exactly using a type of symmetry we call an exchange relation. For one of these families we are able to find an asymptotic expression for the location of the critical adsorption point as a function of the period of the colouring. This expression describes the effect of a regular inhomogeneity in the polymer on the adsorption transition.     

Star partitions of graphs

Let G be a graph and n ≥ 2 an integer. We prove that the following are equivalent: (i) there is a partition (V₁,…,V_m) of V (G) such that each V_i induces one of stars K_1,1,…,K_1,n, and (ii) for every subset S of V(G), G\ S has at most n|S| components with the property that each of their blocks is an odd order complete graph. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 185–190, 1997