# The Rees product of the cubical lattice with the chain

Patricia Muldoon and Margaret A. Readdy†

Department of Mathematics, University of Kentucky, Lexington, KY 40506-0027, USA

**Abstract.** We study enumerative and homological properties of the Rees product of the cubical lattice with the chain. We give several explicit formulas for the Möbius function. The last formula is expressed in terms of the permanent of a matrix and is given by a bijective proof.

**Résumé.** Nous étudions des propriétés énumératives et homologiques du produit de Rees du treillis cubique avec la chaîne. Nous donnons plusieurs formules explicites de la fonction de Möbius de ce poset. La dernière de ces formules est exprimée en termes du permanent d'une matrice et le résultat est donné par une preuve bijective.

**Keywords:** Möbius function, R-labeling, signed barred permutations

## 1 Introduction

In the paper [2], Björner and Welker connect concepts from commutative algebra with poset topology. One such poset construction is the Rees product.

**Definition 1.1** For two graded posets P and Q with rank function $\rho$ the Rees product, denoted $P \star Q$, is the set of ordered pairs $(p, q)$ in the Cartesian product $P \times Q$ with $\rho(p) \ge \rho(q)$. These pairs are partially ordered by $(p, q) \le (p', q')$ if $p \le_P p'$, $q \le_Q q'$, and $\rho(p') - \rho(p) \ge \rho(q') - \rho(q)$.

The rank of the resulting poset is $\rho(P \star Q) = \rho(P)$. For more details concerning the Rees product and other poset products, see [2].

The Rees product of the Boolean algebra with the chain is the poset

$$R_n = ((B_n \setminus \{\hat{0}\}) \star C_n) \cup \{\hat{0}, \hat{1}\},$$

where $B_n$ is the Boolean algebra on $n$ elements and $C_n$ is the chain on $n$ elements $\{1 < 2 < \dots < n\}$. Jonsson [3] settled a conjecture of Björner and Welker [2] regarding the Möbius function of $R_n$.

**Theorem 1.2 (Jonsson)** For the Rees product of the Boolean algebra with the chain, the Möbius function is

$$\mu_{R_n}(\hat{0}, \hat{1}) = (-1)^{n-1} D_n,$$

where $D_n$ is the nth derangement number.

<footnote>†Part of this work was completed during the author’s 2006-2007 sabbatical at MIT.</footnote>
Recall the derangement numbers $D_n$ are given by $D_0 = 1$ and $D_n = n \cdot D_{n-1} + (-1)^n$ for $n \ge 1$. In recent work Sheshian and Wachs [5] have studied the poset homology of the order complex of $R_n$.

The next most natural poset to work with is to replace the Boolean algebra with the face lattice of the $n$-cube. The *Rees product of the cubical lattice with the chain* is the rank $n + 2$ poset

$$G_n = ((\mathscr{C}_n \setminus \hat{0}) \star C_{n+1}) \cup (\hat{0}, \hat{1}),$$

where $\mathscr{C}_n$ is the $n$-cubical lattice, that is, the face lattice of the $n$-dimensional cube. We will represent an element $(x, i) \in G_n \setminus \{\hat{0}, \hat{1}\}$ as an ordered pair where $x = (x_1, x_2, \dots, x_n) \in \{0, 1, \dots\}^n$ and $i \in \{1, \dots, n\}$. Observe that such an element $(x, i)$ has rank $k$ if there are exactly $k-1$ stars appearing in its first coordinate, $1 \le i \le k$.

In this section we give an explicit formula for the Möbius function of the poset $G_n$. After finding an $R$-labeling in Section 2, we relate the Möbius function with a class of permutations, that is, the double augmented barred signed permutations. These are in a one-to-one correspondence with certain skew diagrams. We will return to these when we consider homological questions for $G_n$. In Section 4 we give a bijective proof of the Möbius function result expressed as a permanent of a certain matrix.

Proposition 1.4 gives an explicit formula for the Möbius function of the poset $G_n$. The proof will require the following lemma.

**Lemma 1.3** *The following identity holds*

$$1 + \sum_{k=0}^{n} \binom{n}{k} (-1)^{k+1} k! (n-k+1) = 0.$$

**Proof:** Define sequences $(a_n)_{n \ge 0}$ and $(b_n)_{n \ge 0}$ by $a_n = (-1)^{n+1}n!$ and $b_n = n+1$. These sequences have exponential generating functions

$$A(x) = \sum_{n \ge 0} (-1)^{n+1} x^n = - \frac{1}{1+x} \quad \text{and} \quad B(x) = \sum_{n \ge 0} (1+n) \frac{x^n}{n!} = (1+x)e^x.$$

Thus, $D(x) = A(x)B(x) = -e^x$. But

$$D(x) = \sum_{n \ge 0} \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k} \frac{x^n}{n!} \\ = \sum_{n \ge 0} \sum_{k=0}^{n} \binom{n}{k} (-1)^{k+1} k! (n-k+1) \frac{x^n}{n!},$$

which proves the claim.

□

**Proposition 1.4** *The Möbius function of the Rees product of the cubical lattice with the chain is given by*

