Search

We study algebras satisfying a two-term multilinear identity, namely one of the form $x_1\cdots x_n=qx_{\sigma(1)}\cdots x_{\sigma(n)}$, where $q$ is a parameter from the base field. We show that such algebras with $q=1$ and $\sigma$ not fixing~1 or~$n$ are eventually commutative in the sense that the equality $x_1\cdots x_k =x_{\tau(1)}\cdots x_{\tau(k)}$ holds for $k$ large enough and all permutations $\tau\in S_k$. Calling the minimal such~$k$ the degree of eventual commutativity, we prove that $k$ is never more than~$2n-3,$ and that this bound is sharp. For various natural examples, we prove that $k$ can be taken to be $n+1$ or $n+2$. In the case when $q\ne1$, we establish that the algebra must be nilpotent., Comment: 12 pages - We modified the work taking into account some Latyshev's results related to the present subject

We define a partial order $\mathcal{P}_n$ on permutations of any given size $n$, which is the image of a natural partial order on inversion sequences. We call this the ``middle order''. We demonstrate that the poset $\mathcal{P}_n$ refines the weak order on permutations and admits the Bruhat order as a refinement, justifying the terminology. These middle orders are distributive lattices and we establish some of their combinatorial properties, including characterization and enumeration of intervals and boolean intervals (in general, or of any given rank), and a combinatorial interpretation of their Euler characteristic. We further study the (not so well-behaved) restriction of this poset to involutions, obtaining a simple formula for the M\"obius function of principal order ideals there. Finally, we offer further directions of research, initiating the study of the canonical Heyting algebra associated with $\mathcal{P}_n$, and defining a parking function analogue of $\mathcal{P}_n$., Comment: 21 pages, 3 figures

Previous work has shown that the disarray (or displacement) of an (affine) (signed) permutation is bounded in terms of its Coxeter length. Here, we characterize the permutations for which the bound is sharp in two ways: in terms of a natural property of their reduced words, and by ``globally'' avoiding the pattern 321., Comment: 16 pages; comments welcome!

Stirling permutations are parking functions, and we investigate two parking function statistics in the context of these objects: lucky cars and displacement. Among our results, we consider two extreme cases: extremely lucky Stirling permutations (those with maximally many lucky cars) and extremely unlucky Stirling permutations (those with exactly one lucky car). We show that the number of extremely lucky Stirling permutations of order $n$ is the Catalan number $C_n$, and the number of extremely unlucky Stirling permutations is $(n-1)!$. We also give some results for luck that lies between these two extremes. Further, we establish that the displacement of any Stirling permutation of order $n$ is $n^2$, and we prove several results about displacement composition vectors. We conclude with directions for further study., Comment: 17 pages, 3 tables

In this paper we study a variant of the Malicious Ma\^{i}tre d' problem. This problem, attributed to computer scientist Rob Pike in Peter Winkler's book "Mathematical Puzzles: A Connoisseur's Collection", involves seating diners around a circular table with napkins placed between each pair of adjacent settings. The goal of the ma\^{i}tre d' is to seat the diners in a way that maximizes the number of diners who arrive at the table to find the napkins on both the left and right of their place already taken by their neighbors. Previous work described a seating algorithm in which the ma\^{i}tre d' expects to force about 18% of the diners to be napkinless. In this paper, we show that if the ma\^{i}tre d' learns each diner's preference for the right or left napkin before they are placed at the table, this expectation jumps to nearly $1/3$ (and converges to $1/3$ as the table size gets large). Moreover, our strategy is optimal for every sequence of diners' preferences., Comment: 19 pages, 7 figures

The boolean elements of a Coxeter group have been characterized and shown to possess many interesting properties and applications. Here we introduce "prism permutations," a generalization of those elements, characterizing the prism permutations equivalently in terms of their reduced words and in terms of pattern containment. As part of this work, we introduce the notion of "calibration" to permutation patterns., Comment: to appear in Advances in Applied Mathematics

Given a Stirling permutation w, we introduce the mesa set of w as the natural generalization of the pinnacle set of a permutation. Our main results characterize admissible mesa sets and give closed enumerative formulas in terms of rational Catalan numbers by providing an explicit bijection between mesa sets and rational Dyck paths., Comment: 11 pages, 3 figures

