Structure and enumeration of (3 + 1)-free
posets (extended abstract)

Mathieu Guay-Paquet†

Alejandro H. Morales‡

Eric Rowland

LaCIM, Université du Québec à Montréal, 201 Président-Kennedy, Montréal QC H2X 3Y7, Canada

**Abstract.** A poset is (3 + 1)-free if it does not contain the disjoint union of chains of length 3 and 1 as an induced subposet. These posets are the subject of the (3 + 1)-free conjecture of Stanley and Stembridge. Recently, Lewis and Zhang have enumerated *graded* (3 + 1)-free posets, but until now the general enumeration problem has remained open. We enumerate all (3 + 1)-free posets by giving a decomposition into bipartite graphs, and obtain generating functions for (3 + 1)-free posets with labelled or unlabelled vertices.

**Résumé.** Un poset sans (3 + 1) est un poset qui n'a pas de sous-poset induit formé de deux chaînes disjointes de longeur 3 et 1. Ces posets sont l'objet de la conjecture (3 + 1) de Stanley et Stembridge. Récemment, Lewis et Zhang on énuméré les posets *étagés* sans (3 + 1), mais en général la question d'énumération est restée ouverte jusqu'à maintenant. Nous énumérons tous les posets sans (3 + 1) en donnant une décomposition de ces posets en graphes bipartis, et obtenons des fonctions génératrices qui les énumèrent, qu'ils soient étiquetés ou non.

**Keywords:** (3+1)-free posets, trace monoid, generating functions, chromatic symmetric function

# 1 Introduction

A poset $P$ is (i + j)-free if it contains no induced subposet that is isomorphic to the poset consisting of two disjoint chains of lengths $i$ and $j$. In particular, $P$ is (3 + 1)-free if there are no vertices $a, b, c, d \in P$ such that $a < b < c$ and $d$ is incomparable to $a, b$, and $c$.

Posets that are (3+1)-free play a role in the study of Stanley's chromatic symmetric function [12, 13], a symmetric function associated with a poset that generalizes the chromatic polynomial of a graph. Namely, a well-known conjecture of Stanley and Stembridge [16] is that the chromatic symmetric function of a (3 + 1)-free poset has positive coefficients in the basis of elementary symmetric functions. As evidence toward this conjecture, Stanley [12] verified the conjecture for the class of 3-free posets, and Gasharov [5] has shown the weaker result that the chromatic symmetric function of a (3+1)-free poset is Schur-positive.

To make more progress toward the Stanley–Stembridge conjecture, a better understanding of (3 + 1)-free posets is needed. Reed and Skandera [9, 10] have given structural results and a characterization of (3 + 1)-free posets in terms of their antiadjacency matrix. In addition, certain families of (3 + 1)-free posets have been enumerated. For example, the number of (3 + 1)-and-(2 + 2)-free posets with $n$

<footnote>†Supported by an NSERC Postdoctoral Fellowship</footnote>

<footnote>‡Supported by a CRM-ISM Postdoctoral Fellowship</footnote>
vertices is the nth Catalan number [15, Ex. 6.19(ddd)]; Atkinson, Sagan and Vatter [1] have enumerated the permutations that avoid the patterns 2341 and 4123, which give rise to the (3 + 1)-free posets of dimension two; and Lewis and Zhang [7] have made significant progress by enumerating graded (3 + 1)-free posets in terms of bicoloured graphs(i) using a new structural decomposition. However, until now the general enumeration problem for (3 + 1)-free posets remained open [14, Ex. 3.16(b)].

In this paper, we give generating functions for (3+1)-free posets with unlabelled and labelled vertices in terms of the generating functions for bicoloured graphs with unlabelled and labelled vertices, respectively. As in the graded case, the two problems are equally hard, although the enumeration problem for bicoloured graphs has received more attention.

In the unlabelled case, let $p_{\text{unl}}(n)$ be the number of (3 + 1)-free posets with $n$ unlabelled vertices, and let $S(c, t)$ be the unique formal power series solution (in $c$ and $t$) of the cubic equation

$$S(c, t) = 1 + \frac{c}{1+c} S(c, t)^2 + tS(c, t)^3. \qquad (1)$$

We show that the ordinary generating function for unlabelled (3 + 1)-free posets is

$$\sum_{n \ge 0} p_{\text{unl}}(n) x^n = S(x/(1-x), 1-2x - B_{\text{unl}}(x)^{-1}), \qquad (2)$$

