# Ferrers Graphs, D-Permutations, and Surjective Staircases

Alexander Lazar  Department of Mathematics, KTH Royal Institute of Technology,
Stockholm 114 28, Sweden<EMAIL_ADDRESS>
(Date: October 27, 2021)

###### Abstract.

We introduce a new family of hyperplane arrangements inspired by the
homogenized Linial arrangement (which was recently introduced by Hetyei), and
show that the intersection lattices of these arrangements are isomorphic to
the bond lattices of Ferrers graphs. Using recent work of Lazar and Wachs we
are able to give combinatorial interpretations of the characteristic
polynomials of these arrangements in terms of permutation enumeration. For
certain infinite families of these hyperplane arrangements, we are able to
give generating function formulas for their characteristic polynomials. To do
so, we develop a generalization of Dumont’s surjective staircases, and
introduce a polynomial which enumerates these generalized surjective
staircases according to several statistics. We prove a recurrence for these
polynomials and show that in certain special cases this recurrence can be
solved explicitly to yield a generating function. We also prove refined
versions of several of these results using the theory of complex hyperplane
arrangements.

###### Key words and phrases:

Genocchi numbers, hyperplane arrangements, characteristic polynomials, Ferrers
graphs, surjective staircases

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 Ferrers Graphs and $\Gamma_{V}$
  4. 4 Homogenized $\nu$-Arrangements
  5. 5 New Generating Function Formulas
  6. 6 General Techniques
  7. 7 Generating Function Proofs
  8. 8 Dowling Analogs
  9. 9 Final Remarks and Further Questions

##  1\. Introduction

The aim of this paper is to generalize recent results of Lazar and Wachs [14,
12] on the combinatorics of the _homogenized Linial arrangement_ in several
different directions.

The homogenized Linial arrangement, which was introduced by Hetyei in [10], is
the real hyperplane arrangement $\mathcal{H}_{2n-1}$ in

$\\{(x_{1},\dots,x_{n+1},y_{1},\dots,y_{n})\operatorname{\,|\,}x_{i},\,y_{i}\in\operatorname{\mathbb{R}}\\}=\operatorname{\mathbb{R}}^{2n+1}$

given by

$\mathcal{H}_{2n-1}=\\{x_{i}-x_{j}=y_{i}\operatorname{\,|\,}1\leq i<j\leq
n+1\\}.$

Hetyei showed that the number of regions of $\mathcal{H}_{2n-1}$ is equal to
the _median Genocchi number_ $h_{n}$. The median Genocchi numbers and their
partner sequence the _Genocchi numbers_ $g_{n}$ are classical sequences that
appear in several areas of combinatorics (see [8, 10, 14, 16, 18, 22], among
others) and number theory (e.g., [1]).

Intersecting $\mathcal{H}_{2n-1}$ with the subspace
$y_{1}=y_{2}=\cdots=y_{n}=0$ yields the braid arrangement

$\\{x_{i}-x_{j}=0\operatorname{\,|\,}1\leq i<j\leq{n+1}\\}$

in $\operatorname{\mathbb{R}}^{n+1}$, while intersecting it with
$y_{1}=y_{2}=\cdots=y_{n}=1$ yields the _Linial arrangement_

$\\{x_{i}-x_{j}=1\operatorname{\,|\,}1\leq i<j\leq n+1\\}$

in $\operatorname{\mathbb{R}}^{n+1}$. We can therefore think of
$\mathcal{H}_{2n-1}$ as being defined by a particular choice of homogenization
of the defining equations for the hyperplanes in the braid or Linial
arrangements.

In [14], Lazar and Wachs studied this arrangement further. They showed that
the intersection lattice of $\mathcal{H}_{2n-1}$ is isomorphic to the bond
lattice of a bipartite graph $\Gamma_{2n}$ and used that interpretation to
give a combinatorial interpretation of the coefficients of the characteristic
polynomial $\chi_{\mathcal{L}(\mathcal{H}_{2n-1})}(t)$ of $\mathcal{H}_{2n-1}$
in terms of a new class of permutations they called _D-permutations_.

Lazar and Wachs showed that the D-permutations on $[2n]$ are bijection with
certain elements of the class of _surjective staircases_ (due to Dumont [8]).
Using a generating function result of Randrianarivony [16] and Zeng [22] for
surjective staircases, Lazar and Wachs proved ([14, Theorem 5.5]) a generating
function formula for $\chi_{\mathcal{L}(\mathcal{H}_{2n-1})}(t)$:

(1) $\sum_{n\geq
1}\chi_{\mathcal{L}(\mathcal{H}_{2n-1})}(t)\,x^{n}=\sum_{n\geq
1}\frac{(t-1)_{n-1}(t-1)_{n}\,x^{n}}{\prod_{k=1}^{n}(1-k(t-k)x)},$

where $(a)_{n}$ denotes the falling factorial $a(a-1)\cdots(a-(n-1))$.

The various perspectives used in [14] — hyperplane arrangements, $\Gamma_{2n}$
and D-permutations, and surjective staircases — suggest several possible
avenues to generalize the results of that paper. In this paper, we consider
three of them.

In the course of [14], the authors found it useful to consider a larger class
of graphs $\Gamma_{V}$ where $V\subseteq[2n]$ for any $n$. One possible
direction for generalizing of the results of [14] would therefore be to study
the combinatorics of $\Gamma_{V}$ for arbitrary $V$. The study of these
$\Gamma_{V}$ was initiated in [14], where the authors showed that the
coefficients of the characteristic polynomial of the bond lattice of
$\Gamma_{V}$ can be interpreted in terms of the D-permutations on $V$. The
authors also noted that $\Gamma_{2n}$ belongs to a class of graphs known as
_Ferrers graphs_ , and remarked that the same was true for all $\Gamma_{V}$.

Another possible direction for generalizing [14] is suggested by the theory of
hyperplane arrangements. Beyond the braid and Linial arrangements, there are a
number of other _deformations_ of the braid arrangement (studied in detail in
[15]), such as the _Shi arrangement_

$\\{x_{i}-x_{j}=0,1\operatorname{\,|\,}1\leq i<j\leq n\\},$

_semiorder arrangement_

$\\{x_{i}-x_{j}=\pm 1\operatorname{\,|\,}1\leq i<j\leq n\\},$

and _Catalan arrangement_

$\\{x_{i}-x_{j}=-1,0,1\operatorname{\,|\,}1\leq i<j\leq n\\}.$

Therefore, one might wish to study the combinatorics of homogenizations of
these deformations. Let $\nu=(\nu_{1},\dots,\nu_{n})$ be a weak composition of
$m$. That is, $\nu$ is an ordered $n$-tuple of nonnegative integers whose sum
is $m$. For all such $\nu$, we define the _homogenized $\nu$-arrangement_
$\mathcal{H}_{\nu}$ to be

$\\{x_{i}-x_{j}=y_{i}^{(\ell)}\operatorname{\,|\,}1\leq i<j\leq
n+1,1\leq\ell\leq\nu_{i}\\}.$

For instance, taking $\nu=(2,2,\dots,2)$ gives us the arrangement

$\\{x_{i}-x_{j}=y_{i}^{(1)},y_{i}^{(2)}\operatorname{\,|\,}1\leq i<j\leq
n+1\\}.$

Intersecting this arrangement with the subspace where
$y_{1}^{(1)}=y_{2}^{(1)}=\cdots=y_{n}^{(1)}=0$ and
$y_{1}^{(2)}=y_{2}^{(2)}=\cdots=y_{n}^{(2)}=1$ yields the Shi arrangement.

The third possible direction is to generalize the notion of surjective
staircases. Surjective staircases are surjective functions
$F:[2n]\to\\{2,4,\dots,2n\\}$ that satisfy $F(x)\geq x$. A key tool used in
[14] to prove Equation (1) is the _generalized Dumont–Foata polynomial_
$\Lambda_{2n}$, which enumerates the surjective staircases with domain $[2n]$
with respect to six statistics. Randrianarivony [16] and Zeng [22] proved a
recurrence and a generating function formula for the $\Lambda_{2n}$, and it is
this formula which eventually yields Equation (1). One natural generalization
would be to consider surjective functions $F:V\to\\{\text{even elements of
}V\\}$ which satisfy $F(x)\geq x$ for any finite
$V\subset\operatorname{\mathbb{Z}}_{>0}$. Given the role that the generalized
Dumont–Foata polynomials play in [14], we also wish to define analogous
polynomials for domains other than $[2n]$.

The pleasant surprise of these three generalizations is that they remain very
closely related. In this paper, we show that for any $\nu$ the intersection
lattice of $\mathcal{H}_{\nu}$ is isomorphic to the bond lattice of some
$\Gamma_{V}$. Hence, the coefficients of the characteristic polynomial of
$\mathcal{H}_{\nu}$ have an interpretation in terms of the D-permutations on
$V$. We then develop the theory of surjective staircases with domain $V$: we
define a generalization $\Lambda_{V}$ of the generalized Dumont–Foata
polynomials $\Lambda_{2n}$ and prove a recurrence for the $\Lambda_{V}$
generalizing the Randrianarivony–Zeng recurrence for $\Lambda_{2n}$.

For certain infinite families of homogenized $\nu$-arrangements, we are able
to solve our new recurrence explicitly to obtain generating function formulas
for their corresponding $\Lambda_{V}$.

For one such family that we denote $\mathcal{H}_{n,k}$, this new machinery
lets us prove an analog of Equation (1):

(2) $\sum_{n\geq 1}\chi_{\mathcal{L}(\mathcal{H}_{n,k})}(t)u^{n}=\sum_{n\geq
1}\frac{(t-1)_{n-1}\left((t-1)_{n}\right)^{k}u^{n}}{\prod_{i=1}^{n}\left(1-i(t-i)^{k}u\right)},$

where $(a)_{n}=a(a-1)\cdots(a-(n-1))$.

These techniques also let us derive a generating function for the chromatic
polynomial of the complete bipartite graph $K_{n,k}$:

(3) $\sum_{n\geq 1}\text{ch}(K_{n,k})(t)u^{n}=\sum_{n\geq
1}\frac{(t)_{n}\left[(t-n)^{k}+(n-1)(t-(n-1))^{k-1}\right]u^{n}}{\prod_{i=0}^{n-1}(1-iu)}.$

The rest of this paper is structured as follows.

  * •

In Section 2 we state some preliminary definitions and results.

  * •

In Section 3 we give a detailed proof of the equivalence between Ferrers
graphs and the graphs $\Gamma_{V}$ (remarked without proof in [14, Remark
3.1]). This equivalence is interesting in its own right, but the language of
Ferrers graphs is also convenient for many of our later results.

  * •

In Section $4$ we formally introduce the hyperplane arrangements
$\mathcal{H}_{\nu}$. We that show each such arrangement is isomorphic to the
graphic arrangement of a Ferrers graph, and moreover that the arrangement of
any Ferrers graph can be obtained in this way.

  * •

In Section 5 we give generating function formulas for the characteristic
polynomials of two infinite families of Ferrers graphs, and also give refined
versions of these generating functions arising from complex hyperplane
arrangements (à la [12]).

  * •

In Section 6 we develop the theory of surjective staircases with arbitrary
domains, as well as the generalization $\Lambda_{V}$ of the generalized
Dumont–Foata polynomial $\Lambda_{2n}$. We state and prove a recurrence for
$\Lambda_{V}$ that extends the Randrianarivony–Zeng recurrence for
$\Lambda_{2n}$.

  * •

In Section 7 we prove the generating function formulas from Section 5.

  * •

In Section 8 we outline an extension of the results of Sections 6 and 7 to
complex hyperplane arrangements, and prove the refined generating function
formulas of Section 5.

  * •

In Section 9 we give some final remarks and questions for further study.

Many of the results of this paper were first announced in the extended
abstract [13] and appeared in detail in the author’s Ph.D. dissertation [11,
Chapter 5].

##  2\. Preliminaries

###  2.1. Hyperplane Arrangements and Geometric Lattices

A _real hyperplane arrangement_ is a finite collection $\mathcal{H}$ of
hyperplanes in $\operatorname{\mathbb{R}}^{d}$. The complement
$\operatorname{\mathbb{R}}^{d}\setminus\mathcal{H}$ consists of finitely many
connected components, which are called the _regions of $\mathcal{H}$_. The
combinatorial data of $\mathcal{H}$ can be collected into the _intersection
poset_ $\mathcal{L}(\mathcal{H})$, which consists of the intersections of
hyperplanes in $\mathcal{H}$ (viewed as affine subspaces of
$\operatorname{\mathbb{R}}^{d}$) ordered according to reverse containment. We
define the _rank_ $\mathrm{rk}(\mathcal{H})$ of $\mathcal{H}$ to be the length
of $\mathcal{L}(\mathcal{H})$.

If all of the hyperplanes in $\mathcal{H}$ have a nonempty common
intersection, we say $\mathcal{H}$ is _central_. The intersection poset of a
central arrangement is a geometric lattice, and if $\mathcal{H}$ is non-
central its intersection poset is a geometric semilattice (in the sense of
[20]).

One important invariant of a hyperplane arrangement is the _characteristic
polynomial_ $\chi_{\mathcal{L}(\mathcal{H})}(t)$ of its intersection poset. If
$P$ is any ranked poset with bottom element $\hat{0}$, its characteristic
polynomial is defined by

$\chi_{P}(t)=\sum_{X\in
P}\mu_{P}(\hat{0},X)t^{\mathrm{rk}(P)-\mathrm{rk}(X)},$

where $\mu_{P}$ is the Möbius function of $P$.

A well-known formula of Zaslavsky [21] relates the number of regions
$r(\mathcal{H})$ of $\mathcal{H}$ to the characteristic polynomial of
$\mathcal{L}(\mathcal{H})$:

(4)
$r(\mathcal{H})=(-1)^{\mathrm{rk}(\mathcal{H})}\chi_{\mathcal{L}(\mathcal{H})}(-1).$

###  2.2. Graphs and Bond Lattices

Associated to any finite graph $G$ with vertex set $V$ and edge set $E$ is the
_graphic hyperplane arrangement_ $\mathcal{H}_{G}$, which is given by

$\mathcal{H}_{G}=\\{x_{i}-x_{j}=0\operatorname{\,|\,}\\{i,j\\}\in E\\}.$

The intersection lattice of $\mathcal{H}_{G}$ is called the _bond lattice of
$G$_ and is denoted $\Pi_{G}$. An equivalent description of $\Pi_{G}$ can be
given as a subposet of the lattice $\Pi_{V}$ of set partitions of $V$. A set
partition $\pi=B_{1}|B_{2}|\cdots|B_{k}$ of $V$ belongs to $\Pi_{G}$ if and
only if the induced subgraph $G|_{B_{i}}$ is connected for all $i$.

The bond lattice of $G$ also determines the chromatic polynomial
$\mathrm{ch}(G)(t)$ in the sense that

$\mathrm{ch}(G)(t)=t\cdot\chi_{\Pi_{G}}(t).$

###  2.3. The Homogenized Linial Arrangement and D-Permutations

In [14], Lazar and Wachs considered a family of bipartite graphs $\Gamma_{V}$
for $V$ a finite subset of $\operatorname{\mathbb{Z}}_{>0}$. Given such a $V$,
$\Gamma_{V}$ is the graph on vertex set $V$ with an edge $\\{2i-1,2j\\}$
whenever $2i-1<2j$. If $V=[2n]$, we omit the brackets and write $\Gamma_{2n}$.