$$\mu_{G_n}(\hat{0}, \hat{1}) = -1 + \sum_{i=0}^{n} (-1)^{n-i} \cdot 2^{n-i} \binom{n}{i} (i+1)(n-i)!.$$
**Proof:** Let $x$ be an element of corank $k$ from $G_n - \{\hat{0}, \hat{1}\}$. First note that the number of elements of corank $i$ in the half-open interval $[x, \hat{1})$, is $\binom{k-1}{i-1} \cdot (k-i+1)$. This follows from the fact that the element $x = (b, p)$ has $k-1$ non-stars appearing in $b$, so a corank $i$ element $y = (c, q) \in [x, \hat{1})$ has $i-1$ more stars appearing in $c$ and the second coordinate $q$ satisfying $p \le q \le p+k-i+1$. Hence there are $\binom{k-1}{i-1} \cdot (k-i+1)$ such elements $y$. Secondly, we claim that for a corank $k$ element $x \in G_n - \{\hat{0}, \hat{1}\}$, we have

$$ \mu_{G_n}(x, \hat{1}) = (-1)^k \cdot (k-1)! \quad (1) $$

We induct on the corank $k$. The case $k=0$ is clear, as then $x$ is a coatom. For the general case, we have

$$ \begin{aligned} \mu_{G_n}(x, \hat{1}) &= - \sum_{x<y \le \hat{1}} \mu_{G_n}(y, \hat{1}) \\ &= - \left( 1 + \sum_{\substack{x<y \le \hat{1}, \\ 1 \le \text{corank}(y) \le k-1}} \mu_{G_n}(y, \hat{1}) \right) \\ &= - \left( 1 + \sum_{i=1}^{k-1} (-1)^i \cdot (i-1)! \cdot \text{number of elements of corank } i \text{ in } [x, \hat{1}) \right), \end{aligned} $$

where the third equality is applying the induction hypothesis. The number of corank $i$ elements in the half-open interval $[x, \hat{1})$ is $\binom{k-1}{i-1} \cdot (k-i+1)$, giving

$$ \mu_{G_n}(x, \hat{1}) = - \left( 1 + \sum_{i=1}^{k-1} (-1)^i \binom{k-1}{i-1} \cdot (i-1)! \cdot (k-i+1) \right) = (-1)^k \cdot (k-1)! $$

by Lemma 1.3.

To finish the argument, there are $2^{n-k} \cdot \binom{n}{k} \cdot (k+1)$ elements of rank $k+1$, each having Möbius value $\mu(x, \hat{1}) = (-1)^{n-k+1} \cdot (n-k)!$. Hence the lemma follows the fact that for a poset $P$ with $\hat{0}$ and $\hat{1}$, the identity $\mu_P(\hat{0}, \hat{1}) = -\sum_{\hat{0}<x\le\hat{1}} \mu_P(x, \hat{1})$ holds. $\square$

## 2 Edge labeling

We begin by recalling some facts about R-labelings. For a complete overview, we refer the reader to Section 5 of Björner and Wachs' paper [1].

Given a poset $P$ an edge labeling is a map $\lambda : E(P) \to \Lambda$, where $E(P)$ denotes the edges in the Hasse diagram of $P$ and the labels form a poset $\Lambda$. An edge labeling $\lambda$ is said to be an R-labeling if in every interval $[x, y]$ of $P$ there is a unique saturated chain $c : x = x_0 < x_1 < \dots < x_k = y$ whose labels are rising, that is, which satisfies $\lambda(x_0, x_1) <_{\Lambda} \lambda(x_1, x_2) <_{\Lambda} \dots <_{\Lambda} \lambda(x_{k-1}, x_k)$. Given a maximal chain $m : \hat{0} = x_0 < x_1 < \dots < x_n = \hat{1}$ in $P$, the descent set of $m$ is the set $D(m) = \{i : \lambda(x_{i-1}, x_i) <_{\Lambda} \lambda(x_i, x_{i+1})\}$. Alternatively, when we view the labels of the maximal chain as the word $\lambda(m) = \lambda_1 \dots \lambda_n$, where $\lambda_i = \lambda(x_{i-1}, x_i)$ and the rank of $P$ is $n$, there is a descent in the $i$th position of $\lambda(m)$ if the labels $\lambda_i$ and $\lambda_{i+1}$ are either incomparable in the label poset $\Lambda$ or satisfy $\lambda_i >_{\Lambda} \lambda_{i+1}$. In particular, a maximal chain $m$ is said to be rising if its descent set satisfies $D(m) = \emptyset$ and falling if $D(m) = \{1, \dots, n\}$.
<table><thead><tr><th>n</th><th>D<sub>n</sub> = (-1)<sup>n</sup>μ<sub>R<sub>n</sub></sub>(0̂, 1̂)</th><th>(-1)<sup>n</sup>μ<sub>G<sub>n</sub></sub>(0̂, 1̂)</th></tr></thead><tbody><tr><td>0</td><td>1</td><td>0</td></tr><tr><td>1</td><td>0</td><td>1</td></tr><tr><td>2</td><td>1</td><td>2</td></tr><tr><td>3</td><td>2</td><td>15</td></tr><tr><td>4</td><td>9</td><td>116</td></tr><tr><td>5</td><td>44</td><td>1165</td></tr><tr><td>6</td><td>265</td><td>13974</td></tr><tr><td>7</td><td>1854</td><td>195643</td></tr><tr><td>8</td><td>14833</td><td>3130280</td></tr><tr><td>9</td><td>133496</td><td>56345049</td></tr><tr><td>10</td><td>1334961</td><td>1126900970</td></tr></tbody></table>