where $B_{\text{unl}}(x) = 1 + 2x + 4x^2 + 8x^3 + 17x^4 + \dots$ is the ordinary generating function for unlabelled bicoloured graphs. Before our investigation, the On-Line Encyclopedia of Integer Sequences [11] had 22 terms in the entry [11, A049312] for the coefficients of $B_{\text{unl}}(x)$, but only 7 terms in the entry [11, A079146] for the numbers $p_{\text{unl}}(n)$. Using (2), we have closed this gap; the numbers $p_{\text{unl}}(n)$ for $n = 0, 1, 2, \dots, 22$ are

1, 1, 2, 5, 15, 49, 173, 639, 2469, 9997, 43109, 205092, 1153646, 8523086, 91156133, 1446766659, 32998508358, 1047766596136, 45632564217917, 2711308588849394, 219364550983697100, 24151476334929009951, 3618445112608409433287.

Similarly, in the labelled case, let $p_{\text{lbl}}(n)$ be the number of (3 + 1)-free posets with $n$ labelled vertices. We show that the exponential generating function for labelled (3 + 1)-free posets is

$$\sum_{n \ge 0} p_{\text{lbl}}(n) \frac{x^n}{n!} = S(e^x - 1, 2e^{-x} - 1 - B_{\text{lbl}}(x)^{-1}), \qquad (3)$$

where $B_{\text{lbl}}(x) = \sum_{n \ge 0} \sum_{i=0}^{n} \binom{n}{i} 2^{i(n-i)} \frac{x^n}{n!}$ is the exponential generating function for labelled bicoloured graphs. Such bicoloured graphs are easy to count, but before our investigation the OEIS had only 9 terms in the entry [11, A079145] for $p_{\text{lbl}}(n)$. Using (3), arbitrarily many terms $p_{\text{lbl}}(n)$ can be computed.

Our main tool is a new decomposition of (3 + 1)-free posets into *parts* (called *clone sets* and *tangles*). This *tangle decomposition* is compatible with the automorphism group, in the sense that for a (3 + 1)-free poset $P$, Aut($P$) breaks up as the direct product of the automorphism groups of its parts. The tangle decomposition also generalizes a decomposition of Reed and Skandera [10] for (3 + 1)-and-(2 + 2)-free

<footnote>(i) Throughout this paper, a *bicoloured graph* is a bipartite graph with a specified ordered bipartition. For example, there are 2 bicoloured graphs with 1 vertex, 6 bicoloured graphs with 2 labelled vertices, and 4 bicoloured graphs with 2 unlabelled vertices.</footnote>
posets given by *altitudes* of vertices. In terms of generating functions, the restriction of our results to (3 + 1)-and-(2 + 2)-free posets corresponds to the specialization $t = 0$ in (1). Indeed, one can see that $S(x/(1-x), 0)$ satisfies the functional equation for the Catalan generating function, which is consistent with the enumeration result stated earlier for (3 + 1)-and-(2 + 2)-free posets [15, Ex. 6.19(ddd)].

**Remark 1.1.** Using the tangle decomposition it is possible to quickly generate all (3 + 1)-free posets of a given size up to isomorphism in a straightforward way (see Theorem 3.10). With this approach, we were able to list all (3 + 1)-free posets on up to 11 vertices in a few minutes on modest hardware. Note that this technique can accommodate the generation of interesting subclasses of (3 + 1)-free posets (e.g., (2 + 2)-free, weakly graded, strongly graded, co-connected, fixed height) or constructing these posets from the bottom up, level by level (which can help compute invariants like the chromatic symmetric function).

**Remark 1.2.** Comparing the list of numbers above with data provided by Joel Brewster Lewis for the number of graded (3 + 1)-free posets [11, A222863, A222865], it appears that, asymptotically, almost all (3 + 1)-free posets are graded. We prove this in the full version of this paper [6], building on the asymptotic analysis of Lewis and Zhang for the graded (3 + 1)-free posets. In fact, almost all (3 + 1)-free posets are 3-free, so their Hasse diagrams are bicoloured graphs.

**OUTLINE.** In Section 2, we describe the tangle decomposition of a (3 + 1)-free poset into clone sets and tangles and use it to compute the poset's automorphism group. In Section 3, we describe the relationships between the different clone sets and tangles of a (3+1)-free poset as parts of a structure called the *skeleton* and enumerate the possible skeleta. In Section 4, we enumerate tangles in terms of bicoloured graphs, and as a result we obtain generating functions for (3 + 1)-free posets.

## 2 The tangle decomposition

Throughout the paper, we assume that $P$ is a (3 + 1)-free poset. We write $a \parallel b$ if vertices $a$ and $b$ in a poset are incomparable. In this section, we describe the tangle decomposition of a (3 + 1)-free poset.