A permutation $\sigma\in\mathfrak{S}_{V}$ is a _D-permutation_ if
$\sigma(i)\geq i$ whenever $i$ is odd and $\sigma(i)\leq i$ whenever $i$ is
even. We write $\mathcal{D}_{V}$ for the set of $D$-permutations of $V$.

######  Example 2.1.

The elements of $\mathcal{D}_{4}$ are given below.

$(1)(2)(3)(4)$ | $(1,2)(3)(4)$ | $(1,2)(3,4)$ | $(1,4)(2)(3)$
---|---|---|---
$(1,4,2)(3)$ | $(1,3,4)(2)$ | $(3,4)(1)(2)$ | $(1,3,4,2)$

In [14], the authors compute the coefficients of $\chi_{\Pi_{\Gamma_{V}}}$ in
terms of D-permutations:

######  Theorem 2.2 ([14, Theorem 3.5]).

Let $V$ be a finite subset of $\operatorname{\mathbb{Z}}_{>0}$. For all
$\pi\in\Pi_{\Gamma_{V}}$,

$(-1)^{|\pi|}\mu_{\Pi_{\Gamma_{V}}}(\hat{0},\pi)=|\\{\sigma\in\mathcal{D}_{V}\operatorname{\,|\,}\mathrm{cyc}(\sigma)=\pi\\}|,$

where $\mathrm{cyc}(\sigma)$ is the set partition whose blocks are comprised
of the elements of the cycles of $\sigma$. Consequently,

(5) $\chi_{\Pi_{\Gamma_{V}}}(t)=\sum_{k=1}^{2n}s_{D}(V,k)t^{k-1},$

where $(-1)^{k}s_{D}(V,k)$ is equal to the number of D-permutations on $A$
with exactly $k$ cycles.

###  2.4. Ferrers Graphs

In [9], Ehrenborg and van Willigenburg introduced a family of graphs called
_Ferrers graphs_. Since their introduction, they have been studied in a
variety of contexts such as combinatorial commutative algebra [3], chip-firing
[17], matroid theory [4], and in terms of graph invariants like their Boolean
complexes [2]. A Ferrers graph is a bipartite graph on vertex partition
$R=\\{r_{1},\dots,r_{n}\\}$ and $C=\\{c_{1},\dots,c_{m}\\}$ such that if
$\\{r_{i},c_{j}\\}$ is an edge, then $\\{r_{\ell},c_{k}\\}$ is an edge for all
$i\leq\ell\leq n$ and $1\leq k\leq j$, and $\\{r_{1},c_{1}\\}$ and
$\\{r_{n},c_{m}\\}$ are edges.111Ehrenborg and van Willigenburg’s definition
is slightly different from ours — they reverse the indexes of the $r$’s. To
any Ferrers graph $G$, we can associate an integer partition
$\lambda=(\lambda_{n},\dots,\lambda_{1})$, where $\lambda_{i}$ is the degree
of $r_{i}$ in $G$. Note that we are distinguishing between $R$ and $C$ in this
definition.

If we draw the Ferrers diagram for $\lambda$, label the rows $r_{1}$ through
$r_{n}$ from bottom to top, and label the columns $c_{1}$ through $c_{m}$ from
left to right, then the Ferrers diagram for $\lambda$ will have a square in
the row labeled $r_{i}$ and column labeled $c_{j}$ if and only if
$\\{r_{i},c_{j}\\}$ is an edge of $G$.

######  Example 2.3.

The graph $\Gamma_{6}$ on vertex set $R=\\{2,4,6\\}$ and $C=\\{1,3,5\\}$ is
shown below:

It is not hard to see that $\Gamma_{6}$ is a Ferrers graph with associated
partition $\lambda=(3,2,1)$, whose Ferrers diagram is seen below:

[] & [1] [3] [5]

[6]

[4]

[2]

The following proposition is an immediate consequence of the Ferrers diagram
description of the edges of a Ferrers graph.

######  Proposition 2.4.

If $G$ and $H$ are Ferrers graphs, then $G\cong H$ if and only if $G$ and $H$
have the same associated partition, or have conjugate associated partitions.

##  3\. Ferrers Graphs and $\Gamma_{V}$

Let $V$ be a finite subset of $\operatorname{\mathbb{Z}}_{>0}$. Let $O(V)$ be
the set of odd elements of $V$ and let $E(V)$ be the set of even elements of
$V$. Suppose that $O(V)=\\{2i_{1}-1<\cdots<2i_{n}-1\\}$ and
$E(V)=\\{2j_{1}<\cdots<2j_{m}\\}$. We define the _partition type_ of $V$,
denoted $\lambda(V)$, as follows. For each $k\in[m]$, let
$\lambda_{k}\coloneqq\\#\\{a\operatorname{\,|\,}2i_{a}-1<2j_{k}\\}$. Then
$\lambda_{m}\geq\cdots\geq\lambda_{1}$, so
$\lambda=(\lambda_{m},\dots,\lambda_{1})$ is an integer partition.

######  Example 3.1.

Suppose that $V=\\{1,3,7,9\\}\sqcup\\{2,4,6,10\\}$. Then
$\lambda(V)=(4,2,2,1)$. The Ferrers diagram of $(4,2,2,1)$ is shown below,
with the rows labeled by the even elements of $V$ and the columns labeled by
the odd elements of $V$:

[] & [1] [3] [7] [9]

[10]

[6]

[4]

[2] .

The following theorem explains our choice of labeling in the previous example.

######  Theorem 3.2.

Let $V$ be a finite subset of $\operatorname{\mathbb{Z}}_{>0}$ such that $\max
V$ is even and $\min V$ is odd. Then $\Gamma_{V}$ is a Ferrers graph with
$R=E(V)$ and $C=O(V)$. Moreover the partition associated to $\Gamma_{V}$ is
$\lambda(V)$. Conversely, given a Ferrers graph $G$, there is a finite subset
$V$ of $\operatorname{\mathbb{Z}}_{>0}$ such that $\Gamma_{V}\cong G$.

###### Proof.

Recall that $\Gamma_{V}$ has an edge between $2i-1$ and $2j$ if and only if
$2i-1<2j$. We see that $\\{2i_{1}-1,2j_{1}\\}$ is an edge of $\Gamma_{V}$
(since $\min V=2i_{1}-1$), and $\\{2i_{m}-1,2j_{n}\\}$ is an edge (since
$2j_{n}=\max V$). Moreover, if $\\{2i_{a}-1,2j_{b}\\}$ is an edge of
$\Gamma_{V}$ then $\\{2i_{k}-1,2j_{\ell}\\}$ is an edge of $\Gamma_{V}$ for
all $1\leq k\leq a$ and all $b\leq\ell\leq n$, since $2i_{k}-1\leq
2i_{a}-1<2j_{b}\leq 2j_{\ell}$. Hence, $\Gamma_{V}$ is a Ferrers graph with
$R=E(V)$ and $C=O(V)$, and moreover the associated partition of $\Gamma_{V}$
is $\lambda(V)$ by the definition of $\lambda(V)$.

Conversely, suppose that $G$ is a Ferrers graph on vertex set
$R=\\{r_{1},\dots,r_{n}\\}$ and $C=\\{c_{1},\dots,c_{m}\\}$. Associated to $G$
is the integer partition $\lambda$ given by $\lambda_{i}=\deg r_{i}$. We
construct a set $V_{\lambda}$ from the Ferrers diagram of $\lambda$ as
follows. Let $V_{0}=\\{0\\}$.

  1. (1)

Start at the southwest corner of the Ferrers diagram for $\lambda$, and walk
the path along the lower border of the Ferrers diagram.

  2. (2)

If the $i$th step is to the east, label the edge we have just traversed with
the smallest odd integer $2k-1$ larger than $\max V_{i-1}$ and let
$V_{i}\coloneqq V_{i-1}\cup\\{2k-1\\}$.

  3. (3)

If the $i$th step is to the north, label the edge we have just traversed with
the smallest even integer $2k$ larger than $\max V_{i-1}$ and let
$V_{i}\coloneqq V_{i-1}\cup\\{2k\\}$.

  4. (4)

Stop when the northeast corner of the Ferrers diagram is reached, after $m+n$
steps. We define $V_{\lambda}\coloneqq V_{n+m}\setminus\\{0\\}$.

Note that $\min V_{\lambda}$ is odd and $\max V_{\lambda}$ is even, since our
walk must start with a step to the east and end with a step north. Thus,
$\Gamma_{V_{\lambda}}$ is a Ferrers graph by our previous argument. By
Proposition 2.4, to show that $\Gamma_{V_{\lambda}}\cong G$, it suffices to
show that $\lambda(V_{\lambda})=\lambda$. Indeed, $\lambda_{i}$ is the number
of squares in the $i$th row from the bottom of the Ferrers diagram for
$\lambda$. By construction, the number of squares in the $i$th row from the
bottom of the Ferrers diagram is equal to the number of odd elements of
$V_{\lambda}$ that are smaller than the $i$th smallest even element $2j_{i}$
of $V$. But by definition, this quantity is equal to
$\lambda(V_{\lambda})_{i}$. Hence, $\lambda(V_{\lambda})=\lambda$. ∎

Our construction of $V_{\lambda}$ is very similar to the _ab -word_
construction in [9], which Ehrenborg and van Willigenburg use to give a
formula for the chromatic polynomial of $G_{\lambda}$.

The following corollary is an immediate consequence of Proposition 2.4 and
Theorem 3.2.

######  Corollary 3.3.

Let $V$ and $W$ be finite sets of positive integers such that $\min V$, $\min
W$ are odd and $\max V$, $\max W$ are even. Then $\Gamma_{V}\cong\Gamma_{W}$
if and only if $\lambda(V)=\lambda(W)$.

######  Remark 3.4.

Let $G$ be a Ferrers graph. By [14, Theorem 4.10] we see that

$\text{ch}_{G}(t)=\sum_{\sigma\in\mathcal{D}_{V}}(-t)^{c(\sigma)},$

where $c(\sigma)$ is the number of cycles of $\sigma$, and $V$ is the set
constructed from $G$ in our proof of Theorem 3.2.

##  4\. Homogenized $\nu$-Arrangements

Let $\nu=(\nu_{1},\nu_{2},\dots,\nu_{n})$ be a weak composition of $m$. We
define the _homogenized $\nu$-arrangement_ in

$(x_{1},x_{2},\dots,x_{n+1},y_{1}^{(1)},y_{1}^{(2)},\dots,y_{1}^{(\nu_{1})},y_{2}^{(1)},\dots,y^{(\nu_{2})}_{2},\dots,y_{n}^{(1)},\dots,y_{n}^{(\nu_{n})})=\operatorname{\mathbb{R}}^{m+n+1}$

to be

$\mathcal{H}_{\nu}=\\{x_{i}-x_{j}=y_{i}^{(\ell)}\operatorname{\,|\,}1\leq
i<j\leq n+1,1\leq\ell\leq\nu_{i}\\}.$

Notice that when $\nu=(1,1,\dots,1)$, $\mathcal{H}_{\nu}=\mathcal{H}_{2n-1}$.
Our goal for this section is to study these homogenized $\nu$-arrangements by
relating them to Ferrers graphs.

Let $\lambda(\nu)$ be the partition
$(\nu_{1}+\cdots+\nu_{n},\dots,\nu_{1}+\nu_{2},\nu_{1})$. We construct a
Ferrers graph $G_{\nu}$ from $\nu$ by labeling the columns of the Ferrers
diagram for $\lambda(\nu)$ from left to right by

$1^{(1)},1^{(2)},\dots,1^{(\nu_{1})},3^{(1)},3^{(2)},\dots,3^{(\nu_{2})},\dots,(2n-1)^{(1)},(2n-1)^{(2)},\dots,(2n-1)^{(\nu_{n})}$

and labeling the rows of the Ferrers diagram from bottom to top by

$2,4,6,\dots,2n.$

Then $G_{\nu}$ is the Ferrers graph on vertex set $C\sqcup R$, where

$C=\\{1^{(1)},\dots,1^{(\nu_{1})},3^{(1)},\dots,3^{(\nu_{2})},\dots,(2n-1)^{(1)},\dots,(2n-1)^{(\nu_{n})}\\}$

and

$R=\\{2,\dots,2n\\},$

whose edges are $\\{(2i-1)^{(\ell)},2j\\}$ for all $2i-1<2j$ and
$1\leq\ell\leq\nu_{i}$.

######  Example 4.1.

Let $\nu=(3,3,3)$. The Ferrers diagram for $\lambda(\nu)=(9,6,3)$, together
with the labels described above, is shown below.

$\ytableau\none&\none[1^{(1)}]\none[1^{(2)}]\none[1^{(3)}]\none[3^{(1)}]\none[3^{(2)}]\none[3^{(3)}]\none[5^{(1)}]\none[5^{(2)}]\none[5^{(3)}]\\\
\none[6]\;\;\;\;\;\;\;\;\;\\\ \none[4]\;\;\;\;\;\;\\\ \none[2]\;\;\;.$

######  Theorem 4.2.

For all weak compositions $\nu=(\nu_{1},\dots,\nu_{n})$ of $m$, there is an
invertible $\operatorname{\mathbb{Z}}$-linear transformation from
$\operatorname{\mathbb{R}}^{m+n+1}$ to itself that takes $\mathcal{H}_{\nu}$
to the graphic hyperplane arrangement $\mathcal{A}_{G_{\nu}}$. Consequently,
$\mathcal{L}(\mathcal{H}_{\nu})\cong\Pi_{G_{\nu}}$.

###### Proof.

Let $(e_{1},\dots,e_{m+n+1})$ be the standard basis for
$\operatorname{\mathbb{R}}^{m+n+1}$. For notational convenience, we define
vectors $u_{i}$ and $u_{i}^{(j)}$ by setting

$\displaystyle(u_{1}^{(1)},u_{1}^{(2)},\dots,u_{1}^{(\nu_{1})},$
$\displaystyle
u_{2},u_{3}^{(1)},\dots,u_{3}^{(\nu_{2})},u_{4},\dots,u_{2n-1}^{(1)},\dots,u_{2n-1}^{(\nu_{n})},u_{2n},u_{m+n+1})$
$\displaystyle=(e_{1},\dots,e_{m+n+1}),$

and also define $v_{i}$ and $v_{i}^{(j)}$ by setting

$\displaystyle(v_{1},v_{2},\dots,v_{n+1},v_{n+2}^{(1)},\dots,v_{n+2}^{(\nu_{1})},$
$\displaystyle
v_{n+3}^{(1)},\dots,v_{n+3}^{(\nu_{2})},\dots,v_{2n+1}^{(1)},\dots,v_{2n+1}^{(\nu_{n})})$
$\displaystyle=(e_{1},\dots,e_{m+n+1}).$

For all $1\leq i\leq j\leq n$ and all $1\leq\ell\leq\nu_{i}$, we define the
hyperplane

$K_{i,j}^{(\ell)}=\\{w\in\operatorname{\mathbb{R}}^{m+n+1}\operatorname{\,|\,}(u_{2i-1}^{(\ell)}-u_{2j})\cdot
w=0\\},$

