# Four Variations on Graded Posets

Yan X Zhang

► To cite this version:

Yan X Zhang. Four Variations on Graded Posets. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.829-840, 10.46298/dmtcs.2492 . hal-01337770

HAL Id: hal-01337770

https://hal.science/hal-01337770

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Four Variations on Graded Posets

Yan X Zhang¹†

¹Department of Mathematics, UC Berkeley, Berkeley, CA, USA

**Abstract.** We explore the enumeration of some natural classes of graded posets, including (2 + 2)-avoiding graded posets, (3 + 1)-avoiding graded posets, (2 + 2)- and (3 + 1)-avoiding graded posets, and the set of all graded posets. As part of this story, we discuss a situation when we can switch between enumeration of labeled and unlabeled objects with ease, which helps us generalize a result by Postnikov and Stanley from the theory of hyperplane arrangements, answer a question posed by Stanley, and see an old result of Klarner in a new light.

**Résumé.** Nous étudions l’énumération de certaines classes naturelles de posets gradués, y compris ceux qui évitent les motifs (2+2), (3+1), (2+2) et (3+1), et l’ensemble de tous les posets gradués. En particulier, nous considérons une situation où l’énumération d’objets marqués et non marqués sont reliées de façon simple, ce qui nous permet de généraliser un résultat de Postnikov et Stanley en théorie des arrangements d’hyperplans, répondre à une question posée par Stanley, et voir sous un nouveau jour un vieux résultat de Klarner et Kreweras.

**Keywords:** posets, combinatorics, generating functions, poset avoidance, linear algebra

## 1 Introduction

The enumeration of posets has been a classical part of enumerative combinatorics. Graded posets form a very natural subfamily of posets to consider. (2 + 2)-avoidance and (3 + 1)-avoidance are two types of poset-avoidance frequently encountered in literature. Combining these two types of avoidance gives 4 natural families of graded posets:

* All graded posets;

* (2 + 2)- and (3 + 1)-avoiding graded posets.

* (2 + 2)-avoiding graded posets;

* (3 + 1)-avoiding graded posets;

This extended abstract summarizes some enumerative results on these four families. After some preliminaries in Section 2, we enumerate all graded posets in Section 3 in a way that better packages old results of Klarner [Kla69] and Kreweras [Kre85]. We also develop some unifying themes for the other three families.

<footnote>†Email: yanzhang@math.berkeley.edu</footnote>
<table><caption>**Tab. 1:** The OGF and EGF for two simple classes of posets.</caption><thead><tr><th></th><th>OGF</th><th>EGF</th></tr></thead><tbody><tr><td>n-element sets (antichains)</td><td><sup>1</sup>&frasl;<sub>1-x</sub></td><td>e<sup>x</sup></td></tr><tr><td>n-element lists (chains)</td><td><sup>1</sup>&frasl;<sub>1-x</sub></td><td><sup>1</sup>&frasl;<sub>1-x</sub></td></tr></tbody></table>

Then, we take a detour and explore a question of Stanley, in Section 4, obtaining the main result Theorem 4.1. Some other ramifications of these results are discussed at the end of Section 4 and Section 8, including a generalization of an observation in work of Stanley and Postnikov on hyperplane arrangements [PS00], and Yangzhou Hu's [Hu14] direct application of our theorem in enumerating (2 + 2)-avoiding posets.

Finally, we go back to the families of problems listed above and discuss our results in Sections 5, 6, and 7. The last of these, Section 7, is a brief sketch of a particularly fruitful standalone work of enumerating (3 + 1)-avoiding graded posets, joint with Lewis [LZ13]. This work was fortuitously timed shortly before the enumeration of all (3 + 1)-avoiding posets by Guay-Paquet, Morales, and Rowland [GPMR13]. We end with some ideas for future work in Section 8.

# 2 Preliminaries

## 2.1 Generating Functions

When we count combinatorial structures with a concept of “size,” such as posets (where a choice of a “size function” would be the number of vertices), we frequently consider using a generating function to count the said structure for every size simultaneously. Two types of generating functions usually occur:

* the OGF (ordinary generating function), usually for unlabeled structures. If there are $o_n$ objects with size $n$, the OGF is

$$O(x) = \sum_{n} o_{n}x^{n}.$$

* the EGF (exponential generating function), usually for structures labeled by $\{1, \dots, n\}$. If there are $e_n$ objects with size $n$, the EGF is

$$E(x) = \sum_{n} e_{n} \frac{x^{n}}{n!}.$$

OGFs and EGFs together tell the story of the symmetries of the combinatorial family and carry different information. An example of two extreme cases, with the same OGF but different EGFs, can be seen in Table 1.

## 2.2 Posets and Poset Avoidance

In this work, all posets we care about are finite. We represent (and refer to) all such posets by their Hasse diagrams, so we use the language of graphs. For a poset $P$, we use $V(P)$ to denote its vertices.

We say a poset $P$ contains (avoids) another poset $Q$ if we can (cannot) select some vertices $S \subset V(P)$ and some edges of $P$ such that they form an isomorphic poset to $Q$. We are only going to be interested in the case where $Q$ is of the form $(a_1 + a_2 + \dots + a_k)$, which we use to mean the union of $k$ incomparable
<figure><img src="image_2.png" /><figcaption>**Tab. 2:** Some examples of poset avoidance.</figcaption></figure>

chains of lengths $a_1, \dots, a_k$; in fact, we will basically only see $(2+2)$ or $(3+1)$. A $(2+2)$-avoiding poset is also called an *interval order*, and a $(2+2)$- and $(3+1)$-avoiding poset is called an *interval semiorder*. Examples are given in Table 2. A standard reference on posets is Stanley [Sta11].

## 3 All Graded Posets

There is some ambiguity in the literature about the concept of a graded poset, so it is important that we start by being precise. In this work, we define a poset $P$ to be *weakly-graded (of rank $M$)* if there is a *rank function* $r: V(P) \to \mathbb{Z}$ such that if $x$ covers $y$ then $r(x) - r(y) = 1$. Furthermore, we define a poset to be *strongly-graded*, or simply *graded*, if all maximal chains have the same length. In this situation, we can consider all minimal vertices to have rank 0 and all maximal vertices to have the same rank $M$. See Figure 1 for a comparison.

Strongly-graded posets tend to be easier to work with because they do not have problematic boundary conditions that come up with weakly-graded posets. Furthermore, the enumeration of weakly-graded posets from strongly-graded ones seems to be a routine but tedious exercise of inclusion-exclusion on the boundary conditions. Thus, we simply call strongly-graded posets *graded* in our work; this choice is consistent with, say, Stanley [Sta11].

<figure><img src="image_3.png" /><figcaption>**Fig. 1:** In our language: a non-graded poset, a weakly graded poset, and a strongly graded poset.</figcaption></figure>

Now, we make a simple but very important observation: the subposet induced by two adjacent ranks of a weakly-graded poset is just a bipartite graph. Thus, it makes sense to consider the EGF of the
$\psi_w(m, n) = 2^{mn}$ counting bipartite graphs with $m$ vertices on one side and $n$ on the other:

$$ \Psi_w(x, y) = \sum_{m,n \ge 0} \psi_w(m, n) \frac{x^m y^n}{m! n!} = \sum_{m,n \ge 0} \frac{2^{mn} x^m y^n}{m! n!}. $$

Similarly, the subposet induced by two adjacent ranks of a graded poset is just a bipartite graph with no isolated vertices. The EGF enumerating these structures is

$$ \Psi_s(x, y) = \sum_{m,n \ge 0} \psi_s(m, n) \frac{x^m y^n}{m! n!} = e^{-x-y} \Psi_w(x, y) $$

by inclusion-exclusion. $\Psi_w$ will resurface when we talk about $(3+1)$-graded posets in Section 7. With the concession of treating the $\psi_s$'s as “simple,” we obtain the following:

**Theorem 3.1** For the enumeration of all graded posets, the following hold:

* Let $V = [\sqrt{x^1/1!} \quad \sqrt{x^2/2!} \quad \dots \quad \sqrt{x^r/r!} \quad \dots]^T$ be an infinite column matrix. Let $D$ be the infinite diagonal matrix with diagonal entries matching that of $V$. Let $A = \{A_{ij}\}$, where $A_{ij} = \psi_s(i, j)$ for $i, j \ge 1$. Then, the generating function for all graded posets is:

$$ P(x) = V^T (I - DAD)^{-1} V. $$

* The above calculation with infinite matrices and vectors can be made finite in the following way: take $r \ge 1$ an integer and let $V_r$ be the $r \times 1$ truncation of the first $r$ elements of $V$. Similarly, let $D_r$ and $A_r$ be the $r \times r$ truncations of $D$ and $A$ respectively. Then the generating function for all graded posets with at most $r$ vertices on each rank is:

$$ P_r(x) = V_r^T (I_r - D_r A_r D_r)^{-1} V_r. $$

A similar calculation with different $V$ can be used to give generating functions for weakly-graded posets.

**Proof idea:** We can think of a graded poset with $n$ levels as $(n-1)$ “slices” of 2-level posets glued together at their vertices. There are $\psi_s(i, j)$ possible slices with $i$ and $j$ vertices at their two levels, and keeping track of how they fit together naturally gives us the result. $\square$

Klarner [Kla69] gave an enumeration of weakly-graded posets (which he called *graded*) and Krew-eras [Kre85] gave a similar enumeration of graded posets (which he called *tiered*<sup>(i)</sup>). Both results were presented in nested sums of the form

$$ \sum f(n_1, n_2) f(n_2, n_3) \cdots f(n_{i-1}, n_i) g(n_i), $$

where $f(m, n)$ and $g(n)$ are specific functions and the sum, as noted by Klarner [Kla69] himself, “extends over all compositions $(n_1, \dots, n_i)$ of $n$ into an unrestricted number of positive parts.” Theorem 3.1 is the most natural reformulation of these results as these sums occur naturally from matrix multiplication.

<footnote><sup>(i)</sup> As promised, there is indeed a lot of ambiguity in the literature!</footnote>
<figure><img src="image_4.png" /><figcaption>**Fig. 2:** In each row, cloning one of the vertices repeatedly gives the posets to the right. Decloning at the cloned vertices would revert to the posets at the left.</figcaption></figure>

# 4 Seeds and Gardens

As an interlude, we examine four results on enumerating interval orders and semiorders, all by different authors:

• (Wine and Freund [WF57]) OGF of interval semiorders: $O(x) = \frac{1-\sqrt{1-4x}}{2x}$.

• (Stanley [Sta96]) EGF of interval semiorders: $E(x) = \frac{1-\sqrt{4e^{-x}-3}}{2(1-e^{-x})}$.

• (Zagier [Zag01]) EGF of interval orders: $E(x) = \sum_n \prod_{k=1}^n (1 - e^{-kx})$.

• (Bousquet-Melou [BMCDK10]) OGF of interval orders: $O(x) = \sum_n \prod_{k=1}^n (1 - (1-x)^k)$.

Note that for both interval orders and semiorders, we have $E(x) = O(1-e^{-x})$. Our work was motivated by Stanley's question (personal communication) of the unifying reason behind this pattern, which clearly does not hold for arbitrary combinatorial structures (recall Table 1)!