Given a vertex $a \in P$, we write $D_a = \{x \in P : x < a\}$ and $U_a = \{x \in P : x > a\}$ for the (strict) downset and upset of $a$. The set $\mathcal{J}(P)$ of all downsets of $P$ (that is, all downward closed subsets of $P$, not just those of the form $D_a$ for some $a \in P$) forms a distributive lattice, and in particular a poset, under set inclusion. Similarly, the set of upsets of $P$ forms a poset under set inclusion, but it will be convenient for us to consider instead the complements $P \setminus U_a \in \mathcal{J}(P)$ of the upsets of vertices $a \in P$.

**Definition 2.1.** The view $v(a)$ from a vertex $a \in P$ is the pair $(D_a, P \setminus U_a) \in \mathcal{J}(P) \times \mathcal{J}(P)$. If $v(a) = v(b)$, then we say $a$ and $b$ are *clones* and write $a \approx b$.

Note that the set $v(P)$ of views of all vertices of $P$ inherits a poset structure from the set $\mathcal{J}(P) \times \mathcal{J}(P)$, where $v(a) \le v(b)$ if and only if $D_a \subseteq D_b$ and $U_a \supseteq U_b$.

Also note that two vertices $a, b \in P$ are clones precisely when they are *interchangeable*, in the sense that the permutation of the vertices of $P$ which only exchanges $a$ and $b$ is an automorphism of $P$.

**Example 2.2.** Figure 1 shows a (3 + 1)-free poset and its view poset. Since $v(d) = v(e)$, we have $d \approx e$.

**Remark 2.3.** The notion of clones is related to the notion of *trimming* of Lewis and Zhang [7]. Also, Zhang [18] has used techniques involving clones and (2+2)-avoidance to prove enumeration results about families of graded posets.

**Definition 2.4.** Let $a, b \in P$. We write $a \triangleleft b$ if $D_a \parallel D_b$, and we write $a \triangleleftharpoons b$ if $U_a \parallel U_b$.
<figure><img src="image_1.png" /><figcaption>**Fig. 1:** Left: the Hasse diagram of a (3 + 1)-free poset *P* with 10 vertices. Centre: the list of views of the vertices of *P*. Right: the view poset *v*(*P*).</figcaption></figure>

The idea behind the notation is the following. If $a \not\vdash b$, then there is some vertex $c \in D_a \setminus D_b$, so that $c < a$ and $c \not< b$, and there is some $d \in D_b \setminus D_a$, so that $d \not< a$ and $d < b$. Then, it can be checked that $a, b, c, d$ are distinct vertices, and that they are incomparable except for the two relations $c < a$ and $d < b$. Hence we have the following induced (2 + 2) subposet with $a$ and $b$ on the top:

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

Dually, if $a \not\vdash b$ then there is an induced (2 + 2) subposet with $a$ and $b$ on the bottom.

**Example 2.5.** In Figure 1, we have $f \not\vdash g$ and $b \not\vdash c$, but not $a \not\vdash b$, since $U_b \subseteq U_a$.

The following lemma records basic properties of the relations $\leq$, $\not\leq$, and $\not\vdash$ and their interactions.

**Lemma 2.6.** Let $P$ be a (3 + 1)-free-poset, and let $a, b, c$ be any vertices of $P$.

(i) If $a \approx b$ and $b \approx c$, then $a \approx c$.

(ii) If $a \not\vdash b$ and $b \approx c$, then $a \not\vdash c$.

(iii) If $a \vdash b$ and $b \approx c$, then $a \vdash c$.

(iv) If $a \not\vdash b$, then $U_a = U_b$.

(v) If $a \vdash b$, then $D_a = D_b$.

(vi) We have $v(a) \parallel v(b)$ if and only if $a \not\vdash b$ or $a \vdash b$.

(vii) It is not the case that both $a \not\vdash b$ and $b \vdash c$.

Now, consider a graph $\Gamma$ on the vertices of $P$ with edge set $\{(a, b) : a \not\vdash b\}$. We say that a subset $A \subseteq P$ is the *top of a tangle* if $|A| \ge 2$ and $A$, when viewed as a subset of $V(\Gamma)$, is a connected component of $\Gamma$. Analogously, a subset $B \subseteq P$ is the *bottom of a tangle* if $|B| \ge 2$ and $B$ is a connected component under the relation $\not\vdash$.

By conclusion (vii) of Theorem 2.6, if $A$ is the top of a tangle and $B$ is the bottom of a tangle, then $A \cap B = \emptyset$. Let us say that a top of a tangle $A$ and a bottom of a tangle $B$ are *matched* if there is an induced (2 + 2) subposet whose top two vertices are in $A$, and whose bottom two vertices are in $B$.
**Proposition 2.7.** In a (3+1)-free poset *P*, every top of a tangle is matched to a unique bottom of a tangle, and every bottom of a tangle is matched to a unique top of a tangle. That is, there is a perfect matching between tops of tangles and bottoms of tangles of *P*.