**Tab. 1:** Table of Möbius values for the Rees product of the Boolean algebra with the chain and the Rees product of the cubical lattice with the chain.

The usefulness of an *R*-labeling is that it gives an alternate way to compute the Möbius function $\mu$ of a poset. Variations of this result are due to Stanley in the case of admissible lattices, Björner for *R*-labelings and edge lexicographic labelings, and Björner-Wachs for non-pure posets with a *CR*-labeling. See [1] for historical details.

**Theorem 2.1** Let $P$ be a poset of rank $n$ with unique minimal element $0̂$ and unique maximal element $1̂$. Suppose $P$ has an *R*-labeling. Then with respect to this *R*-labeling,

$$ \mu(0̂, 1̂) = (-1)^n \cdot \text{number of falling maximal chains in } P $$

Let $\lambda: E(G_n) \to \{0, \pm 1, \pm 2, \dots, \pm n, n+1\} \times \{0, 1\}$ be a labeling of the edges of the Hasse diagram of $G_n$ defined by

<table><thead><tr><th></th><th>Edge</th><th>Condition</th><th>λ(E)</th><th>Notation</th></tr></thead><tbody><tr><td>(x, i)</td><td>∠ (y, i)</td><td>x<sub>a</sub> = 1, y<sub>a</sub> = *</td><td>(a, 0)</td><td>a</td></tr><tr><td>(x, i)</td><td>∠ (y, i)</td><td>x<sub>a</sub> = 0, y<sub>a</sub> = *</td><td>(-a, 0)</td><td>-a</td></tr><tr><td>(x, i)</td><td>∠ (y, i + 1)</td><td>x<sub>a</sub> = 1, y<sub>a</sub> = *</td><td>(a, 1)</td><td>ā</td></tr><tr><td>(x, i)</td><td>∠ (y, i + 1)</td><td>x<sub>a</sub> = 0, y<sub>a</sub> = *</td><td>(-a, 1)</td><td>-a</td></tr><tr><td>0̂</td><td>∠ (x, 1)</td><td></td><td>(0, 0)</td><td>0</td></tr><tr><td>(x, i)</td><td>∠ 1̂</td><td></td><td>(n + 1, 0)</td><td>n + 1</td></tr></tbody></table>

where $x = (x_1, \dots, x_n)$ and $y = (y_1, \dots, y_n)$. The elements $\{0, \pm 1, \dots, \pm n, n+1\} \times \{0, 1\}$ are partially ordered with the product order, that is $(x, i) \le (y, j)$ if $x \le y$ and $i \le j$.

**Proposition 2.2** The labeling $\lambda$ is an *R*-labeling of $G_n$.

**Proof:** Let $I = [(x, i), (y, j)]$ be an interval in $G_n - \{0̂, 1̂\}$ of length $m$ with $x = (x_1, \dots, x_n)$ and $y = (y_1, \dots, y_n)$. We wish to find a saturated chain $c: (x, i) = (z_0, p_0) \prec (z_1, p_1) \prec \dots \prec (z_m, p_m) = (y, j)$ in the interval $I$ with increasing edge labels.
Let $S_0 = \{k : x_k = 0 \text{ and } y_k = *\}$ and $S_1 = \{k : x_k = 1 \text{ and } y_k = *\}$. Let $s = j - i$ and $t = |S_0|$. Without loss of generality, we may assume $S_0 = \{i_1, \dots, i_t\}$ and $S_1 = \{i_{t+1}, \dots, i_m\}$ with $i_1 > \dots > i_t$ and $i_{t+1} < \dots < i_m$. Set $(z_0, p_0) = (x, i)$. For $1 \le k \le m$, let $(z_k, p_k) = ((z_{1,k}, \dots, z_{n,k}), p_k)$ where

$$z_{i,k} = \begin{cases} * & \text{if } i = i_k, \\ z_{i,k-1} & \text{otherwise,} \end{cases}$$

and

$$p_k = \begin{cases} p_{k-1} & \text{if } 1 \le k \le m-s, \\ p_{k-1} + 1 & \text{otherwise.} \end{cases}$$

The first coordinate of the edge labels of the chain $c$ form the strictly increasing sequence $-i_1 < \dots < -i_t < i_{t+1} < \dots < i_m$ as the $i_j$'s are all positive, while the second coordinate of the edge labels form the weakly increasing sequence $0 \le \dots \le 0 \le 1 \le \dots \le 1$. Hence the chain $c$ constructed is increasing.

We also claim that the chain $c$ is the unique such chain that is increasing in the interval $I$. For any maximal chain in this interval, each $i \in S_0$ appears as the first coordinate in an edge label with a negative sign and every $i \in S_1$ must appear with a positive sign. Hence there is exactly one way to linearly order these $m$ values. The second coordinate of the labels of any maximal chain in $I$ is a permutation of the multiset $\{0^{m-s}, 1^s\}$. Again, there is exactly one way to order these $m$ values in a weakly increasing fashion. Hence the increasing chain $c$ is unique.