First, we define some notions that capture the concept of “cloning” vertices in a poset; in fact, these notions are generalizable to other combinatorial structures, though we limit our statements to posets for clarity in this paper. Given a poset $P$, call two incomparable vertices $x$ and $x'$ in $V(P)$ *exchangeable* if for all $y \in V(P)$, $x < y$ (resp. $x > y$) if and only if $x' < y$ (resp. $x' > y$). Given a poset $P$ and a vertex $x \in V(P)$, we denote by *cloning at* $x$ the process that outputs a poset $P'$ with an additional vertex $x'$ exchangeable with $x$. We denote by *de-cloning at* $x$ the process that outputs a poset $P'$ with $x$ removed, given that $x$ was exchangeable with at least one other vertex $x' \in V(P)$. An example of cloning can be seen in Figure 2. It is easy to see that repeated de-cloning associates each poset to exactly one seed.

Let a *seed* be a poset that cannot be de-cloned (i.e. it has no pair of exchangeable vertices). Let a *garden* be a collection of posets that result from cloning from a set $S$ of seeds. We say it has the *seed (exponential) generating function* $S(x) = \sum_P \frac{x^{|V(P)|}}{|V(P)|!}$, where we sum over all seeds $P$. Example: the garden of isolated vertices has a single seed of size 1; this is just the top row of Figure 2.

Call a poset *primitive* if it has no nontrivial automorphism. Note that a primitive poset must be a seed, because otherwise exchanging two exchangeable vertices is a nontrivial automorphism, but the reverse is not true: consider the poset $(2+2)$, which is the lower-left poset in Figure 2. Its automorphism group is $\mathbb{Z}_2$ but no pairs of vertices are exchangeable. This property of $(2+2)$ is actually the key point of our situation:
**Theorem 4.1** When all seeds in a garden are primitive<sup>(ii)</sup>, its OGF $O(x)$, EGF $E(x)$, and seed EGF $S(x)$ satisfy $E(x) = S(e^x - 1)$, $E(x) = O(1 - e^{-x})$, and $O(x) = S(x/(1-x))$.

Whenever this situation happens, we can switch between all three generating functions at ease, as depicted below. For some more examples of this principle applied to other combinatorial structures, see Figure 6 in Section 8.

<figure><img src="image_5.png" /></figure>

Of particular relevance to us, however, is:

**Proposition 4.2** If we have a garden of posets that avoid (2+2), then all seeds in the garden are primitive.

In particular, the gardens corresponding to interval orders and interval semiorders are both (2 + 2)-avoiding, which explains the numerology that we observed at the beginning of this chapter; see Figure 3. For later sections in our work, we now know that for the classes of graded posets that are (2+2)-avoiding, we can cheaply obtain both the EGFs and OGFs from one another, and we should not expect this nice situation to occur for the “all graded posets” and “(3 + 1)-avoiding graded posets” classes.

It turns out that this observation was not only useful for our work in this paper, but also a couple of other projects.

* Before we finished this extended abstract, Hu [Hu14] borrowed our result for her work on the number of fixed-length semiorders.

* One of the main results, Theorem 7.1, in Postnikov and Stanley's work [PS00] on deformations of Coxeter hyperplane arrangements can be seen as a special case of Theorem 4.1.

* We can use Proposition 4.2 to immediately generalize our observation about interval semiorders to that of marked interval orders as found in Stanley [Sta96]. We leave this discussion to Appendix A.

## 5 (3 + 1)- and (2 + 2)-avoiding Graded Posets

Given a sum of chains $C = (x + y)$, we say that P grade-avoids $x[b_x] + y[b_y]$, where the $b_i$ are in $\mathbb{Z}$, if we cannot find an incomparable x-chain $C_x$ and y-chain $C_y$ and a fixed $b \in \mathbb{Z}$ such that for $i \in \{x, y\}$, the j-th element of the chain $C_i$ is in the $(b_i + j + b)$-th rank of P. Intuitively, grade-avoidance captures avoidance of chains contiguous in the levels of P at a specified relative level.

$$E(x) = R_K(x)O(1 - e^{-x}),$$

where $R_K(x)$ is a rational function dependent only on the cycle index.

<footnote><sup>(ii)</sup> A generalization, which we will not use here but is good to keep in mind, is that when all seeds in a garden have the same cycle index $K$, we have</footnote>
<figure><img src="image_6.png" /><figcaption>**Fig. 3:** Triplets of generating functions for interval orders (top) and interval semiorders (bottom). Note the juxtaposition of not-obviously related objects.</figcaption></figure>

Now that we enter the territory of poset avoidance, we introduce the following lemma, which captures a very powerful idea that we use in all the remaining cases. The simple intuition underneath the technical-sounding description (and a technical proof, which we omit) is that the avoidance of a sum of two chains in weakly-graded posets is a “local condition”; in other words, if $P$ contains a sum of two chains, we do not have to look arbitrarily far to find those chains.

**Lemma 5.1** Let $S = x+y-2$. A weakly-graded poset $P$ is $(x+y)$-avoiding if and only if it grade-avoids all $(x[b_x] + y[b_y])$, where $\min(b_x, b_y) = 0$ and for $i \in \{x, y\}$, $i + b_i - 1 \le S$.

Our main result is:

**Theorem 5.2** The OGF for graded interval semiorders is

$$O(x) = \frac{1 - 3x + 2x^2 - x^3}{(1 - x)(1 - 3x + x^2)}.$$
<figure><img src="image_7.png" /><figcaption>Fig. 4: A height-k poset can be decomposed into a "skeleton" plus k sets of almost-independent "slices."</figcaption></figure>

<figure><img src="image_8.png" /></figure>

<table><caption>Fig. 5: The three generating functions that come up from graded interval semiorders.</caption><tr><td>s<sub>n</sub> = A000045(n + 1)(n!): 1, 1, 2, 6, 48, 360, ...</td><td>S(x) = 1 + x + <sup>x<sup>2</sup></sup>&frasl;<sub>1-x-x<sup>2</sup></sub></td></tr><tr><td>o<sub>n</sub> = A055588(n - 1): 1, 1, 2, 4, 9, 22, 56, 145, ...</td><td>O(x) = <sup>1-3x+2x<sup>2</sup>-x<sup>3</sup></sup>&frasl;<sub>(1-x)(1-3x+x<sup>2</sup>)</sub></td></tr><tr><td>e<sub>n</sub> = ???? : 1, 3, 13, 99, 1021, 12723, ...</td><td>E(x) = ...</td></tr></table>

The triplet of related generating functions can be found in Figure 5.

**Proof idea:** Lemma 5.1 allows us to basically only consider adjacent levels when we check for poset containment. The combination of (3 + 1) and (2 + 2) avoidance shows that there is at least one vertex on each level of the poset that is adjacent to all vertices in the levels above and below. These vertices form a "skeleton" of the poset; furthermore, each vertex not of this form belongs to a unique "slice" that spans two adjacent ranks. The problem is then basically equivalent to choosing the size of the skeleton and then picking the slices independently. See Figure 4 for intuition. □

Our enumeration of graded interval seminorders seems to be original, although the generating function has already appeared in literature in the context of directed column-convex polyominoes [DP03]. Since we have (2 + 2)-avoidance, we also get to put the enumeration into context of Proposition 4.2. Note that looking at the seed EGF suggests some relation with Fibonacci numbers, as the generating function is somewhat similar to the classic generating function $\frac{1}{1-x-x^2}$.
# 6 (2 + 2)-avoiding Graded Posets

For (2 + 2)-avoiding graded posets, we have the following result; note its similarity with Theorem 3.1.

**Theorem 6.1** *The following are true about the enumeration of graded interval orders:*

* Let $A = \{A_{ij}\}$, where

$$A_{ij} = \sum_{l=0}^{\infty} \frac{x^{l+n}}{l!n!} \sum_{m'=0}^{m} \binom{m}{m'} \psi_{2+2}(n, l+m'),$$

where $\psi_{2+2}(i, j)$ has the exponential generating function

$$\sum_{i,j} \psi_{2+2} \frac{x^i y^j}{i!j!} = \frac{1}{e^x + e^y - e^{x+y}}.$$

Then, the EGF for graded interval orders is:

$$P(x) = (e^x - 1)[(I - (e^x - 1)A)^{-1}]_{0,0}.$$

**Proof idea:** We again use Lemma 5.1 to reduce the set of combinatorial conditions we have to check to a finite number. We no longer have (3 + 1)-avoidance, so it is a more technical problem to count the “slices,” where $\psi_{2+2}(i, j)$ plays a similar role with $\psi_s(i, j)$ in Theorem 3.1. □

With the EGF, we may apply Theorem 4.1 to obtain the OGF. We do not include the triplet of sequences as we could not find further insight (none of the sequences are in the OEIS, for example). Maybe a keen reader could find something we did not!

# 7 (3 + 1)-avoiding Graded Posets

(3 + 1)-avoidance is ubiquitous in the study of poset-avoidance, including the Stanley-Stembridge conjecture [SS93], the birthday problem [Fad11], etc. When we started this project, the enumeration of (3 + 1)-avoiding posets had been a long-standing unsolved problem, so we thought to explore the graded version as a stepping stone. Using some intuitions developed in the earlier sections we successfully enumerated (3 + 1)-avoiding graded posets in a standalone work joint with Lewis [LZ13], with the following main result (note the re-appearance of $\Psi_w$):

**Theorem 7.1 ([LZ13])** *The EGF for graded (3 + 1)-avoiding posets is:*

$$F(x) = e^x - 1 + \frac{2e^x + (e^x - 2)\Psi_w(x, x)}{2e^{2x} + e^x + (e^{2x} - 2e^x - 1)\Psi_w(x, x)}.$$

This story has a happy ending – soon afterwards, Guay-Paquet, Morales, and Rowland [GPMR13] obtained the complete enumeration of (3 + 1)-avoiding posets, using some techniques similar to ours (as predicted, $\Psi_w$ appears in their work also, albeit in a different form) and some more sophisticated techniques of their own.
# 8 Conclusion and Future Directions

In this work, we have basically understood the enumeration and structure of the four classes of graded posets in a fairly organized manner. However, there are many fruitful directions for future work:

* The real value of Theorem 4.1 may lie not in its modest application to generating functions, but rather in its ability to predict relationships between seemingly-unrelated objects, such as the appearance of Motzkin objects, Fibonacci numbers, and directed column-convex polyominos in Figures 6 and 5.

* Theorem 4.1 can be used to juxtapose many more triplets of generating functions, including some very familiar ones. Figure 6 gives a couple of examples, and we have verified a few more that we did not include due to space. For example, compositions are just (2 + 1)-avoiding posets, which avoid (2 + 2)! We welcome the reader to explore further in this direction.

* The matrices that appear in the enumeration of all graded posets and (2+2)-avoiding graded posets still have potential to be simplified, maybe with something like a spectral theory of infinite matrices over the ring of formal power series.

* Lemma 5.1, while seemingly simple, is very powerful and crucial to our work. It may be extended to give a unified theory of chain-avoidance. This seems to be a useful project if posets besides (2 + 2)- and (3 + 1)- start to become relevant in poset-avoidance.

* It may be useful to recast the work in Section 4, which is really about cycle indices at heart, in a more algebraic language, such as species or invariant theory.

# Acknowledgements

The author thanks Richard Stanley for motivating the enumeration of graded posets and for ever-helpful advice, and Joel Lewis, Alejandro Morales, Francois Bergeron, and Alexander Postnikov for helpful discussion. In particular, the author is grateful for Joel Lewis for the collaboration that led to the (3 + 1)-avoiding graded posets work and for helping build much of the intuition in the other projects as well. The author also appreciates the high-quality reviews of the two anonymous referees. Much of this work was done at MIT, when the author was supported via an NSF Graduate Fellowship.

# A An Application of Theorem 4.1 - Marked Interval Orders

We end with a generalization of a result of Stanley [Sta96] from studying hyperplane arrangements. Consider an embedding of $n$ intervals in $\mathbb{R}$ such that each interval is marked at several points. Consider two arrangements to be equivalent if for every two intervals $a$ and $b$, the number of marked points of $a$ to the left of the leftmost (not necessarily marked!) point of $b$ are the same. Call such an equivalence class a *marked interval order*. This generalizes some familiar arrangements. For example:

* Each interval only marked at the right endpoint: interval orders of a particular set of lengths;

* Each interval only marked at the right endpoint, each interval having length 1: interval semiorders $(x_i - x_j \in \{1, -1\})$;
<figure><img src="image_9.png" /><figcaption>**Fig. 6:** Top: our garden has a single seed of a single vertex. Bottom: our garden has a single seed of *n* distinguishable objects. Strictly speaking, we are applying Theorem 4.1 to an extended category of posets that allow distinct “colors.”</figcaption></figure>

* Each interval with exactly *n* equidistant marks: a similar situation as generalized Shi arrangements $(x_i - x_j \in \{-k, -k+1, \dots, -1, 1, \dots, k\})$

Each such family $\mathcal{O}$ of marked interval orders corresponds to a region of the hyperplane arrangement $\mathcal{A}(\mathcal{O})$ of $\mathbb{R}^n$ constructed by following: for each $j$, pick $l_1, l_2, \dots, l_n$ dependent on the interval lengths and create the hyperplane arrangement from the hyperplanes $x_i - x_j = l_1, \dots, l_n$ for all $i$. In general, we are going to get deformations of the Braid arrangement. A slightly more general version of Theorem 4.1 fairly quickly generalizes Theorem 2.3 from [Sta96] and the result from Postnikov and Stanley [PS00] that labeled interval semiorders correspond (with multiplicity $n$!) to regions of the Catalan arrangement.

**Theorem A.1** Let $\mathcal{O}$ be any family of marked interval orders. Labeled members of $\mathcal{O}$ correspond to regions of $\mathcal{A}(\mathcal{O})$ and unlabeled members of $\mathcal{O}$ correspond (with multiplicity $n$!) to regions of $\mathcal{A}(\mathcal{O}) \cup \mathcal{B}$, where $\mathcal{B}$ is the Braid arrangement; their EGF $E(x)$ and OGF $O(x)$ satisfy $E(x) = O(1 - e^{-x})$.

## References

[BMCDK10] Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, and Sergey Kitaev. (2+ 2)-free posets, ascent sequences and pattern avoiding permutations. *Journal of Combinatorial*
Theory, Series A, 117(7):884–909, 2010.

[DP03] Emeric Deutsch and Helmut Prodinger. A bijection between directed column-convex polyominoes and ordered trees of height at most three. *Theoretical computer science*, 307(2):319–325, 2003.

[Fad11] Sukhada Fadnavis. A generalization of the birthday problem and the chromatic polynomial. *arXiv:1105.0698*, 2011.

[GPMR13] Mathieu Guay-Paquet, Alejandro H Morales, and Eric Rowland. Structure and enumeration of (3+ 1)-free posets. *arXiv:1303.3652*, 2013.

[Hu14] Yangzhou Hu. On the number of fixed-length semiorders. *Journal of Integer Sequences*, 17(2):3, 2014.

[Kla69] David A Klarner. The number of graded partially ordered sets. *Journal of Combinatorial Theory*, 6(1):12–19, 1969.

[Kre85] Germain Kreweras. Denombrement des ordres etages. *Discrete Mathematics*, 53:147–149, 1985.

[LZ13] Joel Brewster Lewis and Yan X Zhang. Enumeration of graded (3+ 1)-avoiding posets. *Journal of Combinatorial Theory, Series A*, 120(6):1305–1327, 2013.

[OEI04] OEIS Foundation Inc. (2001). The On-Line Encyclopedia of Integer Sequences. A055888, 2004.

[PS00] Alexander Postnikov and Richard P Stanley. Deformations of Coxeter hyperplane arrangements. *Journal of Combinatorial Theory, Series A*, 91(1):544–597, 2000.

[SS93] Richard P Stanley and John R Stembridge. On immanants of Jacobi-Trudi matrices and permutations with restricted position. *Journal of Combinatorial Theory, Series A*, 62(2):261–279, 1993.

[Sta96] Richard P Stanley. Hyperplane arrangements, interval orders, and trees. *Proceedings of the National Academy of Sciences*, 93(6):2620–2625, 1996.

[Sta11] Richard P Stanley. *Enumerative combinatorics*, volume 1. Cambridge university press, 2011.

[WF57] RL Wine and John E Freund. On the enumeration of decision patterns involving n means. *The Annals of Mathematical Statistics*, pages 256–259, 1957.

[Zag01] Don Zagier. Vassiliev invariants and a strange identity related to the dedekind eta-function. *Topology*, 40(5):945–960, 2001.