Theorem 2.7 justifies the terms ‘top of a tangle’ and ‘bottom of a tangle’ and the following definition.

**Definition 2.8.** A tangle is a matched pair $T = (A, B)$ of a top of a tangle $A$ and a bottom of a tangle $B$.

In other words, a tangle is a subposet of *P* that is connected by induced (2+2) subposets. In particular, *P* is (2+2)-free exactly when it has no tangles.

**Example 2.9.** Very often, a two-level poset which is not connected consists of a single tangle. For example, let *P* be the poset with vertices {*a*₁, *a*₂, *a*₃, *c*₁, *c*₂} ∪ {*b*, *d*} and relations *a*ᵢ > *c*ⱼ, *b* > *d*. Then, the connected components of *P* are {*a*₁, *a*₂, *a*₃, *c*₁, *c*₂} and {*b*, *d*}. Every subset of the form {*a*ᵢ, *b*, *c*ⱼ, *d*} forms an induced (2 + 2) subposet, so {*a*₁, *a*₂, *a*₃, *b*} is the top of a tangle, {*c*₁, *c*₂, *d*} is the bottom of a tangle, and the whole poset *P* is a single tangle.

**Example 2.10.** In the poset *P* of Figure 1, the connected component of *f* under ≀≀ is {*f*, *g*}, and the connected component of *b* under ≀≀ is {*b*, *c*}. Therefore *P* contains the tangle *T* = {*{f,g}*, {*b,c*}}. One can check that in fact this is the only tangle of *P*.

**Definition 2.11.** Let $T_1 = (A_1, B_1), \dots, T_s = (A_s, B_s)$ be the tangles of $P$. A clone set is an equivalence class, under $\approx$, of vertices in $P \setminus \bigcup_{j=1}^s (A_j \cup B_j)$. We refer to tangles and clone sets as *parts* of $P$. The set of parts is the *tangle decomposition* of $P$.

**Example 2.12.** The tangle decomposition of the poset in Figure 1 appears in Figure 2. It consists of six parts—five clone sets and one tangle.

<figure><img src="image_3.png" /><figcaption>**Fig. 2:** Left: the Hasse diagram of the poset *P* from Figure 1. Centre: the tangle decomposition of *P* into its parts. Right: a compatible listing of the parts. Clone sets are enclosed in circles, and tangles are enclosed in boxes.</figcaption></figure>

The tangle decomposition provides a decomposition of a (3 + 1)-free poset from which the automorphism group, among other properties, can be computed. To show this, it will be useful to have a different characterization of the tops of tangles, bottoms of tangles, and clone sets of *P* which gives a natural ordering of these subsets of *P*, as follows. A *co-connected component* of a poset *Q* is a connected component of the incomparability graph of *Q*.

**Proposition 2.13.** Let $v(P) \subseteq \mathcal{J}(P) \times \mathcal{J}(P)$ be the poset of views of all vertices of the (3+1)-free poset *P*. Then, there is a listing $(S_1, S_2, \dots, S_k)$ of the co-connected components of $v(P)$ such that for every $x \in S_i$ and every $y \in S_{i+1}$, we have $x < y$. Moreover, the preimages $v^{-1}(S_i)$ for $i = 1, 2, \dots, k$ are exactly the tops of tangles, bottoms of tangles, and clone sets of *P*.
Let Aut($P$) be the automorphism group of the poset $P$. Any part $X_i$ of $P$ gives an induced subposet of $P$, and we write Aut($X_i$) for its automorphism group as a poset. In particular, if $X_i$ is a clone set with $k$ vertices, then Aut($X_i$) is the symmetric group on these $k$ vertices; if $X_i$ is a tangle, then it can be seen as a bicoloured graph (with colour classes 'top' and 'bottom'), and Aut($X_i$) is the group of colour-preserving automorphisms of this graph.

**Theorem 2.14.** Let $P$ be a (3 + 1)-free poset, decomposed into its clone sets $C_1, C_2, \dots, C_r$ and its tangles $T_1, T_2, \dots, T_s$. Then, the automorphism group of $P$ is

$$ \mathrm{Aut}(P) = \prod_{i=1}^{r} \mathrm{Aut}(C_i) \times \prod_{j=1}^{s} \mathrm{Aut}(T_j). $$