and the arrangement

$\mathcal{K}=\\{K_{i,j}^{\ell}\operatorname{\,|\,}1\leq i\leq j\leq
n,\;1\leq\ell\leq\nu_{i}\\}.$

We observe that $\mathcal{K}\cong\mathcal{A}_{G_{\nu}}$. Indeed, $\mathcal{K}$
is the graphic hyperplane arrangement of the graph on $m+n+1$ vertices
obtained from $G_{\nu}$ by adjoining an isolated vertex $m+n+1$.

Now, for all $1\leq i\leq j\leq n$ and $1\leq\ell\leq\nu_{i}$, we write

$H_{i,j}^{\ell}=\\{w\in\operatorname{\mathbb{R}}^{m+n+1}\operatorname{\,|\,}(v_{i}-v_{j+1}-v_{n+i+1}^{(\ell)})\cdot
w=0\\}.$

Clearly,

$\mathcal{H}_{\nu}=\\{H_{i,j}^{\ell}\operatorname{\,|\,}1\leq i\leq j\leq
n,\;1\leq\ell\leq\nu_{i}\\}.$

Now, consider the linear transformation $\phi$ from
$\operatorname{\mathbb{R}}^{m+n+1}$ to itself, given by

  * •

$\phi(u_{2i-1}^{\ell})=v_{i}-v_{n+i+1}^{(\ell)}$,

  * •

$\phi(u_{2j})=v_{j+1}$,

  * •

$\phi(u_{m+n+1})=v_{1}$.

To show that this $\operatorname{\mathbb{Z}}$-linear transformation is
invertible, we define the linear transformation $\tilde{\phi}$ from
$\operatorname{\mathbb{R}}^{m+n+1}$ to itself on the standard basis as
follows:

  * •

$\tilde{\phi}(v_{1})=u_{m+n+1}$,

  * •

$\tilde{\phi}(v_{i})=u_{2i-2}$ for $2\leq i\leq n+1$,

  * •

$\tilde{\phi}(v_{n+2}^{(\ell)})=u_{\lambda_{n}+n+1}-u_{1}^{(\ell)}$ for
$\ell\in[\nu_{1}]$,

  * •

$\tilde{\phi}(v_{n+i+1}^{(\ell)})=u_{2i-2}-u_{2i-1}^{(\ell)}$ for $1<i\leq n$
and $\ell\in[\nu_{i}]$.

We see that

  * •

$\phi(\tilde{\phi}(v_{1}))=\phi(u_{m+n+1})=v_{1}$

  * •

$\phi(\tilde{\phi}(v_{i}))=\phi(u_{2i-2})=v_{i}$ for $2\leq i\leq n+1$

  * •

$\phi(\tilde{\phi}(v_{n+2}^{(\ell)}))=\phi(u_{m+n+1}-u_{1}^{(\ell)})=v_{1}-(v_{1}-v_{n+2}^{(\ell)})=v_{n+2}^{(\ell)}$
for $\ell\in[\nu_{1}]$

  * •

$\phi(\tilde{\phi}(v_{n+i+1}^{(\ell)}))=\phi(u_{2i-2}-u_{2i-1}^{(\ell)})=v_{i}-(v_{i}-v_{n+i+1}^{(\ell)})=v_{n+i+1}^{(\ell)}$
for $2\leq i\leq n$, $\ell\in[\nu_{i}]$.

Hence, $\phi$ is invertible, so let $A$ be the matrix of $\phi$ with respect
to the standard basis and let $\psi$ be the linear operator on
$\operatorname{\mathbb{R}}^{m+n+1}$ whose matrix in the standard basis is
$(A^{-1})^{T}$.

We claim that $\psi$ takes each hyperplane $K_{i,j}^{\ell}$ to the
corresponding hyperplane $H_{i,j}^{\ell}$. Indeed, suppose $w\in
K_{i,j}^{\ell}$ so $(u_{2i-1}^{(\ell)}-u_{2j})\cdot w=0$. Then

$\phi(u_{2i-1}^{(\ell)}-u_{2j})\cdot\psi(w)=(v_{i}-v_{n+i+1}^{(\ell)}-v_{j+1})\cdot\psi(w),$

and

$\displaystyle\phi(u_{2i-1}^{(\ell)}-u_{2j})\cdot\psi(w)$
$\displaystyle=A(u_{2i-1}^{(\ell)}-u_{2j})\cdot((A^{-1})^{T}w)$
$\displaystyle=(A^{-1}A(u_{2i-1}^{(\ell)}-u_{2j}))\cdot w$
$\displaystyle=(u_{2i-1}^{(\ell)}-u_{2j})\cdot w$ $\displaystyle=0,$

so $(v_{i}-v_{n+i+1}^{(\ell)}-v_{j+1})\cdot\psi(w)=0$. Hence, $\psi(w)\in
H_{i,j}^{(\ell)}$, which proves the claim. ∎

##  5\. New Generating Function Formulas

In this section we present generating function formulas for two infinite
families of Ferrers graphs. The proofs of these formulas rely on techniques
that we develop in Section 6, so we defer the proofs to Sections 7 and 8.

###  5.1. $k$-Staircases

For any $n,k\geq 1$, we define the _$k$ -staircase with $n$ steps_ to be the
partition $\lambda_{k}^{(n)}=(nk,(n-1)k,\dots,k)$. The case $n=4$ and $k=3$ is
shown below.

$\ytableau\;&\;\;\;\;\;\;\;\;\;\;\;\\\ \;\;\;\;\;\;\;\;\;\\\ \;\;\;\;\;\;\\\
\;\;\;$

######  Theorem 5.1.

Fix $k\geq 1$. For any sequence of subsets $V_{1}^{k},V_{2}^{k},\dots$ of
$\operatorname{\mathbb{Z}}_{>0}$ with $\lambda(V_{n}^{k})=\lambda^{(n)}_{k}$,
we have the following generating function formula for
$\chi_{\Pi_{\Gamma_{V_{n}^{k}}}}(t)$:

$\sum_{n\geq 1}\chi_{\Pi_{\Gamma_{V_{n}^{k}}}}(t)u^{n}=\sum_{n\geq
1}\frac{(t-1)_{n-1}\left((t-1)_{n}\right)^{k}u^{n}}{\prod_{i=1}^{n}\left(1-i(t-i)^{k}u\right)},$

where $(x)_{n}=x(x-1)\cdots(x-(n-1))$.

This generating function formula (and equivalently the formula in Corollary
5.3) reduces to [14, Equation (1.9)] when $k=1$; notice that when $k=1$,
$\Gamma_{V_{n}^{k}}\cong\Gamma_{2n}$. Applying Theorem 3.2 and the fact that
$t\chi_{\Pi_{G}}(t)$ is the chromatic polynomial of $G$, we can restate
Theorem 5.1 as follows:

######  Corollary 5.2.

For each $n,k\geq 1$, let $G_{n,k}$ be a Ferrers graph whose associated
partition is $\lambda_{k}^{(n)}$. Then we have the following generating
function formula for the chromatic polynomial $\text{ch}_{G_{n,k}}(t)$:

$\sum_{n\geq 1}\text{ch}_{G_{n,k}}(t)u^{n}=\sum_{n\geq
1}\frac{(t)_{n}\left((t-1)_{n}\right)^{k}u^{n}}{\prod_{i=1}^{n}\left(1-i(t-i)^{k}u\right)}.$

As a consequence of Theorem 4.2, we can view the generating function formula
of Theorem 5.1 as a generating function formula for the characteristic
polynomials of the homogenized $(k,k,\dots,k)$-arrangements, as seen in
Equation (2):

######  Corollary 5.3.

Let $\mathcal{H}_{n,k}\coloneqq\mathcal{H}_{(k,k,\dots,k)}$. Then

$\sum_{n\geq 1}\chi_{\mathcal{L}(\mathcal{H}_{n,k})}(t)u^{n}=\sum_{n\geq
1}\frac{(t-1)_{n-1}\left((t-1)_{n}\right)^{k}u^{n}}{\prod_{i=1}^{n}\left(1-i(t-i)^{k}u\right)}.$

If we define an appropriate complex hyperplane arrangement
$\mathcal{H}_{n,k}^{m}$, then by combining the techniques from this paper and
[11, Chapter 4] (see also the forthcoming paper [12]), we can compute an
$m$-analog of the generating function from Theorem 5.1:

######  Theorem 5.4.

Let $\mathcal{H}_{n,k}^{m}$ be the hyperplane arrangement in

$\\{(x_{1},\dots,x_{n},y_{1}^{(1)},\dots,y_{1}^{(k)},\dots,y_{n}^{(1)},\dots,y_{n}^{(k)})\operatorname{\,|\,}x_{i},y_{j}^{(\ell)}\in\operatorname{\mathbb{C}}\\}=\operatorname{\mathbb{C}}^{nk+n}$

given by

$\displaystyle\mathcal{H}_{n,k}^{m}=$
$\displaystyle\\{x_{i}-\omega^{p}x_{j}=y_{i}^{(\ell)}\operatorname{\,|\,}1\leq
i<j\leq n,0\leq p\leq m-1,1\leq\ell\leq k\\}$
$\displaystyle\cup\\{x_{i}=y^{(\ell)}_{i}\operatorname{\,|\,}1\leq i\leq
n,1\leq\ell\leq k\\},$

where $\omega=e^{\frac{2\pi i}{m}}$. Then

(6) $\sum_{n\geq
1}\chi_{\mathcal{L}(\mathcal{H}_{n,k}^{m})}(t)u^{n-1}=\sum_{n\geq
1}\frac{(t-1)_{n-1,m}\left((t-1)_{n,m}\right)^{k}u^{n-1}}{\prod_{i=0}^{n-1}\left(1-(im+1)(t-(im+1))^{k}u\right)},$

where $(x)_{n,m}=x(x-m)\cdots(x-(n-1)m)$.

Note that this equation specializes to [12, 11, Equation (1.11)] when $k=1$.

###  5.2. Complete Bipartite Graphs

Let $T_{n}^{k}\coloneqq\\{1,3,5,\dots,2k-1\\}\sqcup\\{2k,\dots,2(k+n-1)\\}$.
We note that $\lambda(T_{n}^{k})=\mu_{k}^{(n)}$ where $\mu_{k}^{(n)}$ is the
rectangular shape $(\underbrace{k,k,\dots,k}_{n})$. The partition
$\mu_{3}^{(4)}$ is shown below.

$\ytableau\;&\;\;\\\ \;\;\;\\\ \;\;\;\\\ \;\;\;$

It is clear that the Ferrers graph $\Gamma_{T_{n}^{k}}$ is the complete
bipartite graph $K_{n,k}$. The chromatic polynomial of $K_{n,k}$ has been
well-studied (Swenson gives a closed form expression for it in [19], and
Ehrenborg and van Willigenburg give a different proof in [9]). Using our
techniques, we give a generating function formula for its chromatic
polynomial.

######  Theorem 5.5.

For all $k\geq 1$, we have

$\sum_{n\geq 1}\text{ch}(K_{n,k})(t)u^{n}=\sum_{n\geq
1}\frac{(t)_{n}\left[(t-n)^{k}+(n-1)(t-(n-1))^{k-1}\right]u^{n}}{\prod_{i=0}^{n-1}(1-iu)}.$

We can also give an $m$-analog of the generating function for the
characteristic polynomial of the complete bipartite graph.

######  Theorem 5.6.

Let $\mathcal{J}_{n,k}^{m}$ be the hyperplane arrangement in

$\\{(x_{1},\dots,x_{n},y^{(1)},\dots,y^{(k)})\operatorname{\,|\,}x_{i},y^{(j)}\in\operatorname{\mathbb{C}}\\}=\operatorname{\mathbb{C}}^{n+k}$

given by

$\mathcal{J}_{n,k}^{m}=\\{x_{1}-\omega^{p}x_{j}=y^{(\ell)}\operatorname{\,|\,}1<j\leq
n,0\leq p\leq m-1,1\leq\ell\leq
k\\}\cup\\{x_{1}=y^{(\ell)}\operatorname{\,|\,}1\leq\ell\leq k\\},$

where $\omega=e^{\frac{2\pi i}{m}}$.

Then $\chi_{\mathcal{J}_{1,k}^{m}}(t)=(t-1)^{k}$ and

$\displaystyle\sum_{n\geq 2}$
$\displaystyle\chi_{\mathcal{J}_{n,k}^{m}}(t)u^{n-1}$
$\displaystyle=\sum_{n\geq
2}\frac{(t-1)_{n-1,m}\left[(t-1-m(n-1))^{k}+(m(n-2)+1)(t-1-m(n-2))^{k-1}\right]u^{n-1}}{\prod_{i=0}^{n-2}\left[1-(mi+1)u\right]}.$

##  6\. General Techniques

In this section we will state and prove several technical results generalizing
the theory of surjective staircases, which were introduced by Dumont in [8]
(this theory was used in [14] to study the homogenized Linial arrangement).
These results will be used in Sections 7 and 8 to prove the results of Section
5.

###  6.1. Generalized Surjective Staircases

Let $S$ be a finite subset of the positive integers with largest element $2n$.
We define the _staircase diagram of $S$_ to be the Ferrers diagram whose rows
are labeled from bottom to top with the even elements of $S$ in increasing
order and whose columns are labeled from left to right with all of the
elements of $S$ in increasing order, with a cell in the row labeled $2i$ and
column labeled $j$ if and only if $j\leq 2i$. Note that the staircase diagram
of $S$ is not the same as the Ferrers diagram of the partition $\lambda(S)$
defined in Section 3 — we can recover $\lambda(S)$ from the staircase diagram
of $S$ by deleting the columns labeled with the even elements of $S$.

Let $S^{\prime}$ be the subset of $S$ obtained by removing $2n$ and all odd
elements between $2m$ and $2n$ from $S$, where $2m$ is the second-largest even
element of $S$ (if $S$ contains only one even element,
$S^{\prime}=\emptyset$). We can view $S^{\prime}$ as the set whose staircase
diagram is obtained by deleting the top row of the staircase diagram of $S$.
Similarly, let $S^{\prime\prime}$ be the set whose staircase diagram is
obtained from the staircase diagram of $S^{\prime}$ by deleting the top row of
its staircase diagram.

######  Example 6.1.

Suppose that $S=\\{1,2,4,5,7,8\\}$. The staircase diagram for $S$ is seen
below.

& [1] [2] [4] [5] [7] [8]

[8]

[4]

[2]

In this case, $S^{\prime}=\\{1,2,4\\}$. The staircase diagram for $S^{\prime}$
is seen below.

& [1] [2] [4]

[4]

[2]

Finally, $S^{\prime\prime}=\\{1,2\\}$. The staircase diagram for
$S^{\prime\prime}$ is seen below.

& [1] [2]

[2]

We say a function $F:S\to S$ is excedent if $F(x)\geq x$ for all $x\in S$. A
_generalized sujective staircase_ is a surjective excedent map $F$ from $S$ to
the set of even elements of $S$. Let $\mathcal{X}_{S}$ be the set of all
excedent functions $F:S\to S$ and $\mathcal{E}_{S}$ be the set of all
generalized surjective staircases with domain $S$.

For all $F\in\mathcal{E}_{S}$, we define

$w(F)=x^{\text{mo}(F)}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{\text{me}(F)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)},$