For the case when the interval is $[0, (y, j)] \in G_n$ with $(y, j) \ne \hat{1}$, the first edge label in any saturated chain is always $(0, 0)$. Hence the first coordinate of the labels in any increasing chain in this interval must all be non-negative, implying an increasing chain must pass through the atom $(a, 1) = ((1, \dots, 1), 1)$. The remainder of the increasing chain is given by the unique increasing maximal chain in the interval $[(a, 1), (y, j)]$.

For an interval of the form $[(x, i), \hat{1}]$, since the last edge label of any saturated chain has label $(n+1, 0)$, this forces all the elements of such a chain to be of the form $(y, i)$ with $x \le \mathscr{c}_n y$. In particular, the rank $n$ element of such a chain is precisely the element $(b, i) = ((*, \dots, *), i)$. Hence the increasing maximal chain in $[(x, i), \hat{1}]$ is given by the increasing maximal chain guaranteed in $[(x, i), (b, i)]$ concatenated with the element $\hat{1}$. $\square$

In personal communication with Shaeshian and Wachs, they show that if two graded posets $P$ and $Q$ are shellable (here “shellable” loosely means that both posets are EL-shellable or CL-shellable), then all the intervals in the Rees product $P * Q$ are also shellable.

### 3 Falling chains

Define the set of (double augmented) barred signed permutations $\overline{\pm S_n}$ to be those permutations $\pi = \pi_0 \pi_1 \cdots \pi_{n+1}$ satisfying (i) $\pi_0 = 0$ and $\pi_{n+1} = n+1$, (ii) for $1 \le i \le n$, $\pi_i$ is equal to one of $a_i$, $-a_i$, $\bar{a}_i$ or $-\bar{a}_i$ for some $a_i \in \{1, \dots, n\}$, and (iii) $a_1 \cdots a_n$ is a permutation in the symmetric group $S_n$ on $n$ elements. Given a barred signed permutation $\pi \in \overline{\pm S_n}$, we will write $|\pi| = |\pi_0||\pi_1|\cdots|\pi_{n+1}|$ to denote the double augmented permutation $\pi$ with all of the negative signs and/or bars removed from each element, that is, $|\pi|$ is a permutation of the elements $\{0, 1, \dots, n+1\}$ with $|\pi_0| = 0$ and $|\pi_{n+1}| = n+1$.

Given a double augmented barred signed permutation $\pi = \pi_0 \pi_1 \cdots \pi_{n+1}$, a descent at position $i$ occurs when $|\pi_i| > |\pi_{i+1}|$. This is equivalent to the usual notion of descent in the unsigned and unbarred permutation $|\pi|$ as defined above.
**Proposition 3.1** With respect to the R-labeling $\lambda$ of the poset $G_n$, the falling chains are described as the set of double augmented barred signed permutations $\pi = \pi_0\pi_1 \cdots \pi_{n+1} \in \pm S_n$ satisfying

1. if $\pi_i$ is unbarred then there must be a descent at the ith position.

2. if $\pi_i$ is barred, then either (i) $\pi_{i+1}$ is unbarred or (ii) $\pi_{i+1}$ is barred and there is a descent at the ith position.

**Example 3.2** The permutation $(0, -3, \overline{-4}, 2, \overline{-1}, 5) \in \pm S_4$ corresponds to the falling chain $\hat{0} \prec (0100, 1) \prec (01 * 0, 1) \prec (01 * *, 2) \prec (0 * **, 2) \prec (* * **, 3) \prec \hat{1}$ in the poset $G_4$.

**Proof:** Given a barred signed permutation satisfying the conditions of the proposition, we wish to find a falling chain $c: \hat{0} \prec (x_1, i_1) \prec \cdots \prec (x_n, i_n) \prec \hat{1}$ in $G_n$. For $1 \le k \le n$, if $\pi_k < 0$ then set $x_{1,k} = 1$; otherwise set $x_{1,k} = 0$. To find $(x_k, i_k)$ recursively, set $i_1 = 0$, let $x_{w_k,k} = *$, and set

$$i_k = \begin{cases} i_{k-1} + 1 & \text{if } \pi_k \text{ is barred,} \\ i_{k-1} & \text{if } \pi_k \text{ is not barred.} \end{cases}$$

Observe that $c$ is a falling chain. The labels on the barred signed permutation correspond to the labels on the falling chain. Note that if the unbarred signed permutation does not have a descent at some position $k$, then $\pi_k$ is barred and $\pi_{k+1}$ is not, implying the second coordinate in the labeling $\lambda((x_k, i_k), (x_{k+1}, i_{k+1}))$ is 1, while the second coordinate in the labeling $\lambda((x_{k+1}, i_{k+1}), (x_{k+2}, i_{k+2}))$ is 0. Hence, the chain is not rising in the $k$th position. Otherwise, the unbarred permutation has a descent and hence the first coordinate in the labeling $\lambda((x_k, i_k), (x_{k+1}, i_{k+1}))$ is greater than the first coordinate in the labeling $\lambda((x_{k+1}, i_{k+1}), (x_{k+2}, i_{k+2}))$ and hence the chain is not rising. $\square$

**Theorem 3.3**

$$\mu_{G_n}(\hat{0}, \hat{1}) = (-1)^n \cdot \sum_c 2^{n-c_1} \binom{n}{c_1, \dots, c_k} \cdot c_1 \cdot \prod_{i=2}^k (c_i - 1),$$

where the sum is over all compositions $c = c_1 + \cdots + c_k$ of $n$ and $1 \le k \le n$.