Note that the tangle decomposition of a (3+1)-free poset $P$ into its parts generalizes the decomposition considered by Reed and Skandera [10] of a (3 + 1)-and-(2 + 2)-free poset given by the altitude $\alpha(a) = |D_a| - |U_a|$ of the vertices $a \in P$, since the altitude $\alpha(a)$ is a function of the view $v(a)$. Of course, even in a (3 + 1)-free poset $P$ with an induced (2 + 2) subposet, the altitude is well-defined, and it gives a finer decomposition of $P$ than the tangle decomposition. However, the altitude decomposition is too fine, as the example in Figure 3 shows. Namely, there is an automorphism $\tau$ which swaps the two vertices with altitude -1, the two vertices with altitude -2, and two of the three vertices with altitude 2, as illustrated. But there is no automorphism which acts nontrivially on a single block of the altitude decomposition.

In contrast, for the tangle decomposition, every automorphism of the poset can be factored as a product of automorphisms which only act nontrivially on a single part.

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** A poset $P$ consisting of a single tangle. The vertices are labelled by their altitude $\alpha$, and the arrows describe an automorphism $\tau$ of $P$.</figcaption></figure>

## 3 Skeleta

Any finite poset $P$ can be decomposed into *levels* as follows: take $L_1$ to be the set of minimal vertices of $P$, $L_2$ to be the set of subminimal vertices (that is, the set of minimal vertices of $P \setminus L_1$), and so on up to the set $L_h$ of sub$(h-1)$minimal vertices of $P$, where $h$ is the *height* of $P$. We say that the *level* of a vertex $a \in P$ is $\ell(a)$, where $a \in L_{\ell(a)}$.

If $P$ is (3 + 1)-free, then the only interesting part of the poset structure occurs between adjacent levels, as the following proposition shows.

**Proposition 3.1 (Lewis and Zhang [7]).** Let $P$ be a (3 + 1)-free poset and $a, b \in P$ be two vertices with $\ell(a) \le \ell(b) - 2$. Then, we have $a < b$.

Note that the covering relations of $P$ may include relations $a < b$ for which $\ell(a) = \ell(b) - 2$. This occurs in Figure 1, for example, where $b < h$, $c < h$, $f < j$, and $g < j$ are covering relations.
The following proposition gives a partial converse of Theorem 3.1.

**Proposition 3.2** (Reed and Skandera [10]). Let $P$ be a poset such that for any two vertices $a, b \in P$ with $\ell(a) \le \ell(b) - 2$, we have $a < b$. Then, $P$ is (3 + 1)-free if and only if for any two vertices $c, d \in P$ with $\ell(c) = \ell(d)$, we have $U_c \subseteq U_d$ or $D_c \subseteq D_d$ (and symmetrically, $U_c \supseteq U_d$ or $D_c \supseteq D_d$).

Note that the vertices of a clone set $C_i$ all have the same downset, so they are on the same level. Also, any copy of the (2+2) poset must be contained in two adjacent levels, so any tangle $T_j$ must be contained in two adjacent levels. Thus, we can speak of the level of a clone set or the (adjacent) levels of a tangle.

By construction, the poset structure between two parts of $P$ is fairly restricted. If $C_i$ and $C_j$ are distinct clone sets, then $C_i$ is either completely above, completely below, or completely incomparable with $C_j$ (meaning that every vertex of $C_i$ has the same relationship with every vertex of $C_j$). If $C_i$ is a clone set and $T_j$ is a tangle, then $C_i$ can be

* completely above $T_j$;

* completely above the bottom of $T_j$ and incomparable with the top;

* completely below the top of $T_j$ and incomparable with the bottom;

* completely below $T_j$; or

* completely incomparable with $T_j$.

Similarly, there are only six possible ways for two tangles $T_i$ and $T_j$ to relate to each other. The following theorem shows how all of these relationships between different parts of $P$ can be put together.

**Theorem 3.3.** Let $P$ be a (3 + 1)-free poset, decomposed into clone sets $C_1, \dots, C_r$ and tangles $T_1, \dots, T_s$. Then, there exists a listing $(X_1, \dots, X_{r+s})$ of the clone sets and the tangles of $P$ such that, for any two vertices $a \in X_i$ and $b \in X_j$ with $i \ne j$, we have $a < b$ exactly when

(i) $\ell(a) \le \ell(b) - 2$; or

(ii) $\ell(a) = \ell(b) - 1$ and $i < j$.

**Definition 3.4.** A listing which satisfies the conditions of Theorem 3.3 is called a *compatible listing*.

**Example 3.5.** A compatible listing for the poset in Figure 1 is $(\{a\}, \{d, e\}, \{h\}, (\{f, g\}, \{b, c\}), \{j\}, \{i\})$, as shown in Figure 2.

*idea for Theorem 3.3.* For each level, we can get a partial listing of the parts which intersect $L_i$ according to their positions on the view poset $v(P)$. Then, the listing for $L_i$ and $L_{i+1}$ can be interleaved in a unique way to respect condition (ii), so it follows that all of them can be reconciled into a single compatible listing. $\square$

Note that the listing $(X_1, X_2, \dots, X_{r+s})$ from Theorem 3.3 is not unique in general. In particular, if $(\dots, X_i, X_{i+1}, \dots)$ is a compatible listing, then the listing $(\dots, X_{i+1}, X_i, \dots)$ obtained by swapping the parts $X_i$ and $X_{i+1}$ is compatible exactly when $X_i$ and $X_{i+1}$ contain no vertices on the same or on adjacent levels of $P$. We call such a swap *valid*.

**Example 3.6.** In Figure 2 we can swap the clone set $\{j\}$ on level 4 with the tangle $(\{f, g\}, \{b, c\})$ on levels 1 and 2 to obtain another compatible listing for the poset.

Therefore the natural setting for compatible listings is that of free partially commuting monoids [3], also known as trace monoids [4].
**Definition 3.7.** Let $\Sigma$ be the countable alphabet

$$ \Sigma = \{c_1, c_2, \dots, c_i, \dots\} \cup \{t_{12}, t_{23}, \dots, t_{i+1}, \dots\}, $$

let $\Sigma^*$ be the free monoid generated by $\Sigma$, and let $M$ be the free partially commuting monoid with commutation relations

$$ \begin{array}{ll} c_i c_j = c_j c_i, & \text{if } |i - j| \ge 2, \\ c_i t_{j j+1} = t_{j j+1} c_i, & \text{if } i \le j - 2 \text{ or } i \ge j + 3, \\ t_{i i+1} t_{j j+1} = t_{j j+1} t_{i i+1}, & \text{if } |i - j| \ge 3. \end{array} $$

**Definition 3.8.** If $P$ is a $(3+1)$-free poset, then for each compatible listing $(X_1, X_2, \dots, X_{r+s})$ of its clone sets and tangles, we can obtain a word in $\Sigma^*$ by replacing each clone set at level $i$ by the letter $c_i$ and each tangle straddling levels $\{i, i+1\}$ by the letter $t_{i i+1}$. It can be seen that any two compatible listings for $P$ are related by a sequence of valid swaps, so the set of these words is an equivalence class under the commutation relations for $M$ (see, e.g., [4, Chapter 1]), and the corresponding element of $M$ is called the skeleton of $P$.

**Example 3.9.** The two representatives in $\Sigma^*$ for the skeleton of the poset in Figure 2 are $c_1 c_2 c_3 t_{12} c_4 c_3$ and $c_1 c_2 c_3 c_4 t_{12} c_3$.

The point of a skeleton is that it exactly captures the relationships between different parts of $P$. More precisely, two posets with the same skeleton and isomorphic parts are themselves isomorphic; conversely, given a skeleton, any set of parts (with the right number of clone sets and tangles) can be plugged into the skeleton. Together, Theorem 3.10, Theorem 3.11, and Theorem 3.12 below show this and give a characterization of the elements of $M$ which are skeleta.

**Corollary 3.10.** Let $P$ be a $(3+1)$-free poset. Then, $P$ is uniquely determined (up to isomorphism) by its skeleton together with, for each letter $c_i$ or $t_{i i+1}$ of the skeleton, the cardinality of the corresponding clone set or the isomorphism class of the corresponding tangle.

**Theorem 3.11.** Let $m$ be an element of the monoid $M$. Then, $m$ is the skeleton of some $(3+1)$-free poset if and only if

(i) every representative $w \in \Sigma^*$ for $m$ starts with the letter $c_1$ or $t_{12}$; and

(ii) no representative $w \in \Sigma^*$ for $m$ contains a factor of the form $c_i c_i$, $i \ge 1$.

Note that condition (i) of Theorem 3.11 corresponds to the requirement that every vertex of $P$ on level $L_{i+1}$ be greater than some vertex on the previous level $L_i$, while condition (ii) forbids pairs of clone sets that could be merged into a single clone set.

**Theorem 3.12.** Let $m$ be an element of the monoid $M$. Then, there exists a representative $w_0 \in \Sigma^*$ for $m$ for which every pair of consecutive letters is either

$$ \begin{array}{ll} c_i c_j & \text{for } i \ge j - 1; \text{ or} \\ c_i t_{j j+1} & \text{for } i \ge j - 1; \text{ or} \\ t_{i i+1} c_j & \text{for } i \ge j - 2; \text{ or} \\ t_{i i+1} t_{j j+1} & \text{for } i \ge j - 2. \end{array} $$