and

$\Lambda_{S}(x,y,z,\bar{x},\bar{y},\bar{z})=\sum_{F\in\mathcal{E}_{S}}w(F),$

where the statistics are defined as follows:

  * •

$2i-1\in S^{\prime}$ is a _surfixed point_ of $F$ if $F(2i-1)$ is the least
even element of $S$ larger than $2i-1$. A surfixed point $2i-1$ is _isolated_
if there is no $j$ with $F(j)=F(2i-1)$ and _doubled_ otherwise. We write
$\text{si}(F)$ and $\text{sd}(F)$ for the numbers of isolated and doubled
surfixed points, respectively.

  * •

$2i\in S^{\prime}$ is a _fixed point_ of $F$ if $F(2i)=2i$. A fixed point $2i$
is _isolated_ if there is no $j$ with $F(j)=2i$ and is _doubled_ otherwise. We
write $\text{fd}(F)$ and $\text{fi}(F)$ for the numbers of isolated and
doubled fixed points, respectively.

  * •

$2i-1\in S^{\prime}$ is an _odd maximum_ of $F$ if $F(2i-1)=2n$ and $2i\in
S^{\prime}$ is an _even maximum_ of $F$ if $F(2i)=2n$. We write $\text{mo}(F)$
and $\text{me}(F)$ for the numbers of odd and even maxima of $F$,
respectively.

Note that elements of $S\setminus S^{\prime}$ do not count as maxima or
(sur)fixed points.

Generalized surjective staircases can be visualized using fillings of
staircase diagrams of $S$.

######  Example 6.2.

The following surjective staircase has weight $z\bar{x}\bar{y}$:

& [1] [2] [4] [5] [7] [8]

[8] X X X X

[4] X

[2] X .

When $S=[2n]$, these polynomials specialize to the _generalized Dumont–Foata
polynomials_ $\Lambda_{2n}$. The generalized Dumont–Foata polynomials were
introduced by Dumont in [6], and Randrianarivony [16] and Zeng [22]
independently proved a generating function formula for them.

######  Remark 6.3.

It is clear to see that $\Lambda_{S}$ depends only on $\lambda(S)$. That is,
if $S$ and $T$ are two finite sets of integers with $\lambda(S)=\lambda(T)$,
then the polynomials $\Lambda_{S}$ and $\Lambda_{T}$ are also equal.

######  Theorem 6.4.

Let $S$ be a finite set of positive integers whose largest element is even.
Suppose that $S^{\prime}\setminus S^{\prime\prime}$ contains $\ell$ odd
elements. Then,

  1. (1)

If $|S^{\prime}|=0$, $\Lambda_{S}=1$.

  2. (2)

If $|S^{\prime}|\geq 1$,

$\displaystyle\Lambda_{S}(x,y,z,\bar{x},\bar{y},\bar{z})=$
$\displaystyle(y+\bar{x})(x+\bar{z})^{\ell}\Lambda_{S^{\prime}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z})$
$\displaystyle+x^{\ell-1}[x(\bar{y}-y)+\ell\bar{x}(z-\bar{z})-x\bar{x}]\Lambda_{S^{\prime}}(x,y,z,\bar{x},\bar{y},\bar{z}).$

When $\ell=1$, this is the same as the recurrence for $\Lambda_{2n}$ in terms
of $\Lambda_{2n-2}$ from [16, Theorem 3] and [22, Theorem 4]. Indeed, our
proof generalizes the techniques used in Zeng’s proof of [22, Theorem 4]. Our
proof requires the following lemma.

######  Lemma 6.5.

Given a surjective staircase $F\in\mathcal{E}_{S^{\prime}}$ construct a
surjective staircase $\hat{F}_{X}\in\mathcal{E}_{S}$ by choosing a proper
subset $X$ of $F^{-1}(2m)$, where $2m=\max S^{\prime}$, and defining
$\hat{F}_{X}$ by

$\hat{F}_{X}(a)=\begin{cases}2n,&a\in X\cup(S\setminus S^{\prime})\\\
F(a),&\text{otherwise}\end{cases}.$

This map $(F,X)\mapsto\hat{F}_{X}$ is a well-defined bijection from the set of
pairs $(F,X)$ where $F\in\mathcal{E}_{S^{\prime}}$ and $X\subsetneq
F^{-1}(2m)$ to $\mathcal{E}_{S}$.

###### Proof.

Diagramatically, $\hat{F}_{X}$ is obtained from $F$ by adding a new top row to
the staircase diagram for $F$, moving a proper subset of the filled squares in
the top row of $F$ to this new top row, and filling all of the squares
corresponding to the elements of $S\setminus S^{\prime}$. ∎

######  Example 6.6.

Let $S=\\{1,2,4,5,7,8\\}$. Then $S^{\prime}=\\{1,2,4\\}$. Suppose that
$F\in\mathcal{E}_{S^{\prime}}$ is the surjective staircase pictured below, and
$X=\\{2\\}$.

& [1] [2] [4]

[4] *(red) X X

[2] X

Then $\hat{F}_{X}\in\mathcal{E}_{S}$ is the following surjective staircase.

& [1] [2] [4] [5] [7] [8]

[8] X X X X

[4] X

[2] X

###### Proof of Theorem 6.4.

If $|S^{\prime}|=0$, then $|\Lambda_{S}|=1$ and the weight of that surjective
staircase must be $1$.

Now, suppose $|S^{\prime}|\geq 1$. We proceed by using Lemma 6.5 to compute
$\Lambda_{S}$ in terms of $\Lambda_{S^{\prime}}$.

Given a pair $(X,F)$, we wish to compute $w(\hat{F}_{X})$ in terms of $w(F)$
and $X$. Let $\text{MO}(F)$ and $\text{ME}(F)$ be the sets of odd and even
maxima of $F$, respectively (so $|\text{MO}(F)|=\text{mo}(F)$ and
$|\text{ME}(F)|=\text{me}(F)$). Furthermore, let $O(X)$ and $E(X)$ be the
numbers of odd and even elements of $X$, respectively.

Case 1. Suppose that $2m\notin X$.

If $X=F^{-1}(2m)\setminus\\{2m\\}$, then

$\displaystyle w(\hat{F}_{X})$
$\displaystyle=x^{\text{mo}(F)+\ell}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{\text{me}(F)}\bar{y}^{\text{fi}(F)+1}\bar{z}^{\text{sd}(F)}$
$\displaystyle=x^{\ell}\bar{y}w(F).$

Thus, the set of all such $\hat{F}_{X}$ contribute
$x^{\ell}\bar{y}\Lambda_{S^{\prime}}$ to $\Lambda_{S}$.

Now, suppose that $X$ contains exactly $k$ of the $\ell$ odd elements of
$S^{\prime}\setminus S^{\prime\prime}$ for $0\leq k\leq\ell$, but that
$X\subsetneq F^{-1}(2m)\setminus\\{2m\\}$. Then $O(X)\geq k$, since the new
maxima of $\hat{F}_{X}$ consist of some subset of the odd maxima of $F$ along
with the $k$ odd elements of $|T\setminus U|$. Hence we have

$\displaystyle w(\hat{F}_{X})$
$\displaystyle=x^{O(X)}y^{\text{fd}(F)+1}z^{\text{si}(F)}\bar{x}^{E(X)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)+(\ell-k)}$
$\displaystyle=x^{k}y\bar{z}^{\ell-k}\left(x^{O(X)-k}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{E(X)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}\right).$

Any such $X$ can be obtained by choosing subsets $A$ and $B$ of the odd and
even maxima of $F$, respectively, and then choosing $k$ elements of
$S^{\prime}\setminus S^{\prime\prime}$ in $\binom{\ell}{k}$ ways. Thus, when
$k<\ell$ we see

$\displaystyle\sum_{F\in\mathcal{E}_{S^{\prime}}}$
$\displaystyle\sum_{\begin{subarray}{c}X\subsetneq
F^{-1}(2m)\setminus\\{2m\\}\\\ |X\cap(S^{\prime}\setminus
S^{\prime\prime})|=k\end{subarray}}w(\hat{F}_{X})$
$\displaystyle=\sum_{F\in\mathcal{E}_{S^{\prime}}}\sum_{\begin{subarray}{c}X\subsetneq
F^{-1}(2m)\setminus\\{2m\\}\\\ |X\cap(S\setminus
S^{\prime\prime})|=k\end{subarray}}x^{k}y\bar{z}^{\ell-k}\left(x^{O(X)-k}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{E(X)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}\right)$
$\displaystyle=y\sum_{F\in\mathcal{E}_{S^{\prime}}}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}\binom{\ell}{k}x^{k}\bar{z}^{\ell-k}\sum_{A\times
B\subseteq\text{MO}(F)\times\text{ME}(F)}x^{|A|}\bar{x}^{|B|}$
$\displaystyle=y\binom{k}{\ell}x^{k}\bar{z}^{\ell-k}\sum_{F\in\mathcal{E}_{S^{\prime}}}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}(x+1)^{\text{mo}(F)}(\bar{x}+1)^{\text{me}(F)}$
$\displaystyle=y\binom{k}{\ell}x^{k}\bar{z}^{\ell-k}\Lambda_{S^{\prime}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z}).$

Meanwhile, when $k=\ell$, $X$ must consist of the $\ell$ odd elements of
$S^{\prime}\setminus S^{\prime\prime}$ along with a _proper_ subset of the
maxima of $F$ (we considered the case when $X$ contained all of
$F^{-1}(2m)\setminus\\{2m\\}$ already). This yields

$\displaystyle\sum_{F\in\mathcal{E}_{S^{\prime}}}$
$\displaystyle\sum_{\begin{subarray}{c}X\subsetneq
F^{-1}(2m)\setminus\\{2m\\}\\\ |X\cap(S^{\prime}\setminus
S^{\prime\prime})|=k\end{subarray}}w(\hat{F}_{X})$
$\displaystyle=\sum_{F\in\mathcal{E}_{S^{\prime}}}\sum_{\begin{subarray}{c}X\subsetneq
F^{-1}(2m)\setminus\\{2m\\}\\\ |X\cap(S^{\prime}\setminus
S^{\prime\prime})|=\ell\end{subarray}}x^{\ell}y\left(x^{O(X)-\ell}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{E(X)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}\right)$
$\displaystyle=y\sum_{F\in\mathcal{E}_{S^{\prime}}}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}x^{\ell}\sum_{A\times
B\subsetneq\text{MO}(F)\times\text{ME}(F)}x^{|A|}\bar{x}^{|B|}$
$\displaystyle=yx^{\ell}\sum_{F\in\mathcal{E}_{S^{\prime}}}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}\left((x+1)^{\text{mo}(F)}(\bar{x}+1)^{\text{me}(F)}-x^{\text{mo}(F)}\bar{x}^{\text{me}(F)}\right)$
$\displaystyle=yx^{\ell}\left(\Lambda_{S^{\prime}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z})-\Lambda_{S^{\prime}}(x,y,z,\bar{x},\bar{y},\bar{z})\right).$

Summing over all $k$ between $0$ and $\ell$ (including the case when
$X=F^{-1}(2m)\setminus\\{2m\\})$, we obtain a total contribution of

$\displaystyle y$
$\displaystyle\left(\sum_{k=0}^{\ell}\binom{\ell}{k}x^{k}\bar{z}^{\ell-k}\right)\Lambda_{S^{\prime}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z})-x^{\ell}(\bar{y}-y)\Lambda_{S^{\prime}}(x,y,z,\bar{x},\bar{y},\bar{z})$
$\displaystyle=y(x+\bar{z})^{\ell}\Lambda_{S^{\prime}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z})+x^{\ell}(\bar{y}-y)\Lambda_{S^{\prime}}(x,y,z,\bar{x},\bar{y},\bar{z})$

to $\Lambda_{S}$.

Case 2. Suppose that $2m\in X$.

Again, suppose that $X$ contains exactly $k$ of the $\ell$ odd elements of
$T\setminus U$ for $0\leq k\leq\ell$.

When $k=\ell$, $X$ consists of $S^{\prime}\setminus S^{\prime\prime}$ (which
consists of $\ell$ odd elements and one even element) along with some proper
subset of the maxima of $F$. In this case,

$\displaystyle w(\hat{F}_{X})$
$\displaystyle=x^{O(X)}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{E(X)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}$
$\displaystyle=x^{\ell}\bar{x}\left(x^{|A|}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{|B|}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}\right),$

where $A$ and $B$ are subsets of $\text{MO}(F)$ and $\text{ME}(F)$,
respectively, such that $A\times B\neq\text{MO}(F)\times\text{ME}(F)$.

Hence,

$\displaystyle\sum_{F\in\mathcal{E}_{S^{\prime}}}$
$\displaystyle\sum_{\begin{subarray}{c}X\subseteq F^{-1}(2m)\\\
(S^{\prime}\setminus S^{\prime\prime})\subseteq
X\end{subarray}}w(\hat{F}_{X})$
$\displaystyle=\sum_{F\in\mathcal{E}_{S^{\prime}}}x^{\ell}\bar{x}\sum_{A\times
B\subsetneq\text{MO}(F)\times\text{ME}(F)}x^{|A|}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{|B|}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}$
$\displaystyle=x^{\ell}\bar{x}\sum_{F\in\mathcal{E}_{S^{\prime}}}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}\sum_{A\times
B\subsetneq\text{MO}(F)\times\text{ME}(F)}x^{|A|}\bar{x}^{|B|}$
$\displaystyle=x^{\ell}\bar{x}\sum_{F\in\mathcal{E}_{S^{\prime}}}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}\left((x+1)^{\text{mo}(F)}(\bar{x}+1)^{\text{me}(F)}-x^{\text{mo}(F)}\bar{x}^{\text{me}(F)}\right)$
$\displaystyle=x^{\ell}\bar{x}\left(\Lambda_{S^{\prime}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z})-\Lambda_{S^{\prime}}(x,y,z,\bar{x},\bar{y},\bar{z})\right).$

When $k=\ell-1$, there are two possibilities. If
$X=F^{-1}(2m)\setminus\\{2i-1\\}$ for some $2i-1\in S^{\prime}\setminus
S^{\prime\prime}$, then

$\displaystyle w(\hat{F}_{X})$
$\displaystyle=x^{\text{mo}(F)+(\ell-1)}y^{\text{fd}(F)}z^{\text{si}(F)+1}\bar{x}^{\text{me}(F)+1}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}$
$\displaystyle=x^{\ell-1}z\bar{x}w(F).$

This can happen in $\ell$ ways, so such $\hat{F}_{X}$ give a contribution of
$\ell x^{\ell-1}z\bar{x}\Lambda_{S^{\prime}}$ to $\Lambda_{S}$.

On the other hand, if there is at least one maximum of $F$ that is not in $X$,
then $X$ consists of $2m$, $(\ell-1)$ odd elements of $S^{\prime}\setminus
S^{\prime\prime}$, and some proper subset of the maxima of $F$. In this case,

$\displaystyle w(\hat{F}_{X})$
$\displaystyle=x^{|A|+(\ell-1)}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{|B|+1}\bar{y}^{\text{si}(F)}\bar{z}^{\text{sd}(F)+1}$
$\displaystyle=x^{\ell-1}\bar{x}\bar{z}\left(x^{|A|}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{|B|}\bar{y}^{\text{si}(F)}\bar{z}^{\text{sd}(F)}\right),$

