Printer Friendly

Counting self-dual interval orders.

1 Introduction

The aim of this paper is to enumerate interval orders (also known as (2 + 2)-free posets) with respect to several natural poset statistics, including the size, the magnitude, and the number of minimal and maximal elements. We are mostly motivated by the generating function formulas recently obtained by Bousquet-Melou et al. [3], Kitaev and Remmel [14], and Dukes et al. [5].

Although the formulas derived in this paper provide a common generalization of these previous results, the method we use is different. The previous results were derived using a recursive bijection between interval orders and ascent sequences, due to Bousquet-Melou et al. [3]. In this paper, we instead use an encoding of interval orders by upper-triangular matrices without zero rows and zero columns (we call such matrices Fishburn matrices. Our approach is considerably simpler than the approach based on ascent sequences. More importantly, our approach allows to easily capture the notion of poset duality, which corresponds to transposition of Fishburn matrices. Consequently, we are easily able to adapt our method to the problem of enumerating self-dual interval orders, for which no explicit enumeration has been known so far.

Basic Notions

All the posets considered in this paper are assumed to be finite. We also assume that the posets are unlabeled, that is, isomorphic posets are taken to be identical. Let P be a poset with a strict order relation [??]. A strict down-set of an element y [member of] P is the set D(y) of all the elements of P that are smaller than y, i.e., D(y) = {x [member of] P; x [??] y}. Similarly, the strict up-set of y, denoted by U(y), is the set {x [member of] P; x [??] y}. Note that y is a minimal element of P if and only if D(y) is empty, and y is a maximal element if and only if U(y) is empty.

For a poset P, the following conditions are known to be equivalent [2, 8]:

* P is (2 + 2)-free, that is, P does not have an induced subposet isomorphic to the disjoint union of two chains of length two.

* P has an interval representation, that is, with each element x [member of] P we may associate a real closed interval [[l.sub.x], [r.sub.x]], in such a way that x [??] y if and only if [r.sub.x] < [l.sub.y].

* For any two elements x, y [member of] P, the strict down-sets D(x) and D(y) are comparable by inclusion, i.e., D(x) [subset or equal to] D(y) or D(y) [subset or equal to] D(x).

* For any two elements x, y [member of] P, the strict up-sets D(x) and D(y) are comparable by inclusion.

The posets that satisfy these properties are known as interval orders. Let us briefly review some of their basic properties. For a more thorough exposition, see e.g. Fishburn's monograph [11].

Let P be an interval order. Two elements x and y of P are indistinguishable if U(x) = U(y) and D(x) = D(y). This is an equivalence relation on P. If no two distinct elements of P are indistinguishable, then P is said to be primitive. Every interval order P can be uniquely obtained from a primitive interval order P' by simultaneously replacing each element of P' by a positive number of 'duplicates'.

Since any two strict down-sets in P are comparable by inclusion, it is possible to arrange all the distinct strict down-sets into an increasing chain [D.sub.1] [??] [D.sub.2] [??] ... [??] [D.sub.m], where m is the number of distinct strict down-sets determined by elements of P. An element x [member of] P is said to have level i, if D(x) = [D.sub.i]. Note that [D.sub.1] is always the empty set, and the elements of level 1 are exactly the minimal elements of P. Following Fishburn [9, 10], we call the number m of distinct strict down-sets the magnitude of P. It turns out that m is also equal to the number of distinct strict up-sets, and we can order the strict up-sets of P into a decreasing chain [U.sub.1] [??] [U.sub.2] [??] ... [??] [U.sub.m], and we say that x has up-level i if U(x) = [U.sub.i]. The maximal elements of P are precisely the elements of up-level m, and we have [U.sub.m] = 0. It can be shown [10] that an element of level i has an up-level greater than or equal to i. An interval representation of P can be obtained by mapping an element x with level i and up-level j to the (possibly degenerate) interval [i, j]. This is the unique representation of P by intervals with endpoints belonging to the set [m] = {1,2, ..., m}, and in particular, there is no interval representation of P with fewer than m distinct endpoints.

The dual of a poset P is the poset [bar.P] with the same elements as P and an order relation [??] defined by [x [??] y [??] y [??] y [??] x. A poset is self-dual if it is isomorphic to its dual. The dual of an interval order P of magnitude m is again an interval order of magnitude m, and an element of level i and up-level j in P has the level m + 1 - j and up-level m + 1 - i in [bar.P].

Throughout this paper, an important part will be played by a bijective correspondence between interval orders and a certain kind of integer matrices, which we will call Fishburn matrices. We will state the key properties of the correspondence without proof. A slightly more technical, but essentially equivalent, version of this correspondence has been used by Fishburn [9, 11], where these matrices are called 'characteristic matrices'. The matrix representation has also been applied in several other papers related to interval orders [4, 6, 7].

A Fishburn matrix is an upper-triangular square matrix M of nonnegative integers with the property that every row and every column contains a nonzero entry. A Fishburn matrix is called primitive if all its entries are equal to 0 or 1. We always assume that a matrix has its rows numbered from top to bottom, and columns numbered left-to-right, starting with row and column number one. Let [M.sub.ij] be the entry of M in row i and column j.

An interval order P of magnitude m corresponds to an m x m Fishburn matrix M with [M.sub.ij] being equal to the number of elements of P that have level i and up-level j. Conversely, given an m x m Fishburn matrix M, we may recover the corresponding interval order P by taking the collection of intervals that contains precisely [M.sub.ij] copies of the interval [i, j], and taking this to be the interval representation of P.

This correspondence is a bijection between Fishburn matrices and interval orders. In fact, in this correspondence, each nonzero entry [M.sub.ij] of M can be associated with a group of [M.sub.ij] indistinguishable elements of P. Note that the sum of the i-th row of M is equal to the number of elements of level i in P, and similarly for column-sums and up-levels.

Primitive interval orders correspond to primitive Fishburn matrices. If the order P is mapped to a matrix M, then the dual order [bar.P] is mapped to the matrix [bar.M] obtained from M by transposition along the diagonal running from bottom-left to top-right. If a matrix M is equal to [bar.M], we call it self-dual. Of course, self-dual matrices are representing precisely the self-dual interval orders.

Previous work and our results

Interval orders are equinumerous with several other combinatorial structures. Apart from the correspondence between interval orders and Fishburn matrices, there are also bijections mapping interval orders to other combinatorial objects, such as ascent sequences [3], Stoimenow matchings [17], or certain classes of pattern-avoiding permutations [3, 16]. Many of these combinatorial structures have been studied independently even before their relationship to interval orders was discovered.

The concept of interval order has been introduced by Fishburn [8] in 1970. In 1976, Andresen and Kjeldsen [1] have studied, under different terminology, an enumeration problem equivalent to counting the number of primitive Fishburn matrices with respect to their dimension and the number of elements in the first row, which in poset terminology corresponds to the number of primitive interval orders of a given magnitude and number of minimal elements. They obtained asymptotic bounds for the number of these matrices, as well as recurrence formulas that allowed them to compute several exact initial values.

In 1987, Haxell, McDonald and Thomason [12] have described the first efficient algorithm to compute the number of interval orders, using a recurrence derived using Fishburn matrices, which were already known to be equinumerous with interval orders, thanks to the work of Fishburn [11].

In 1998, Stoimenow [17] has introduced the concept of 'regular linearized chord diagram', later often referred to as a 'Stoimenow matching'. A Stoimenow matching of size n is a matching on the set [2n] in which no two nested edges have adjacent endpoints. Stoimenow has introduced these matchings as a tool in the study of Vassiliev invariants of knots, and computed several asymptotic bounds on their number. Later, these bounds were improved by Zagier [19], who also showed that the generating function of Stoimenow matchings enumerated by their size admits a simple formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

Recently, Bousquet-Meilou, Claesson, Dukes and Kitaev [3] have found a sequence of bijections, showing that interval orders are equinumerous with several other combinatorial objects, including Stoimenow matchings. They have also provided an alternative proof for (1), and derived a formula for the refined generating function that counts interval order with respect to their size and magnitude. This result has prompted renewed interest in this line of research. Dukes, Kitaev, Remmel and Steingrimsson [5] have found an expression for the generating function that enumerates primitive interval orders with respect to their size and magnitude, and deduced a formula that counts interval orders by their size, magnitude and the number of indistinguishable elements. Kitaev and Remmel [14] have obtained, among other results, the formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (2)

where F(x, y) is the generating function of interval orders in which x counts the size and y the number of minimal elements of the interval order. They conjectured that F(x, y) can be also expressed in the following form:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

This conjecture has been subsequently confirmed by Yan [18] and independently by Levande [15]. Let us remark formula (3) also appears in Zagier's work [19, Theorem 1], but there it is interpreted in terms of Stoimenow matchings, not interval orders.

In Section 2 of this paper, we generalize the above-mentioned results of Bousquet-Meilou et al. [3], Dukes et al. [5], and Kitaev and Remmel [14], by obtaining a closed-form expression for the generation function of primitive interval orders, counted with respect to their magnitude, their size, and their number of minimal and maximal elements. From this expression, it is possible to directly derive the generating function of general interval orders, or of interval orders with bounded size of indistinguishability classes, counted with respect to the same statistics.

However, the main significance of our results is not in counting more statistics than previous papers, but rather in presenting a much simpler method to derive the generating functions. Previous results were largely based on a bijection, constructed by Bousquet-Meilou et al. [3], which maps interval orders to a certain kind of integer sequences, known as 'ascent sequences'. This bijection has a complicated recursive definition, which consequently leads to difficult recurrences for generating functions, which then require great ingenuity to be solved into closed forms. In contrast, the arguments in this paper are based on the encoding of interval orders as Fishburn matrices. We exploit a relationship between Fishburn matrices of dimension m and those of dimension m + 1 to obtain a recurrence for the generating function that can be easily solved by elementary means.

To further illustrate the benefit of this approach, in Section 3 we enumerate self-dual interval orders, by a slightly more elaborate application of the same basic technique. The problem of counting self-dual interval orders with respect to their size, or counting primitive self-dual Fishburn matrices with respect to their dimension, does not seem to have been addressed by previous research, presumably because there is no known way to characterize self-duality in terms of ascent sequences. In view of this, it is remarkable that the expressions we obtain for the generating functions of self-dual objects are almost as simple as those of their non-self-dual counterparts.

2 Enumeration of Interval Orders

Recall that a primitive poset is a poset that does not contain any two indistinguishable elements. Our main concern will be to find an expression for the generating function of primitive interval orders, or equivalently, of 01-Fishburn matrices.

Let us call an element of a poset P isolated if it is not comparable to any other element of P. Note that an element is isolated if and only if it is both minimal and maximal. The number of isolated elements of an interval order P is equal to the value of the top-right cell of the corresponding Fishburn matrix. We will call the top-right cell of the matrix the corner cell.

Let us also say that an element of the poset P is internal if it is neither minimal nor maximal. We will consider these statistics of an interval order P:

* the magnitude of P, denoted by mag(P),

* the number of isolated elements, denoted by iso(P),

* the number of non-isolated minimal elements, denoted by min(P),

* the number of non-isolated maximal elements, denoted by max(P), and

* the number of internal elements, denoted by int(P).

In particular, the size of P is equal to iso(P) + min(P) + max(P) + int(P), and its number of minimal elements is equal to min(P) + iso(P). In Table 1, we summarize these statistics, with their interpretation both in terms of posets and in terms of matrices. As a matter of convenience, we restrict ourselves to nonempty interval orders and non-empty matrices in our arguments. If M is the Fishburn matrix representing an interval order P, we write iso(M) as a synonym for iso(P), and similarly for the other statistics. For an integer n [greater than or equal to] 0, we let [V.sub.n](a, b) denote the polynomial (a + 1)[(b + 1).sup.n] - 1.

Let P be the set of all non-empty primitive interval orders, and let G be the generating function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We can now state the main result of this section.

Theorem 2.1 The generating function G(t, v, w, x, y) satisfies the identity

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

Remark 2.2 Let [S.sub.n] = [S.sub.n] (t, v, w, x, y) denote the n-th summand of the sum on the right-hand side of (4). Clearly, [S.sub.n] is a multiple of [t.sup.n+1]. Consequently, the sum on the right-hand side of (4) converges as a sum of power series in t. Moreover, [S.sub.n] has total degree at least n in the variables v and w. Thus, the sum also converges as a sum of power series in v and w. Furthermore, for all k, the coefficient of [t.sup.k] in [S.sub.n] is a polynomial in v, w, x and y, and for all k, l, the coefficient of [v.sup.k] [w.sup.l] is a polynomial in t, x, and y.

The properties stated in the above remark make the identity (4) amenable to many combinatorially meaningful substitutions. Before we state the proof of the theorem, we demonstrate several possible substitutions. Note that some of the formulas we derive have been previously obtained by different methods.

Corollary 2.3 [5, Theorem 8] Let [p.sub.k] be the number of primitive interval orders of size k. The generating function of [p.sub.k] is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Corollary 2.4 Let [m.sub.k] be the number of primitive k x k Fishburn matrices (or equivalently, the number of primitive interval orders of magnitude k). Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let G be the set of non-empty interval orders, and let [G.sup.*] (t, v, w, x, y) be the corresponding generating function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Each interval order can be uniquely obtained from a primitive interval order by replacing each element with a group of indistinguishable elements. In terms of generating functions, this means that

[G.sup.*] (t,v,w,x,y) = G(t, v/1 - v, w/1 - w, x/1 - x, y/1 - y).

By substituting into (4), we get the next corollary.

Corollary 2.5 The generating function [G.sup.*] (t, v, w, x, y) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

From Corollary 2.5 we can obtain yet another proof of the formula (3) derived by Levande [15] and Yan [18] (and indirectly also by Zagier [19]) for the generating function of interval orders counted by their size and number of maximal elements (or equivalently size and number of minimal elements).

Corollary 2.6 [15, 18, 19] Let [g.sub.k,l] be the number of interval orders with k elements and having exactly l maximal elements (including isolated ones). We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Kitaev and Remmel have obtained a different expression for the generating function from the previous corollary. This alternative expression can also be derived from the general formula for [G.sup.*], by restricting the general formula to count minimal elements, rather than maximal ones.

Corollary 2.7 [14] With [g.sub.k,l] as in Corollary 2.6, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

Let us now prove Theorem 2.1. Define [G.sub.k](v, w, x, y) = [[t.sup.k]]G(t, v, w, x, y), that is, [G.sup.k] is the coefficient of [t.sup.k] in G. We will state the proof in the language of Fishburn matrices rather than in the equivalent language of interval orders. It is thus convenient to view [G.sub.k] as the generating function of the primitive k x k Fishburn matrices.

The next lemma provides the main idea in the proof of Theorem 2.1.

Lemma 2.8 For any k [.sub.>] 1, we have

[G.sub.k+1](v, w, x, y) = v[G.sub.k](v + w + vw, w, x + y + xy, y) - v[G.sub.k](v, w, x,y). (6)

Proof: Let [M.sub.k] denote the set of primitive k x k Fishburn matrices. We will describe an operation which from a given matrix M [member of] [M.sub.k] produces a (typically not unique) new matrix M' [member of] [M.sub.k+1]. The matrix M' is created by adding to M a new rightmost column and a new bottom row, and filling them according to these rules:

* [M'.sub.k+1 k+1] = 1, and all the other cells in row k + 1 of M' have value 0.

* For every j [less than or equal to] k, if [M.sub.j,k] = 0, then [M'.sub.j,k] = [M'.sub.j,k+1] = 0.

* For every j [less than or equal to] k, if [M.sub.j,k] = 1 we choose one of the three possibilities to fill [M'.sub.j,k] and [M'.sub.j,k+1]: either [M'.sub.j,k] = 0 and [M'.sub.j,k+1] = 1, or [M'.sub.j,k] = [M'.sub.j,k+1], = 1 and [M'.sub.j,k+1] = 0.

* Any other cell has the same value in M' as in M.

If M has p 1-cells in column k, then the above operation can produce [3.sup.p] matrices M'. All these [3.sup.p] matrices are upper-triangular, all of them have at least one 1-cell in each row, all of them have at least one 1-cell in each column different from column k, and all except for exactly one of them have at least one 1-cell in column k. In other words, for a given M [member of] [M.sub.k] with p 1-cells in column k, the above operation produces [3.sup.p] - 1 matrices M' from [M.sub.k+1] (and one 'bad' matrix not belonging to [M.sub.k+1]). It is not difficult to see that each matrix M' [member of] [M.sub.k+1] can be created in this way from exactly one matrix M [member of] [M.sub.k].

More generally, suppose that M [member of] [M.sub.k] is a matrix with iso(M) = a, min(M) = b, max(M) = c and int(M) = d, that is, M contributes the monomial [x.sup.a][y.sup.b][v.sup.c][w.sup.d] into [G.sub.k](v, w, x, y). Then all the Fishburn matrices produced from M have generating function

v[((x + y + xy).sup.a][y.sup.b][(v + w + vw).sup.c][w.sup.d]- [x.sup.a][y.sup.b][v.sup.c][w.sup.d]),

where the leftmost factor of v counts the 1-cell (k + 1, k + 1) of M'. Summing this expression over all M [member of] [M.sub.k] gives the recurrence from the statement of the lemma. ?

An idea very similar to the previous proof has already been used by Haxell, McDonald, and Thomason [12] to obtain an efficient algorithm for the enumeration of interval orders. It is also closely related to the approach that Khamis [13] has used to derive a recurrence formula for the number of interval orders of a given size and height.

We now deduce Theorem 2.1 from Lemma 2.8 by a simple manipulation of series. For any power series F(v, w, x, y), let [sigma][F(v, w, x, y)] denote the power series F(v + w + vw, w, x + y + xy, y), that is, a represents the substitution of v + w + vw for v and x + y + xy for x. Let [[sigma].sup.(i)] [F(v, w, x, y)] denote the i-fold iteration of [sigma], i.e., [[sigma].sup.(0)][F] = F and for i [greater than or equal to] 1, [[sigma].sup.(i)] [F] = [sigma] [[sigma].sup.(i-1)][F]]. Note that

[[sigma].sup.a(i)] [F(v, w, x, y)] = F([V.sub.i](v, w), w, [V.sub.i](x, y), y).

By writing [G.sub.k] for [G.sub.k](v, w, x, y) and G for G(t, v, w, x, y), we can rewrite (6) as [G.sub.k+1] = v[sigma][[G.sub.k]] - v[G.sub.k], which implies G - t[G.sub.1] = tv[sigma][G] - tvG. Since [G.sub.1] = x, this simplifies into

G = tx/1 + tv] + tv/1 + tv [sigma][G]. (7)

Substituting repeatedly the right-hand side of (7) for the occurrence of G on the right-hand side, we obtain for any m [greater than or equal to] 1 the identity

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (8)

Since the rightmost summand of the right-hand side of (8) is O([t.sup.m+1]), we can take the limit as m [right arrow] [infinity], to obtain the identity in Theorem 2.1. This proves the theorem.

3 Self-dual posets

Recall that a k x k Fishburn matrix M represents a self-dual interval order if and only if M is invariant under transposition along the north-east diagonal, or in other words, if for each i, j the cell (i, j) has the same value as the cell (k - j + 1, k - i + 1). We will say that the two cells (i, j) and (k - j + 1, k - i + 1) form a symmetric pair.

As in the previous section, we will first concentrate on enumerating the primitive matrices. Unless otherwise noted, the generating functions are counting nonempty objects.

We distinguish three types of cells in a k x k matrix M: a cell (i, j) is a diagonal cell if i + j = k + 1, i.e., (i, j) belongs to the north-east diagonal of the matrix. If i + j < k + 1 (i.e., (i, j) is above and to the left of the diagonal) then (i, j) is a North-West cell, or NW-cell, while if i + j > k + 1, then (i, j) is an SE-cell. The diagonal cells and SE-cells together uniquely determine a self-dual matrix.

Apart of the statistics introduced in Section 2 (see Table 1), we will also consider three new statistics of a matrix M.

* diag(M) is the sum of all the diagonal cells except for the corner cell.

* se(M) is the sum of all the SE-cells that do not belong to the last column.

* nw(M) is the sum of all the NW-cells that do not belong to the first row.

In particular, the sum of all cells in M is equal to iso(M) + min(M) + max(M) + se(M) + nw(M) + diag(M). In a self-dual matrix we of course have min(M) = max(M) and se(M) = nw(M), so the above sum is equal to iso(M) + diag(M) + 2 max(M) + 2se(M).

If k > 1 , then among all the k x k primitive self-dual Fishburn matrices, exactly half have the corner cell filled with 1. This is because changing the corner cell from 1 to 0 cannot create an empty row or empty column, since the cells (1,1) and (k, k) are always 1-cells and the value of the corner cell also does not affect the symmetry of the matrix. We will first enumerate the symmetric matrices whose corner cell has the fixed value 1, and then use the above observation to obtain the full count.

Let S + be the set of primitive self-dual Fishburn matrices whose corner cell is equal to 1. Define the generating function [S.sup.+] (t, v, w, z) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The next theorem is the key result of this section.

Theorem 3.1 The generating function [S.sup.+] (t, v, w, z) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (9)

The comments in Remark 2.2 apply to the expression (9) as well.

Before we prove Theorem 3.1, we first state some of its consequences. Although Theorem 3.1 provides all the information we need for our enumerations, it is often more convenient to work with the closely related generating function that counts all Fishburn matrices, rather than just those that belong to [S.sup.+]. Let S be the set of primitive self-dual Fishburn matrices, and define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 3.2 The generating function S satisfies the identity

S(t, v, w, x, z) = (1 + x) [S.sup.+](t, [v.sup.2], [w.sup.2], z) - t. (10)

Consequently, S(t, v, w, x, z) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: The factor (1 + x) on the right-hand side of (10) corresponds to the fact that each primitive self-dual matrix either belongs to [S.sup.+] or is obtained from a matrix in [S.sup.+] by changing its corner cell from 1 to 0. The subtracted t accounts for the fact that the 1 x 1 matrix containing 0 is not a Fishburn matrix, even though it can be obtained from a matrix in [S.sup.+] by changing the corner cell. The substitutions into [S.sup.+] are straightforward

Corollary 3.3 Let [S.sub.m] be the number of self-dual primitive interval orders on m elements, with [S.sub.0] = 1. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Corollary 3.4 Let [r.sub.m] be the number of primitive self-dual m x m Fishburn matrices. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let [S.sup.*] (t, v, w, x, z) be the generating function of (not necessarily primitive) self-dual interval orders, with variables having the same meaning as in S(t, v, w, x, z). Clearly, a Fishburn matrix M representing a self-dual interval order may be obtained in a unique way from a matrix M' representing a primitive interval order, by changing each diagonal 1-cell of M' into an arbitrary non-zero cell, and by changing a symmetric pair of non-diagonal 1-cells of M' into a pair of nonzero cells having the same value. Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Corollary 3.5 Let [g.sub.m] be the number of self-dual interval orders on m elements, with [g.sub.0] = 1. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The proof of Theorem 3.1 is based on the same general idea as the proof of Theorem 2.1. Let us define [S.sup.+.sub.k](v, w, z) = [[t.sup.k]][S.sup.+](t, v, w, z). The next lemma is the self-dual analogue of Lemma 2.8.

Lemma 3.6 For any k [greater than or equal to] 1, we have

[S.sup.+.sub.k+2](v, w, z) = v(1 + v)(1 + z)[S.sup.+.sub.k](v + w + vw, w, z) - v[S.sup.+.sub.k](v, w, z). (11)

Proof: Let [S.sup.+.sub.k] be the set of matrices of [S.sup.+] of size k x k. We will show how a given matrix M [member of] [S.sup.+.sub.k] can be extended into a matrix M' [member of] [S.sup.+.sub.k+2]. Assume, just for the sake of this proof, that matrices in [S.sup.+.sub.k] have rows and columns indexed by 1 , 2, ..., k, while matrices in [S.sup.+.sub.k+2] have rows and columns indexed by 0, 1, ..., k + 1. Thus, if a cell (i, j) is a diagonal cell in M [member of] [S.sup.+.sub.k], then (i, j) is also a diagonal cell in M' [member of] [S.sup.+.sub.k+2], and similarly for SE-cells and NW-cells. The matrix M' is created from M by these rules:

* [M'.sub.k+1 k+1] = 1, and any other cell in row k + 1 of M' has value 0.

* [M'.sub.0,k+1] = 1. Note that the cell (0, k +1) is the corner cell of M'.

* [M'.sub.1,k] = 1. is filled arbitrarily by 0 or 1, and [M'.sub.1,k+1] is filled arbitrarily by 0 or 1 as well. (Recall that [M.sub.1,k] = 1 by the definition of [S.sup.+].)

* For any j [member of] {2, ..., k}, if [M.sub.j,k] = 0, then [M'.sub.j,k] = [M'.sub.j'k+1] = 0, while if [M.sub.j,k] = 1, choose one of three possibilities: either [M'.sub.j,k] = 0 and [M'.sub.j,k+1] = 1, or [M'.sub.j,k] = [M'.sub.j,k+1] = 1, or [M'.sub.j,k] = 1 and [M'.sub.j,k+1] = 0.

* Any other SE-cell or diagonal cell of M' has the same value in M' as in M, and the NE-cells of M' are filled in order to form a self-dual matrix.

From a given matrix M [member of] [S.sup.+.sub.k] with max(M) = p, this procedure creates 4 x [3.sup.p] distinct self- dual matrices of size (k + 2) x (k + 2), which all belong to [S.sup.+.sub.k+2] except for one matrix, which has column k filled with zeros. If M is a matrix that contributes a monomial [v.sup.p][w.sup.q][z.sup.r] into the generating function [S.sup.+.sub.k] (v, w, z), then the matrices in [S.sup.+.sub.k+2] created from M have the generating function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It is easy to see that each matrix M' [member of] [S.sup.+.sub.k+2] can be generated by the above rules from a unique matrix M [member of] [S.sup.+.sub.k]. By summing the identity (12) over all M [member of] [S.sup.+.sub.k], we obtain the identity (11).

To prove Theorem 3.1 from Lemma 3.6, we can just imitate the proof of Theorem 2.1 from Lemma 2.8. We omit the straightforward argument.

4 Final remarks

The formulas of the form we derived in this paper are useful in providing an efficient way to explicitly compute the coefficients of the corresponding generating functions. It is not clear, however, whether one can use such formulas to extract information about the asymptotic growth of the coefficients. Zagier [19] has used formula (1), together with some highly non-trivial power series identities, to find a very precise asymptotic estimate of the number of interval orders on n elements. The corresponding formula for self-dual interval orders from Corollary 3.5 has a similar form, and perhaps it might be also used as a basis for an asymptotic estimate.

References

[1] E. Andresen and K. Kjeldsen. On certain subgraphs of a complete transitively directed graph. Discrete Mathematics, 14(2):103-119, 1976.

[2] K. P. Bogart. An obvious proof of Fishburn's interval order theorem. Discrete Mathematics, 118(1-3):239- 242, 1993.

[3] M. Bousquet-Melou, A. Claesson, M. Dukes, and S. Kitaev. (2+2)-free posets, ascent sequences and pattern avoiding permutations. J. Comb. Theory Ser. A, 117(7):884-909, 2010.

[4] A. Claesson and S. Linusson. n! matchings, n! posets. Proceedings of American Mathematical Society, 139:435-449, 2011.

[5] M. Dukes, S. Kitaev, J. Remmel, and E. Steingrimsson. Enumerating (2 + 2)-free posets by indistinguishable elements. arXiv:1006.2696, 2010.

[6] M. Dukes, V. Jelinek, and M. Kubitzke. Composition matrices, (2 + 2)-free posets and their specializations. Electronic J. Combin., 18(1)(P44), 2011.

[7] M. Dukes and R. Parviainen. Ascent sequences and upper triangular matrices containing non-negative integers. Electronic J. Combin., 17(R53), 2010.

[8] P. C. Fishburn. Intransitive indifference with unequal indifference intervals. Journal of Mathematical Psychology, 7(1):144- 149, 1970.

[9] P. C. Fishburn. Interval lengths for interval orders: A minimization problem. Discrete Mathematics, 47:63-82, 1983.

[10] P. C. Fishburn. Interval graphs and interval orders. Discrete Mathematics, 55(2):135-149, 1985.

[11] P. C. Fishburn. Interval orders and interval graphs: A study of partially ordered sets. John Wiley & Sons, 1985.

[12] P. E. Haxell, J. J. McDonald, and S. K. Thomason. Counting interval orders. Order, 4:269-272, 1987. 10.1007/BF00337889.

[13] S. M. Khamis. Height counting of unlabeled interval and N-free posets. Discrete Mathematics, 275(1-3):165-175, 2004.

[14] S. Kitaev and J. Remmel. Enumerating (2+2)-free posets by the number of minimal elements and other statistics. In 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010.

[15] Paul Levande. Two new interpretations of the Fishburn numbers and their refined generating functions. arXiv:1006.3013, 2010.

[16] R. Parviainen. Wilf classification of bi-vincular permutation patterns. arXiv:0910.5103, 2009.

[17] A. Stoimenow. Enumeration of chord diagrams and an upper bound for Vassiliev invariants. J. Knot Theory Ramifications, 7:93-114, 1998.

[18] S. H. F. Yan. On a conjecture about enumerating (2 + 2)-free posets. arXiv:1006.1226, 2010.

[19] D. Zagier. Vassiliev invariants and a strange identity related to the Dedekind eta-function. Topology, 40(5): 45-960, 2001.

Vit Jelinekl ([dagger])

Fakultat fur Mathematik, Universitat Wien, Wien, Austria

([dagger]) Supported by grant no. 090038011 from the Icelandic Research Fund and by grant Z130-N13 from the Austrian Science Foundation (FWF). Part of this research was conducted during the author's stay at the University of Reykjavik. jelinek@kam.mff.cuni.cz
Tab. 1: The statistics of interval orders

statistic    poset interpretation    matrix interpretation   variable

   mag       magnitude               number of rows              t
   iso       num. of isolated        value of corner cell        x
             elements

   min       num. of non-isolated    sum of the first row,       y
             minimal elements        except the corner
                                     cell

   max       num. of non-isolated    sum of the last             v
             maximal elements        column, except the
                                     corner cell

   int       num. of internal        sum of cells outside        w
             elements                first row and last
                                     column
COPYRIGHT 2011 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Jelinek, Vit
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUAU
Date:Jan 1, 2011
Words:6057
Previous Article:Bumping algorithm for set-valued shifted tableaux.
Next Article:A reciprocity approach to computing generating functions for permutations with no pattern matches.
Topics:

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |