We revisit staircases for words and prove several exact as well as asymptotic results for longest left-most staircase subsequences and subwords and staircase separation number. The latter is defined as the number of consecutive maximal staircase subwords packed in a word. We study asymptotic properties of the sequence (), the number of -array words with separations over alphabet [] and show that for any ≥ 0, the growth sequence ( ,()) converges to a characterized limit, independent of . In addition, we study the asymptotic behavior of the random variable , the number of staircase separations in a random word in [] and obtain several limit theorems for the distribution of , including a law of large numbers, a central limit theorem, and the exact growth rate of the entropy of . Finally, we obtain similar results, including growth limits, for longest -staircase subwords and subsequences.

We study the joint distribution of the input sum and the output sum of a deterministic transducer. Here, the input of this finite-state machine is a uniformly distributed random sequence. We give a simple combinatorial characterization of transducers for which the output sum has bounded variance, and we also provide algebraic and combinatorial characterizations of transducers for which the covariance of input and output sum is bounded, so that the two are asymptotically independent. Our results are illustrated by several examples, such as transducers that count specific blocks in the binary expansion, the transducer that computes the Gray code, or the transducer that computes the Hamming weight of the width-[Formula: see text] non-adjacent form digit expansion. The latter two turn out to be examples of asymptotic independence.

Let [Formula: see text] be a Krull monoid with finite class group [Formula: see text] such that every class contains a prime divisor and let [Formula: see text] be the Davenport constant of [Formula: see text]. Then a product of two atoms of [Formula: see text] can be written as a product of at most [Formula: see text] atoms. We study this extremal case and consider the set [Formula: see text] defined as the set of all [Formula: see text] with the following property: there are two atoms [Formula: see text] such that [Formula: see text] can be written as a product of [Formula: see text] atoms as well as a product of [Formula: see text] atoms. If [Formula: see text] is cyclic, then [Formula: see text]. If [Formula: see text] has rank two, then we show that (apart from some exceptional cases) [Formula: see text]. This result is based on the recent characterization of all minimal zero-sum sequences of maximal length over groups of rank two. As a consequence, we are able to show that the arithmetical factorization properties encoded in the sets of lengths of a rank [Formula: see text] prime power order group uniquely characterizes the group.

Embedded trees are labelled rooted trees, where the root has zero label and where the labels of adjacent vertices differ (at most) by [Formula: see text]. Recently it has been proved (see Chassaing and Schaeffer (2004) [8] and Janson and Marckert (2005) [11]) that the distribution of the maximum and minimum labels are closely related to the support of the density of the integrated superbrownian excursion (ISE). The purpose of this paper is to make this probabilistic limiting relation more explicit by using a generating function approach due to Bouttier et al. (2003) [6] that is based on properties of Jacobi's [Formula: see text]-functions. In particular, we derive an integral representation of the joint distribution function of the supremum and infimum of the support of the ISE in terms of the Weierstrass [Formula: see text]-function. Furthermore we re-derive the limiting radius distribution in random quadrangulations (by Chassaing and Schaeffer (2004) [8]) with the help of exact counting generating functions.

Let [Formula: see text] be a finitely generated group, [Formula: see text] a finite set of generators and [Formula: see text] a subgroup of [Formula: see text]. We define what it means for [Formula: see text] to be a context-free pair; when [Formula: see text] is trivial, this specializes to the standard definition of [Formula: see text] to be a context-free group. We derive some basic properties of such group pairs. Context-freeness is independent of the choice of the generating set. It is preserved under finite index modifications of [Formula: see text] and finite index enlargements of [Formula: see text]. If [Formula: see text] is virtually free and [Formula: see text] is finitely generated then [Formula: see text] is context-free. A basic tool is the following: [Formula: see text] is context-free if and only if the Schreier graph of [Formula: see text] with respect to [Formula: see text] is a context-free graph.

Bipartitional relations were introduced by Foata and Zeilberger in their characterization of relations which give rise to equidistribution of the associated inversion statistic and major index. We consider the natural partial order on bipartitional relations given by inclusion. We show that, with respect to this partial order, the bipartitional relations on a set of size [Formula: see text] form a graded lattice of rank [Formula: see text]. Moreover, we prove that the order complex of this lattice is homotopy equivalent to a sphere of dimension [Formula: see text]. Each proper interval in this lattice has either a contractible order complex, or is isomorphic to the direct product of Boolean lattices and smaller lattices of bipartitional relations. As a consequence, we obtain that the Möbius function of every interval is 0, 1, or -1. The main tool in the proofs is discrete Morse theory as developed by Forman, and an application of this theory to order complexes of graded posets, designed by Babson and Hersh, in the extended form of Hersh and Welker.

We study , which are generated by letting [Formula: see text] players draw numbers and assuming that player [Formula: see text] draws [Formula: see text] times from the unit interval and records her largest value. This model is natural in the context of partitions: the score of the [Formula: see text]th player corresponds to the multiplicity of the summand [Formula: see text] in a random partition, with the roles of minimum and maximum interchanged. We study the distribution of several parameters, namely the position of player [Formula: see text], the number of inversions, and the number of ascents. To perform some of the heavy computations, we use the computer algebra package Sigma.

An old conjecture of Graham stated that if [Formula: see text] is a prime and [Formula: see text] is a sequence of [Formula: see text] terms from the cyclic group [Formula: see text] such that all (nontrivial) zero-sum subsequences have the same length, then [Formula: see text] must contain at most two distinct terms. In 1976, Erdős and Szemerédi gave a proof of the conjecture for sufficiently large primes [Formula: see text]. However, the proof was complicated enough that the details for small primes were never worked out. Both in the paper of Erdős and Szemerédi and in a later survey by Erdős and Graham, the complexity of the proof was lamented. Recently, a new proof, valid even for non-primes [Formula: see text], was given by Gao, Hamidoune and Wang, using Savchev and Chen's recently proved structure theorem for zero-sum free sequences of long length in [Formula: see text]. However, as this is a fairly involved result, they did not believe it to be the simple proof sought by Erdős, Graham and Szemerédi. In this paper, we give a short proof of the original conjecture that uses only the Cauchy-Davenport Theorem and pigeonhole principle, thus perhaps qualifying as a simple proof. Replacing the use of the Cauchy-Davenport Theorem with the Devos-Goddyn-Mohar Theorem, we obtain an alternate proof, albeit not as simple, of the non-prime case. Additionally, our method yields an exhaustive list detailing the precise structure of [Formula: see text] and works for an arbitrary finite abelian group, though the only non-cyclic group for which the hypotheses are non-void is [Formula: see text].

In this paper we consider the question of the existence of Hamiltonian circuits in the tope graphs of central arrangements of hyperplanes. Some of the results describe connections between the existence of Hamiltonian circuits in the arrangement and the odd-even invariant of the arrangement. In conjunction with this, we present some results concerning bounds on the odd-even invariant. The results given here can be formulated more generally for oriented matroids and are still valid in that setting.