where $A$ and $B$ are subsets of the odd and even maxima of $F$, respectively,
such that $A\times B\neq\text{MO}(F)\times\text{ME}(F)$. Note that for any
such pair of $A$ and $B$, there are exactly $\ell$ such sets $X$.

Thus,

$\displaystyle\sum_{F\in\mathcal{E}_{S^{\prime}}}$
$\displaystyle\sum_{\begin{subarray}{c}X\subsetneq F^{-1}(2m)\\\ 2m\in X\\\
X\cap(S^{\prime}\setminus S^{\prime\prime})=\ell\end{subarray}}w(\hat{F}_{X})$
$\displaystyle=\ell
x^{\ell-1}\bar{x}\bar{z}\sum_{F\in\mathcal{E}_{S^{\prime}}}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{y}^{\text{si}(F)}\bar{z}^{\text{sd}(F)}\sum_{A\times
B\subsetneq\text{MO}(F)\times\text{ME}(F)}x^{|A|}\bar{x}^{|B|}$
$\displaystyle=\ell
x^{\ell-1}\bar{x}\bar{z}\sum_{F\in\mathcal{E}_{S^{\prime}}}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{y}^{\text{si}(F)}\bar{z}^{\text{sd}(F)}\left((x+1)^{\text{mo}(F)}(\bar{x}+1)^{\text{me}(F)}-x^{\text{mo}(F)}\bar{x}^{\text{me}(F)}\right)$
$\displaystyle=\ell
x^{\ell-1}\bar{x}\bar{z}\left(\Lambda_{S^{\prime}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z})-\Lambda_{S^{\prime}}(x,y,z,\bar{x},\bar{y},\bar{z})\right).$

When $0\leq k\leq\ell-2$ $X$ consists of: $2m$, $k$ odd elements of
$S^{\prime}\setminus S^{\prime\prime}$, and some subset (not necessarily
proper) of the maxima of $F$. Hence,

$\displaystyle w(\hat{F}_{X})$
$\displaystyle=x^{|A|+k}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{|B|+1}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)+(\ell-k)}$
$\displaystyle=x^{k}\bar{x}\bar{z}^{\ell-k}\left(x^{|A|}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{x}^{|B|}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}\right),$

where $A$ and $B$ are subsets of the odd and even maxima of $F$, respectively.
As before, given any pair $A$ and $B$, there are $\binom{\ell}{k}$ such sets
$X$.

Therefore,

$\displaystyle\sum_{F\in\mathcal{E}_{S^{\prime}}}$
$\displaystyle\sum_{\begin{subarray}{c}X\subsetneq F^{-1}(2m)\\\ 2m\in X\\\
X\cap(S^{\prime}\setminus S^{\prime\prime})=k+1\end{subarray}}w(\hat{F}_{X})$
$\displaystyle=\binom{\ell}{k}x^{k}\bar{x}\bar{z}^{\ell-k}\sum_{F\in\mathcal{E}_{S^{\prime}}}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}\sum_{A\times
B\subseteq\text{MO}(F)\times\text{ME}(F)}x^{|A|}\bar{x}^{|B|}$
$\displaystyle=\binom{\ell}{k}x^{k}\bar{x}\bar{z}^{\ell-k}\sum_{F\in\mathcal{E}_{S^{\prime}}}y^{\text{fd}(F)}z^{\text{si}(F)}\bar{y}^{\text{fi}(F)}\bar{z}^{\text{sd}(F)}(x+1)^{\text{mo}(F)}(\bar{x}+1)^{\text{me}(F)}$
$\displaystyle=\binom{\ell}{k}x^{k}\bar{x}\bar{z}^{\ell-k}\Lambda_{S^{\prime}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z}).$

Summing over all $0\leq k\leq\ell$, this gives a total contribution of

$\displaystyle\bar{x}$
$\displaystyle\left(\sum_{k=0}^{\ell}\binom{\ell}{k}x^{k}\bar{z}^{\ell-k}\right)\Lambda_{S^{\prime}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z})+\bar{x}(\ell
x^{\ell-1}z-x^{\ell}-\ell
x^{\ell-1}\bar{z})\Lambda_{S^{\prime}}(x,y,z,\bar{x},\bar{y},\bar{z})$
$\displaystyle=\bar{x}(x+\bar{z})^{\ell}\Lambda_{S^{\prime}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z})+x^{\ell-1}(\ell\bar{x}(z-\bar{z})-x\bar{x})\Lambda_{S^{\prime}}(x,y,z,\bar{x},\bar{y},\bar{z})$

to $\Lambda_{S}$.

Finally, we combine the contributions from Cases 1 and 2 to obtain:

$\displaystyle\Lambda_{S}(x,y,z,\bar{x},\bar{y},\bar{z})=$
$\displaystyle(y+\bar{x})(x+\bar{z})^{\ell}\Lambda_{S^{\prime}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z})$
$\displaystyle+x^{\ell-1}[x(\bar{y}-y)+\ell\bar{x}(z-\bar{z})-x\bar{x}]\Lambda_{S^{\prime}}(x,y,z,\bar{x},\bar{y},\bar{z}).$

∎

###  6.2. D-permutations and Generalized Surjective Staircases

The following lemma was proved in [14, Lemma 5.2]:

######  Lemma 6.7.

There is a bijection

$\phi:\mathcal{D}_{2n}\to\\{f\in\mathcal{E}_{2n+2}:f\mbox{ has no even
maxima}\\}$

such that for all $\sigma\in\mathcal{D}_{2n}$ and $j\in[2n]$, the following
properties hold:

  1. (1)

$j$ is an even cycle maximum of $\sigma$ if and only if it is a fixed point of
$\phi(\sigma)$,

  2. (2)

$j$ is an even fixed point of $\sigma$ if and only if it is an isolated fixed
point of $\phi(\sigma)$,

  3. (3)

$j$ is an odd fixed point of $\sigma$ if and only if it is an odd maximum of
$\phi(\sigma)$.

Our next goal is to generalize Lemma 6.7. Let $V$ be a finite set of positive
integers whose maximum is even, and let $R_{k}$ be a finite set of $k+1$
positive integers consisting of:

  * •

$k$ odd numbers larger than $\max V$, and

  * •

one even number that is larger than the odd numbers.

We will show that the D-permutations on $V$ are in bijection with certain of
the surjective staircases with domain $V\cup R_{k}$.

######  Lemma 6.8.

For any $k$, let $V$ and $R_{k}$ be as above. There is a bijection

$\tilde{\phi}:\mathcal{D}_{V}\to\\{f\in\mathcal{E}_{V\cup
R_{k}}\operatorname{\,|\,}f\text{ has no even maxima}\\},$

such that for all $\sigma\in\mathcal{D}_{V}$ and all $j\in V$

  1. (1)

$j$ is an even cycle maximum of $\sigma$ if and only if $j$ is a fixed point
of $\phi(\sigma)$,

  2. (2)

$j$ is an even fixed point of $\sigma$ if and only if $j$ is an isolated fixed
point of $\phi(\sigma)$,

  3. (3)

$j$ is an odd fixed point of $\sigma$ if and only if $j$ is an odd maximum of
$\phi(\sigma)$.

###### Proof.

Let $\sigma\in\mathcal{D}_{V}$. We wish to apply Lemma 6.7. Let $2m=\max V$,
$2n=\max R_{k}$ and let $\sigma^{\prime}$ be the permutation in
$\mathfrak{S}_{2n-2}$ defined by

$\sigma^{\prime}(i)=\begin{cases}\sigma(i),&i\in V\\\
i,&\text{otherwise}\end{cases}.$

Notice that the map
$\psi:\\{\sigma\in\mathfrak{S}_{V}\\}\to\\{\sigma\in\mathfrak{S}_{2n-2}\operatorname{\,|\,}\sigma(i)=i\operatorname{\;\forall}i\notin
V\\}$ given by $\sigma\mapsto\sigma^{\prime}$ is a bijection.

We apply the map $\phi$ from Lemma 6.7 to $\sigma^{\prime}$ to obtain a
surjective staircase $f^{\prime}\in\mathcal{E}_{2n}$ with no even maxima. Our
next goal is to show that the restriction of $f^{\prime}$ to $V\cup R_{k}$ is
a surjective staircase.

First, recall that for all $i\in[2n-2]\setminus V$, $\sigma^{\prime}(i)=i$.
Hence, if $i\in[2n-2]\setminus V$ is even, $i$ is an isolated fixed point of
$f^{\prime}$, and if $i\in[2n-2]\setminus V$ is odd, $i$ is an odd maximum of
$f^{\prime}$. This tells us immediately that for all $i\in V$,
$f^{\prime}(i)\in[2n]\setminus([2n-2]\setminus V)=V\cup\\{2n-1,2n\\}$. Since
the image of $f^{\prime}$ contains no odd numbers, we see that
$f^{\prime}(i)\in V\cup\\{2n\\}$ for all $i\in V$. In other words,

$f^{\prime}(V)\subseteq\\{\text{even elements of }V\\}\cup\\{2n\\}.$

Conversely, we claim that $\\{\text{even elements of }V\\}\subseteq
f^{\prime}(V)$. Indeed, every element of $[2n-2]\setminus V$ is either a fixed
point or a maximum of $f^{\prime}$, so if $i\in[2n-2]\setminus V$,
$f^{\prime}(i)\notin V$. By definition, $f^{\prime}(2n-1)=f^{\prime}(2n)=2n$.
Hence, $\\{\text{even elements of }V\\}\nsubseteq f^{\prime}([2n]\setminus
V)$, so the only way for $f^{\prime}$ to be surjective is to have

$\\{\text{even elements of }V\\}\subseteq f^{\prime}(V).$

We also see that $f^{\prime}(R_{k})=\\{2n\\}$. Indeed, we know that
$f^{\prime}(2n-1)=f^{\prime}(2n)=2n$ (whether or not $2n-1\in R_{k}$). Any
other element $i$ of $R_{k}$ is an odd element of $[2n-2]\setminus V$, and by
construction, all such $i$ are odd maxima of $f^{\prime}$. Hence,

$f^{\prime}(V\cup R_{k})=\\{\text{even elements of }V\\}\cup\\{2n\\}.$

Thus, we can define a surjective staircase $f\in\mathcal{E}_{V\cup R_{k}}$ by
restricting the domain of $f^{\prime}$ to $V\cup R_{k}$. Indeed, we have just
shown that the image of such an $f$ would be $\\{\text{even elements of V
}\\}\cup\\{2n\\}$, and such an $f$ would be excedent because $f^{\prime}$ was.
We also know that $f$ would have no even maxima because $f^{\prime}$ had no
even maxima.

Finally, note that the image of $\phi\circ\psi$ consists of surjective
staircases $f^{\prime}\in\mathcal{E}_{2n}$ with no even maxima, such that
$f^{\prime}(2i-1)=2n$ for all $2i-1\notin V$, and such that $2i$ is an
isolated fixed point of $f^{\prime}$ for all $2i\notin V$. We observe that
restricting the domain of $f^{\prime}$ to $V\cup R_{k}$ yields a bijection
between the image of $\phi\circ\psi$ and $\\{f\in\mathcal{E}_{V\cup
R_{k}}\operatorname{\,|\,}f\text{ has no even maxima}\\}$. Indeed, given any
$f\in\mathcal{E}_{V\cup R_{k}}$ that has no even maxima, we define a
$g\in\mathcal{E}_{2n}$ with no even maxima by

$g(a)=\begin{cases}f(a),&a\in V\\\ 2n,&a\in[2n]\setminus V\text{ is odd}\\\
a,&a\in[2n]\setminus V\text{ is even}\end{cases}.$

Such a $g$ is in the image of $\phi\circ\psi$ because $2i-1$ is an odd maximum
of $g$ for all $2i-1\in[2n-2]\setminus V$ and $2i$ is an isolated fixed point
of $g$ for all $2i\in[2n-2]\setminus V$. Moreover, by construction we see that
$g|_{V\cup R_{k}}=f$.

Hence, we define $\tilde{\phi}:\mathcal{D}_{V}\to\mathcal{E}_{V\cup R_{k}}$ by
$\tilde{\phi}(\sigma)=\left.\phi(\sigma^{\prime})\right|_{V\cup R_{k}}$. Since
the three desired properties held for $\phi$, they hold for $\tilde{\phi}$
automatically. The map $\tilde{\phi}$ is the composition of three maps
$\sigma\mapsto\sigma^{\prime}\mapsto f^{\prime}\mapsto f$, each of which is a
bijection, so $\tilde{\phi}$ is a bijection. ∎

Next, we prove a technical result generalizing [14, Lemma 5.4].

######  Lemma 6.9.

For any $k$,

$\sum_{\sigma\in\mathcal{D}_{V}}t^{c(\sigma)}=\Lambda_{V\cup
R_{k}}(t,t,1,0,t,1),$

where $c(\sigma)$ is the number of cycles of $\sigma$.

###### Proof.

We apply the bijection $\tilde{\phi}$ from Lemma 6.8:

$\displaystyle\sum_{\sigma\in\mathcal{D}_{V}}t^{c(\sigma)}$
$\displaystyle=\sum_{\sigma\in\mathcal{D}_{V}}t^{\text{fi}(\tilde{\phi}(\sigma))+\text{fd}(\tilde{\phi}(\sigma))+\text{mo}(\tilde{\phi}(\sigma))}$
$\displaystyle=\sum_{\begin{subarray}{c}f\in\mathcal{E}_{V\cup R_{k}}\\\
\text{me}(f)=0\end{subarray}}t^{\text{fi}(f)+\text{fd}(f)+\text{mo}(f)}$
$\displaystyle=\Lambda_{V\cup R_{k}}(t,t,1,0,t,1).$

∎

##  7\. Generating Function Proofs

We now use the technical results established in Section 6 to prove Theorems
5.1 and 5.5.

###  7.1. $k$-step staircases

Let

$S_{n}^{k}=\\{1,3,5,\dots,2nk-1\\}\sqcup\\{2k,4k,\dots,2nk\\},$

and note that $\lambda(S_{n}^{k})$ is the $k$-staircase partition
$\lambda^{(n)}_{k}$.

We are ready to prove a generalization of Randrianarivony and Zeng’s
generating function formula for the generalized Dumont–Foata polynomials.

######  Theorem 7.1.

For all $k\geq 1$,

$\displaystyle\sum_{n\geq 1}$
$\displaystyle\Lambda_{S_{n}^{k}}(x,y,z,\bar{x},\bar{y},\bar{z})u^{n-1}$
$\displaystyle=\sum_{n\geq
1}\frac{(y+\bar{x})^{(n-1)}\left((x+\bar{z})^{(n-1)}\right)^{k}u^{n-1}}{\prod_{i=0}^{n-1}\left(1-(x+i)^{k-1}\left[(x+i)(\bar{y}-y)+k(x+i)(z-\bar{z})-(x+i)(\bar{x}+i)\right]u\right)},$

where $x^{(n)}=x(x+1)\cdots(x+(n-1))$.

###### Proof.