**Proof:** By Theorem 2.1, to determine the Möbius function of the poset $G_n$ it is enough to count the number of falling chains in $G_n$. Proposition 3.1 allows one to separate the double augmented barred signed permutations corresponding to falling chains into substrings which look like a sequence of unbarred numbers followed by a sequence of barred numbers.

By Proposition 3.1, the element 0 will always be part of the first substring and the last substring will consist only of the element $n+1$. Determining the size of each substring is equivalent to taking a composition $c = (c_1, c_2, \dots, c_k)$ of $n$. Note that the first substring will be of size $c_1 + 1$ to account for the element 0 and the $(k+1)$st substring will consist only of the element $n+1$.

In each substring there is a sequence of elements without bars followed by a sequence of elements with bars. Given the size of each substring we determine at what place the barred elements begin. In the first substring we can begin the bars at any place, so there are $c_1$ ways. For all the other substrings the first element cannot be barred, for otherwise it would belong to the previous substring. Thus, we can begin the sequence of barred elements in $c_i - 1$ ways for $i = 2, \dots, k$. The total number of ways to place bars over the elements is $c_1 \cdot \prod_{i=2}^k (c_i - 1)$.
<figure><img src="image_1.png" /><figcaption>Fig. 1: The skew hook shape corresponding to the falling double augmented barred signed permutation $\pi = 0 - 5 - 7 - \underline{8} - \underline{9} 11 \underline{6} \underline{2} - \underline{3} 10 4 - \underline{1} 12$ in $\pm S_{11}$.</figcaption></figure>

Next, we choose the elements that will be in each substring. This is done in $\binom{n}{c_1, c_2, \dots, c_k}$ ways. Now we must sign these elements. Note that the elements in each substring must be arranged in decreasing order. Once we have chosen the signs, this can be done in exactly one way. Furthermore, all of the elements in the first block must be negative because the falling double augmented signed permutation begins with the element 0. This leaves $2^{n-c_1}$ ways to sign the remaining elements. $\square$

# 4 Skew diagrams and a bijective proof

In this section we give a bijective proof of the following theorem.

**Theorem 4.1** *The Möbius function of the Rees product of the cubical lattice with the chain is given by*

$$ \mu_{G_n}(\hat{0}, \hat{1}) = (-1)^n \cdot n \cdot \text{per} \begin{bmatrix} 1 & 2 & \cdots & 2 \\ 2 & 1 & \cdots & 2 \\ \vdots & \vdots & \ddots & \vdots \\ 2 & \cdots & 2 & 1 \end{bmatrix}, $$

that is, $n$ times the permanent of a square $(n-1) \times (n-1)$ matrix having 1's on the diagonal and 2's everywhere else.

In order to do this, we will work with skew diagrams associated to double augmented barred and signed permutations which are falling. In Section 5 we will use these skew diagrams to describe $\Delta(G_n)$, the order complex of the Rees product of the cubical lattice with the chain, in the spirit of Wachs' work with the $d$-divisible partition lattice [7]. We will also use these diagrams to construct an explicit basis for the homology of $G_n$.

We begin by recalling some objects from combinatorial representation theory. For background material in this area, we refer to Sagan's book [4]. Let $(\lambda_1, \dots, \lambda_k) \vdash n$ be a partition of the integer $n$ with $\lambda_1 \le \dots \le \lambda_k$. Recall the Ferrers diagram of $\lambda$ consists of $n$ boxes where row $i$ has $\lambda_i$ boxes for $i=1, \dots, k$ and all the rows are left-justified. Given two Ferrers diagrams $\mu \subseteq \lambda$, the skew diagram $\lambda/\mu$ is the set of all boxes $\lambda/\mu = \{b : b \in \lambda \text{ and } b \notin \mu\}$.
For us, a *hook* is a skew diagram of the form $\lambda/\mu$ where $\lambda = ((h+1)^v)$ and $\mu = (h^{v-1})$. We will be interested in skew diagrams consisting of a disjoint union of hooks. More precisely, let $c = (c_1, \dots, c_k)$ be a composition of $n$ with $c_i = u_i + b_i$, for $i = 1, \dots, k$ where $u_1 \ge 0$, $u_i > 0$ for $i = 2, \dots, k$, and $b_i > 0$ for $i = 1, \dots, k$. Form the partitions $\lambda = (\lambda_1, \dots, \lambda_k)$ and $\mu = (\mu_1, \dots, \mu_k)$ where $\lambda_i = (u_1 + \dots + u_i + i)^{b_i}$ for $1 \le i \le k$, $\mu_i = ((u_1 + \dots + u_i + i - 1)^{b_i - 1}, u_1 + \dots + u_i + i)$ for $1 \le i \le k - 1$, and $\mu_k = (u_1 + \dots + u_k + k - 1)^{b_k - 1}$. The skew diagram $\lambda/\mu$ is then a union of $k$ hooks where the southeast corner of the last box of the $i$th hook touches the northwest corner of the first box of the $(i+1)$st hook. We call such a diagram an *unsigned barred permutation skew diagram*. We call a filling of the $n$ boxes with the elements $\{1, \dots, n\}$ *standard* if the rows are decreasing when read from left to right and the columns are decreasing when read from top to bottom. If we insert a box labelled 0 in front of the first horizontal row and add a box labelled $n+1$ as the new last hook, then we call such a filled diagram a *standard double augmented unsigned barred skew diagram*. Given a double augmented unsigned barred permutation that is falling, recall that it consists of strings of unbarred and barred elements concatenated together. Given such a falling permutation, one forms the standard skew diagram by representing the first string of unbarred elements as the first horizontal string of boxes in the first hook concatenated with the same number of vertical boxes as the number of barred elements in the first string of the permutation. Note that the $i$th hook has $u_i + 1$ horizontal boxes, where $u_i$ is the number of unbarred elements in the first string of the permutation. See Figure 1.

