Let P be a polygon whose vertices have been colored (labeled) cyclically with the numbers 1,2,...,c. Motivated by conjectures of Propp, we are led to consider partitions of P into k-gons which are proper in the sense that each k-gon contains all c colors on its vertices. Counting the number of proper partitions involves a generalization of the k-Catalan numbers. We also show that in certain cases, any proper partition can be obtained from another by a sequence of moves called flips.
Consider lattice paths in Z2 taking unit steps north (N) and east (E). Fix positive integers r,s and put an equivalence relation on points of Z2 by letting v,w be equivalent if v - w = m (r,s) for some m in Z. Call a lattice path valid if whenever it enters a point v with an E-step, then any further points of the path in the class of v are also entered with an E-step. Loehr and Warrington conjectured that the number of valid paths from (0,0) to (nr,ns) is (r+s choose r)n. We prove this conjecture when s = 2.
Let F be a field and let G be a finite graph with a total ordering on its edge set. Richard Stanley noted that the Stanley-Reisner ring F(G) of the broken circuit complex of G is Cohen-Macaulay. Jason Brown gave an explicit description of a homogeneous system of parameters for F(G) in terms of fundamental cocircuits in G. So F(G) modulo this hsop is a finite dimensional vector space. We conjecture an explicit monomial basis for this vector space in terms of the circuits of G and prove that the conjecture is true for two infinite families of graphs. We also explore an application of these ideas to bounding the number of acyclic orientations of G from above.
In a monotonic sequence game, two players alternately choose elements of a sequence from some fixed ordered set. The game ends when the resulting sequence contains either an ascending subsequence of length a or a descending one of length d. We investigate the behaviour of this game when played on finite linear orders or Q and provide some general observations for play on arbitrary ordered sets.
The study of patterns in permutations in a very active area of current research. Klazar defined and studied an analogous notion of pattern for set partitions. We continue this work, finding exact formulas for the number of set partitions which avoid certain specific patterns. In particular, we enumerate and characterize those partitions avoiding any partition of a 3-element set. This allows us to conclude that the corresponding sequences are P-recursive. Finally, we define a second notion of pattern in a set partition, based on its restricted growth function. Related results are obtained for this new definition.
Let ck,l(n) be the number of compositions (ordered partitions) of the integer n whose Ferrers diagram fits inside a k-by-l rectangle. The purpose of this note is to give a simple, algebraic proof of a conjecture of Vatter that the sequence ck,l(0),ck,l(1),...,ck,l(kl) is unimodal. The problem of giving a combinatorial proof of this fact is discussed, but is still open.
We consider the set partition statistics ls and rb introduced by Wachs and White and investigate their distribution over set partitions avoiding certain patterns. In particular, we consider those set partitions avoiding the pattern 13/2, Πn(13/2), and those avoiding both 13/2 and 123, Πn(13/2,123). We show that the distribution over Πn(13/2) enumerates certain integer partitions, and the distribution over Πn(13/2,123) gives q-Fibonacci numbers. These q-Fibonacci numbers are closely related to q-Fibonacci numbers studied by Carlitz and by Cigler. We provide combinatorial proofs that these q-Fibonacci numbers satisfy q-analogues of many Fibonacci identities. Finally, we indicate how p,q-Fibonacci numbers arising from the bistatistic (ls, rb) give rise to p,q-analogues of identities.
Recently, Han discovered two formulas involving binary trees which have the interesting property that hooklengths appear as exponents. The purpose of this note is to give a probabilistic proof of one of Han's formulas. Yang has generalized Han's results to ordered trees. We show how the probabilistic approach can also be used in Yang's setting, as well as for a generalization of Han's formula in terms of certain infinite trees.
Let P be a partially ordered set and consider the free monoid P* of all words over P. If w and w' are in P* then w' is a factor of w if there are words u and v with w = uw'v. Define generalized factor order on P* by letting u ≤ w if there is a factor w' of w having the same length as u such that u ≤ w', where the comparison of u and w' is done componentwise using the partial order in P. One obtains ordinary factor order by insisting that u=w' or, equivalently, by taking P to be an antichain.
Given u in P*, we prove that the language {w : w ≥ u} is accepted by a finite state automaton. If P is finite then it follows that the generating function F(u) = ∑w ≥ u w is rational. This is an analogue of a theorem of Bj\"orner and Sagan for generalized subword order.
We consider the case when P is the positive integers with the usual total order, so that P* is the set of compositions. In this case one obtains a weight generating function F(u;t,x) by substituting t x^n each time the positive integer n appears in F(u). We show that this generating function is also rational by using the transfer-matrix method. Words u and v are said to be Wilf equivalent if F(u;t,x) = F(v;t,x) and we prove various Wilf equivalences combinatorially.
Bj\"orner found a recursive formula for the M\"obius function of ordinary factor order on P*. It follows that one always has μ(u,w) = 0, 1, -1. Using the Pumping Lemma we show that the generating function M(u) = ∑w ≥ u |μ(u,w)| w can be irrational.