Throughout this proof we will abbreviate
$\Lambda_{S}(x,y,z,\bar{x},\bar{y},\bar{z})$ as $\Lambda_{S}$, and similarly
write $\Lambda_{S}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z})$ as
$\Lambda_{S}(x+1,\bar{x}+1)$. By assumption, $S_{1}^{k}$ contains exactly one
even element, so $\Lambda_{S_{1}^{k}}=1$. We can thus write

$\displaystyle\sum_{n\geq 1}\Lambda_{S_{n}^{k}}u^{n-1}$
$\displaystyle=1+\sum_{n\geq 2}\Lambda_{S_{n}^{k}}u^{n-1}$
$\displaystyle=1+\sum_{n\geq
2}(y+\bar{x})(x+\bar{z})^{k}\Lambda_{S_{n-1}^{k}}(x+1,\bar{x}+1)u^{n-1}$
$\displaystyle\;\;\;\;+\sum_{n\geq
2}x^{k-1}[x(\bar{y}-y)+k\bar{x}(z-\bar{z})-x\bar{x}]\Lambda_{S_{n-1}^{k}}u^{n-1}$
$\displaystyle=1+\sum_{n\geq
1}(y+\bar{x})(x+\bar{z})^{k}u\Lambda_{S_{n}^{k}}(x+1,\bar{x}+1)u^{n-1}$
$\displaystyle\;\;\;\;+\sum_{n\geq
1}x^{k-1}[x(\bar{y}-y)+k\bar{x}(z-\bar{z})-x\bar{x}]u\Lambda_{S_{n}^{k}}u^{n-1},$

with the second equality being the recurrence proved in Theorem 6.4.

We can rearrange this equation to obtain

$\displaystyle\left(1-x^{k-1}[x(\bar{y}-y)+k\bar{x}(z-\bar{z})-x\bar{x}]u\right)$
$\displaystyle\sum_{n\geq 1}\Lambda_{S_{n}^{k}}u^{n-1}$
$\displaystyle=1+((y+\bar{x})(x+\bar{z})^{k}u)\sum_{n\geq
1}\Lambda_{S_{n}^{k}}(x+1,\bar{x}+1)u^{n-1},$

so we have

$\displaystyle\sum_{n\geq 1}\Lambda_{S_{n}^{k}}u^{n-1}$
$\displaystyle=\frac{1}{1-x^{k-1}[x(\bar{y}-y)+k\bar{x}(z-\bar{z})-x\bar{x}]u}$
$\displaystyle+\frac{(y+\bar{x})(x+\bar{z})^{k}u}{1-x^{k-1}[x(\bar{y}-y)+k\bar{x}(z-\bar{z})-x\bar{x}]u}\sum_{n\geq
1}\Lambda_{S_{n}^{k}}(x+1,\bar{x}+1)u^{n-1}.$

By recursively expanding the right-hand side of this equation, we obtain the
desired generating function formula. ∎

We can now prove Theorem 5.1.

###### Proof of Theorem 5.1..

By Corollary 3.3, we know that $\Gamma_{S_{n}^{k}}=\Gamma_{V_{n}^{k}}$ for any
$V_{n}^{k}$ satisfying $\lambda(V_{n}^{k})=\lambda^{(n)}_{k}$, so without loss
of generality we can take $V_{n}^{k}=S_{n}^{k}$. By Lemma 6.9, we know that

$\sum_{\sigma\in\mathcal{D}_{S_{n}^{k}}}t^{c(\sigma)}=\Lambda_{S_{n+1}^{k}}(t,t,1,0,t,1).$

Hence, we have

$\displaystyle\sum_{n\geq
1}\sum_{\sigma\in\mathcal{D}_{S_{n}^{k}}}t^{c(\sigma)}u^{n}$
$\displaystyle=\sum_{n\geq 1}\Lambda_{S_{n+1}^{k}}(t,t,1,0,t,1)u^{n}$
$\displaystyle=-1+\sum_{n\geq 1}\Lambda_{S_{n}^{k}}(t,t,1,0,t,1)u^{n-1}$
$\displaystyle=-1+\sum_{n\geq
1}\frac{t^{(n-1)}\left((t+1)^{(n-1)}\right)^{k}u^{n-1}}{\prod_{i=0}^{n-1}\left(1+i(t+i)^{k}u\right)}$
$\displaystyle=\sum_{n\geq
2}\frac{t^{(n-1)}\left((t+1)^{(n-1)}\right)^{k}u^{n-1}}{\prod_{i=0}^{n-1}\left(1+i(t+i)^{k}u\right)}$
$\displaystyle=\sum_{n\geq
1}\frac{t^{(n)}\left((t+1)^{(n)}\right)^{k}u^{n}}{\prod_{i=0}^{n}\left(1+i(t+i)^{k}u\right)},$

with the third equality following from Theorem 7.1.

Next, we have

$\displaystyle\sum_{n\geq
1}\sum_{\sigma\in\mathcal{D}_{S_{n}^{k}}}(-t)^{c(\sigma)-1}u^{n}$
$\displaystyle=-\frac{1}{t}\sum_{n\geq
1}\frac{(-t)^{(n)}\left((-t+1)^{(n)}\right)^{k}u^{n}}{\prod_{i=0}^{n}\left(1+i(-t+i)^{k}u\right)}$
(7) $\displaystyle=\sum_{n\geq
1}\frac{(-1)^{nk+n-1}(t-1)_{n-1}\left((t-1)_{n}\right)^{k}u^{n}}{\prod_{i=0}^{n}\left(1+i(i-t)^{k}u\right)}.$

By Theorem 2.2, we know that
$\chi_{\Pi_{\Gamma_{S_{n}^{k}}}}(t)=(-1)^{nk+n-1}\displaystyle\sum_{\sigma\in\mathcal{D}_{S_{n}^{k}}}(-t)^{c(\sigma)-1}$,
because $\Gamma_{S_{n}^{k}}$ has $nk+n$ vertices. Hence,

$\displaystyle\sum_{n\geq 1}\chi_{\Pi_{\Gamma_{S_{n}^{k}}}}(t)u^{n}$
$\displaystyle=-\sum_{n\geq
1}\sum_{\sigma\in\mathcal{D}_{S_{n}^{k}}}(-t)^{c(\sigma)-1}(-1)^{nk+n}u^{n}$
$\displaystyle=-\sum_{n\geq
1}\sum_{\sigma\in\mathcal{D}_{S_{n}^{k}}}(-t)^{c(\sigma)-1}((-1)^{k+1}u)^{n}$
$\displaystyle=-\sum_{n\geq
1}\frac{(-1)^{nk+n-1}(t-1)_{n-1}\left((t-1)_{n}\right)^{k}(-1)^{nk+n}u^{n}}{\prod_{i=0}^{n}\left(1+i(i-t)^{k}(-1)^{k+1}u\right)}$
$\displaystyle=\sum_{n\geq
1}\frac{(t-1)_{n-1}\left((t-1)_{n}\right)^{k}u^{n}}{\prod_{i=0}^{n}\left(1-i(t-i)^{k}u\right)},$

with the third equality following from Equation (7). ∎

###  7.2. The complete bipartite graph $K_{n,k}$.

Fix $k\geq 1$, and let
$T_{n}^{k}=\\{1,3,5,\dots,2k-1\\}\sqcup\\{2k,\dots,2(k+n-1)\\}$ as in Section
5.2. By applying Theorem 6.4, we see that

$\Lambda_{T_{1}^{k}}=1,$ (8) $\displaystyle\Lambda_{T_{2}^{k}}$
$\displaystyle=(y+\bar{x})(x+\bar{z})^{k}+x^{k-1}[x(\bar{y}-y)-k\bar{x}(\bar{z}-z)-x\bar{x}],$

and

(9) $\displaystyle\Lambda_{T_{n}^{k}}$
$\displaystyle=(y+\bar{x})\Lambda_{T_{n-1}}(x+1,\bar{x}+1)+(\bar{y}-y-\bar{x})\Lambda_{T_{n-1}^{k}}$

for all $n\geq 3$, where
$\Lambda_{T_{n}^{k}}(x+1,\bar{x}+1)\coloneqq\Lambda_{T_{n}^{k}}(x+1,y,z,\bar{x}+1,\bar{y},\bar{z})$.

######  Theorem 7.2.

We have

$\sum_{n\geq 1}\Lambda_{T_{n}^{k}}u^{n-1}=1+\sum_{n\geq
2}\frac{(y+\bar{x})^{(n-2)}\Lambda_{T_{2}^{k}}(x+(n-2),\bar{x}+(n-2))u^{n-1}}{\prod_{i=0}^{n-2}(1-(\bar{y}-y-(\bar{x}+i))u)},$

where $a^{(n)}$ is the rising factorial $a(a+1)\cdots(a+(n-1))$.

###### Proof.

We can write

$\displaystyle\sum_{n\geq 1}$ $\displaystyle\Lambda_{T_{n}^{k}}u^{n-1}$
$\displaystyle=1+\Lambda_{T_{2}^{k}}u+\sum_{n\geq
3}\Lambda_{T_{n}^{k}}u^{n-1}$
$\displaystyle=1+\Lambda_{T_{2}^{k}}u+(y+\bar{x})\sum_{n\geq
3}\Lambda_{T_{n-1}^{k}}(x+1,\bar{x}+1)u^{n-1}+(\bar{y}-y-\bar{x})\sum_{n\geq
3}\Lambda_{T_{n-1}^{k}}u^{n-1}$
$\displaystyle=1+\Lambda_{T_{2}}u+(y+\bar{x})u\sum_{n\geq
2}\Lambda_{T_{n}^{k}}(x+1,\bar{x}+1)u^{n-1}+(\bar{y}-y-\bar{x})u\sum_{n\geq
2}\Lambda_{T_{n}^{k}}u^{n-1},$

with the second equality following from Equation (9).

Subtracting $1$ from both sides, we have

$\sum_{n\geq
2}\Lambda_{T_{n}^{k}}u^{n-1}=\Lambda_{T_{2}^{k}}u+(y+\bar{x})u\sum_{n\geq
2}\Lambda_{T_{n}^{k}}(x+1,\bar{x}+1)u^{n-1}+(\bar{y}-y-\bar{x})u\sum_{n\geq
2}\Lambda_{T_{n}^{k}}u^{n-1}.$

By rearranging, we see

$(1-(\bar{y}-y-\bar{x})u)\sum_{n\geq
2}\Lambda_{T_{n}^{k}}u^{n-1}=\Lambda_{T_{2}^{k}}u+(y+\bar{x})u\sum_{n\geq
2}\Lambda_{T_{n}^{k}}(x+1,\bar{x}+1)u^{n-1},$

or equivalently that

$\sum_{n\geq
2}\Lambda_{T_{n}^{k}}u^{n-1}=\frac{\Lambda_{T_{2}^{k}}u}{1-(\bar{y}-y-\bar{x})u}+\frac{(y+\bar{x})u}{1-(\bar{y}-y-\bar{x})u}\sum_{n\geq
2}\Lambda_{T_{n}^{k}}(x+1,\bar{x}+1)u^{n-1}.$

By recursively expanding the right-hand side of the above equation, we see
that

$\sum_{n\geq 2}\Lambda_{T_{n}^{k}}u^{n-1}=\sum_{n\geq
2}\frac{(y+\bar{x})^{(n-2)}\Lambda_{T_{2}^{k}}(x+(n-2),\bar{x}+(n-2))u^{n-1}}{\prod_{i=0}^{n-2}(1-(\bar{y}-y-(\bar{x}+i))u)}.$

∎

Now, by applying Lemma 6.9, we can prove Theorem 5.5.

###### Proof of Theorem 5.5..

By Lemma 6.9, we know that

$\sum_{\sigma\in\mathcal{D}_{T_{i}^{k}}}t^{c(\sigma)}=\Lambda_{T_{i+1}^{k}}(t,t,1,0,t,1),$

so

$\displaystyle\sum_{n\geq
1}\sum_{\sigma\in\mathcal{D}_{T_{n}^{k}}}t^{c(\sigma)}u^{n}$
$\displaystyle=\sum_{n\geq 2}\Lambda_{T_{n}^{k}}(t,t,1,0,t,1)u^{n-1}$
$\displaystyle=\sum_{n\geq
2}\frac{t^{(n-2)}\left.\left(\Lambda_{T_{2}^{k}}(x+(n-2),\bar{x}+(n-2))\right)\right|_{(t,t,1,0,t,1)}u^{n-1}}{\prod_{i=0}^{n-2}(1+iu)},$

by Theorem 7.2.

Now, by Equation (8),

$\displaystyle\Lambda_{T_{2}^{k}}(x+i,\bar{x}+i)=$
$\displaystyle(y+\bar{x}+i)(x+\bar{z}+i)^{k}$
$\displaystyle+(x+i)^{k-1}\left[(x+i)(\bar{y}-y)-k(\bar{x}+i)(\bar{z}-z)-(x+i)(\bar{x}+i)\right],$

so

$\displaystyle\left.\left(\Lambda_{T_{2}^{k}}(x+i,\bar{x}+i)\right)\right|_{(t,t,1,0,t,1)}$
$\displaystyle=(t+i)(t+i+1)^{k}+(t+i)^{k-1}(-(t+i)i)$
$\displaystyle=(t+i)(t+i+1)^{k}-i(t+i)^{k}.$

Thus, after reindexing we have

$\displaystyle\sum_{n\geq
1}\sum_{\sigma\in\mathcal{D}_{T_{n}^{k}}}t^{c(\sigma)}u^{n}$
$\displaystyle=\sum_{n\geq
1}\frac{t^{(n-1)}((t+(n-1))(t+n)^{k}-(n-1)(t+(n-1))^{k})u^{n}}{\prod_{i=1}^{n-1}(1+iu)}$
$\displaystyle=t(t+1)^{k}u+\sum_{n\geq
2}\frac{t^{(n)}\left[(t+n)^{k}-(n-1)(t+(n-1))^{k-1}\right]u^{n}}{\prod_{i=0}^{n-1}(1+iu)}$

Next, we have

$\displaystyle\sum_{n\geq 1}$
$\displaystyle\sum_{\sigma\in\mathcal{D}_{T_{n}^{k}}}(-t)^{c(\sigma)-1}$
$\displaystyle=-\frac{1}{t}\left((-t)(1-t)^{k}u+\sum_{n\geq
2}\frac{(-t)^{(n)}\left[(n-t)^{k}-(n-1)((n-1)-t)^{k-1}\right]u^{n}}{\prod_{i=0}^{n-1}(1+iu)}\right)$
$\displaystyle=(1-t)^{k}u+\sum_{n\geq
2}\frac{(-1)^{n+k-1}(t-1)_{n-1}\left[(t-n)^{k}+(n-1)(t-(n-1))^{k-1}\right]u^{n}}{\prod_{i=0}^{n-1}(1+iu)}.$

Finally, since $\Gamma_{T_{n}^{k}}$ has $n+k$ vertices,
$\chi_{\Pi_{\Gamma_{T_{n}^{k}}}}(t)=(-1)^{n+k-1}\displaystyle\sum_{\sigma\in\mathcal{D}_{T_{n}^{k}}}(-t)^{c(\sigma)-1}$
by Theorem 2.2. Hence,