Petersen and Tenner defined the depth statistic for Coxeter group elements which, in the symmetric group, can be described in terms of a cost function on transpositions. We generalize that cost function to the other classical (finite and affine) Weyl groups, letting the cost of an individual reflection $t$ be the distance between the integers transposed by $t$ in the combinatorial representation of the group (\`a la Eriksson and Eriksson). Arbitrary group elements then have a well-defined cost, obtained by minimizing the sum of the transposition costs among all factorizations of the element. We show that the cost of arbitrary elements can be computed directly from the elements themselves using a simple, intrinsic formula., Comment: 14 pages. Various improvements suggested by referees. Accepted version, Annals of Combinatorics

Pinnacle sets record the values of the local maxima for a given family of permutations. They were introduced by Davis-Nelson-Petersen-Tenner as a dual concept to that of peaks, previously defined by Billey-Burdzy-Sagan. In recent years pinnacles and admissible pinnacles sets for the type $A$ symmetric group have been widely studied. In this article we define the pinnacle set of signed permutations of types $B$ and $D$. We give a closed formula for the number of type $B$/$D$ admissible pinnacle sets and answer several other related enumerative questions., Comment: 15 pages, 3 figures, to appear in Discrete Mathematics

For each fully commutative permutation, we construct a "boolean core," which is the maximal boolean permutation in its principal order ideal under the right weak order. We partition the set of fully commutative permutations into the recently defined crowded and uncrowded elements, distinguished by whether or not their RSK insertion tableaux satisfy a sparsity condition. We show that a fully commutative element is uncrowded exactly when it shares the RSK insertion tableau with its boolean core. We present the dynamics of the right weak order on fully commutative permutations, with particular interest in when they change from uncrowded to crowded. In particular, we use consecutive permutation patterns and descents to characterize the minimal crowded elements under the right weak order., Comment: 20 pages, 2 figures

For any permutation w, we characterize the reduced words of w that are their own commutation class. When w is the long element n(n-1)...321 and n \ge 4, there are exactly four such words., Comment: Final version, to appear in Journal of Combinatorics

Hitomezashi, a form of traditional Japanese embroidery, gives rise to intricate arrangements of axis-parallel unit-length stitches in the plane. Pete studied these patterns in the context of percolation theory, and the first two authors recently investigated additional structural properties of them. In this paper, we establish several optimization-style results on hitomezashi patterns and provide a complete classification of "long-stitch" hitomezashi patterns in which stitches have length greater than 1. We also study variants in which stitches can have directions not parallel to the coordinate axes., Comment: 19 pages, 13 figures; final version

We define and construct the "canonical reduced word" of a boolean permutation, and show that the RSK tableaux for that permutation can be read off directly from this reduced word. We also describe those tableaux that can correspond to boolean permutations, and enumerate them. In addition, we generalize a result of Mazorchuk and Tenner, showing that the "run" statistic influences the shape of the RSK tableau of arbitrary permutations, not just of those that are boolean., Comment: final version, to appear in Annals of Combinatorics

We study relationships between permutation statistics and pattern-functions, counting the number of times particular patterns occur in a permutation. This allows us to write several familiar statistics as linear combinations of pattern counts, both in terms of a permutation and in terms of its image under the fundamental bijection. We use these enumerations to resolve the question of characterizing so-called "shallow" permutations, whose depth (equivalently, disarray/displacement) is minimal with respect to length and reflection length. We present this characterization in several ways, including vincular patterns, mesh patterns, and a new object that we call "arrow patterns." Furthermore, we specialize to characterizing and enumerating shallow involutions and shallow cycles, encountering the Motzkin and large Schr\"oder numbers, respectively., Comment: 17 pages, to appear in The Electronic Journal of Combinatorics

Motivated by recent work with Mazorchuk, we characterize the conditions under which the intersection of two principal order ideals in the Bruhat order is boolean. That characterization is presented in three versions: in terms of reduced words, in terms of permutation patterns, and in terms of permutation support. The equivalence of these properties follows from an analysis of what it means to have a specific letter repeated in a permutation's reduced words; namely, that a specific 321-pattern appears., Comment: 7 pages, 2 figures

We prove that the grades of simple modules indexed by boolean permutations, over the incidence algebra of the symmetric group with respect to the Bruhat order, are given by Lusztig's a-function. Our arguments are combinatorial, and include a description of the intersection of two principal order ideals when at least one permutation is boolean. An important object in our work is a reduced word written as minimally many runs of consecutive integers, and one step of our argument shows that this minimal quantity is equal to the length of the second row in the permutation's shape under the Robinson-Schensted correspondence. We also prove that a simple module over the above-mentioned incidence algebra is perfect if and only if its index is the longest element of a parabolic subgroup., Comment: 26 pages; to appear in Combinatorial Theory

The odd diagram of a permutation is a subset of the classical diagram with additional parity conditions. In this paper, we study classes of permutations with the same odd diagram, which we call odd diagram classes. First, we prove a conjecture relating odd diagram classes and 213- and 312-avoiding permutations. Secondly, we show that each odd diagram class is a Bruhat interval. Instrumental to our proofs is an explicit description of the Bruhat edges that link permutations in a class., Comment: 17 pages, to appear in Combinatorial Theory

We study tiling-based perimeter and characterize when a given perimeter tile appears in all rhombic tilings of an Elnitsky polygon. Regardless of where on the perimeter this tile appears, its forcing can be described in terms of 321-patterns. We characterize the permutations with maximally many forced right-perimeter tiles, and show that they are enumerated by the Catalan numbers., Comment: 10 pages

The interval poset of a permutation catalogues the intervals that appear in its one-line notation, according to set inclusion. We study this poset, describing its structural, characterizing, and enumerative properties., Comment: 14 pages; final version, to appear in Order

Let $f(x) = \alpha x + \beta \mod 1$ for fixed real parameters $\alpha$ and $\beta$. For any positive integer $n$, define the S\'os permutation $\pi$ to be the lexicographically first permutation such that $0 \leq f(\pi(0)) \leq f(\pi(1)) \leq \cdots \leq f(\pi(n)) < 1$. In this article we give a bijection between S\'os permutations and regions in a partition of the parameter space $(\alpha,\beta)\in [0,1)^2$. This allows us to enumerate these permutations and to obtain the following "three areas" theorem: in any vertical strip $(a/b,c/d)\times [0,1)$, with $(a/b,c/d)$ a Farey interval, there are at most three distinct areas of regions, and one of these areas is the sum of the other two., Comment: 15 pages

We develop the relationship between minimal transitive star factorizations and noncrossing partitions. This gives a new combinatorial proof of a result by Irving and Rattan, and a specialization of a result of Kreweras. It also arises in a poset on the symmetric group whose definition is motivated by the Subword Property of the Bruhat order., Comment: to appear in Discrete Mathematics

Given a permutation w, we look at the range of how often a simple reflection s_k appears in reduced decompositions of w. We compute the minimum and give a sharp upper bound on the maximum. That bound is in terms of 321- and 3412-patterns in w, specifically as they relate in value and position to k. We also characterize when that minimum and maximum are equal, refining a previous result that braid moves are equivalent to 321-patterns., Comment: corrected Theorem 5.1; to appear in Advances in Applied Mathematics

A pinnacle of a permutation is a value that is larger than its immediate neighbors when written in one-line notation. In this paper, we build on previous work that characterized admissible pinnacle sets of permutations. For these sets, there can be specific orderings of the pinnacles that are not admissible, meaning that they are not realized by any permutation. Here we characterize admissible orderings, using the relationship between a pinnacle x and its rank in the pinnacle set to bound the number of times that the pinnacles less than or equal to x can be interrupted by larger values., Comment: to appear in Graphs and Combinatorics

We study the appearance of notable interval structures -- lattices, modular lattices, distributive lattices, and boolean lattices -- in both the Bruhat and weak orders of Coxeter groups. We collect and expand upon known results for principal order ideals, including pattern characterizations and enumerations for the symmetric group. This segues naturally into a similar analysis for arbitrary intervals, although the results are less characterizing for the Bruhat order at this generality. In counterpoint, however, we obtain a full characterization for intervals starting at rank one in the symmetric group, for each of the four structure types, in each of the two posets. Each category can be enumerated, with intriguing connections to Fibonacci and Catalan numbers. We conclude with suggestions for further directions and questions, including an interesting analysis of the intervals formed between a permutation and each generator in its support., Comment: to appear in Journal of Combinatorics

We generalize the well-known broken stick problem in several ways, including a discrete "brick" analogue and a sequential "pick-up sticks/bricks" version. The limit behavior of the broken brick problem gives a combinatorial proof of the broken stick problem. The pick-up version gives a variation on those scenarios, and we conclude by showing a greater context---namely, that the broken stick/brick problem and the pick-up sticks/bricks problem are two extremes in a family of interesting, and largely open, questions., Comment: final version; appeared in Mathematics Magazine

We propose a new graphical format for instant-runoff voting election results. We call this proposal an "accumulation chart." This model, a modification of standard bar charts, is easy to understand, clearly indicates the winner, depicts the instant-runoff algorithm, and summarizes the votes cast. Moreover, it includes the pedigree of each accumulated vote and gives a clear depiction of candidates' coalitions., Comment: to appear in Notices of the AMS

We consider polygonal tilings of certain regions and use these to give intuitive definitions of tiling-based perimeter and area. We apply these definitions to rhombic tilings of Elnitsky polygons, computing sharp bounds and average values for perimeter tiles in convex centrally symmetric 2n-gons. These bounds and values have implications for the combinatorics of reduced decompositions of permutations. We also classify the permutations whose polygons gave minimal perimeter, defined in two different ways. We conclude by looking at some of these questions in the context of domino tilings, giving a recursive formula and generating function for one family, and describing a family of minimal-perimeter regions., Comment: to appear in Advances in Applied Mathematics

"Compactness," or the use of shape as a proxy for fairness, has been a long-running theme in the scrutiny of electoral districts; badly-shaped districts are often flagged as examples of the abuse of power known as gerrymandering. The most popular compactness metrics in the redistricting literature belong to a class of scores that we call contour-based, making heavy use of area and perimeter. This entire class of district scores has some common drawbacks, outlined here. We make the case for discrete shape scores and offer two promising ideas: a cut score and a spanning tree score. We use recent United States redistricting history as a source of examples. No shape metric can work alone as a seal of fairness, but we argue that discrete metrics are better aligned both with the grounding of the redistricting problem in geography and with the computational tools that have recently gained significant traction in the courtroom., Comment: 32 pages, 15 figures; substantially revised

We obtain an upper and lower bound for the number of reduced words for a permutation in terms of the number of braid classes and the number of commutation classes of the permutation. We classify the permutations that achieve each of these bounds, and enumerate both cases., Comment: 19 pages

A permutation of n letters is k-prolific if each (n-k)-subset of the letters in its one-line notation forms a unique pattern. We present a complete characterization of k-prolific permutations for each k, proving that k-prolific permutations of m letters exist for every m \ge k^2/2+2k+1, and that none exist of smaller size. Key to these results is a natural bijection between k-prolific permutations and certain "permuted" packings of diamonds., Comment: to appear in Journal of Combinatorial Theory, Series A

S.~Elnitsky (1997) gave an elegant bijection between rhombic tilings of $2n$-gons and commutation classes of reduced words in the symmetric group on $n$ letters. P.~Magyar (1998) found an important construction of the Bott-Samelson varieties introduced by H.C.~Hansen (1973) and M.~Demazure (1974). We explain a natural connection between S.~Elnitsky's and P.~Magyar's results. This suggests using tilings to encapsulate Bott-Samelson data (in type $A$). It also indicates a geometric perspective on S.~Elnitsky's combinatorics. We also extend this construction by assigning desingularizations to the zonotopal tilings considered by B.~Tenner (2006)., Comment: 9 pages, 5 figures; results and authors added

In certain finite posets, the expected down-degree of their elements is the same whether computed with respect to either the uniform distribution or the distribution weighting an element by the number of maximal chains passing through it. We show that this coincidence of expectations holds for Cartesian products of chains, connected minuscule posets, weak Bruhat orders on finite Coxeter groups, certain lower intervals in Young's lattice, and certain lower intervals in the weak Bruhat order below dominant permutations. Our tools involve formulas for counting nearly reduced factorizations in 0-Hecke algebras; that is, factorizations that are one letter longer than the Coxeter group length., Comment: to appear in Journal of Combinatorial Theory, Series A

We develop the technique of reduced word manipulation to give a range of results concerning reduced words and permutations more generally. We prove a broad connection between pattern containment and reduced words, which specializes to our previous work for vexillary permutations. We also analyze general tilings of Elnitsky's polygon, and demonstrate that these are closely related to the patterns in a permutation. Building on previous work for commutation classes, we show that reduced word enumeration is monotonically increasing with respect to pattern containment. Finally, we give several applications of this work. We show that a permutation and a pattern have equally many reduced words if and only if they have the same length (equivalently, the same number of 21-patterns), and that they have equally many commutation classes if and only if they have the same number of 321-patterns. We also apply our techniques to enumeration problems of pattern avoidance, and give a bijection between 132-avoiding permutations of a given length and partitions of that same size, as well as refinements of this data and a connection to the Catalan numbers., Comment: to appear in Journal of Algebraic Combinatorics

Two mesh patterns are coincident if they are avoided by the same set of permutations. In this paper, we provide necessary conditions for this coincidence, which include having the same set of enclosed diagonals. This condition is sufficient to prove coincidence of vincular patterns, although it is not enough to guarantee coincidence of bivincular patterns. In addition, we provide a generalization of the Shading Lemma (Hilmarsson et al.), a result that examined when a square could be added to the mesh of a pattern., Comment: 17 pages, 17 figures

We compute the expected number of commutations appearing in a reduced word for the longest element in the symmetric group. The asymptotic behavior of this value is analyzed and shown to approach the length of the permutation, meaning that nearly all positions in the reduced word are expected to support commutations. Finally, we calculate the asymptotic frequencies of commutations, consecutive noncommuting pairs, and long braid moves., Comment: to appear in The Australasian Journal of Combinatorics

In this paper we study those generic intervals in the Bruhat order of the symmetric group that are isomorphic to the principal order ideal of a permutation w, and consider when the minimum and maximum elements of those intervals are related by a certain property of their reduced words. We show that the property does not hold when w is a decomposable permutation, and that the property always holds when w is the longest permutation., Comment: to appear in DMTCS

Mesh patterns are a generalization of classical permutation patterns that encompass classical, bivincular, Bruhat-restricted patterns, and some barred patterns. In this paper, we describe all mesh patterns whose avoidance is coincident with classical avoidance, in a sense declaring that the additional data of a mesh was unnecessary for these patterns. We also describe the permutations having the fewest superfluous meshes, and the permutations having the most, enumerating the superfluous meshes in each case., Comment: changed terminology; to appear in Advances in Applied Mathematics

There are several versions of permutation pattern avoidance that have arisen in the literature, and some known examples of two different types of pattern avoidance coinciding. In this paper, we examine barred patterns and vincular patterns. Answering a question of Steingrimsson, we determine when barred pattern avoidance coincides with avoiding a finite set of vincular patterns, and when vincular pattern avoidance coincides with avoiding a finite set of barred patterns. There are 720 barred patterns with this property, each having between 3 and 7 letters, of which at most 2 are barred, and there are 48 vincular patterns with this property, each having between 2 and 4 letters and exactly one bond.

It is well-known that any permutation can be written as a product of two involutions. We provide an explicit formula for the number of ways to do so, depending only on the cycle type of the permutation. In many cases, these numbers are sums of absolute values of irreducible characters of the symmetric group evaluated at the same permutation, although apart from the case where all cycles are the same size, we have no good explanation for why this should be so., Comment: 13 pages

For the elements of a Coxeter group, we present a statistic called depth, defined in terms of factorizations of the elements into products of reflections. Depth is bounded above by length and below by the average of length and reflection length. In this article, we focus on the case of the symmetric group, where we show that depth is equal to sum_i max{w(i)-i, 0}. We characterize those permutations for which depth equals length: these are the 321-avoiding permutations (and hence are enumerated by the Catalan numbers). We also characterize those permutations for which depth equals reflection length: these are permutations avoiding both 321 and 3412 (also known as boolean permutations, which we can hence also enumerate). In this case, it also happens that length equals reflection length, leading to a new perspective on a result of Edelman., Comment: to appear in Journal of Combinatorics

The number of minimal transitive star factorizations of a permutation was shown by Irving and Rattan to depend only on the conjugacy class of the permutation, a surprising result given that the pivot plays a very particular role in such factorizations. Here, we explain this symmetry and provide a bijection between minimal transitive star factorizations of a permutation \pi having pivot k and those having pivot k'., Comment: Final version, to appear in Discrete Mathematics

Given a permutation w, we show that the number of repeated letters in a reduced decomposition of w is always less than or equal to the number of 321- and 3412-patterns appearing in w. Moreover, we prove bijectively that the two quantities are equal if and only if w avoids the ten patterns 4321, 34512, 45123, 35412, 43512, 45132, 45213, 53412, 45312, and 45231., Comment: to appear in Adv. Appl. Math

In previous work, we associated to any finite simple graph a particular set of derangements of its vertices. These derangements are in bijection with the spheres in the wedge sum describing the homotopy type of the boolean complex for this graph. Here we study the frequency with which a given derangement appears in this set., Comment: 6 pages

A poset has the non-messing-up property if it has two covering sets of disjoint saturated chains so that for any labeling of the poset, sorting the labels along one set of chains and then sorting the labels along the other set yields a linear extension of the poset. The linear extension yielded by thus twice sorting a labeled non-messing-up poset may be independent of which sort was performed first. Here we characterize such sort-invariant labelings for convex subposets of a cylinder. They are completely determined by avoidance of a particular subpattern: a diamond of four elements whose smallest two labels appear at opposite points., Comment: 8 pages

We construct and analyze an explicit basis for the homology of the boolean complex of a Coxeter system. This gives combinatorial meaning to the spheres in the wedge sum describing the homotopy type of the complex. We assign a set of derangements to any finite simple graph. For each derangement, we construct a corresponding element in the homology of the complex, and the collection of these elements forms a basis for the homology of the boolean complex. In this manner, the spheres in the wedge sum describing the homotopy type of the complex can be represented by a set of derangements. We give an explicit, closed-form description of the derangements that can be obtained from any graph, and compute this set for several families of graphs. In the cases of complete graphs and Ferrers graphs, these calculations give bijective proofs of previously obtained enumerative results., Comment: final version, to appear in Journal of Algebraic Combinatorics

We prove that the $\gamma$-vector of the barycentric subdivision of a simplicial sphere is the $f$-vector of a balanced simplicial complex. The combinatorial basis for this work is the study of certain refinements of Eulerian numbers used by Brenti and Welker to describe the $h$-vector of the barycentric subdivision of a boolean complex.

The minimum number of elements needed for a poset to have exactly n linear extensions is at most 2sqrt{n}. In a special case, the bound can be improved to sqrt{n}., Comment: Final version, to appear in SIAM J Discrete Math

In this paper we introduce doubly symmetric functions, arising from the equivalence of particular linear combinations of Schur functions and hook Schur functions. We study algebraic and combinatorial aspects of doubly symmetric functions, in particular as they form a subalgebra of the algebra of symmetric functions. This subalgebra is generated by the odd power sum symmetric functions. One consequence is that a Schur function itself is doubly symmetric if and only if it is the Schur function of a staircase shape., Comment: 11 pages

A permutation \tau contains another permutation \sigma as a pattern if \tau has a subsequence whose elements are in the same order with respect to size as the elements in \sigma. This defines a partial order on the set of all permutations, and gives a graded poset P. We give a large class of pairs of permutations whose intervals in P have Mobius function 0. Also, we give a solution to the problem when \sigma occurs precisely once in \tau, and \sigma and \tau satisfy certain further conditions, in which case the Mobius function is shown to be either -1, 0 or 1. We conjecture that for intervals [\sigma,\tau] consisting of permutations avoiding the pattern 132, the magnitude of the Mobius function is bounded by the number of occurrences of \sigma in \tau. We also conjecture that the Mobius function of the interval [1,\tau] is -1, 0 or 1., Comment: final version; to appear in Journal of Combinatorics

In this paper we provide an explicit formula for calculating the boolean number of a Ferrers graph. By previous work of the last two authors, this determines the homotopy type of the boolean complex of the graph. Specializing to staircase shapes, we show that the boolean numbers of the associated Ferrers graphs are the Genocchi numbers of the second kind, and obtain a relation between the Legendre-Stirling numbers and the Genocchi numbers of the second kind. In another application, we compute the boolean number of a complete bipartite graph, corresponding to a rectangular Ferrers shape, which is expressed in terms of the Stirling numbers of the second kind. Finally, we analyze the complexity of calculating the boolean number of a Ferrers graph using these results and show that it is a significant improvement over calculating by edge recursion., Comment: final version, to appear in the The Australasian Journal of Combinatorics