**Theorem 4.2** There exists a bijection between the set of all fixed point free permutations in the symmetric group on $n$ elements and the set of all standard skew diagrams $\lambda/\mu$ having $n$ boxes and hooks of size greater than 1.

**Proof:** We describe an algorithm to move between these two sets. The idea is to first break a cycle at the end of each of its descent runs to form blocks. Each of these blocks will become a hook in the resulting skew diagram. The next step is to use the first element of each block (for the first block, use the second element) to determine which elements will be barred in a given block. The third step is to reverse the order of the blocks. The fact that the original first block contained the smallest element in the given cycle will enable us to recover the complete cycle decomposition of a permutation from its skew diagram in the general case when a permutation has more than one cycle.

We first consider the case where $\pi = (\pi_1, \dots, \pi_n) \in S_n$ consists of a single cycle of length $n$ with $\pi_1 = 1$, that is, the smallest element of the set $\{\pi_1, \dots, \pi_n\}$.

1. Identify the descents within the cycle. For each run of consecutive descents, say $[i,j] = i, i+1, \dots, j$, break the permutation in front of the last descent in the run, that is, the $(j-1)$st position provided this does not create a first block having size one.

2. Suppose reading from left to right the first element in the $i$th block is $m_{i,j}$, where the elements in this block have the linear order $m_{i_1} < m_{i_2} < \dots$. (For the case of the first block, let $m_{1,j}$ be the second element in this block when reading from left to write and where the block elements have linear order $m_{1,1} < m_{1,2} < \dots$.) Rewrite the elements in the block in decreasing order and place bars over each of the last $j-1$ elements.

3. Reverse the order of the blocks, that is, if $B_1|B_2|\dots|B_k$ is the original block decomposition, reverse this to $B_k|B_{k-1}|\dots|B_1$. Finally, remove the vertical block separators.
This yields the union of unsigned hooks, where a hook consists of the run of unbarred elements followed by the run of barred elements.

**Example 4.3** As an example, let $\pi = (135764928) \in S_9$. We have

$$ \begin{aligned} \pi & \rightarrow 1357|64|928 \\ & \rightarrow 1357|46|298 \\ & \rightarrow 753|64|982 \\ & \rightarrow 982647531 \end{aligned} $$

If a permutation consists of more than one cycle, without loss of generality we may assume the permutation is written in standard cycle notation where each cycle is written so that it begins with the smallest element in its cycle and the cycles are then ordered in increasing order by the smallest element in each cycle. Given such a permutation, apply the algorithm to each individual cycle. Concatenate the resulting barred words using the original order of the cycles.

It is straightforward to see that we can reverse this process beginning with a standard unsigned skew diagram. Thus we have a bijection. $\square$

**Example 4.4** Let $8\bar{7}26\bar{1}95\bar{4}\bar{3}$ be a falling barred permutation. The reverse algorithm gives:

$$ \begin{aligned} 8\bar{7}26\bar{1}95\bar{4}\bar{3} & \rightarrow 8\bar{7}2\bar{6}\bar{1}|9\bar{5}\bar{4}\bar{3}| \\ & \rightarrow (6\bar{1})(8\bar{7}2)|(4\bar{3})(9\bar{5}) \\ & \rightarrow (16)(287)|(34)(59) \\ & \rightarrow (16827)(3495) \end{aligned} $$

Let $F \subseteq [n-1]$ be the set of fixed points for a permutation $\pi \in S_{n-1}$. We will build $n$ ordered pairs, $(F_i, \tau)$ where $i = 1, \dots, n$ and $\tau$ is a partial permutation on $n - |F| - 1$ elements from the set $[n]$. Set

$$ F_i = \begin{cases} F \cup \{i\} & \text{if } i \notin F, \\ F \cup \{n\} & \text{if } i \in F, \end{cases} $$

where $i = 1, \dots, n$. To define $\tau$, consider the partial permutation $\hat{\pi}$ consisting of the cycles of $\pi$ with sizes greater than 1. The elements in these cycles can be linearly ordered as $m_{i_1} < m_{i_2} < \dots < m_{i_{n-|F|-1}}$. The elements of $[n] \setminus F_i$ also can be linearly ordered as $l_{i_1} < \dots < l_{i_{n-|F|-1}}$. Define a map $\Psi$ which sends $m_{ij} \mapsto l_{ij}$. Set $\tau = \Psi(\hat{\pi})$. Let $F_\pi = \{(F_i, \tau) : i = 1, \dots, n\}$ so that $|F_\pi| = n$.

**Proposition 4.5** There exists a bijection between $\{F_\pi : \pi \in S_n\}$ and the set of standard unsigned skew diagrams where each hook except the first has size greater than one.