$\displaystyle\sum_{n\geq 1}\chi_{\Pi_{\Gamma_{T_{n}^{k}}}}(t)u^{n}$
$\displaystyle=\sum_{n\geq
1}(-1)^{n+k-1}\sum_{\sigma\in\mathcal{D}_{T_{n}^{k}}}(-t)^{c(\sigma)-1}u^{n}$
$\displaystyle=(-1)^{k-1}\sum_{n\geq
1}\sum_{\sigma\in\mathcal{D}_{T_{n}}}(-t)^{c(\sigma)-1}(-u)^{n}$
$\displaystyle=(t-1)^{k}u$ $\displaystyle\hskip
14.22636pt+(-1)^{k-1}\sum_{n\geq
2}\frac{(-1)^{n+k-1}(t-1)_{n-1}\left[(t-n)^{k}+(n-1)(t-(n-1))^{k-1}\right](-1)^{n}u^{n}}{\prod_{i=0}^{n-1}(1-iu)}$
$\displaystyle=(t-1)^{k}u+\sum_{n\geq
2}\frac{(t-1)_{n-1}\left[(t-n)^{k}+(n-1)(t-(n-1))^{k-1}\right]u^{n}}{\prod_{i=0}^{n-1}(1-iu)}$
$\displaystyle=\sum_{n\geq
1}\frac{(t-1)_{n-1}\left[(t-n)^{k}+(n-1)(t-(n-1))^{k-1}\right]u^{n}}{\prod_{i=0}^{n-1}(1-iu)}.$

Finally, we multiply by $t$ to obtain the desired generating function for the
chromatic polynomial. ∎

##  8\. Dowling Analogs

###  8.1. Homogenized $\nu$-Dowling Arrangements

As in [11, Chapter 4] (see also [12]), we can consider a complex analog of the
homogenized $\nu$-arrangements. Many of the results of the previous sections
can be extended to the complex case after some technical results are
established.

Let $\nu=(\nu_{1},\dots,\nu_{n})$ be a weak composition of $m$, and fix a
positive integer $q$. Let $\omega$ be the primitive $q$th root of unity
$e^{\frac{2\pi i}{q}}$. We define the _homogenized $\nu$-Dowling arrangement_
to be the hyperplane arrangement in

$\\{(x_{1},\dots,x_{n},y_{1}^{(1)},\dots,y_{1}^{(\nu_{1})},y_{2}^{(1)}.\dots,y_{2}^{(\nu_{2})},\dots,y_{n}^{(1)},\dots,y_{n}^{(\nu_{n})})\\}=\operatorname{\mathbb{C}}^{m+n}$

given by

$\displaystyle\mathcal{H}_{\nu}^{q}=$
$\displaystyle\\{x_{i}-\omega^{k}x_{j}=y_{i}^{(\ell)}\operatorname{\,|\,}1\leq
i<j\leq n,0\leq k\leq q-1,1\leq\ell\leq\nu_{i}\\}$
$\displaystyle\cup\\{x_{i}=y_{i}^{(\ell)}\operatorname{\,|\,}1\leq i\leq
n,1\leq\ell\leq\nu_{i}\\}.$

The term “Dowling” comes from the fact that the intersection lattice of
$\mathcal{H}_{\nu}^{q}$ is a subposet of the _Dowling lattice_
$Q_{n}(\operatorname{\mathbb{Z}}_{q})$, introduced by Dowling in [5].

Let $\mathcal{K}_{\nu}^{q}$ be the hyperplane arrangement in
$\operatorname{\mathbb{C}}^{n+m}$ given by:

$\displaystyle\\{x_{2i-1}^{(\ell)}-\omega^{k}x_{2j-2}=0$
$\displaystyle\operatorname{\,|\,}1\leq i<j\leq n,0\leq k\leq
q-1,1\leq\ell\leq\nu_{i}\\}$
$\displaystyle\cup\\{x_{2i-1}^{(\ell)}=0\operatorname{\,|\,}1\leq i\leq
n,1\leq\ell\leq\nu_{i}\\}.$

######  Lemma 8.1.

There is an invertible linear transformation from
$\operatorname{\mathbb{C}}^{n+m}$ to itself that takes the hyperplanes of
$\mathcal{H}_{\nu}^{q}$ to the hyperplanes of $\mathcal{K}_{\nu}^{q}$. In
particular, we have
$\mathcal{L}(\mathcal{H}_{\nu}^{q})\cong\mathcal{L}(\mathcal{K}_{\nu}^{q})$.

###### Proof.

This follows from essentially the same argument as in the proof of Theorem
4.2. See also [12, 11, Lemma 4.2.3]. ∎

The results of [11, Section 4.2] (and of [12]) allow us to interpret the
coefficients of the $\chi_{\mathcal{L}(\mathcal{K}_{\nu}^{q})}(t)$ (and hence
of $\chi_{\mathcal{L}(\mathcal{H}_{\nu}^{q})}(t)$) in terms of certain
decorated D-permutations.

A _$q$ -labeled D-cycle_ on $V\subseteq[2r]$ is a D-cycle $\sigma$ on $V$,
some of whose entries are labeled with elements of $\\{0,\dots,q-1\\}$ subject
to the following conditions.

  * •

The maximum entry of $\sigma$ is labeled $0$.

  * •

If $2r\in V$ and $\sigma$ is written in the form $(w\cdot 2r)$ then the right-
to-left minima of the word $w$ are the only unlabeled entries of $\sigma$.

  * •

If $2r\notin V$ then each entry of $\sigma$ is labeled.

A _$q$ -labeled D-permutation_ on $V\subseteq[2r]$ is a D-permutation $\sigma$
on $V$, some of whose entries are labeled with elements of
$\\{0,\dots,q-1\\}$, such that each cycle of $\sigma$ is a $q$-labeled
D-cycle. We write $\mathcal{D}_{V,r}^{q}$ for the set of $q$-labeled
D-permutations on $V\subseteq[2r]$.

The combinatorics of $q$-labeled D-permutations is equivalent to the
combinatorics of a certain class of edge-decorated forests.

A tree $T$ on vertex set $V\subset\operatorname{\mathbb{Z}}_{>0}$ is
_increasing-decreasing_ (or _ID_ for short) if, when $T$ is rooted at its
largest vertex, each internal vertex $v$ of $T$ satisfies:

  * •

if $v$ is odd then $v$ is smaller than all of its descendants and all of the
children of $v$ are even,

  * •

if $v$ is even then $v$ is larger than all of its descendants and all of the
children of $v$ are odd.

An _ID_ forest is a forest, each of whose connected components is an ID tree.
ID forests were introduced in [14], where the authors showed that the ID
forests on $V$ are exactly the non-broken circuit sets (with respect to a
particular edge order) of the graph $\Gamma_{V}$ [14, Theorem 3.5].

A _$q$ -labeled ID tree_ is a tree $T$ on vertex set $V\subseteq[2r]$ such
that each edge of $T$ not incident to $2r$ is labeled with an element of
$\\{0,\dots,q-1\\}$ (so if $2r\notin V$, each edge of $T$ is labeled). A _$q$
-labeled ID forest_ is a forest, each of whose components is a $q$-labeled ID
tree. We write $\mathcal{F}_{V,r}^{q}$ for the set of $q$-labeled ID forests
on $V\subseteq[2r]$. As in the unlabeled case, the $q$-labeled ID forests are
exactly the non-broken circuit sets of the matroid arising from a complex
hyperplane arrangement studied by Lazar and Wachs [12, 11, Proposition 4.2.8].

In [12, 11, Theorem 4.2.10], Lazar and Wachs construct a bijection between the
$q$-labeled D-permutations on $V$ with $k$ cycles and the $q$-labeled ID
forests on $V$ with $k$ components.

Let $V$ be any finite subset of $\operatorname{\mathbb{Z}}_{>0}$ with odd
minimum and even maximum such that $\lambda(V)=\lambda(\nu)$, and let $2r=\max
V$. Then $V$ has $m$ odd elements and $n$ even elements. We let $2s$ be the
second-largest even element of $V$ and suppose that there are $\ell$ odd
elements of $V$ between $2s$ and $2r$. Finally, we let $V^{\prime}\coloneqq
V|_{[2s]}$.

By [12, 11, Proposition 4.2.8] and [12, 11, Theorem 4.2.10], we have the
following interpretation of the coefficients of
$\chi_{\mathcal{L}(\mathcal{K}_{\nu}^{q})}(t)$.

######  Proposition 8.2.

The coefficient of $(-1)^{k}t^{k-1}$ in
$\chi_{\mathcal{L}(\mathcal{K}_{\nu}^{q})}(t)$ is equal to the number of
$q$-labeled D-permutations on $V$ with exactly $k$ cycles, and hence is equal
to the number of $q$-labeled ID forests on $V$ with exactly $k$ components.

We can thus use Lemma 6.8 to show the following:

######  Theorem 8.3.

For any weak composition $\nu$ of $m$ of length $n$ and any finite
$V\subseteq\operatorname{\mathbb{Z}}_{>0}$ with odd minimum and even maximum
such that $\lambda(\nu)=\lambda(V)$, we have

$\chi_{\mathcal{L}(\mathcal{H}_{\nu}^{q})}(t)=(-1)^{m+n-1}(1-t)^{\ell}q^{m+n-\ell-1}\Lambda_{V}\left(\frac{1-t}{q},\frac{1-t}{q},1,0,\frac{-t}{q},1\right),$

where $\ell$ is the number of odd elements of $V$ between the largest and
second-largest even elements of $V$.

###### Proof.

We have

$\chi_{\mathcal{L}(\mathcal{H}_{\nu}^{q})}(t)=\chi_{\mathcal{L}(\mathcal{K}_{\nu}^{q})}(t)=(-1)^{m+n-1}\sum_{F\in\mathcal{F}_{V,r}^{q}}(-t)^{c(F)-1},$

where $c(F)$ is the number of components of $F$. We let $F^{\prime}$ be the
forest obtained from $F$ by deleting the vertex $2r$. Let $G$ is a $q$-labeled
ID forest on $V\setminus\\{2r\\}$ such that $F^{\prime}=G$, and let $T$ be a
component of $G$. If $T$ is not an isolated even vertex then either $T$ is a
component of $F$, or $T$ is attached to $2r$ in $F$. If $T$ is an isolated
even vertex then $T$ must also be a component of $F$. Hence

$\sum_{\begin{subarray}{c}F\in\mathcal{F}_{V,r}^{q}\\\
F^{\prime}=G\end{subarray}}(-t)^{c(G)-1}=(-t)^{\\#\\{\text{even isolated nodes
of }G\\}}(1-t)^{\\#\\{\text{other components of }G\\}}.$

Moreover, we know that $G$ must have at least $\ell$ isolated odd nodes for
the $\ell$ odd elements of $V$ between $2s$ and $2r$ (since each such vertex
can only share an edge with $2r$). Hence we have

$\displaystyle\sum_{F\in\mathcal{F}_{V,r}^{q}}(-t)^{c(F)-1}$
$\displaystyle=\sum_{G\in\mathcal{F}_{V\setminus\\{2r\\},r}^{q}}\sum_{\begin{subarray}{c}F\in\mathcal{F}_{V,r}^{q}\\\
F^{\prime}=G\end{subarray}}(-t)^{c(G)-1}$
$\displaystyle=\sum_{G\in\mathcal{F}_{V\setminus\\{2r\\},n}^{q}}(-t)^{\\#\\{\text{even
isolated nodes of }G\\}}(1-t)^{\\#\\{\text{other components of }G\\}}$
$\displaystyle=(1-t)^{\ell}\sum_{G\in\mathcal{F}_{V^{\prime},r}^{q}}(-t)^{\\#\\{\text{even
isolated nodes of }G\\}}(1-t)^{\\#\\{\text{other components of }G\\}}.$

By applying the bijection between $\mathcal{F}_{V^{\prime},r}^{q}$ and
$\mathcal{D}_{V^{\prime},r}^{q}$, this last sum becomes

$(1-t)^{\ell}\sum_{\sigma\in\mathcal{D}_{V^{\prime},r}^{q}}(-t)^{\\#\\{\text{even
fixed points of }\sigma\\}}(1-t)^{\\#\\{\text{other cycles of }\sigma\\}}.$

If $\sigma\in\mathcal{D}_{V,r}^{q}$, we let $|\sigma|$ be the underlying
(unlabeled) $D$-permutation in $\mathcal{D}_{V}$. We thus have

$\chi_{\mathcal{L}(\mathcal{K}_{\nu}^{q})}(t)=(-1)^{m+n-1}(1-t)^{\ell}\sum_{\sigma\in\mathcal{D}_{V^{\prime}}}\sum_{\begin{subarray}{c}\tau\in\mathcal{D}_{V^{\prime},n}^{q}\\\
|\tau|=\sigma\end{subarray}}(-t)^{\\#\\{\text{even fixed points of
}\sigma\\}}(1-t)^{\\#\\{\text{other cycles of }\sigma\\}}.$

Since $2r\notin V^{\prime}$, given any $\sigma\in\mathcal{D}_{V^{\prime}}$ we
can construct a $\tau\in\mathcal{D}_{V^{\prime},r}^{q}$ with $|\tau|=\sigma$
by labeling the largest entry of each cycle of $\sigma$ with $0$ and freely
labeling all of the entries of $\sigma$ with the elements of
$\\{0,\dots,q-1\\}$. This means that there are exactly
$q^{|V^{\prime}|-\\#\\{\text{cycles of }\sigma\\}}$ many
$\tau\in\mathcal{D}_{V^{\prime},r}^{q}$ with $|\tau|=\sigma$.

Letting $\text{cyc}(\sigma)$ be the number of cycles of $\sigma$, this means
that we have

$\displaystyle\chi_{\mathcal{L}(\mathcal{K}_{\nu}^{q})}(t)$
$\displaystyle=(-1)^{m+n-1}(1-t)^{\ell}\sum_{\sigma\in\mathcal{D}_{V^{\prime}}}q^{|V^{\prime}|-\text{cyc}(\sigma)}(-t)^{\\#\\{\text{even
fixed pts of }\sigma\\}}(1-t)^{\\#\\{\text{other cycles of }\sigma\\}}$
$\displaystyle=(-1)^{m+n-1}(1-t)^{\ell}q^{|V^{\prime}|}\sum_{\sigma\in\mathcal{D}_{V^{\prime}}}\left(\frac{-t}{q}\right)^{\\#\\{\text{even
fixed points of }\sigma\\}}\left(\frac{1-t}{q}\right)^{\\#\\{\text{other
cycles of }\sigma\\}}$
$\displaystyle=(-1)^{m+n-1}(1-t)^{\ell}q^{m+n-\ell-1}\Lambda_{V}\left(\frac{1-t}{m},\frac{1-t}{m},1,0,\frac{-t}{m},1\right),$

as desired, with the last equality following from Lemma 6.8. ∎

###  8.2. Generating Function Proofs

Since $\mathcal{H}_{n,k}^{m}=\mathcal{H}_{\nu}^{m}$ for
$\nu=(\underbrace{k,k,\dots,k}_{n})$, we are now able to prove Theorem 5.4.

###### Proof of Theorem 5.4.

By Theorem 8.3, we have

$\chi_{\mathcal{L}(\mathcal{H}_{n,k}^{m})}(t)=(-1)^{nk+n-1}(1-t)^{k}m^{nk+n-k-1}\Lambda_{S_{n}^{k}}\left(\frac{1-t}{m},\frac{1-t}{m},1,0,\frac{-t}{m},1\right),$