Furthermore,
(i) this representative $w_0$ is unique and is the lexicographically maximal representative for $m$ with respect to the total order $\{c_1 < t_{12} < c_2 < t_{23} < \cdots\}$ on $\Sigma$;

(ii) if $w_0$ starts with $c_1$ or $t_{12}$, then every representative $w \in \Sigma^*$ for $m$ starts with $c_1$ or $t_{12}$; and

(iii) if $w_0$ does not contain a factor of the form $c_i c_i$, $i \ge 1$, then no representative $w \in \Sigma^*$ for $m$ contains a factor of this form.

**Example 3.13.** Of the two representatives given in Theorem 3.9, $c_1c_2c_3c_4t_{12}c_3$ is lexicographically maximal.

Using this characterization of skeleta, we can enumerate them, and this will allow us to obtain generating functions for (3 + 1)-free posets.

**Theorem 3.14.** *There is a bijection between skeleta of (3 + 1)-free posets and certain decorated Dyck paths. (See Figure 4 for an example.)*

*Proof.* Given the lexicographically maximal representative $w_0$ for a skeleton, we can obtain a decorated Dyck path that starts at (0, 0), ends at (2n, 0) for some $n \ge 0$, and never goes below the x-axis as follows: replace each letter $c_i$ by a (1, 1) step ending at height $i$, each letter $t_{i+1}$ by a (2, 2) step ending at height $i+1$, and add (1, -1) down steps as necessary. We call the result *decorated* since a (2, 2) step can be seen as a pair of consecutive decorated (1, 1) steps. Since $w_0$ not contain $c_i c_i$ as a factor, the decorated Dyck path obtained from $w_0$ contains no sequence (1, 1), (1, -1), (1, 1) of consecutive undecorated steps

<figure><img src="image_5.png" /><figcaption>**Fig. 4:** An example of the bijection given in Theorem 3.14.</figcaption></figure>
(up-down-up). Conversely, every decorated Dyck path avoiding this sequence can be obtained from a skeleton. □

**Theorem 3.15.** Let $S(c, t) \in \mathbb{Q}[[c, t]]$ be the ordinary generating function for skeleta with respect to the number of clone sets and the number of tangles, that is, the formal power series