**Proof:** Given a permutation $\pi$ with fixed point set $F$ and one ordered pair $(F_i, \tau)$, we will define a map which sends $F_i$ to the first hook of the diagram and which sends $\tau$ to the rest of the diagram. To create the first part of the map, write the elements of $F_i$ in decreasing order. To place the bars, consider two cases.

1. If $i \notin F$, place bars over the element $i$ and every element less than $i$.
2. If $i \in F$ we use the linear total order on $F$, say $f_1 < \dots < f_{|F|}$. We have $i = f_j$ for some $j = 1, \dots, |F|$. Place bars over the smallest $j$ elements.

This map can be reversed given the first piece of some unsigned skew diagram.

To determine the rest of the diagram, we use $\tau$, a partial permutation on an $n - |F| - 1$ element subset of $[n]$. There is a bijection between all such partial permutations and the set of fixed point free permutations in $S_{n-|F|-1}$. Use the linear order on the elements of $\tau$, that is, these elements can be written $m_{i_1} < \dots < m_{i_k}$. Let $\Phi$ be a map between these two sets where $\Phi(m_{i_j}) = j$. Note that because the partial permutation $\tau$ can be written as a product of cycles with no one-cycles, then $\Phi(\tau)$ is also a fixed point free product of cycles. Composing $\Phi$ with the algorithm above, we can go from a partial permutation $\tau$ to the rest of the diagram having hook sizes greater than 1. $\square$

To prove Theorem 4.1, we sign the first hook (which consists of the horizontal piece 0 concatenated with the vertical piece) in one way, that is, with all negative signs, and then reorder the elements in decreasing order. For the remaining hooks, we can sign these remaining elements in $2^{n-|F|-1}$ ways and within each hook reorder them in a decreasing manner in one way.

As a corollary, we can slightly modify our proofs to give a bijective proof of Jonsson's result (Theorem 1.2) for the Möbius function of the Rees product of the Boolean algebra with the chain.

# 5 A Basis for the Homology

In this section we consider homological questions for the poset $G_n$. A similar analysis for the $d$-divisible partition lattice was done by Wachs [7],

**Proposition 5.1** *The order complex $\Delta(G_n)$ is a Cohen-Macaulay complex and has vanishing homology groups in every dimension except in top dimension.*

This follows by a result of Björner and Welker [2] that the Rees product of any two Cohen-Macaulay posets is also Cohen-Macaulay. Furthermore, the Möbius function of the poset $G_n$ gives the dimension of the top homology group.

We can go further and find an explicit basis for the homology $H(\Delta(G_n), \mathbb{Z})$ indexed by $\mathcal{F}_n$, the falling augmented signed barred permutations from $\pm S_n$. For each $\sigma \in \mathcal{F}_n$ we define a subposet $G_\sigma$ of $G_n$ as follows. Let $m_\sigma = m_{\sigma,0} < m_{\sigma,1} < \dots < m_{\sigma,n}$ be the chain in $G_n \setminus \{\hat{0}, \hat{1}\}$ labeled by $\sigma \in \mathcal{F}_n$. For example, for the double augmented barred signed permutation $\sigma = \sigma_0 \cdots \sigma_6 = 0 -1 \bar{-3} \bar{5} \bar{2} -4 \bar{6}$, we have $m_\sigma = (01001, 1) < (*1001, 1) < (*1 * 01, 2) < (*1 * 0*, 2) < (** * 0*, 3) < (*** * *, 4)$.

We will define the elements of $G_\sigma$ recursively. The rank 0 elements of $G_\sigma$ are of the form $(x, 1)$, where $x$ is a 0-dimensional face of the $n$-cube. For $1 \le i \le n-1$, the rank $i$ elements of $G_\sigma$ are of the form $(x, j)$, where $x$ is an $i$-dimensional face of the $n$-cube and the second coordinate $j$ is determined according to the following rules:

i. If $\sigma_{i-1}$ is not barred, $\sigma_i$ is not barred, and $\sigma_{i+1}$ is either barred or unbarred, then $j = k$ where $(y, k)$ is any rank $i-1$ element of $G_\sigma$.

ii. If $\sigma_{i-1}$ is either barred or unbarred, and both $\sigma_i$ and $\sigma_{i+1}$ are barred, then $j = k+1$ where $(y, k)$ is any rank $i-1$ element of $G_\sigma$.
iii. If $\sigma_{i-1}$ is either barred or unbarred, $\sigma_i$ is barred and $\sigma_{i+1}$ is not barred, then $j=k$ where $(y, k)$ is a rank $i-1$ element of $G_\sigma$. The exception to this rule is for the $i$-dimensional element $x$ occurring in the chain $m_\sigma$, that is, $m_{\sigma,i} = (x, r)$. In this case, $m_{\sigma,i}$ becomes the element $(x, k+1)$ in $G_\sigma$.

iv. If $\sigma_{i-1}$ is barred, $\sigma_i$ is not barred, and $\sigma_{i+1}$ is either barred or unbarred, then $j=k+1$ where $(y, k)$ is any rank $i-1$ element of $G_\sigma$ different from $m_{\sigma,i-1}$. Notice that both $m_{\sigma,i-1}$ and $m_{\sigma,i}$ have the same second coordinate, namely $k+1$.