where

$S_{n}^{k}=\\{1,3,\dots,2nk-1\\}\sqcup\\{2k,4k,\dots,2nk\\}.$

We have

$\displaystyle\sum_{n\geq
1}\chi_{\mathcal{L}(\mathcal{H}_{n,k}^{m})}(t)u^{n-1}$
$\displaystyle=\sum_{n\geq
1}(-1)^{nk+n-1}(1-t)^{k}m^{nk+n-k-1}\Lambda_{S_{n}^{k}}\left(\frac{1-t}{m},\frac{1-t}{m},1,0,\frac{-t}{m},1\right)u^{n-1}$
$\displaystyle=(t-1)^{k}\sum_{n\geq
1}\Lambda_{S_{n}^{k}}\left(\frac{1-t}{m},\frac{1-t}{m},1,0,\frac{-t}{m},1\right)((-m^{k+1})u)^{n-1}.$

By Theorem 7.1, this last sum is equal to

$(t-1)^{k}\sum_{n\geq
1}\frac{\left(\frac{1-t}{m}\right)^{(n-1)}\left(\left(\frac{1-t}{m}+1\right)^{(n-1)}\right)^{k}((-m)^{n-1})^{k+1}u^{n-1}}{\prod_{i=0}^{n-1}\left(1-\left(\frac{1-t}{m}+i\right)^{k-1}\left[\left(\frac{1-t}{m}+i\right)\frac{-1}{m}-\left(\frac{1-t}{m}+i\right)i\right](-m)^{k+1}u\right)}.$

Now,

$\displaystyle(-m)^{n-1}\left(\frac{1-t}{m}\right)^{(n-1)}$
$\displaystyle=(-m)^{n-1}\prod_{j=1}^{n-1}\left(\frac{1-t}{m}+j-1\right)$
$\displaystyle=\prod_{j=1}^{n-1}t-1-(j-1)m$ $\displaystyle=(t-1)_{n-1,m}.$

Similarly,

$(t-1)(-m)^{n-1}\left(\frac{1-t}{m}+1\right)^{(n-1)}=(t-1)\prod_{j=1}^{n-1}(t-1-jm)=\prod_{j=0}^{n-1}(t-1-jm)=(t-1)_{n,m}.$

Thus, the generating function formula above simplifies to

$\sum_{n\geq 1}\chi_{\mathcal{L}(\mathcal{H}_{n,k}^{m})}(t)u^{n-1}=\sum_{n\geq
1}\frac{(t-1)_{n-1,m}\left((t-1)_{n,m}\right)^{k}u^{n-1}}{\prod_{i=0}^{n-1}\left(1-(im+1)(t-(im+1))^{k}u\right)},$

as desired. ∎

Since $\mathcal{J}_{n,k}^{m}=\mathcal{H}_{\nu}^{m}$ for
$\nu=(k,\underbrace{0,\dots,0}_{n-1})$, a similar argument allows us to prove
Theorem 5.6.

###### Proof of Theorem 5.6.

By Theorem 8.3, we have

$\chi_{\mathcal{J}_{n,k}^{m}}(t)=\begin{cases}(t-1)^{k},&n=1\\\
(-m)^{n+k-1}\Lambda_{T_{n}^{k}}\left(\frac{1-t}{m},\frac{1-t}{m},1,0,\frac{-t}{m},1\right),&n\geq
2\end{cases},$

so

$\displaystyle\sum_{n\geq 2}\chi_{\mathcal{J}_{n,k}^{m}}(t)u^{n-1}$
$\displaystyle=(-m)^{k}\sum_{n\geq
2}\Lambda_{T_{n}^{k}}\left(\frac{1-t}{m},\frac{1-t}{m},1,0,\frac{-t}{m},1\right)(-mu)^{n-1},$

and by Theorem 5.5 the last sum is equal to

$(-m)^{k}\sum_{n\geq
2}\frac{\left(\frac{1-t}{m}\right)^{(n-2)}\Lambda_{T_{2}^{k}}(x+n-2,\bar{x}+n-2)\left|{}_{\left(\frac{1-t}{m},\frac{1-t}{m},1,0,\frac{-t}{m},1\right)}\right.(-m)^{n-1}u^{n-1}}{\prod_{i=0}^{n-2}\left[1-\left(\frac{-1}{m}-i\right)(-m)u\right]}.$

Now, we know that

$\displaystyle\Lambda_{T_{2}^{k}}(x+i,\bar{x}+i)=$
$\displaystyle(y+\bar{x}+i)(x+\bar{z}+i)^{k}$
$\displaystyle+(x+i)^{k-1}\left[(x+i)(\bar{y}-y)-k(\bar{x}+i)(\bar{z}-z)-(x+i)(\bar{x}+i)\right],$

so

$\displaystyle(-m)$
${}^{k+1}\Lambda_{T_{2}^{k}}(x+n-2,\bar{x}+n-2)\left|{}_{\left(\frac{1-t}{m},\frac{1-t}{m},1,0,\frac{-t}{m},1\right)}\right.$
$\displaystyle=(t-1-m(n-2))\left[(t-1-m(n-1))^{k}+(m(n-2)+1)(t-1-m(n-2))^{k-1}\right].$

Since $(-m)^{n-2}\left(\frac{1-t}{m}\right)^{(n-2)}=(t-1)_{n-2,m}$ and
$(t-1-m(n-2))(t-1)_{n-2,m}=(t-1)_{n-1,m}$, the generating function formula
simplifies to

$\displaystyle\sum_{n\geq 2}$
$\displaystyle\chi_{\mathcal{J}_{n,k}^{m}}(t)u^{n-1}$
$\displaystyle=\sum_{n\geq
2}\frac{(t-1)_{n-1,m}\left[(t-1-m(n-1))^{k}+(m(n-2)+1)(t-1-m(n-2))^{k-1}\right]u^{n-1}}{\prod_{i=0}^{n-2}\left[1-(mi+1)u\right]},$

as desired.

∎

##  9\. Final Remarks and Further Questions

In [14, Corollary 3.9], it was shown that
$-\chi_{\mathcal{L}(\mathcal{H}_{2n-1})}(0)$ is equal to the _(unsigned)
Genocchi number_ $g_{n}$, and Hetyei’s count of the number of regions of
$\mathcal{H}_{2n-1}$ in [10] tells us that
$-\chi_{\mathcal{L}(\mathcal{H}_{2n-1})}(-1)$ is equal to the median Genocchi
number $h_{n}$. It therefore seems reasonable to define a family of
generalizations $g_{n,k}$ and $h_{n,k}$ by

(10) $\displaystyle g_{n,k}$
$\displaystyle=(-1)^{nk+n-1}\chi_{\mathcal{L}(\mathcal{H}_{n,k})}(0)$ (11)
$\displaystyle h_{n,k}$
$\displaystyle=(-1)^{nk+n-1}\chi_{\mathcal{L}(\mathcal{H}_{n,k})}(-1).$

Using Corollary 5.3, we can derive generating function formulas for these
sequences as functions of $k$.

(12) $\displaystyle\sum_{n\geq 1}g_{n,k}u^{n}=\sum_{n\geq
1}(-1)^{nk+n-1}\chi_{\mathcal{L}(\mathcal{H}_{n,k})}(0)$
$\displaystyle=\sum_{n\geq
1}\frac{(n-1)!(n!)^{k}u^{n}}{\prod_{i=1}^{n}(1+i^{2}u)}$ (13)
$\displaystyle\sum_{n\geq 1}h_{n,k}u^{n}=\sum_{n\geq
1}(-1)^{nk+n-1}\chi_{\mathcal{L}(\mathcal{H}_{n,k})}(-1)$
$\displaystyle=\sum_{n\geq
1}\frac{n!((n+1)!)^{k}u^{n}}{\prod_{i=1}^{n}(1+i(i+1)u)}$

These generating functions reduce to generating functions due to Barsky and
Dumont [1] for the Genocchi and median Genocchi numbers, respectively, when
$k=1$.

Specializing the proof of Theorem 8.3 to $m=1$ and $V=S_{n}^{k}$ (c.f. [14,
Theorem 4.14]), we see that

(14)
$\chi_{\mathcal{L}(\mathcal{H}_{n,k})}(t)=(1-t)^{k}\sum_{\sigma\in\mathcal{D}_{S_{n-1}^{k}}}(-t)^{\\#\\{\text{even
fixed points of }\sigma\\}}(1-t)^{\\#\\{\text{other cycles of }\sigma\\}}$

By evaluating Equation (14) at $t=-1$, we obtain a decomposition of $h_{n,k}$
into powers of $2$ for all $n\geq 2$:

(15) $h_{n,k}=\sum_{j=1}^{k(n-1)}h_{n-1,k}^{j}2^{j+k},$

where $h_{n,k}^{j}$ is the number of D-permutations on $S_{n}^{k}$ with
exactly $j$ cycles that are not even fixed points.

In [14, Corollary 4.16], the authors obtain a decomposition of the Genocchi
numbers into powers of $2$ that is expected to be the same as a decomposition
due to Sundaram [18, Theorem 3.15]. However, the proof of this decomposition
relies on a factorization of $\chi_{\mathcal{L}(\mathcal{H}_{2n-1})}(t)$ [14,
Theorem 4.15] whose proof does not immediately generalize to
$\mathcal{H}_{n,k}$.

######  Question 9.1.

What is the largest power of $(t-1)$ that divides
$\chi_{\mathcal{L}(\mathcal{H}_{n,k})}(t)$?

######  Question 9.2.

Is there a decomposition of $g_{n,k}$ analogous to Sundaram’s decomposition of
$g_{n}$?

There is a wealth of literature studying the Genocchi numbers and median
Genocchi numbers. It would be interesting to see which results about those
sequences can be generalized to this broader setting. For example, the
Genocchi and median Genocchi numbers can be obtained from one another via a
triangular array known as a Seidel triangle (see, e.g., [7]).

######  Question 9.3.

Is there an analogous relationship between $g_{n,k}$ and $h_{n,k}$?

## Acknowledgments

This paper is based on work conducted during the author’s dissertation
research. As such, he would like to thank his thesis committee: Bruno
Benedetti, Mitsunori Ogihara, Richard Stanley, and especially his advisor
Michelle Wachs, without whose guidance this paper would not have been
possible. The author also wishes to thank Vic Reiner for introducing him to
the notion of Ferrers graphs, and Bennet Goeckner and Joseph Doolittle for
their help with editing.

## References

  * [1] D. Barsky and D. Dumont  “Congruences pour les nombres de Genocchi de 2e espèce”  In _Study Group on Ultrametric Analysis. 7th–8th years: 1979–1981 (Paris, 1979/1981) (French)_ Secrétariat Math., Paris, 1981, pp. Exp. No. 34, 13
  * [2] A. Claesson, S. Kitaev, K. Ragnarsson and B. E. Tenner  “Boolean complexes for Ferrers graphs”  In _Australas. J. Combin._ 48, 2010, pp. 159–173
  * [3] A. Corso and U. Nagel  “Monomial and toric ideals associated to Ferrers graphs”  In _Trans. Amer. Math. Soc._ 361.3, 2009, pp. 1371–1395  DOI: 10.1090/S0002-9947-08-04636-9
  * [4] P. Cranford et al.  “Biconed graphs, edge-rooted forests, and h-vectors of matroid complexes”  In _arXiv e-prints_ , 2020, pp. arXiv:2005.09138  arXiv:2005.09138 [math.CO]
  * [5] T. A. Dowling  “A class of geometric lattices based on finite groups”  In _J. Combinatorial Theory Ser. B_ 14, 1973, pp. 61–86
  * [6] D. Dumont  “Conjectures sur des symétries ternaires liées aux nombres de Genocchi” Formal power series and algebraic combinatorics (Montreal, PQ, 1992)  In _Discrete Math._ 139.1-3, 1995, pp. 469–472  DOI: 10.1016/0012-365X(94)00149-D
  * [7] D. Dumont  “Further triangles of Seidel-Arnold type and continued fractions related to Euler and Springer numbers”  In _Adv. in Appl. Math._ 16.3, 1995, pp. 275–296  DOI: 10.1006/aama.1995.1014
  * [8] D. Dumont  “Interprétations combinatoires des nombres de Genocchi”  In _Duke Math. J._ 41, 1974, pp. 305–318  URL: http://projecteuclid.org/euclid.dmj/1077310398
  * [9] R. Ehrenborg and S. Willigenburg  “Enumerative properties of Ferrers graphs”  In _Discrete Comput. Geom._ 32.4, 2004, pp. 481–492  DOI: 10.1007/s00454-004-1135-1
  * [10] G. Hetyei  “Alternation acyclic tournaments”  In _European J. Combin._ 81, 2019, pp. 1–21  DOI: 10.1016/j.ejc.2019.04.007
  * [11] A. Lazar  “The homogenized Linial arrangement and its consequences in enumerative combinatorics”, 2020
  * [12] A. Lazar and M. L. Wachs  “A Dowling generalization of the homogenized Linial arrangement” In preparation, 2021
  * [13] A. Lazar and M. L. Wachs  “On the homogenized Linial arrangement: intersection lattice and Genocchi numbers”  In _Séminaire Lotharingien de Combinatoire (FPSAC 2019)_ 82B, 2019, pp. Paper 93, 12pp  URL: https://www.mat.univie.ac.at/~slc/wpapers/FPSAC2019/93.html
  * [14] A. Lazar and M. L. Wachs  “The homogenized Linial arrangement and Genocchi numbers”  In _arXiv e-prints_ , 2019  arXiv:1910.07651
  * [15] A. Postnikov and R. P. Stanley  “Deformations of Coxeter hyperplane arrangements” In memory of Gian-Carlo Rota  In _J. Combin. Theory Ser. A_ 91.1-2, 2000, pp. 544–597  DOI: 10.1006/jcta.2000.3106
  * [16] A. Randrianarivony  “Polynômes de Dumont-Foata généralisés”  In _Sém. Lothar. Combin._ 32, 1994, pp. Art. B32d, approx. 12
  * [17] T. Selig, J. P. Smith and E. Steingrímsson  “EW-tableaux, Le-tableaux, tree-like tableaux and the abelian sandpile model”  In _Electron. J. Combin._ 25.3, 2018, pp. Paper 3.14, 32
  * [18] S. Sundaram  “The homology of partitions with an even number of blocks”  In _J. Algebraic Combin._ 4.1, 1995, pp. 69–92  DOI: 10.1023/A:1022437708487
  * [19] J. R. Swenson  “The chromatic polynomial of a complete bipartite graph”  In _Amer. Math. Monthly_ 80, 1973, pp. 797–798  DOI: 10.2307/2318170
  * [20] M. L. Wachs and J. W. Walker  “On geometric semilattices”  In _Order_ 2.4, 1986, pp. 367–385  DOI: 10.1007/BF00367425
  * [21] T. Zaslavsky  “Facing up to arrangements: face-count formulas for partitions of space by hyperplanes”  In _Mem. Amer. Math. Soc._ 1.issue 1, 154, 1975, pp. vii+102
  * [22] J. Zeng  “Sur quelques propriétés de symétrie des nombres de Genocchi”  In _Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993)_ 153.1-3, 1996, pp. 319–333  DOI: 10.1016/0012-365X(95)00145-M