[1,2]Qi Zhang

[1]College of Science, Liaoning Petrochemical University, No.1 Dandong Road,
Fushun, 113001, Liaoning, People’s Republic of China

2]Liaoning Provincial Key Laboratory of Novel Micro-Nano Functional Materials,
Liaoning Petrochemical University, No.1 Dandong Road, Fushun, 113001,
Liaoning, People’s Republic of China

# Hamiltonian formulation of linear non-Hermitian systems

<EMAIL_ADDRESS>*  [

###### Abstract

For a linear non-Hermitian system, I demonstrate that a Hamiltonian can be
constructed such that the non-Hermitian equations can be expressed exactly in
the form of Hamilton’s canonical equations. This is first shown for discrete
systems and then extended to continuous systems. With this Hamiltonian
formulation, I am able to identify a conserved charge by applying Noether’s
theorem and recognize adiabatic invariants. When applied to Hermitian systems,
all the results reduce to the familiar ones associated with the Schrödinger
equation.

###### keywords:

Linear non-Hermitian system, Hamilton’s canonical equation, Adiabatic
invariant, Conserved charge

##  1 Introduction

For a conserved system, its Newton’s equations of motion can be recast in the
canonical Hamiltonian form as discussed extensively in textbooks on classical
mechanics [1]. Interestingly, a Schrödinger equation can also be formulated in
a Hamiltonian framework [2, 3]. Consider a Schrödinger equation,

$\text{i}\hbar\frac{\partial}{\partial t}|\psi\rangle=H_{0}|\psi\rangle\,,$
(1)

where $H_{0}$ is a Hermitian matrix and
$|\psi\rangle=(\psi_{1},\psi_{2},...,\psi_{n})^{T}$ is a column vector. It has
been shown that it can be reformulated as Hamilton’s equations of motion with
${\mathcal{H}}_{0}=\braket{\Psi}{H_{0}}{\Psi}$ as its Hamiltonian and Poisson
brackets between $\psi^{*}_{i}$’s and $\psi^{*}_{j}$’s [2, 3]. Such a
reformulation not only provides a distinct theoretical perspective into
quantum dynamics described by the Schrödinger equation, with access to various
tools developed for Hamiltonian systems [1, 4, 5], but also enables
approximate quantum dynamics semi-classically [6].

In recent decades, sparked by studies of PT-symmetric systems [7] and bosonic
Bogoliubov excitations [8], there has been substantial interest and research
into non-Hermitian systems, both theoretically [9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23] and experimentally [24, 25, 26, 27, 28, 29, 30].
In this work, I demonstrate that a Hamiltonian formulation can also be
constructed for any linear non-Hermitian system. Specifically, when the
Hermitian matrix $H_{0}$ in the Schrödinger equation is replaced by a non-
Hermitian matrix $h$ that is diagonalizable, I show how to build a Hamiltonian
such that the non-Hermitian equation can be derived as its equations of
motion. I first consider the case where $h$ is a finite matrix, and then
extend the discussion to continuous systems. While specific non-Hermitian
systems have been formulated previously using Hamiltonian or Lagrangian
approaches [31, 32], the formulation presented here is generic and applicable
to any linear non-Hermitian system whose Hamiltonian matrix is diagonalizable.

This Hamiltonian formulation is applied to identify adiabatic invariants for
non-Hermitian systems and find a conserved charge using Noether’s theorem [5].
It is anticipated that more interesting results will emerge for linear non-
Hermitian systems, as many powerful analytical tools have been developed for
Hamiltonian systems [1]. Just as many nonlinear Hermitian systems, such as
Newton’s equations of motion and nonlinear Gross-Pitaevskii equations, can be
cast into canonical Hamiltonian form [33], it is desirable to find a
Hamiltonian formulation for nonlinear non-Hermitian systems. The method
introduced here is limited to certain special cases, and a more comprehensive
treatment of nonlinear non-Hermitian Hamiltonian systems remains an open
challenge for future work.

##  2 Discrete linear non-Hermitian systems

###  2.1 Key aspects of the dynamics

Conventional quantum systems can be either discrete, such as spins, or
continuous, such as electrons in atoms. For clarity, we first consider a
discrete linear non-Hermitian system, whose dynamical equation takes the form

$\text{i}\hbar\frac{\partial}{\partial t}|\psi\rangle=h|\psi\rangle\,.$ (2)

where, to distinguish from the Hermitian case, $h$ is denoted as an $n\times
n$ non-Hermitian matrix that is diagonalizable and
$|\psi\rangle=(\psi_{1},\psi_{2},...,\psi_{n})^{T}$ is a vector in an
$n$-dimensional linear space. This serves as a discrete model before extending
the formulation to continuous non-Hermitian systems. In general, the
diagonalizable matrix $h$ has two sets of $n$ eigenvectors $|a_{j}\rangle$ and
$|b_{j}\rangle$ with $j=1,\ldots n$ satisfying [34],

$h|a_{j}\rangle=E_{j}|a_{j}\rangle,\quad\langle b_{j}|h=\langle b_{j}|E_{j}.$
(3)

They are biorthonormal,

$\langle b_{i}|a_{j}\rangle=\delta_{ij},$ (4)

and complete,

$\sum_{j}|a_{j}\rangle\langle b_{j}|=1\,.$ (5)

The eigenvalues $E_{j}$ may be complex in general. The vectors $|a_{j}\rangle$
and $|b_{j}\rangle$ are referred to as the right and left eigenvectors of $h$,
respectively. Since $h$ is non-Hermitian, satisfying $h^{\dagger}\neq h$, the
right and left eigenvectors are usually distinct, i.e.
$|a_{j}\rangle\neq|b_{j}\rangle$.

This biorthogonal eigenbasis provides a framework to analyze the non-Hermitian
dynamics. For example, consider a general state $|\psi(t)\rangle$ satisfying
dynamics (2), which can be expanded as (when $h$ is diagonalizable such that
Eq. (5) holds),

$|\psi(t)\rangle=\sum_{j}c_{j}(t)|a_{j}\rangle,$ (6)

where the coefficients

$c_{j}(t)=c_{j}(0)e^{-\frac{\text{i}}{\hbar}E_{j}t}=\langle
b_{j}|\psi(t)\rangle,$ (7)

are given by the biorthonormal equation (4). Focusing on the subset of
eigenstates with nonzero $c_{j}$, we can construct corresponding coefficients,

$\bar{c}_{j}(t)c_{j}(t)=|C_{j}|^{2},$ (8)

where the $|C_{j}|^{2}$ are arbitrary constants. The variables $\bar{c}_{j}$
apparently evolve as

$\bar{c}_{j}(t)=\bar{c}_{j}(0)e^{\frac{\text{i}}{\hbar}E_{j}t},$ (9)

This defines a conjugate left state

$\langle\bar{\phi}(t)|=\sum_{j}\bar{c}_{j}(t)\langle b_{j}|,$ (10)

which, by the eigenrelation in Eq. (3), satisfies the conjugate dynamics

$-\text{i}\hbar\frac{\partial}{\partial
t}\langle\bar{\phi}|=\langle\bar{\phi}|h,$ (11)

showing $|\bar{\phi}\rangle$ evolves under the adjoint Hamiltonian
$h^{\dagger}$.

The dynamics given by Eq. (2) and (11) lead directly to

$\frac{\partial}{\partial t}\langle\bar{\phi}|\psi\rangle=0$ (12)

This shows that the overlap between the left and right states,
$\langle\bar{\phi}|\psi\rangle$, is conserved over time. However, the norm of
the right eigenstate $\langle\psi|\psi\rangle$ is in general not a constant
due to the non-Hermiticity of the Hamiltonian operator $h$ [35].

When the eigenvalues $E_{j}$ of the Hamiltonian $h$ are real, it is convenient
to initialize the biorthogonal wavefunctions as

$|\bar{c}_{j}(0)|=|c_{j}(0)|,$ (13)

for which $|\bar{c}_{j}(t)|=|c_{j}(t)|=|C_{j}|$ at any subsequent time t. In
this case, the biorthogonal formulation retains the normalization condition at
all times. Additionally, when $h$ becomes Hermitian, the left and right
eigenvectors become identical, i.e. $|a_{j}\rangle=|b_{j}\rangle$.
Consequently, the biorthogonal wavefunction $\langle\bar{\phi}|$ reduces to
the standard single wavefunction $\langle\psi|$, restoring the conventional
form of the Schrödinger equation. Here, conservation of the overlap
$\langle\bar{\phi}|\psi\rangle$ corresponds to conservation of the total
probability $\langle\psi|\psi\rangle$, as in standard quantum mechanics. The
biorthogonal framework therefore provides a natural generalization of the
Hermitian theory that recovers the standard results when $h$ is Hermitian.

###  2.2 The Hamiltonian formulation

The dynamics described by Eqs. (2) and (11) allow establishing a Hamiltonian
formulation for non-Hermitian systems in a straightforward manner. In this
formulation, the state should be represented by canonical variables. We can
naturally take $q_{j}=i\hbar\psi_{j}$ as the canonical variables. Unlike the
Hermitian case, since $h\neq h^{\dagger}$ here, the pairs
$(i\hbar\psi_{j},\psi_{j}^{*})$ can no longer constitute canonical variables
[31, 32]. This arises from the non-Hermiticity of $h$, which prevents
$\psi_{j}$ and $\psi_{j}^{*}$ from satisfying the required Poisson bracket
relations to be canonically conjugate. The non-Hermiticity induces additional
constraints between the wavefunction and its complex conjugate, requiring a
more careful construction of the phase space. Identifying an appropriate set
of canonical variables is key to formulating a valid Hamiltonian framework for
non-Hermitian systems.

Fortuitously, the right and left eigenstate dynamics in Eqs. (2) and (11)
indicate that the components of the conjugate left state
$\langle\bar{\phi}|=(\bar{\phi}_{1},\bar{\phi}_{2},\ldots,\bar{\phi}_{n})$
constitute the canonical momenta conjugate to the canonical coordinates given
by the right state $|\psi\rangle=(\psi_{1},\psi_{2},\ldots,\psi_{n})^{T}$,
with $q_{k}=\text{i}\hbar\psi_{k},p_{k}=\bar{\phi}_{k}$ forming canonical
variable pairs. The Hamilton’s equations then take the form

$\frac{d(\text{i}\hbar\psi_{k})}{dt}=\frac{\partial\mathcal{H}}{\partial\bar{\phi}_{k}},\quad\frac{d(\bar{\phi}_{k})}{dt}=-\frac{\partial\mathcal{H}}{\partial(\text{i}\hbar\psi_{k})},$
(14)

where the Hamiltonian $\mathcal{H}$ for these canonical equations is

$\mathcal{H}(\bar{\phi}_{1},\ldots,\bar{\phi}_{n},\text{i}\hbar\psi_{1},\ldots,\text{i}\hbar\psi_{n})=\langle\bar{\phi}|h|\psi\rangle.$
(15)

Thus, the phase space dimension is $2n$, consistent with the canonical
dynamics. The biorthogonal framework thereby allows identifying a proper phase
space description despite the non-Hermiticity of $h$. When $h$ becomes
Hermitian, $|\bar{\phi}\rangle$ reduces to $|\psi\rangle$, restoring the
canonical structure of the standard Schrödinger equation.

To clarify the canonical equations, we can make a time-independent canonical
transformation

$(\bar{\phi}_{1},\ldots,\bar{\phi}_{n},\text{i}\hbar\psi_{1},\ldots,\text{i}\hbar\psi_{n})\rightarrow(\bar{c}_{1},\ldots,\bar{c}_{n},\text{i}\hbar
c_{1},\ldots,\text{i}\hbar c_{n}),$

leaving the Hamiltonian $\mathcal{H}$ numerically unchanged. The canonical
equations then become

$\frac{d(\text{i}\hbar
c_{j})}{dt}=\frac{\partial\mathcal{H}}{\partial\bar{c}_{j}},\quad\frac{d\bar{c}_{j}}{dt}=-\frac{\partial\mathcal{H}}{\partial(\text{i}\hbar
c_{j})},$ (16)

with $\mathcal{H}$ expressed as

$\mathcal{H}=\sum_{j=1}^{n}E_{j}\bar{c}_{j}c_{j}.$ (17)

The transformed variables $c_{j}$ and $\bar{c}_{j}$ evolve as Eqs. (7) and
(9).

The Lagrangian of the non-Hermitian dynamics can be expressed as

$\mathcal{L}={\text{i}}\hbar\langle\bar{\phi}|\frac{\partial}{\partial
t}|\psi\rangle-\langle\bar{\phi}|h|\psi\rangle,$ (18)

where the Lagrangian equations

$\frac{d}{dt}\frac{\partial\mathcal{L}}{\partial\dot{\psi}_{j}}-\frac{\partial\mathcal{L}}{\partial\psi_{j}}=0$
(19)

are equivalent to the canonical equations in (14). This demonstrates the
correspondence between the Lagrangian and Hamiltonian formulations, with the
conjugate left and right states providing the necessary structure to construct
a valid Lagrangian despite $h$ being non-Hermitian. The biorthonormal
framework thereby allows deriving a self-consistent Lagrangian description in
addition to the Hamiltonian dynamics.

###  2.3 An application: recognizing the adiabatic invariants

As an application, consider a Hamiltonian
$\mathcal{H}(\mathbf{R})=\langle\bar{\phi}|h(\mathbf{R})|\psi\rangle$ that
depends on slowly varying parameters $\mathbf{R}$. When the eigenenergies
$E_{j}$ are real, according to Eqs. (6), (8) and (10), the variables
$(\bar{c}_{j},c_{j})$ and thus $(\bar{\phi}_{j},\psi_{j})$ undergo periodic
oscillations. In this case, the $n$ actions

$I_{j}=\frac{\text{i}\hbar}{2\pi}\oint\bar{\phi}_{j}d\psi_{j}.$ (20)

defined by the adiabatic theorem, are invariant. In the canonical
representation of Eq. (16), this becomes

$I_{j}=\frac{\text{i}\hbar}{2\pi}\oint\bar{c}_{j}d\hbar
c_{j}=\hbar\bar{c}_{j}(0)c_{j}(0)=\hbar|C_{j}|^{2},$ (21)

showing the occupation numbers remain constant when eigenenergies are real,
consistent with previous results [36]. This demonstrates the non-Hermitian
adiabatic theorem is identical to the conventional quantum one when energies
are entirely real. Adiabatic invariance holds for non-Hermitian Hamiltonians
just as in standard quantum mechanics.

###  2.4 An example

As a specific example, we consider the two-level Lorentzian system from Ref.
[37], governed by the Bogoliubov-de Gennes equations

${\text{i}}\hbar\frac{d}{dt}\left(\begin{array}[]{c}a\\\
b\end{array}\right)=h\left(\begin{array}[]{c}a\\\
b\end{array}\right)=\left(\begin{array}[]{cc}z&x+\text{i}y\\\
-x+\text{i}y&-z\end{array}\right)\left(\begin{array}[]{c}a\\\
b\end{array}\right),$ (22)

where $x,y,z$ are real parameters. These equations describe the non-Hermitian
dynamics of bosonic Bogoliubov quasiparticles in various systems. The
biorthonormal eigenstates of $h$ are

$|a_{1}\rangle=\left(\begin{array}[]{c}u\\\
v\end{array}\right),\quad|a_{2}\rangle=\left(\begin{array}[]{c}v^{*}\\\
u^{*}\end{array}\right),|b_{1}\rangle=\left(\begin{array}[]{c}u\\\
-v\end{array}\right),\quad|b_{2}\rangle=\left(\begin{array}[]{c}-v^{*}\\\
u^{*}\end{array}\right),\\\ $ (23)

satisfying Eqs. (4) and (5), with $|u|^{2}-|v|^{2}=1$. The variables $(u,v)$
in Eq. (23) are functions of the parameters $(x,y,z)$, defined explicitly as

$\displaystyle
u=-\text{sgn}(z)\frac{\left(z^{2}-x^{2}-y^{2}\right)^{\frac{1}{2}}+|z|}{\left\\{\left[|z|+\left(z^{2}-x^{2}-y^{2}\right)^{\frac{1}{2}}\right]^{2}-x^{2}-y^{2}\right\\}^{\frac{1}{2}}}$
$\displaystyle
v=\frac{x-\text{i}y}{\left\\{\left[|z|+\left(z^{2}-x^{2}-y^{2}\right)^{\frac{1}{2}}\right]^{2}-x^{2}-y^{2}\right\\}^{\frac{1}{2}}},$
(24)

The $\text{sgn}(z)$ in Eq. (2.4) represents the sign function of the parameter
$z$. For a state $|\psi\rangle=(\psi_{1},\psi_{2})^{T}$, if $\langle
b_{1}|\psi\rangle\neq 0$ and $\langle b_{2}|\psi\rangle\neq 0$, the conjugate
state is

$\langle\bar{\phi}|=(\bar{\phi}_{1},\bar{\phi}_{2})=\frac{|C_{1}|^{2}}{\langle
b_{1}|\psi\rangle}\langle b_{1}|+\frac{|C_{2}|^{2}}{\langle
b_{2}|\psi\rangle}\langle b_{2}|,$ (25)

yielding,

$\displaystyle\bar{\phi}_{1}$ $\displaystyle=$
$\displaystyle\frac{|C_{1}|^{2}u^{*}}{u^{*}\psi_{1}-v^{*}\psi_{2}}-\frac{|C_{2}|^{2}v}{-v\psi_{1}+u\psi_{2}},$
$\displaystyle\bar{\phi}_{2}$ $\displaystyle=$
$\displaystyle-\frac{|C_{1}|^{2}v^{*}}{u^{*}\psi_{1}-v^{*}\psi_{2}}+\frac{|C_{2}|^{2}u}{-v\psi_{1}+u\psi_{2}}.$
(26)

The Hamiltonian
$\mathcal{H}(\bar{\phi}_{1},\bar{\phi}_{2},\text{i}\hbar\psi_{1},\text{i}\hbar\psi_{2})=\langle\bar{\phi}|h|\psi\rangle$
and Lagrangian $\mathcal{L}$ can then be constructed. During the evolution in
Eq. (22), the overlap $\langle\bar{\phi}|\psi\rangle$ is conserved per Eq.
(12). When $z^{2}\geq x^{2}+y^{2}$, the two eigenenergies of $h$ are real. In
this parameter region, as $(x,y,z)$ vary adiabatically, the adiabatic
invariants in Eqs. (20) and (21) apply.

##  3 Extension to continuous systems

Transitioning from a discrete to a continuous system is possible when the
number of degrees of freedom becomes non-countably infinite. For clarity, we
adopt the coordinate representation by denoting $|\mathbf{x}\rangle$ as the
coordinate eigenstate with eigenvalue $\mathbf{x}$, i.e.
$\hat{x}|\mathbf{x}\rangle=\mathbf{x}|\mathbf{x}\rangle$ where $\hat{x}$ is
the coordinate operator. As in the discrete case, the eigenfunctions take the
biorthonormal form of Eq. (3) but with the $j$th right and left eigenfunctions
$a_{j}(\mathbf{x})=\langle\mathbf{x}|a_{j}\rangle$ and
$b_{j}(\mathbf{x})=\langle\mathbf{x}|b_{j}\rangle$ now being continuous
functions of $\mathbf{x}$. The biorthonormal and completeness conditions
become

$\int
b_{j}(\mathbf{x})^{*}a_{k}(\mathbf{x})d\mathbf{x}=\delta_{jk},\quad\sum_{j}a_{j}(\mathbf{x})b_{j}(\mathbf{x^{\prime}})^{*}=\delta(\mathbf{x}-\mathbf{x}^{\prime}).$
(27)

In terms of the wavefunction $\psi(\mathbf{x})=\langle\mathbf{x}|\psi\rangle$,
the Schrödinger equation is

$\text{i}\hbar\frac{\partial}{\partial
t}\psi(\mathbf{x})=\hat{h}\psi(\mathbf{x}),$ (28)

where $\hat{h}$ is the Hamiltonian operator in coordinate representation,
related to the matrix element
$\langle\mathbf{x}^{\prime}|h|\mathbf{x}\rangle=\hat{h}(\hat{x},-\text{i}\hbar\partial/\partial\mathbf{x})\delta(\mathbf{x}-\mathbf{x}^{\prime})$.
The canonical variables follow identically to the discrete case: (i) expanding
Š×(x) as

$\psi(\mathbf{x})=\sum_{j}c_{j}a_{j}(\mathbf{x}),$ (29)

(ii) constructing the canonical conjugate field

$\bar{\phi}(\mathbf{x})=\langle\bar{\phi}|\mathbf{x}\rangle=\sum_{j}\bar{c}_{j}b_{j}^{*}(\mathbf{x}),$
(30)

with

$\bar{c}_{j}c_{j}=|C_{j}|^{2}.$ (31)

As shown, $\bar{\phi}(\mathbf{x})$ and $\psi(\mathbf{x})$ satisfy the
canonical equations

$\frac{d(\text{i}\hbar\psi_{k})}{dt}=\frac{\partial\mathbb{H}}{\partial\bar{\phi}_{k}},\quad\frac{d(\bar{\phi}_{k})}{dt}=-\frac{\partial\mathbb{H}}{\partial(\text{i}\hbar\psi_{k})},$
(32)

with Hamiltonian density

$\mathbb{H}=\bar{\phi}(\mathbf{x})\hat{h}\psi(\mathbf{x}).$ (33)

The Lagrangian density is

$\mathbb{L}(\mathbf{x})={\text{i}}\hbar\bar{\phi}(\mathbf{x})\dot{\psi}(\mathbf{x})-\bar{\phi}(\mathbf{x})\hat{h}\psi(\mathbf{x}).$
(34)

The equations of motion satisfy the Euler-Lagrange equation for a continuous
field,

$\frac{\partial\mathbb{L}}{\partial\psi}-\nabla\cdot\frac{\partial\mathbb{L}}{\partial(\nabla\psi)}-\frac{\partial}{\partial
t}\left(\frac{\partial\mathbb{L}}{\partial\dot{\psi}}\right)=0.$ (35)

As an application, consider the linear non-Hermitian dynamics given by the 3D
Schrödinger equation with a complex potential $V(\mathbf{x})$

$\text{i}\hbar\frac{\partial}{\partial
t}\psi(\mathbf{x},t)=-\frac{\hbar^{2}}{2m}\nabla^{2}\psi(\mathbf{x},t)+V(\mathbf{x})\psi(\mathbf{x},t).$
(36)

The Lagrangian density of this system is (dropping the edge term)

$\mathbb{L}(\mathbf{x})={\text{i}}\hbar\bar{\phi}(\mathbf{x})\dot{\psi}(\mathbf{x})-\bar{\phi}(\mathbf{x})V\psi(\mathbf{x})-\frac{\hbar^{2}}{2m}\nabla\bar{\phi}(\mathbf{x})\cdot\nabla\psi.$
(37)

Consider an intrinsic symmetry of the non-Hermitian dynamics

$\psi\rightarrow\psi^{\prime}=e^{\text{i}\alpha}\psi,\quad\bar{\phi}\rightarrow\bar{\phi}^{\prime}=e^{-\text{i}\alpha}\bar{\phi},$
(38)

with $\alpha$ a constant. This symmetry follows from the dynamics (28) and
biorthogonal relations (6)-(31). For infinitesimal $\alpha$

$\psi\rightarrow\psi^{\prime}=\psi+\text{i}\alpha\psi,\quad\bar{\phi}\rightarrow\bar{\phi}^{\prime}=\bar{\phi}-\text{i}\alpha\bar{\phi}.$
(39)

Applying Noether’s theorem for intrinsic symmetries
$j^{\mu}=\frac{\partial\mathbb{L}}{\partial(\partial_{\mu}\psi)}\delta\psi$
derives the conserved currents (up to an unimportant constant factor)

$j^{0}=\bar{\phi}\psi,\quad
j^{\mathbf{x}}=\frac{i\hbar}{2m}(\bar{\phi}\nabla\psi-\psi\nabla\bar{\phi}).$
(40)

Since $\psi$ and $\bar{\phi}$ are intimately related, the gradients
$\nabla\psi$ and $\nabla\bar{\phi}$ must be treated equally as general
velocities in deriving this.

Equation (40) gives,

$\frac{\partial}{\partial
t}(\bar{\phi}\psi)+\frac{i\hbar}{2m}\nabla\cdot(\bar{\phi}\nabla\psi-\psi\nabla\bar{\phi})=0$
(41)

This identifies a conserved charge

$Q=\int\bar{\phi}(\mathbf{x})\psi(\mathbf{x})d^{3}\mathbf{x}$ (42)

When $V(\mathbf{x})$ becomes real, $Q$ restores to the standard probability
density of the Schrödinger wavefunction.

The conserved charge suggests that $\bar{\phi}(\mathbf{x})\psi(\mathbf{x})$
may represent the real probability amplitude of finding a non-Hermitian
particle described by state $|\psi\rangle$ at position $\mathbf{x}$. Thus, by
employing the Lagrangian density (37), it should also be of considerable
interest to derive the semiclassical trajectories of a wavepacket of a
continuous-level non-Hermitian system, as has been done for traditional
quantum systems [6]. This would provide insight into the motion and
localization properties of non-Hermitian wavepackets, which could be a
potentially fruitful direction for further research.

##  4 Summary

In summary, a Hamiltonian formulation has been established for linear non-
Hermitian dynamics. As applications, adiabatic invariants and a conserved
charge have been obtained. All of these results naturally reduce to familiar
quantities in Hermitian quantum systems. This work advances the theoretical
understanding of non-Hermitian systems and highlights promising directions for
future research. In particular, quantization of non-Hermitian systems and
deriving semiclassical trajectories of wavepackets remain areas of
considerable interest. Generalization to nonlinear non-Hermitian systems is
also of great interest. Overall, this Hamiltonian formulation provides a
foundation to further develop analytical tools for linear non-Hermitian
systems and potentially for nonlinear ones.

Acknowledgments

I thank Biao Wu from Peking University for the helpful discussion.

## References

  * [1] V.I. Arnold (1989) Mathematical Methods of Classical Mechanics. Springer. ISBN 9780387968902.
  * [2] A. Heslot, Phys. Rev. D 31, 1341 (1985).
  * [3] S. Weinberg, Ann. Phys. (N.Y.) 194, 336 (1989).
  * [4] P.A.M. Dirac, Proc. R. Soc. 107, 725 (1925); M. Born, V.A. Fock, Zeitschrift für Physik A 51 165 (1928).
  * [5] E. Noether, Mathematisch-Physikalische Klasse. 1918, 235 (1918).
  * [6] M.C. Chang, Q. Niu, Phys. Rev. B 53, 7010 (1996); G. Sundaram, Q. Niu, ibid. 59, 14195 (1999).
  * [7] C.M. Bender and S. Boettcher, Phys. Rev. Lett. 80, 5243 (1998).
  * [8] B. Wu and Q. Niu, New J. of Phys. 5, 104 (2003).
  * [9] C.M. Bender, D.C. Brody and H.F. Jones, Phys. Rev. Lett. 89, 270401 (2002).
  * [10] S. Longhi, Phys. Rev. Lett. 103, 123601 (2009).
  * [11] C.T. West, T. Kottos, and T. Prosen, Phys. Rev. Lett. 104, 054102 (2010).
  * [12] Q. Wang, J. Phys. A: Math. Gen. 43, 295301 (2010).
  * [13] L. Guo, L. Du, C. Yin, Y. Zhang, and S. Chen, Phys. Rev. A 97, 032109 (2018); C. Yin, H. Jiang, L. Li, R. Lü, and S. Chen, ibid 97, 052115 (2018); H. Jiang, C. Yang, and S. Chen, ibid 98, 052116 (2018).
  * [14] H. Shen, B. Zhen, L. Fu, Phys. Rev. Lett. 120, 146402 (2018).
  * [15] H. Wu and J.-H. An, Phys. Rev. B 102, 041119(R) (2020).
  * [16] J. Pi and R. Lü, J. Phys.: Condens. Matter 33 345601 (2021).
  * [17] Y.H. Song, X. Wang, H.D. Liu, and X.X. Yi, J. Phys. A: Math. Theor. 56 015304 (2023).
  * [18] Y. Xu, Front. Phys. 14, 43402 (2019).
  * [19] K. Li and Y. Xu, Phys. Rev. Lett. 129, 093001 (2022).
  * [20] S. Yao and Z. Wang, Phys. Rev. Lett. 121, 086803 (2018).
  * [21] K. Zhang, Z. Yang, and C. Fang, Phys. Rev. Lett. 125, 126402 (2020).
  * [22] K. Cao, S.-P. Kou, cond-mat/arXiv:2304.04691.
  * [23] Y. Fu and Y. Zhang, cond-mat/arXiv:2307.16632.
  * [24] A. Regensburger, C. Bersch, M.A. Miri, G. Onishchukov, D.N. Christodoulides, and U. Peschel, Nature (London) 488, 167 (2012).
  * [25] B. Peng, S.K. Ozdemir, S. Rotter, H. Yilmaz, M. Liertzer, F. Monifi, C.M. Bender, F. Nori, and L. Yang, Science 346, 328 (2014).
  * [26] L. Feng, Z.J. Wong, R.-M. Ma, Y. Wang, and X. Zhang, Science 346, 972 (2014).
  * [27] Z.-P. Liu et.al., Phys. Rev. Lett. 117, 110802 (2016)
  * [28] X.-Y. Lü, H. Jing, J.-Y. Ma, and Y. Wu, Phys. Rev. Lett. 114, 253601 (2015).
  * [29] Q. Li et.al., Guo Optica 6, 67 (2019).
  * [30] L. Xiao et. al., Nature Physics 13, 1117 (2017).
  * [31] M.A. Rego-Monteiro and F.D. Nobre, Phys. Rev. A 88, 032105 (2013).
  * [32] W.Y. Wang, B. Sun, and J. Liu, Phys. Rev. A 106, 063708 (2022).
  * [33] J. Liu, B. Wu, and Q. Niu, Phys. Rev. Lett. 90, 170404 (2003).
  * [34] A. Mostafazadeh, J. Math. Phys. 43, 3944 (2002).
  * [35] J.-W. Ryu, quant-ph/arXiv:2307.12021.
  * [36] Q. Zhang and B. Wu, Phys. Rev. A 99, 032121 (2019).
  * [37] Q. Zhang and B. Wu, New. J. Phys. 20 013024 (2018).


# Sieved Enumeration of Interval Orders and Other Fishburn Structures

Stuart A. Hannah  Computer and Information Sciences
Livingstone Tower
University of Strathclyde
Glasgow
Scotland

###### Abstract.

Following a result of Eriksen and Sjöstrand (2014) we detail a technique to
construct structures following the Fishburn distribution from appropriate
Mahonian structures.

This technique is introduced on a bivincular pattern of Bousquet-Mélou et al.
(2010) and then used to introduce a previously unconsidered class of
matchings; explicitly, zero alignment matchings according to the number of
arcs which are both right-crossed and left nesting.

We then define a statistic on the factorial posets of Claesson and Linusson
(2011) counting the number of features which we refer to as mislabelings and
demonstrate that according to the number of mislabelings that factorial posets
follow the Fishburn distribution.

As a consequence of our approach we find an identity for the Fishburn numbers
in terms of the Mahonian numbers.

###### Key words and phrases:

interval order, 2+2-free poset, Fishburn, permutation pattern

###### 2000 Mathematics Subject Classification:

Primary 05A15

## Introduction

Eriksen and Sjöstrand [7] provide a remarkable refinement of Zagier’s formula
for certain Fishburn structures. It follows from their results that the
following patterns are equidistributed in permutations:

,  and  .

Furthermore they prove that the above patterns are equidistributed with the
number of right nestings in non-left nesting matchings. They show the
distribution is given by the coefficients $f_{n,k}$ of the following ordinary
generating function,

$\displaystyle\sum_{n=0}\sum_{\pi\in\mathfrak{S}_{n}}x^{n}y^{\sigma({\pi})}$
$\displaystyle=\sum_{n=0}\sum_{k=0}f_{n,k}x^{n}y^{k}$
$\displaystyle=\sum_{m=0}(-1)^{m}\prod_{i=1}^{m}\frac{(1+(y-1)x)^{i}-1}{1-y}.$

We refer to this as the _Fishburn distribution_.

Observing that the above equation can be written in terms of a substitution of
the $q$-factorial $\bm{({n})_{q}!}$ as

$\displaystyle\sum_{n\geq 0}\bm{({n})_{x(y-1)+1}!}x^{n},$

allows for a new approach for the enumeration of Fishburn structures. This
makes explicit a link between Fishburn and Mahonian structures. In this paper
we demonstrate this technique on three structures. We first recreate Eriksen
and Sjöstrand’s result on occurrences in permtuations of the first of the
above patterns. We then introduce a new Fishburn structure showing that the
number of arcs which are both left-nesting and right-crossed in matchings with
no alignments follow the Fishburn distribution. Then we identify a new feature
on the factorial posets of Claesson and Linusson [4] which we name
mislabelings. A factorial poset with zero mislabelings satisfies a condition
of Claesson and Linusson giving that the poset is a canonically labeled
interval order, thus allowing us to recreate a result of Bousquet-Mélou et al.
[2].

As a consequence of the relationship to the $q$-factorial we provide a new
identity for coefficients $f_{n,k}$ of the Fishburn distribution with respect
to the Mahonian numbers $m_{n,k}$ (A008302), that

$f_{n,k}=\sum_{i=k}^{n-2}(-1)^{i+k}{i\choose k}\sum_{j=i}^{n-i\choose
2}{j\choose i}m_{n-i,j}.$

Of particular interest is when $k=0$, which gives an identity for the $n$th
Fishburn number (A022493)

$\sum_{i=0}^{n-2}(-1)^{i}\sum_{j=i}^{n-i\choose 2}{j\choose i}m_{n-i,j}.$

## Terminology and background

For $a,b\in\mathbb{Z}$ with $a<b$ let $[b]$ denote the set $\\{1,\dots,b\\}$
and $[a,b]$ the set $\\{a,\dots,b\\}$.

For $U$ a linearly ordered set with $x\in U$ where $x$ is _not_ the maximal
element of $U$ then, where there is no ambiguity, we shall abuse notation
using $x+1$ to refer to the immediate successor of $x$ in $U$.

### Mahonian numbers

For $n\in\mathbb{N}$ let $\bm{({n})_{q}!}$ denote the $q$-factorial, defined
as

$\displaystyle\bm{({n})_{q}!}$
$\displaystyle=\prod_{i=1}^{n}\sum_{j=0}^{i-1}q^{j}=\prod_{i=1}^{n}\frac{1-q^{i}}{1-q}.$

The coefficients of the $q$-factorial are known as the Mahonian numbers
(A008302). The first few terms are shown in Figure 1. We shall use $m_{n,k}$
to denote the $k$th entry of row $n$.

Mahonian numbers derive their name from seminal work identifying permutation
statistics by Major MacMahon [11]. As a result, and particularly in the case
of permutations, structures counted by the $q$-factorial are often referred to
as Mahonian structures.

1

1, 1

1, 2, 2, 1

1, 3, 5, 6, 5, 3, 1

1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1

1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1

…

Figure 1. Mahonian Triangle (A008302), $m_{n,k}$

### Permutation patterns

A permutation is a bijection on a finite set $U$. The results in this paper
assume that there is a total order on $U$. We shall therefore assume
throughout that for $n\in\mathbb{N}$ permutations as elements of
$\mathfrak{S}_{n}$ are bijections on the set $[n]$.

For $n,k\in\mathbb{N}$ with $n>k$ take permutations $\pi\in\mathfrak{S}_{n}$
and $\tau\in\mathfrak{S}_{k}$. An occurrence of $\tau$ as a _classical
permutation pattern_ in $\pi$ is a subsequence of $\pi$ whose entries are in
the same relative order as in $\tau$. For example taking $\tau=132$ and
$\pi=4671253$ then the following subsequences of $\pi$ correspond to
occurrences of $\tau$,

$465\quad 475\quad 153\quad 253.$

Permutations may be represented on a grid by dots placed at line intersects
such that each line is intersected by exactly one dot. The permutation maps
the value indicated by each vertical line to the value of the corresponding
horizontal line indicated by the dot placement. For example, the grid below
corresponds to the permutation $4671253$.

11223344556677

A _mesh pattern_ , introduced by Brändén and Claesson [3], consists of a
classical permutation pattern and a (potentially empty) set of shaded boxes on
the grid representation of that pattern. An occurrence of a mesh pattern
consists of an occurrence of the underlying classical permutation such that
there are no entries of $\pi$ contained within the shaded boxes.

For example, there are two occurrences of the following mesh pattern in $\pi$,

$\raisebox{2.58334pt}{ \leavevmode\hbox to40.04pt{\vbox
to40.04pt{\pgfpicture\makeatletter\hbox{\hskip 0.10048pt\lower-0.10048pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}} {}{{}}{}
{{}{}}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{9.95863pt}{0.0pt}\pgfsys@moveto{9.95863pt}{0.0pt}\pgfsys@lineto{9.95863pt}{9.95863pt}\pgfsys@lineto{19.91727pt}{9.95863pt}\pgfsys@lineto{19.91727pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{19.91727pt}{9.95863pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{{}{}}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{9.95863pt}{9.95863pt}\pgfsys@moveto{9.95863pt}{9.95863pt}\pgfsys@lineto{9.95863pt}{19.91727pt}\pgfsys@lineto{19.91727pt}{19.91727pt}\pgfsys@lineto{19.91727pt}{9.95863pt}\pgfsys@closepath\pgfsys@moveto{19.91727pt}{19.91727pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{{}{}}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{9.95863pt}{19.91727pt}\pgfsys@moveto{9.95863pt}{19.91727pt}\pgfsys@lineto{9.95863pt}{29.87592pt}\pgfsys@lineto{19.91727pt}{29.87592pt}\pgfsys@lineto{19.91727pt}{19.91727pt}\pgfsys@closepath\pgfsys@moveto{19.91727pt}{29.87592pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{{}{}}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{9.95863pt}{29.87592pt}\pgfsys@moveto{9.95863pt}{29.87592pt}\pgfsys@lineto{9.95863pt}{39.83455pt}\pgfsys@lineto{19.91727pt}{39.83455pt}\pgfsys@lineto{19.91727pt}{29.87592pt}\pgfsys@closepath\pgfsys@moveto{19.91727pt}{39.83455pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{{}{}}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{0.0pt}{9.95863pt}\pgfsys@moveto{0.0pt}{9.95863pt}\pgfsys@lineto{0.0pt}{19.91727pt}\pgfsys@lineto{9.95863pt}{19.91727pt}\pgfsys@lineto{9.95863pt}{9.95863pt}\pgfsys@closepath\pgfsys@moveto{9.95863pt}{19.91727pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{{}{}}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{19.91727pt}{9.95863pt}\pgfsys@moveto{19.91727pt}{9.95863pt}\pgfsys@lineto{19.91727pt}{19.91727pt}\pgfsys@lineto{29.87592pt}{19.91727pt}\pgfsys@lineto{29.87592pt}{9.95863pt}\pgfsys@closepath\pgfsys@moveto{29.87592pt}{19.91727pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{{}{}}{{}}{}{}{}{}{{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgf@tempcolor}{rgb}{0.55,0.55,0.55}\pgfsys@invoke{\lxSVG<EMAIL_ADDRESS>}\pgfsys@moveto{29.87592pt}{9.95863pt}\pgfsys@moveto{29.87592pt}{9.95863pt}\pgfsys@lineto{29.87592pt}{19.91727pt}\pgfsys@lineto{39.83455pt}{19.91727pt}\pgfsys@lineto{39.83455pt}{9.95863pt}\pgfsys@closepath\pgfsys@moveto{39.83455pt}{19.91727pt}\pgfsys@fill\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope {}{{}}{}{}{ {}{}{}{}{ }{
}{ }{ }{ }{
}{}}{}\pgfsys@moveto{0.09952pt}{0.09952pt}\pgfsys@moveto{0.09952pt}{9.95863pt}\pgfsys@lineto{39.73502pt}{9.95863pt}\pgfsys@moveto{0.09952pt}{19.91727pt}\pgfsys@lineto{39.73502pt}{19.91727pt}\pgfsys@moveto{0.09952pt}{29.87592pt}\pgfsys@lineto{39.73502pt}{29.87592pt}\pgfsys@moveto{9.95863pt}{0.09952pt}\pgfsys@lineto{9.95863pt}{39.73502pt}\pgfsys@moveto{19.91727pt}{0.09952pt}\pgfsys@lineto{19.91727pt}{39.73502pt}\pgfsys@moveto{29.87592pt}{0.09952pt}\pgfsys@lineto{29.87592pt}{39.73502pt}\pgfsys@moveto{39.73502pt}{39.73502pt}\pgfsys@stroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{9.95863pt}{9.95863pt}\pgfsys@moveto{11.70866pt}{9.95863pt}\pgfsys@curveto{11.70866pt}{10.92516pt}{10.92516pt}{11.70866pt}{9.95863pt}{11.70866pt}\pgfsys@curveto{8.99211pt}{11.70866pt}{8.2086pt}{10.92516pt}{8.2086pt}{9.95863pt}\pgfsys@curveto{8.2086pt}{8.99211pt}{8.99211pt}{8.2086pt}{9.95863pt}{8.2086pt}\pgfsys@curveto{10.92516pt}{8.2086pt}{11.70866pt}{8.99211pt}{11.70866pt}{9.95863pt}\pgfsys@closepath\pgfsys@moveto{9.95863pt}{9.95863pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{19.91727pt}{29.87592pt}\pgfsys@moveto{21.6673pt}{29.87592pt}\pgfsys@curveto{21.6673pt}{30.84244pt}{20.88379pt}{31.62595pt}{19.91727pt}{31.62595pt}\pgfsys@curveto{18.95074pt}{31.62595pt}{18.16724pt}{30.84244pt}{18.16724pt}{29.87592pt}\pgfsys@curveto{18.16724pt}{28.9094pt}{18.95074pt}{28.12589pt}{19.91727pt}{28.12589pt}\pgfsys@curveto{20.88379pt}{28.12589pt}{21.6673pt}{28.9094pt}{21.6673pt}{29.87592pt}\pgfsys@closepath\pgfsys@moveto{19.91727pt}{29.87592pt}\pgfsys@fillstroke\pgfsys@invoke{
}
{}{{}}{}{{{}}{}{}{}{}{}{}{}{}}{}\pgfsys@moveto{29.87592pt}{19.91727pt}\pgfsys@moveto{31.62595pt}{19.91727pt}\pgfsys@curveto{31.62595pt}{20.88379pt}{30.84244pt}{21.6673pt}{29.87592pt}{21.6673pt}\pgfsys@curveto{28.9094pt}{21.6673pt}{28.12589pt}{20.88379pt}{28.12589pt}{19.91727pt}\pgfsys@curveto{28.12589pt}{18.95074pt}{28.9094pt}{18.16724pt}{29.87592pt}{18.16724pt}\pgfsys@curveto{30.84244pt}{18.16724pt}{31.62595pt}{18.95074pt}{31.62595pt}{19.91727pt}\pgfsys@closepath\pgfsys@moveto{29.87592pt}{19.91727pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\;.$

namely $465$ and $253$. Whereas, although an occurrence of the underlying
classical pattern, $475$ is not an occurrence the above mesh pattern as $5$
occurs between the $4$ and $7$.

A _vincular pattern_ is a mesh pattern where only entire columns may be shaded
out. A _bivincular pattern_ is a mesh pattern where any shaded boxes must
contribute to an entire row or column of shaded boxes. The above mesh pattern
is also a bivincular pattern.

A permutation with no occurrences of a pattern is said to _avoid_ that
pattern.

Occurrences of the pattern

,

are known as _inversions_ and are counted by the $q$-factorial (see MacMahon
[11]).

### Posets

A poset $P$ is defined as a set and an associated binary relation $<_{P}$
satisfying reflexivity, antisymmetry, and transitivity. A poset constructed on
some linearly ordered set $U$ is said to be _naturally labeled_ if
$i<_{P}j\implies i<_{U}j$.

An _interval order_ is a poset $P$ where each $z\in P$ can be assigned a
closed interval $[l_{z},r_{z}]\in\mathbb{R}$ such that $x<_{P}y$ if and only
if $r_{x}<l_{y}$. Equivalent conditions are that an interval order is a poset
whose predecessor sets can be assigned a total order by inclusion [1] or that
a poset is an interval order if it has no induced subposet isomorphic to the
pair of disjoint two element chains, i.e. the poset is $(2+2)$-free [8].

For $i\in P$, let the following notation be used for the predecessor and
successor sets of $i$:

$\displaystyle\operatorname{Pred}{i}=\\{j\in P:j<_{P}i\\},\quad\quad$
$\displaystyle\operatorname{pred}{i}=|\operatorname{Pred}{i}|,$
$\displaystyle\operatorname{Succ}{i}=\\{\ell\in P:i<_{P}\ell\\},\quad\quad$
$\displaystyle\operatorname{succ}{i}=|\operatorname{Succ}{i}|.$

### Matchings

A perfect matching of size $n$ is a fixed point free involution of semi-length
$n$. Matchings are typically represented as a set of ordered pairs $(i,j)$
such that $i<j$ or diagrammatically as arcs on the numberline $[2n]$. For
example, the matching of size $10$

$\\{(1,10),(2,9),(3,6),(4,11),(5,7),(8,12),(13,15),(14,16)\\},$

is diagrammatically represented as

12345678910111213141516

A _nesting_ arc in a matching is an arc which is entirely encloses another arc
when seen diagrammatically, i.e. an $(i,j)$ such that there exists $(k,\ell)$
with $i<k<\ell<j$. The arc which is enclosed is known as a _nested_ arc. If
$k=i+1$ then the arcs are called _left-nesting_ and _left-nested_
respectively. If $\ell+1=j$ then the arcs are _right-nesting_ and _right-
nested_ respectively.

A _crossing_ arc in a matching is the leftmost of two intersecting arcs when
seen diagrammatically, i.e. an $(i,j)$ such that there exists $(k,\ell)$ with
$i<k<j<\ell$. The same approach as for nestings is taken to define _crossed,
left-crossing, left-crossed, right-crossing_ and _right-crossed_ arcs.

An alignment in a matching is two arcs $(i,j)$ and $(k,\ell)$ such that
$i<j<k<\ell$.

For two arcs $(i,j)$ and $(k,\ell)$, we say that $k$ is an _embraced nested
opener_ if $k$ is the opener for an arc nested by $(i,j)$.

### Statistics and features

Given some set of structures $X$ a _statistic_ $\psi$ is defined as a function
taking a structure to a positive integer, i.e. $\psi:X\to\mathbb{Z}_{+}$.

A _feature_ of a structure is a property, aspect or substructure of a
combinatorial structure. For example, an inversion in a permutation, or a
nesting in a matching.

### Background

Studying interval orders and permutations avoiding $\sigma$ Bousquet-Mélou et
al. [2] demonstrate that their ordinary generating function is given by

$\sum_{n\geq 0}\prod_{k=1}^{n}(1-(1-x)^{k})=\bm{({n})_{-x+1}!}x^{n},$

a function originally considered by Zagier [13] in enumerating a restricted
class matchings (non-neighbor nesting matchings).

As an intermediate structure Bousquet-Mélou et al. introduce _ascent
sequences_ , sequences of the form $b_{1}b_{2}\dots b_{n}$ defined recursively
with $b_{1}=0$ and $b_{i+1}\in[0,\operatorname{asc}{(b_{1}b_{2}\dots
b_{i})}+1]$ where $\operatorname{asc}{}$ counts the total number of ascents
contained within the sequence. Ascent sequences are used to encode the
construction of interval orders via insertions of new maximal elements.
Bousquet-Mélou et al. present a case analysis to determine the predecessor set
of the $i$th inserted element which is both dependent on the value $b_{i}$ and
elements previously inserted. Ascent sequences are additionally used to
construct non-neighbor nesting matchings and permutaions avoiding $\sigma$,
thus giving bijective correspondences between the structures.

In studying non-neighbor nesting matchings Zagier gave an asymptoic forumla
for their number $f_{n}$.

$f_{n}\sim
n!\frac{12\sqrt{3}}{\pi^{\frac{5}{2}}}e^{\tfrac{\pi^{2}}{12}}\left(\frac{6}{\pi^{2}}\right)^{n}\sqrt{n}.$

We refer to $f_{n}$ as the _Fishburn numbers_.

Taking advantage of the equivalent definition for interval orders, that
predecessor sets can be given a total order under inclusion, Dukes, Jelínek
and Kubitzke [5] provide an intuitive relation between interval orders and
their generating function. They show a simple bijection between interval
orders and the integer matrices of Dukes and Parviainen [6]. An integer matrix
of size $n$ is defined as an $m\times m$, upper triangular, non-row and non-
column empty matrix with integer entries summing to $n$. Dukes, Jelínek and
Kubitzke show that two elements are related in an interval order if they share
a hook under the diagonal of the integer matrix.

Claesson and Linusson [4] introduce the $n!$ matchings, a subset of matchings
with no left-nestings enumerated by $n!$ according to semi-length. Levande
[10], solving a conjecture of Claesson and Linusson, finds an additional
subset of non left-nesting matchings counted by the Fishburn numbers.

Eriksen and Sjöstrand [7] provide bijections between various Fishburn
structures enumerated by $n!$—including non-left matchings and
permutations—and a class of filled partition shapes. In doing so they find the
full Fishburn distribution for these structures, differing from previous work
which had focused solely on avoidance.

## Original Fishburn permutation

We lead with a previously studied example. Recall the mesh pattern

$\sigma$ =  ,

with avoidance originally given by Bousquet-Mélou et al. [2] and the full
distribution given by Eriksen and Sjöstrand [7].

In their paper Eriksen and Sjöstrand show a bijection between permutations and
filled partition shapes by using the filled entries in the partition shapes to
encode the insertion of elements into an ordered list of blocks. Upon
completion the block structure is dropped and the elements read left-to-right
return the permutation. Their bijection allows that multiple statistics are
equidistributed between the two structures and through this they provide the
non-commutative generating function with respect to those statistics.

In this section we shall focus on a small part of their work by considering
the distribution of occurrences of $\sigma$ in isolation from other
statistics. This differs from the work of Eriksen and Sjöstrand in that the
proof is based on insertion of entries into a permutation rather than encoding
the construction. Our application of the sieve principle is the same.

We begin with the fact that the number of inversions in permutations follow
the Mahonian distribution. To construct a permutation of size $n$ with $i$
marked occurrences of $\sigma$ take a permutation of size $n-i$ with $i$
marked inversions. Each marked inversion will be used to insert a new entry
which is the first entry of an occurrence of $\sigma$. The sieve principle
will be then be applied to return those permutations strictly satisfying that
_all_ occurrences of $\sigma$ are marked.

Define an order on inversions based on the position in the permutation of the
first entry in the tuple and value of the second entry in the tuple. For
$a_{1}a_{2}\dots a_{n}$ a permutation let $(a_{i},a_{j})$ and
$(a_{i^{\prime}},a_{j^{\prime}})$ be two, non-equal inversions. If
$i=i^{\prime}$ it follows $a_{i}=a_{i^{\prime}}$ and without loss of
generality we can assume $a_{j}<a_{j^{\prime}}$. We then define

$(a_{i},a_{j})<(a_{i^{\prime}},a_{j^{\prime}}).$

Otherwise $i\neq i^{\prime}$ then without loss of generality assume
$i<i^{\prime}$. Then we define

$(a_{i},a_{j})<(a_{i^{\prime}},a_{j^{\prime}}).$

As an example, in the permutation $246531$ the following inversions are sorted

$(4,1)<(6,1)<(6,5).$

According to the above order each inversion $(a_{j},a_{k})$ is used to insert
a new entry into the permutation. Taking the position before the leftmost
entry to be position $0$, increment all $a_{i}>a_{k}$ by one and insert
$a_{k}+1$ at position $j-1$. Thus an occurrence of $\sigma$ is created.

######  Example 1.

Take the permutation
$2{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}4}653{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}$
where we consider the following inversions to be marked

$(4,1)<(6,1)<(6,5).$

As the values in the inversions change, at each step the next inversion to be
used will be colored in red. Inserted entries will be marked blue.

The inversion $(4,1)$ is the first inversion under our defined order. Increase
all entries greater than $1$ by $1$

$357641,$

and insert $2$ at position $1$

$3{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}2}5{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}7}64{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}1}.$

The next inversion is now labeled $(7,1)$ with the $7$ at position $4$.
Increase all entries greater than $1$ and insert $2$ at position $3$

$4{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}3}6{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}2}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}87}51.$

Applying the process to the final inversion, now labeled $(8,7)$, leads to the
permutation

$4{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}3}6{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color@cmyk@fill{1}{0}{0}{0}2}{\color[rgb]{0,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,1}\pgfsys@color@cmyk@stroke{1}{0}{0}{0}\pgfsys@color<EMAIL_ADDRESS>
Note that the inserted entries (marked blue) are all the first entries in an
occurrence of $\sigma$.

######  Proposition 2.

The above procedure describes a bijection between permutations with marked
inversions marked and permutations with the first entry in an occurrence of
$\sigma$ marked.

###### Proof.

To show that this mapping is well defined we need to demonstrate that at each
step the insertion of an entry does not remove an occurrence of $\sigma$
previously inserted by this process.

This is enforced by the ordering defined on inversions. Let $(a_{i},a_{j})$
and $(a_{i^{\prime}},a_{j^{\prime}})$ be inversions.

  1. (1)

If $i=i^{\prime}$ then $a_{j}<a_{j^{\prime}}$ and therefore
$(a_{i},a_{j})<(a_{i^{\prime}},a_{j^{\prime}})$. Our insertion process gives
that $a_{j^{\prime}}+1$ is inserted in the position immediately following that
of $a_{j}$ and thus forming an ascent with $a_{j}$. Furthermore as
$a_{j^{\prime}}>a_{j}$, the minimal entry in the occurrence of $\sigma$ that
$a_{j}$ is contained in is not incremented. Therefore the occurrence is
preserved with the newly inserted entry $a_{j^{\prime}}$ taking the role of
the largest entry in the occurrence.

  2. (2)

If $i<i^{\prime}$ then $(a_{i},a_{j})<(a_{i^{\prime}},a_{j^{\prime}})$. As
$a_{j^{\prime}}+1$ is inserted further to the right in the permutation the
ascent that $a_{i}$ involved cannot be broken. If $a_{j}<a_{j^{\prime}}$ the
minimal entry in the occurrence of $\sigma$ remains unchanged. If
$a_{j}>a_{j^{\prime}}$ then all entries in the occurrence of $\sigma$
containing $a_{j}$ are incremented. If $a_{j}=a_{j^{\prime}}$ then
$a_{j^{\prime}}$ replaces the minimal entry of the occurrence of $\sigma$
containing $a_{j}$.

Thus the mapping is well defined. To show that the mapping is a bijection we
demonstrate that it is both injective and surjective.

Injectivity is enforced by the total order on inversions and that an inversion
pair uniquely determines the entry which is inserted.

For surjectivity note that the process we have defined inserts the first
entries of marked occurrences of $\sigma$ in a left-to-right order within the
permutation. We can consider the reverse of the insertion operation taking a
permutation with marked occurrences of $\sigma$ to a permutation with marked
inversions.

Given a permutation of size $n$ with marked occurrences of $\sigma$, take the
rightmost marked occurrence. Removing the first entry contained in the
occurrence and standardizing the permutation leaves a permutation of size
$n-1$ with a marked inversion. Surjectivity follows from repeated application.
∎

######  Corollary 3.

Permutations with marked occurrences of $\sigma$ are given by the ordinary
generating function

$u(x,z)=\sum_{n\geq 0}\bm{({n})_{xz+1}!}x^{n}.$

###### Proof.

Permutations with respect to inversions are enumerated by the $q$-factorial.
Under the above process an inversion is either marked, in which case a new
entry uniquely specifying a marked occurrence of $\sigma$ is inserted, or it
is unmarked. This is equivalent to the substitution $(xz+1)$ in place of $q$
in the $q$-factorial with the marking of the occurrence of $\sigma$ denoted by
$z$. ∎

Recreating Eriksen and Sjöstrand’s result we now apply the sieve principle to
permutations with _subsets_ of $\sigma$ marked returning those with _all_
$\sigma$ marked. For more details see Wilf [12, Chapter 4, Section 2].

######  Corollary 4.

Permutations with respect to occurrences of $\sigma$ are given by the ordinary
generating function

$\sum_{n\geq 0}\bm{({n})_{x(y-1)+1}!}x^{n}.$

###### Proof.

The previous corollary gives that permutations with respect to marked
occurrences of $\sigma$ are given by the ordinary generating function

$u(x,z)=\sum_{n\geq 0}\bm{({n})_{xz+1}!}x^{n}.$

In this set a permutation with $k$ marked occurrences of $\sigma$ occurs a
total of $k\choose i$ times with $i$ occurrences of $\sigma$ marked.

Let $f(x,y)$ be the ordinary generating function for permutations with _all_
occurrences of $\sigma$ marked. Consider the substitution of $y$ by $z+1$.
This corresponds to remarking occurrences of $\sigma$ with a $z$, or unmarking
them them with the $1$. As such each permutation will occur $k\choose i$ times
with $i$ occurrences of $\sigma$ now marked by $z$. We then have that

$u(x,z)=f(x,z+1).$

The result then follows through the reverse substitution of $z$ by $y-1$ into
$u(x,z)$. ∎

######  Remark 5.

The distributions of

and

given by Eriksen and Sjöstrand [7] can be shown in a near identical manner.
Again the key is to note that in occurrences of these patterns each has a
point whose value and position are uniquely determined by the other points and
that together these other two points form an inversion.

## Technique

We can generalize the previous two corollaries to explicitly state a new
technique for constructing Fishburn structures. We present it as the following
theorem.

######  Theorem 6.

Let $\mathcal{F}$ be a Mahonian stucture according to the distribution of some
$q$-feature.

$\mathcal{F}$ follows the Fishburn distribution with respect to some feature
$p$ if we can show there is a bijection between $\mathcal{F}$ structures of
size $n$ with $i$ marked $q$-features and $\mathcal{F}$ structures of size
$n+i$ with $i$ marked $p$-features.

###### Proof.

By definition, the distribution of $q$-features in $\mathcal{F}$ follows the
ordinary generating function

$\sum_{n\geq 0}\bm{({n})_{q}!}x^{n}.$

Take $\mathcal{F}$ with subsets of $q$-features marked by some variable $w$.
As a $q$-feature is either marked or it is not then the generating function
for such structures is given by the substitution of $q$ by $w+1$ into the
previous equation. We therefore have

$\sum_{n\geq 0}\bm{({n})_{w+1}!}x^{n}.$

We now use that there exists a bijection between $\mathcal{F}$ structures of
size $n$ with $i$ marked $q$-features and $\mathcal{F}$ structures of size
$n+i$ with $i$ marked $p$-features. This allows that subsets of $q$-features
marked with $w$ can be taken to subsets of $p$-features marked by $z$ with the
inclusion of an additional element. In terms of generating function this
corresponds to the substitution of $w$ by $xz$.

Therefore the ordinary generating function of $\mathcal{F}$ structures with
subsets of marked $p$-features is

$\sum_{n\geq 0}\bm{({n})_{xz+1}!}x^{n}.$

If subsets of $p$-features are marked, then each $\mathcal{F}$ structure
occurs $i\choose j$ times with $j$ marked $p$-features. By the sieve principle
(see Wilf [12, Chapter 4, Section 2]), as in the previous corollary, through
the substitution of z by $y-1$ it then follows that $\mathcal{F}$ structures
with _all_ $p$-features marked are given by the ordinary generating function
for the Fishburn distribution

$\sum_{n\geq 0}\bm{({n})_{x(y-1)+1}!}x^{n}.$

∎

## Zero alignment matchings

In this section we apply Theorem 6 to identify a new Fishburn statistic on a
subset of matchings. Explicitly, matchings with zero alignments follow the
Fishburn distribution according to the number of arcs which are both left-
nesting and right-crossed.

Recall that two arcs $(i,j)$ and $(k,\ell)$ are an alignment if $i<j<k<\ell$.

A matching with no alignments (a zero alignment matching) is equivalently
characterized as one where _all_ the openers in the diagrammatic
representation occur before _all_ the closers.

######  Proposition 7.

There are $n!$ zero alignment matchings of semi-length $n$.

Furthermore they are enumerated by $\bm{({n})!}$ when refined according to the
number of nestings.

###### Proof.

This is easiest seen via recursion with a bijection between matchings with no
alignments and inversion tables. Take the empty matching and the empty
inversion table to be in bijection.

Let $b_{1}b_{2}\dots b_{n}$ be an inversion table with each $b_{i}\in[0,i-1]$
and $M$ the matching constructed from $b_{1}b_{2}\dots b_{n-1}$. Label the
position to the left of the first closer as $0$ and label the positions to the
left of an opener right-to-left from $1$ to $n-1$. Insert a new arc into $M$
with opener at position $b_{n}$ and closer at the rightmost position in the
matching.

By construction inserted openers occur to the left of all the closers and it
is easy to see that entries in the inversion table correspond to the number of
nested arcs. ∎

Recall that a left-nesting arc is an arc $(i,j)$ such that there exists an arc
$(i+1,\ell)$ with $\ell<j$. Recall also that $(i,j)$ is right-crossed if there
exists an arc $(k,j-1)$ with $k<i$. We shall call an arc which is both left-
nesting and right-crossed a _confused_ arc.

Define an order on embraced nested openers. We shall write embraced nested
openers as ordered pairs. Take $((i,j),k)$ and
$((i^{\prime},j^{\prime}),k^{\prime})$ where $k$ and $k^{\prime}$ are closers
with $(i,j)$ an arc embracing $k$ and $(i^{\prime},j^{\prime})$ an arc
embracing $k^{\prime}$. If $k=k^{\prime}$ then, without loss of generality,
assume $j<j^{\prime}$ and define

$((i^{\prime},j^{\prime}),k^{\prime})<((i,j),k).$

Otherwise, without loss of generality, assume $k<k^{\prime}$ then define

$((i^{\prime},j^{\prime}),k^{\prime})<((i,j),k).$

For example, take the matching $\\{(1,9),(2,12),(3,10),(4,7),(5,8),(6,11)\\}$.

123456789101112

The following subset of embraced nested openers are sorted:

$((2,12),4)\quad<\quad((1,9),4)\quad<\quad((2,12),3).$

Given a matching with a subset of embraced openers marked, using the above
order, for each embraced nested opener $((i,j),k)$ insert a new arc opening
immediately to the left of the embraced nested opener $k$ and closing
immediately to the right of arc closer $j$. As $i<k$ the new arc is therefore
right-crossed, furthermore as the arc with opener $k$ is nested by $(i,j)$ it
follows that the newly inserted arc left nests the arc with opener $k$. As
both right-crossed and left-nesting the inserted arc is confused.

######  Example 8.

We demonstrate on our example matching.

123456789101112

Consider the following nested openers marked.

$((2,12),4)\quad((1,9),4)\quad((2,12),3)$

As in the example for permutations the next nested opener to be considered
will be colored red and inserted arcs blue. Inserting a confused arc from the
first embraced nested opener results in the following matching.

1234567891011121314

The next two steps are as follows.

12345678910111213141516123456789101112131415161718

It is easily checked that the inserted arcs are confused and their removal
returns the original matching.

######  Proposition 9.

The above is a bijection between zero alignment matchings with marked embraced
openers and zero alignment matchings with marked confused arcs.

###### Proof.

We are required to show that at each stage the process is well defined: that
no alignments are introduced and and that no previously inserted confused arc
has its left nesting or right crossed attributes removed.

That no alignment is introduced can be seen by contradiction. As the inserted
arc has its opener to the left of an existing opener and its closer to the
right of an existing closer no new alignment can be introduced if the original
matching was a zero alignment matching.

That each step of the process does not break the right-crossed or left-nesting
property of a previously inserted arc is given by the order on nested openers.
If two inserted arcs share the same opener as part of their nested opener,
then that both arcs are still left nesting is given by the order on nesting
arc closers. If two inserted arcs share the same nesting arc closer as part of
their nested opener, then that both arcs are right nesting is given by the
order of the opener.

Each inserted arc has its opener and closer uniquely determined by the nested
opener. Furthermore it is clear that removing inserted arcs returns the
original matching. Injectivity and surjectivy are thus simple. ∎

The following corollary then results from Theorem 6 and the above Proposition.

######  Corollary 10.

Zero alignment matchings with respect to confused arcs follow the Fishburn
distribution.

## Factorial posets

Identifying appropriate statistics and applying the technique given by Theorem
6 to the factorial posets of Claesson and Linusson [4] allows for a new method
for the enumeration of interval orders which differs from both the recursive
construction of Bousquet-Mélou et al. [2] and the matrix hook bijection of
Dukes, Jelínek and Kubitzke [5].

Claesson and Linusson [4] define the _factorial posets_ , a set of labeled
interval orders counted by $n!$, as follows. A factorial poset $P$ on some
linearly ordered underlying set $U$ is a naturally labeled poset with the
additional condition that, for $i,j,k\in U$,

$i<_{U}j<_{P}k\implies i<_{P}k.$

This is referred to as the _factorial condition_.

Easily seen to be equivalent, a poset is factorial if and only if for all
$k\in P$ there exists $j\in[0,k-1]$ such that $\operatorname{Pred}{k}=[1,j]$.
As the predecessor sets can be linearly ordered by inclusion it follows that
factorial posets are interval orders.

Claesson and Linusson take advantage of this by using entries of an inversion
table to encode the construction of a factorial poset, thus giving that the
two structures are in bijection. We include their result for completeness.

######  Theorem 11 (Claesson and Linusson [4]).

Factorial posets on $[n]$ are in bijection with inversion tables of length
$n$.

###### Proof.

As a poset is factorial if and only if for all $k\in P$ there exists
$j\in[0,k-1]$ such that $\operatorname{Pred}{k}=[1,j]$. An inversion table
$b_{1}b_{2}\dots b_{n}$ is given by setting $b_{k}$ to the value
$j\in[0,k-1]$. ∎

Claesson and Linusson identify numerous statistics preserved by their
bijection. In particular that the number of _incomparable pairs_ in factorial
posets, defined as

$|\\{(i,j)\in P\times P:i\not<_{P}j,i<_{U}j\\}|,$

are enumerated by the $q$-factorial.

Taking two factorial posets to be equivalent if they are structurally
isomorphic, Claesson and Linusson demonstrate that posets satisfying that for
all $i\in[n-1]$

$\operatorname{pred}{i}\leq\operatorname{pred}{(i+1)}\quad\mbox{or}\quad\operatorname{succ}{i}>\operatorname{succ}{(i+1)}$

are unique representatives of their class.

Again we include their result.

######  Proposition 12 (Claesson and Linusson [4]).

There is exactly one way to label a $(2+2)$-free poset such that it satisfies

$\operatorname{pred}{i}\leq\operatorname{pred}{(i+1)}\quad\mbox{or}\quad\operatorname{succ}{i}>\operatorname{succ}{(i+1)}.$

###### Proof.

A poset satisfying the above condition has that for all $i\in[n]$ the pairs

$(\operatorname{succ}{i},\operatorname{pred}{i})$

are weakly decreasing on the first coordinate and weakly increasing on the
second. The factorial condition gives that for $i,j\in[n]$ the pairs
$(\operatorname{succ}{i},\operatorname{pred}{i})$ and
$(\operatorname{succ}{j},\operatorname{pred}{j})$ are equal if an only if the
pairs are indistinguishable within the poset, thus giving a canonical
labeling. ∎

We extend this notion to consider a new feature on factorial posets,
explicitly elements which _fail_ to satisfy this property.

######  Definition 13 (Mislabeling).

Define a mislabeling in a factorial poset on $[n]$ to be an $i\in[n-1]$ such
that

$\operatorname{pred}{i}>\operatorname{pred}{(i+1)}\quad\mbox{and}\quad\operatorname{succ}{i}\leq\operatorname{succ}{(i+1)}.$

######  Example 14.

The poset

124356

Has set of mislabelings $\\{2,4\\}$.

By definition a factorial poset with zero mislabelings satisfies the condition
from Proposition 12 and is thus a unique representative of its isomorphism
class.

A consequence of the factorial condition is that if
$\operatorname{pred}{i}>\operatorname{pred}{(i+1)}$ then $i$ and $i+1$ are
incomparable as if $i<_{P}i+1$ then the factorial condition requires that for
all $\ell<_{U}i\implies\ell<_{P}{i+1}$. Furthermore there must exist $\ell$
such that $\ell<_{P}i$ but that $\ell\not<_{P}i+1$.

Therefore an equivalent condition to
$\operatorname{pred}{i}>\operatorname{pred}{(i+1)}$ is that there exists an
induced subposet isomorphic to $(2+1)$ with the following labeling

$\ell$$i$$i+1$

### Sieved enumeration of interval orders

Recall that we write incomparable pairs as $(i,j)$ with $i<_{U}j$ and let $U$
be some linearly ordered set with $|U|=n$. For some $k\in[0,n-1]$ take a poset
$P$ built on the first $n-k$ elements of $U$ with $k$ marked incomparable
pairs.

Define an order on incomparable pairs. Let $(i,j)$ and
$(i^{\prime},j^{\prime})$ be two pairs. If $j=j^{\prime}$ without loss of
generality assume $i<_{U}i^{\prime}$. Then we define

$(i^{\prime},j^{\prime})<(i,j).$

Otherwise $j\neq j^{\prime}$ then without loss of generality assume
$j<_{U}j^{\prime}$. Then we define

$(i,j)<(i^{\prime},j^{\prime}).$

To illustrate, the following pairs are sorted according to the above order.

$(2,3)<(1,3)<(4,6)<(3,6).$

In this order, each pair $(i,j)$ is then used to insert a new element into the
poset. This new element has predecessor set

$\\{h\in P:h\leq_{U}i\\},$

and successor set

$\operatorname{Succ}{j}.$

Increment all $k\in P$ with $k\geq_{U}j$ to its immediate successor in $U$,
giving the newly inserted element the value $j$.

By definition this introduces an occurrence of

$i$$j$$j+1$

into the new poset with the inserted element marked in blue. Furthermore as
the successor set of the inserted element $j$ is equal to that of the
successor set of the element now labeled $j+1$ it follows that the newly
inserted element with label $j$ is a mislabeling.

######  Example 15.

Consider our earlier factorial poset built on $[6]$.

124356

We consider the following incomparable pairs to be marked

$(2,3)<(1,3)<(4,6)<(3,6)$

As the values within the pairs change at each stage we will denote the next
incomparable pair to be used in red. Inserted elements will be colored blue.

The pair $(2,3)$ specifies the new element $\ell$ to be inserted defined by

$\operatorname{Pred}{\ell}=\\{h\in
U:h\leq_{U}2\\}=\\{1,2\\}\quad\mbox{and}\quad\operatorname{Succ}{\ell}=\operatorname{Succ}{3}=\\{4\\}.$

12$\ell$4356

All elements with label greater or equal to $3$ are incremented by one and the
newly inserted element $\ell$ is given the label $3$.

1235467

The remaining steps are as follows.

12365784

$\longrightarrow$ 123657948 $\longrightarrow$ 12365710489

Thus we have returned a poset of size $10$ with set of marked mislabelings
$\\{3,4,8,9\\}$.

######  Proposition 16.

The procedure described above gives a bijection between factorial posets with
marked incomparable pairs and factorial posets with marked mislabelings.

###### Proof.

We shall first show that the process described above is well defined. This is
equivalent to showing that at each insertion the following properties are
preserved for the resulting poset: it is naturally labeled, it satisfies the
factorial condition and it does not remove any mislabelings previously
inserted by the process.

For the incomparable pair $(i,j)$ and newly inserted element $\ell$ we have
that $\ell$ covers all $\\{h\in P:h<_{U}i\\}$ and thus by construction it is
both naturally labeled and satisfies the factorial condition. Elements smaller
than $j$ under $U$ remain unchanged. The newly inserted element is given the
same successor set as the element which previously had that label and thus the
insertion does not break the factorial condition for any element larger under
$U$ than $j$ and also ensures that the naturally labeled property is
preserved.

That no previously inserted mislabelings are removed by the process is given
by the order on incomparable pairs and the factorial property, thus the
process is a mapping between factorial posets with marked incomparable pairs
to factorial posets with marked mislabelings.

Next we show that the mapping is bijective. That it is injective follows from
the total order defined on incomparable pairs and that the insertion of a new
element is uniquely determined by an incomparable pair.

It remains to show surjectivity. The process we have defined inserts
mislabelings in order according to $U$. We can consider the reverse of the
insertion operation taking a factorial poset with marked mislabelings to a
factorial poset with marked incomparable pairs.

Given a factorial poset of size $n$ with $k$ marked mislabelings take the
mislabeling with the largest value $j$ and remove it from the poset. As $j$ is
a mislabeling there exists $\ell<_{P}j$ such that $\ell\not<j+1$. Take the
largest such $\ell$ and mark the incomparable pair consisting of $(\ell,j+1)$.
Thus we have returned a poset of size $n-1$ with $i-1$ mislabelings and $1$
marked incomparable pair. Surjectivity follows from repeated application.

As it is both surjective and injective the mapping is a bijection. ∎

The following corollary then results from Theorem 6 and Proposition 16.

######  Corollary 17.

Factorial posets follow the Fishburn distribution according to the number of
mislabelings.

Substitution of $y=0$ into the ordinary generating function for the Fishburn
distribution,

$\sum_{n\geq 0}\bm{({n})_{x(y-1)+1}!}x^{n}|_{y=0},$

returns the ordinary generating function for factorial posets with no
mislabelings. Proposition 12 gives that such posets are unique representatives
of their isomorphism class thus yielding, as expected, the result of Bousquet-
Mélou et al. [2] that the generating function for unlabeled interval orders is
given by

$\sum_{n\geq 0}\bm{({n})_{-x+1}!}x^{n}.$

## Fishburn distribution

1

2

6, 1

24, 9

120, 72, 5

720, 600, 98, 1

5040, 5400, 1450, 76

40320, 52920, 20100, 2200, 35

362880, 564480, 279300, 48750, 2299, 9

…

Figure 2. Unsieved Fishburn distribution: number of structures of size $n$
with $i$ marked $p$-features, $u_{n,i}$

We obtain the following corollaries concerning the Fishburn distribution from
Theorem 6 and its proof.

######  Corollary 18.

For some appropriate structure let $p$ be a feature which follows the Fishburn
distribution and $q$ a feature which follows the Mahonian distribution.

Letting $u_{n,i}$ denote the number of structures of size $n$ with $i$ marked
$p$-features,

$\sum_{n\geq 0}\sum_{i\geq 0}u_{n,i}x^{n}z^{i}=\sum_{n\geq
0}\bm{({n})_{xz+1}!}x^{n},$

we have that

$u_{n,i}=\sum_{j=i}^{n-i\choose 2}{j\choose i}m_{n-i,j}.$

The first few terms of $u_{n,i}$ are shown in Figure 2

###### Proof.

Theorem 6 gives that a $q$-factorial structure of size $n-i$ with $i$ marked
$q$-features can be extended to a structure of size $n$ with $i$ marked
$p$-features.

For a Mahonian structure of size $n-i$ with $j$ $q$-features then $i$ are
selected. The number of $q$-factorial structures of size $n-i$ with $j$
$q$-features is given by Mahonian number $m_{n-i,j}$.

The maximum number of $q$-features a $q$-factorial structure of size $n-i$ can
have is ${n-i\choose 2}$. Thus $j$ is bounded

$i\leq j\leq{n-i\choose j}.$

∎

######  Remark 19.

The row sums of Figure 2 (A179525), i.e.

$\sum_{i=0}u_{n,i},$

have previously been studied by Jelínek [9] as counting _primitive row
Fishburn matrices_ , upper-triangular, binary non-row empty matrices,
according to the sum of the entries. Jelínek considers such matrices as part
of his work on counting self-dual interval orders; he demonstrates a relation
between the generating functions of self-dual interval orders enumerated by a
reduced size function and primitive row Fishburn matrices.

We note that the coefficient of $x^{n}z^{k}$ in the refined formula

$\sum_{n\geq 0}\bm{({n})_{xz+1}!}x^{n}$

can be interpreted as counting the number of primitive row Fishburn matrices
such that:

  1. (1)

There are a total of $k$ entries in the matrix that are not the first to occur
in their row.

  2. (2)

The entries in the matrix sum to $n$.

######  Corollary 20.

Recalling that $f_{n,k}$ denotes the coefficient in the Fishburn distribution

$\sum_{n\geq 0}\sum_{k\geq 0}f_{n,k}x^{n}y^{k}=\sum_{n\geq
0}\bm{({n})_{x(y-1)+1}!}x^{n},$

we have that

$\displaystyle f_{n,k}$ $\displaystyle=\sum_{i=k}^{n-2}(-1)^{i+k}{i\choose
k}u_{n,i}$ $\displaystyle=\sum_{i=k}^{n-2}(-1)^{i+k}{i\choose
k}\sum_{j=i}^{n-i\choose 2}{j\choose i}m_{n-i,j}.$

The first few terms are shown in Figure 3

###### Proof.

Again for some appropriate structure let $p$ be a feature which follows the
Fishburn distribution.

Recall from the proof of Theorem 6 that to take structures with subsets of
$p$-features marked to structures with all _all_ $p$-features marked
corresponds to the substitution of $y-1$ by $z$.

The result then follows from the previous corollary and binomial expansion. ∎

1

2

5, 1

15, 9

53, 62, 5

217, 407, 95, 1

1014, 2728, 1222, 76

5335, 19180, 13710, 2060, 35

31240, 142979, 146754, 39644, 2254, 9

…

Figure 3. Fishburn distribution, $f_{n,k}$

######  Remark 21.

In the above corollary the upper bound $n-2$ for the initial summation is
justified by noting that an occurrence of $\sigma$ can be uniquely determined
by the first element in the occurrence and that two more entries must follow
in the permutation. Therefore there can be no more than $n-2$ occurrences of a
Fishburn statistic in a structure of size $n$.

This is sufficient for our purposes however we note that this is _not_ the
least upper bound (easily checked empirically). We leave this as an open
question.

######  Question 22.

Is there an aesthetically pleasing expression for the least upper bound for
the value of a Fishburn statistic?

## References

  * [1] Kenneth P. Bogart  “An obvious proof of Fishburn’s interval order theorem”  In _Discrete Mathematics_ 118.1–3, 1993, pp. 239 –242  DOI: http://dx.doi.org/10.1016/0012-365X(93)90065-2
  * [2] Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes and Sergey Kitaev  “(2+2) free Posets, Ascent Sequences and Pattern Avoiding Permutations”  In _Journal of Combinatorial Theory, Series A_ 117.7 Orlando, FL, USA: Academic Press, Inc., 2010, pp. 884–909  DOI: 10.1016/j.jcta.2009.12.007
  * [3] Petter Brändén and Anders Claesson  “Mesh Patterns and the Expansion of Permutation Statistics as Sums of Permutation Patterns”  In _Electronic Journal of Combinatorics_ 18.2, 2011  URL: http://www.combinatorics.org/Volume_18/Abstracts/v18i2p5.html
  * [4] Anders Claesson and Svante Linusson  “n! matchings, n! posets”  In _Proceedings of the American Mathematical Society_ 139, 2011, pp. 435–449
  * [5] Mark Dukes, Vít Jelínek and Martina Kubitzke  “Composition matrices, (2+2)-free posets and their specializations”  In _The Electronic Journal of Combinatorics_ 18.1, 2011
  * [6] Mark Dukes and Robert Parviainen  “Ascent sequences and upper triangular matrices containing non-negative integers”  In _Electronic Journal of Combinatorics_ 17, 2010
  * [7] Niklas Eriksen and Jonas Sjöstrand  “Equidistributed statistics on matchings and permutations”  In _The Electronic Journal of Combinatorics_ 21.4, 2014
  * [8] Peter C. Fishburn  “Intransitive indifference with unequal indifference intervals”  In _Journal of Mathematical Psychology_ 7.1, 1970, pp. 144 –149  DOI: http://dx.doi.org/10.1016/0022-2496(70)90062-3
  * [9] Vít Jelínek  “Counting general and self-dual interval orders”  In _Journal of Combinatorial Theory, Series A_ 119.3, 2012, pp. 599 –614  DOI: http://dx.doi.org/10.1016/j.jcta.2011.11.010
  * [10] Paul Levande  “Fishburn Diagrams, Fishburn Numbers and Their Refined Generating Functions”  In _Journal of Combinatorial Theory, Series A_ 120.1 Orlando, FL, USA: Academic Press, Inc., 2013, pp. 194–217  DOI: 10.1016/j.jcta.2012.07.012
  * [11] Percy A. MacMahon  “Combinatory Analysis”, Dover Books on Mathematics Series  Dover Publications, 2004
  * [12] Herbert S. Wilf  “generatingfunctionology: Third Edition”, Ak Peters Series  Taylor & Francis, 2005
  * [13] Don Zagier  “Vassiliev invariants and a strange identity related to the Dedekind eta-function”  In _Topology_ 40.5, 2001, pp. 945 –960  DOI: http://dx.doi.org/10.1016/S0040-9383(00)00005-7