$$S(c, t) = \sum_{r,s \ge 0} (\text{\# of distinct skeleta with } r \text{ clone sets and } s \text{ tangles}) c^r t^s.$$

Then, $S(c, t)$ is uniquely determined by the equation

$$S(c, t) = 1 + \frac{c}{1+c} S(c, t)^2 + t S(c, t)^3. \qquad (4)$$

idea. See Figure 5. □

<figure><img src="image_6.png" /><figcaption>**Fig. 5:** Equations relating the sets counted by $S(c, t)$, $S_1(c, t)$, and $S_2(c, t)$, where $S_1(c, t)$ and $S_2(c, t)$ are the generating functions for decorated Dyck paths beginning with (1, 1) and (2, 2), respectively.</figcaption></figure>

# 4 Enumeration

In this section, we carry out the enumeration of unlabelled and labelled (3 + 1)-free posets by reducing it to the enumeration of unlabelled and labelled bicoloured graphs. Our approach is to consider such a bicoloured graph as a (3 + 1)-free poset in the natural way (with colour classes 'top' and 'bottom') and to apply the machinery of Section 3, as shown in the following lemma.

**Lemma 4.1.** The ordinary generating function for skeleta of bicoloured graphs is given by

$$\sum_{r_1, r_2, s \ge 0} \binom{\text{\# of skeleta of bicoloured graphs with } r_1}{\text{clone sets on level 1, } r_2 \text{ clone sets on level 2, and } s \text{ tangles}} c_1^{r_1} c_2^{r_2} t_{12}^s = \left(1 - \frac{c_1}{1+c_1} - \frac{c_2}{1+c_2} - t_{12}\right)^{-1}. \quad (5)$$
Now that we have an explicit expression for the generating function of skeleta of bicoloured graphs, we can perform appropriate substitutions to get equations relating the generating functions for tangles and for bicoloured graphs.

**Theorem 4.2.** Let $B_{\text{unl}}(x, y) \in \mathbb{Q}[[x, y]]$ be the ordinary generating function for unlabelled bicoloured graphs, up to isomorphism. Then, the ordinary generating function for unlabelled tangles is

$$T_{\text{unl}}(x, y) = 1 - x - y - B_{\text{unl}}(x, y)^{-1}.$$

*Proof.* This follows from Theorem 4.1 by plugging in the values $c_1 = x/(1-x)$ and $c_2 = y/(1-y)$ for the clone sets of unlabelled vertices and $t = T_{\text{unl}}(x, y)$ for the tangles in (5). □

**Theorem 4.3.** Let $B_{\text{lbl}}(x, y) \in \mathbb{Q}[[x, y]]$ be the exponential generating function for labelled bicoloured graphs, that is, the formal power series

$$B_{\text{lbl}}(x, y) = \sum_{i,j \ge 0} 2^{ij} \frac{x^i y^j}{i!j!}.$$

Then, the exponential generating function for labelled tangles is

$$T_{\text{lbl}}(x, y) = e^{-x} + e^{-y} - 1 - B_{\text{lbl}}(x, y)^{-1}.$$

*Proof.* This follows from Theorem 4.1 by plugging in the values $c_1 = e^x - 1$ and $c_2 = e^y - 1$ for the clone sets of labelled vertices and $t = T_{\text{lbl}}(x, y)$ for the tangles in (5). □

With these expressions for the generating functions $T_{\text{unl}}(x, y)$ and $T_{\text{lbl}}(x, y)$ in hand, the following corollaries of Theorem 3.15 yield the equations (2) and (3) from the introduction.

**Corollary 4.4.** Let $S(c, t)$ be the generating function of Theorem 3.15 for skeleta. Then, the ordinary generating function for unlabelled (3 + 1)-free posets is

$$\sum_{n \ge 0} p_{\text{unl}}(n) x^n = S(x/(1-x), T_{\text{unl}}(x, x)).$$

**Corollary 4.5.** Let $S(c, t)$ be the generating function of Theorem 3.15 for skeleta. Then, the exponential generating function for labelled (3 + 1)-free posets is

$$\sum_{n \ge 0} p_{\text{lbl}}(n) \frac{x^n}{n!} = S(e^x - 1, T_{\text{lbl}}(x, x)).$$

**Remark 4.6.** François Bergeron has pointed out to us that the results of this section can be generalized to obtain the cycle index series (see [2]) for the species of (3 + 1)-free posets.

# 5 Acknowledgements

This work grew out of a working session of the algebraic combinatorics group at LaCIM with active participation from Chris Berg, Franco Saliola, Luis Serrano, and the authors. It was facilitated by computer exploration using various types of mathematical software, including Sage [17] and its algebraic combinatorics features developed by the Sage-Combinat community [8]. In addition, the authors would like to thank Joel Brewster Lewis for several conversations and suggesting looking at asymptotics and Mark Skandera and Yan X Zhang for helpful discussions.
References

[1] M. D. Atkinson, Bruce E. Sagan, and Vincent Vatter. Counting (3 + 1)-avoiding permutations. *European Journal of Combinatorics*, 33(1):49–61, 2011.

[2] François Bergeron, Gilbert Labelle, and Pierre Leroux. *Combinatorial Species and Tree-like Structures*. Cambridge University Press, 1997.

[3] Pierre Cartier and Dominique Foata. *Problèmes combinatoires de commutation et réarrangements*. Lecture Notes in Mathematics, No. 85. Springer-Verlag, Berlin, 1969.

[4] Volker Diekert. *Combinatorics on Traces*. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 1990.

[5] Vesselin Gasharov. Incomparability graphs of (3 + 1)-free posets are s-positive. *Discrete Math.*, 157:211–215, 1996.

[6] Mathieu Guay-Paquet, Alejandro H. Morales, and Eric Rowland, *Structure and enumeration of (3 + 1)-free posets*, http://arxiv.org/abs/1303.3652.

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

[8] The Sage-Combinat community. Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2012. http://combinat.sagemath.org.

[9] Mark Skandera. A characterization of (3 + 1)-free posets. *J. Combin. Theory Ser. A*, 93(2):231–241, 2001.

[10] Mark Skandera and Brian Reed. Total nonnegativity and (3 + 1)-free posets. *J. Combin. Theory Ser. A*, 103(2):237–256, 2003.

[11] Neil J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. http://oeis.org/.

[12] Richard P. Stanley. A symmetric function generalization of the chromatic polynomial of a graph. *Advances in Math.*, 111:166–194, 1995.

[13] Richard P. Stanley. Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, & notable open problems. *Discrete Math.*, 193:267–286, 1998.

[14] Richard P. Stanley. *Enumerative Combinatorics, Volume 1*. Cambridge University Press, second edition, 2011.

[15] Richard P. Stanley. *Enumerative Combinatorics, Volume 2*. Cambridge University Press, 1999.

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

[17] W. A. Stein et al. Sage mathematics software (version 5.3), 2012.

[18] Yan X Zhang. Variations on graded posets. In preparation, 2012.