Finally, there are two rank $n$ elements $(\cdots, k)$ and $(\cdots, k+1)$, where $k$ is the second coordinate of any rank $n-1$ element of $G_\sigma$.

Define $\tilde{\mathscr{C}}_n$ to be the poset $\mathscr{C}_n\setminus\{\hat{0}\} \cup \{\hat{1}'\}$, that is, the face lattice of the $n$-dimensional cube with its minimal element removed and adjoined with a second maximal element $\hat{1}'$ which also covers all the coatoms in $\mathscr{C}_n\setminus\{\hat{0}\}$.

**Theorem 5.2** For $\sigma \in \mathcal{F}_n$, the order complex $\Delta(G_\sigma)$ is isomorphic to the suspension of the barycentric subdivision of the boundary of the $n$-cube.

**Corollary 5.3** For $\sigma \in \mathcal{F}_n$, the order complex $\Delta(G_\sigma)$ is homotopy equivalent to the suspension of the $(n-1)$-dimensional sphere, $S^{n-1}$.

The suspension of $S^{n-1}$ is homotopic to $S^n$, and as a result $\Delta(G_\sigma)$ is a triangulation of the $n$-sphere. Let $\rho_\sigma$ denote a fundamental cycle of the spherical complex $\Delta(G_\sigma)$. To show that the set $\{\rho_\sigma : \sigma \in \mathcal{F}_n\}$ forms a basis for $H(G_n)$, we first place a total order on $\mathcal{F}_n$. Let $\sigma = 0\sigma_1 \cdots \sigma_n n + 1$ and $\tau = 0\tau_1 \cdots \tau_n n + 1$ be two permutations from $\mathcal{F}_n$. If the entries $\sigma_1, \dots, \sigma_{i-1}$ and $\tau_1, \dots, \tau_{i-1}$ are unbarred, $\sigma_i$ is barred and $\tau_i$ is unbarred, then we say $\sigma > \tau$. Otherwise, if $\sigma$ and $\tau$ are barred and unbarred at exactly the same places and the permutation $\sigma$ without the bars is lexicographically greater than the permutation $\tau$ without its bars, then we say $\sigma > \tau$. We then have

**Lemma 5.4** If $m_\tau$ is a chain in $G_\sigma$, then $\tau \le \sigma$.

Using Lemma 5.4, one can use a straightening argument to conclude the desired basis result.

**Theorem 5.5** The set $\{\rho_\sigma : \sigma \in \mathcal{F}_n\}$ forms a basis for $H(G_n)$ over $\mathbb{Z}$.

We are currently developing a representation of $H(\Delta(G_n))$ over the symmetric group using skew Specht modules.

# 6 Concluding remarks

Recall that the derangement number $D_n$ can be expressed as the permanent

$$D_n = \operatorname{per} \begin{bmatrix} 0 & 1 & 1 & \cdots & 1 \\ 1 & 0 & 1 & \cdots & 1 \\ 1 & 1 & 0 & \cdots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \cdots & 0 \end{bmatrix}.$$
What poset *P* would have its Möbius function related to the permanent

$$ \text{per} \begin{bmatrix} s & r & r & \cdots & r \\ r & s & r & \cdots & r \\ r & r & s & \cdots & r \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ r & r & r & \cdots & s \end{bmatrix} ? $$

Although it is not the case the Möbius numbers in Theorem 4.1 count derangements in the action on the *n*-cube, they do in fact count a class of type *BC* permutations, namely, those that fix (setwise) exactly two sides of the given cube. Equivalently, those that fix exactly two points of the dual crosspolytope. (Those two points are necessarily antipodal.) To obtain the $n \times \text{per}(A)$ formula, where $\text{per}(A)$ is the permanent of the $(n-1) \times (n-1)$ matrix with ones on the diagonal and twos off the diagonal, there are $n$ ways to pick a pair of antipodal points. It is not hard to show that $\text{per}(A)$ counts derangements in the action of the stabilizer of these two points on the vertices of the $(n-1)$-crosspolytope spanned by the remaining $2n-2$ points using the fact that for any given permutation $w$ in $S_{n-1}$, there are $2^{n-1-\text{fix}(w)}$ barred permutations associated with $w$ that are derangements in the given action.

# 7 Acknowledgements

The authors would like to thank the referees for their comments, Richard Ehrenborg for suggesting the open problem stated in the concluding remarks and John Shareshian for his group theoretic insight on the Möbius values appearing in Theorem 4.1.

# References

[1] A. BJÖRNER AND M. WACHS, Shellable nonpure complexes and posets. I, *Trans. Amer. Math. Soc.* **348** (1996), no. 4, 1299–1327.

[2] A. BJÖRNER AND V. WELKER, Segre and Rees products of posets, with ring-theoretic applications, *J. Pure Appl. Algebra* **198** (2005), 43–55.

[3] J. JONSSON, The Rees product of a Boolean algebra and a chain, preprint 2005.

[4] B. E. SAGAN, “The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions,” Springer-Verlag, New York, Inc., 2001.

[5] J. SHARESHIAN AND M. WACHS, *q*-Eulerian polynomials: Excedance Number and Major Index, *math.CO/0608274*.

[6] R. P. STANLEY, “Enumerative Combinatorics, Vol. I,” Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986.

[7] M. WACHS, A basis for the homology of *d*-divisible partition lattices, *Adv. Math.* **117** (1996), 294–318.