# Tuning magnetic states in CrI3 bilayers via Moiré patterns

###### Abstract

Commensurable twisted bilayers can drastically change the magnetic properties
of chromium trihalide layered compounds, which opens novel opportunities for
tuning magnetic states through layer rotations. Here, we introduce a
mathematical approach to obtain Moiré patterns in twisted hexagonal bilayers
by performing a certain commensurable rotation $\theta$ over one layer. To
test our approach, we apply it to find Moiré structures with
$\theta=21.79^{\circ}$ and $32.20^{\circ}$ in the phases R$\bar{3}$ and C2/m
of CrI3. For comparison purposes, we also consider a non-shifted CrI3
structure. Electronic and magnetic properties of the so-obtained systems are
computed by Ab-Initio methodologies. Results show the presence of rotation-
angle-dependent magnetic configurations and steep modifications of the
dispersion bands due to variations in the nearest and next nearest distances
among layers of Cr atoms. Modifications obtained from these commensurable
rotations are discussed on the basis of competition among different energy
contributions due to changes in the atomic arrangements.

###### keywords:

Moiré patterns, 2D materials, CrI3, magnetic order

A. M. León E. A. Velásquez* F. Caro-Lopera J. Mejía-López

Dr. A. M. León
Max Planck Institute for Chemical Physics of Solids, Dresden, Germany.

Prof. E. A. Velásquez
Grupo MATBIOM, Facultad de Ciencias Básicas, Universidad de Medellín,
Medellín, Colombia.
Email Address<EMAIL_ADDRESS>
Prof. F. Caro-Lopera
Facultad de Ciencias Básicas, Universidad de Medellín, Medellín, Colombia.

Prof. J. Mejía-López
Centro de Investigación en Nanotecnología y Materiales Avanzados CIEN-UC,
Facultad de Física, Pontificia Universidad Católica de Chile. CEDENNA,
Santiago, Chile.

##  1 Introduction

Commensurable rotated layers of graphene have promoted relevant research
during the last decades. Thus, the so-called twistronics became popular after
the discovery of the magic angle at around $1.1^{\circ}$ for superconductivity
of two projectively coincident rotated layers of graphene [1, 2]. Other
interesting phenomena such as ferromagnetism [3, 4], spin textures [5], flat
bands [6, 7], van Hove singularities [8, 9], and correlated insulating phases
[10, 11] have also been found in this system. Using the same commensurable
hexagonal cell via atomic networks, a number of theoretical and experimental
works have been reported in other crystallographic structures. For example, in
hexagonal boron nitride structures, the presence of moiré patterns leads to
the formation of electronic minibands [12]; and systems such a twisted bilayer
MoS2 show changes in their phonon properties due to the periodic potentials of
the moiré patterns [13]. Experimental evidence of interlayer valley excitons
trapped in a moiré potential has also been found in MoSe2/WSe2 heterobilayers
[14]; and tunable collective phases have been found to be present in twisted
bilayer transition metal dichalcogenides [15]. These systems have emerged as
interesting materials to be explored under twist angles and moiré patterns
since they lead to remarkable effects on the electronic [16, 17, 15, 18] and
optical properties, such as the appearance of interlayer valley excitons [19,
17, 20] and excitonic complexes such as the recently reported “trions” trapped
in moiré superlattices [21, 22]. These recent advances open new avenues to
explore artificial excitonic crystals and quantum optic effects in these
systems [21, 22, 23].

From a mathematical point of view, the underlying definition of the hexagonal
commensurable cells presented some inconsistencies or unclear relationships
with existing works via Diophantine Equation [24, 25, 26]. A different general
approach based on multilayer twisted affine lattices, known as Bravais-moiré
theory, has been applied independently to the existing reports on Diophantine
equations and to the study of optical properties in square photonic crystals
[27, 28]. It has also been applied to study graphene by introducing two unseen
classes of twisted graphene with different electronic properties [29].

The aforementioned works have the common feature that the bilayer is
projectively coincident with the reference lattice, i.e., when the points of
the Bravais lattice of the second layer are projected onto the plane of the
first layer they coincide exactly in space. However, there are materials which
have the so-called displaced Bravais-moiré, with non-coincident projected
layers, and therefore the problem of commensurate rotation must be considered.
This relatively unexplored situation in twistronic appears naturally in
Chromium Trihalides bilayer compounds (CrX3, X = Cl, Br, I), where one layer
is shifted respect to the other. However the commensurable rotation in these
types of systems has not been discussed so far. Furthermore, these magnetic
compounds present unique opportunities to explore the moiré pattern effect on
both their electronic and magnetic properties due to the strong interplay
between magnetism and lattice degrees of freedom. Among the CrX3 family, the
CrI3 is considered a fascinating material that displays novel physical
properties in the low dimensional limit. The magnetic interactions coupled to
the lattice degrees of freedom give rise to FM or different AFM interactions
depending on the number of layers and the structural phases. The understanding
of these properties is being object of intense research recently with the
focus on unraveling the interplay among magnetism, anisotropy, stacking and
the layer limit (monolayers and bilayers)[30, 31, 32, 33]. Recent theoretical
works have reported interesting approaches revealing that the magnetism is
governed by mechanisms beyond super-exchange interactions [34], in which the
interlayer exchange (FM/AFM) depends on the competition of the $d$-orbital
interactions, which, in turn, depends on the different neighborhood generated
by the stacking layers [35, 34]. These works suggest that this unique
interplay between stacking and magnetism could have direct implications on
moiré systems, and, in particular, in twisted CrI3, where the stacking can
dramatically alter the magnetic properties.

The innovation of twisted CrI3 also involves a complex obstacle related to the
metastability of the system when the shifted layers are rotated respect each
other. The strong magnetic forces among the lattices do not guarantee that
periodic stabilization can be achieved. A very recent study in this direction
evidenced the stability of moiré structures at low angles twist at around
$1.0$-$1.36^{\circ}$ [36]. They exploit the well-known property of
approximated commensuration (quasi-commensurability) via very small rotation
angles, which allows certain long-period moiré patterns and useful
mathematical simplifications for calculations. To the best of our knowledge,
there are no works of exactly parametrized twisted magnetic bilayers with no
use of approximated moiré periodicity. Therefore, we have focused on
commensurable rotation angles in the CrI3 bilayer in our research.

This work provides exact formulae for commensurable hexagonal super cells
suitable for complex twisted systems as CrI3. We explore formation of moiré
structures at high rotation angles, namely $\theta$=$21.79^{\circ}$ and
$32.20^{\circ}$, on CrI3. First we discuss a general construction of moiré
structure in non-shifted layers and then we present a general mathematical
construction of moiré structures on shifted layers for the two well known
stacking of CrI3 the R$\bar{3}$ and the C2/m structural phases, known as low
and high temperature structures, respectively. The main goal of this work is
to show a general mathematical method for construction of moiré structures
through shifted layers and to apply this methodology to explore the changes in
the electronic, magnetic and structural properties of CrI3 with moiré
patterns.

##  2 Results and Discussion

###  2.1 Bravais-moiré Theory Under Shifted Twisted Lattices

The Bravais-moiré theory deals with the problem of finding a super cell that
reproduces $n$ projected layers on $R^{2}$ in a periodic way. The $n$ layers
lie in parallel planes and are allowed to be different Bravais lattices and
affine transformations of each other. The classical literature considers $n=2$
centered (AA-type stacking) or non-centered hexagonal (e.g. AB-type stacking)
or square Bravais under identity transformations (trivial affine), which are
similar and initially coincident, then a super unit cell is found through a
commensurable rotation of the second layer as respect to the common origin
with the first lattice. The so-called commensurable angle is obtained when a
given position vector of the first lattice coincides with a position vector of
the second lattice after performing the related rotation. Finding the
commensurable rotation reduces to find the solution of a Diophantine equation
based on a mapping of the integer pair $(r,s)$ (associated with a linear
combination of the position vector in the first lattice) into an integer pair
$(r^{\prime},s^{\prime})$ of the position vector after rotation of the second
lattice.

Under the general affine approach, the commensurable angle $0<\theta<\pi/3$
for $n=2$ non centered hexagonal Bravais of the initially projected coincident
lattices (stacking AA-type), is given by [29]:

$\displaystyle\cos\theta=\frac{r^{2}+6rs-3s^{2}}{6s^{2}+2r^{2}},$ (1)

where $r=2m+s$, with $m$ and $s$ two non-null natural coprime integers which
satisfy $m>s$. Other equations, similar to Equation 1, have been reported to
obtain commensurable angles with different parameterizations [37, 38, 39].
These different parameterizations must, however, give place to the same
solutions to the Diophantine equations that give rise to the commensurability.
Therefore, all the treatments of rotated bilayers in the AA stacking must
match among them, except for their parameterization and the domain of validity
of the parameters used.

The rotation of the layer through this angle, Lrot, defines a commensurable
hexagonal supercell located in the plane of the first layer, Lfix, with fixed
Bravais lattice, which is taken as a reference, with vertices at the positions
defined by:

$\displaystyle p_{1}$ $\displaystyle=$ $\displaystyle
k\left(\sqrt{3}r/2,3s/2\right)$ (2) $\displaystyle p_{2}$ $\displaystyle=$
$\displaystyle k\left(-\sqrt{3}(3s-r)/4,3(s+r)/4\right)$ $\displaystyle p_{3}$
$\displaystyle=$ $\displaystyle k\left(-\sqrt{3}(3s+r)/4,-3(s-r)/4\right)$
$\displaystyle p_{4}$ $\displaystyle=$ $\displaystyle
k\left(-\sqrt{3}r/2,-3s/2\right)$ $\displaystyle p_{5}$ $\displaystyle=$
$\displaystyle k\left(\sqrt{3}(3s-r)/4,-3(s+r)/4\right)$ $\displaystyle p_{6}$
$\displaystyle=$ $\displaystyle k\left(\sqrt{3}(3s+r)/4,3(s-r)/4\right),$

where $k$ is the length of the reference unit lattice vector. Figure 1(b)
shows the Bravais-moiré for $r=5$, $s=1$ with the corresponding commensurable
rotation of $21.79^{\circ}$. Note the coincident points addressing the
commensurable principle, as expected.

Now, let us assume that an application involves two different Bravais that are
not projectively coincident before the rotation (e.g AB-type stacking, AC-type
stacking, etc.). Then we wonder for the commensurable rotation and the
primitive vertices of the corresponding super cell. As far as we known, these
types of commensurable systems are not reported so far, and the associated
super lattice vectors and commensurable rotation need to be developed. The
solution will be trivial if we adapt the principle given by the Equation (1):

Lemma 1. Let $H$ be a non centered hexagonal Bravais in $R^{2}$ spanned by the
super lattice vectors defined by the points $p_{3}-p_{4}$ and $p_{5}-p_{4}$
under the commensuration angle $\theta$ in Equation (1). Any new Bravais
lattice $V$ constructed by a similarity (Euclidean) transformation of $H$ is
also spanned by the same super lattice vectors of $H$.

For a proof, note that $V$ is just a scaling, rotation and/or translation of
$H$; then $V$ can be seen as an atomic basis in the commensurable super cell
defined by the lattice vectors of $H$. In other words, $V$ is just an
Euclidean lattice spanning the same $R^{2}$, via the lattice original vectors
of $H$.

We refer to the Bravais $H$ as the hidden or phantom lattice because it is
used for generating the covering of $R^{2}$; meanwhile the resulting Bravais
$V$ constructed by a rigid Euclidean transformation of $H$ will be named the
visible lattice since it will keep the coordinates of the atoms of interest.

Finally, the so-called shifted-scaled or rotated Bravais-moiré can be easily
constructed by commensurable rotation (Equation (1)). Let us assume that a
fixed non centered hexagonal Bravais $L_{fix}$ is given. Let us construct a
second visible Bravais $V$, which is a translation, rotation or a scaling of a
hidden non centered hexagonal Bravais $H$ initially projectively coincident
with $L_{fix}$. According to the lemma, the visible Bravais $V$, which now can
be refer to as $L_{rot}$ in the notation of Equation (1), is a new Bravais-
moiré just obtained by a commensurable rotation $\theta$ of $H$ respect to
$L_{fix}$, and the hexagonal supercell vertices are the same $p_{1}\cdots
p_{6}$ given for the classical twisted hexagonal bilayer. The resulting
shifted-scaled or rotated Bravais-moiré hides the Bravais $H$, and only shows
$L_{fix}$ and $L_{rot}$.

The application of lemma 1 for $r=5$, $s=1$ is shown in Figure 1(c). Here, the
shifted Bravais-moiré lattice of the visible Bravais lattice, $V=L_{rot}$,
represented by green points in the figure, is a rigid translation of the
hidden lattice $H$ (gray points in the figure). $H$ is rotated $21.79^{\circ}$
respect to the fixed reference Bravais lattice $L_{fix}$, which is represented
by purple points. The super cell is defined by the same vectors given by
setting Equation (1) for a classical Bravais-moiré indexed by $r=5$, $s=1$ and
shown in Figure 1(c), as well.

It is possible to apply this general construction to various 2D structures
such as CrI3, MoS2, etc., by considering that a crystal structure consist of a
Bravais lattice and a set of base atoms placed at each point of the
lattice[40]. Thus, we explore the moiré structures for the CrI3 with a non-
shifted cell which has a symmetry group R3, and shifted cells with symmetry
groups R$\bar{3}$ (low temperature ferromagnetic phase) and C2/m (high
temperature antiferromagnetic phase).

###  2.2 Structural and Magnetic Properties

The formation of moiré patterns under commensurable rotations, following the
method explained in previous section, is applied to different stacking of the
CrI3 structure with R3, R$\bar{3}$ and C2/m symmetries. In each case, the top
layer $L_{rot}$ is rotated respect to the fixed layer $L_{fix}$ with a
commensurate angle of $21.79^{\circ}$ ($r$=5 and $s$=1) and $32.20^{\circ}$
($r$=7 and $s$=1). These two angles correspond to the cells built with the
smallest number of atoms under commensurable conditions. Table 1 shows the
amount of atoms needed in the primitive cell for simulating the systems at
some selected twist angles. The smaller the commensurable twist angle the
higher the amount of atoms needed, which strongly limits the possibility of
performing DFT calculations.

Table 2 reports the optimized lattice parameters, neighbors interlayer
distances and magnetic order for each phase and for the rotation angles
considered here ($0^{\circ}$, $21.79^{\circ}$ and $32.20^{\circ}$). Figure
2(a) shows the lowest energy Bravais-moiré crystalline structures, after
relaxation, for each angle considered.

First, the lattice parameters are similar in each phase, when the rotation
angle is fixed. For $\theta=0^{\circ}$, the R$\bar{3}$ structure has the
highest cohesion energy, i.e., it is the most stable and can be considered as
the fundamental state, as already reported previously [30, 34, 41, 42]. The
C2/m phase has an energy difference of 1.1 meV/atom with respect to the ground
state, while the R3 phase is the structure with the lowest cohesion energy,
with an energy difference of 4.7 meV/atom with respect to the ground state.
Although this structure is a high energy metastable state, which has not been
previously reported, it is important for the analysis of the rotated layers,
as we will discuss below.

To describe the structural changes in each phase, we analyze the atomic
coordination of Cr atoms by counting the number of nearest (n.n.) and next
nearest neighbors (n.n.n) among Cr atoms belonging to different layers. We
obtain the coordination interval to each atom from the radial distribution
function (RDF) of each system, defining it as those atoms that lie around the
peaks of the RDF, as shown in Figure 2(b) and detailed in Table 2. In this way
we find that R$\bar{3}$ has the smallest interlayer distance with 1 and 9 n.n.
and n.n.n., as reported [34, 35]. In C2/m and R3, the number of n.n. and
n.n.n. change to (4,4) and (2,6), respectively, and they are at larger
distances (see Table 2).

As a layer rotates over another one, there is a change in the distances among
atoms and therefore there is a change in the neighborhood. As the tuning angle
increases to $\theta=21.79^{\circ}$, the new configuration of R$\bar{3}$ has
larger interlayer distances with respect to the phases with $\theta$=0 and
with respect to the C2/m and R3 phases rotated by the same angle, as well. The
number of n.n. and n.n.n. also changes with respect to $\theta=0^{\circ}$,
giving now (10,6), (1,14), and (1,16) for the moiré systems R$\bar{3}$, C2/m,
and R3, respectively. Finally, by increasing the angle to
$\theta=32.20^{\circ}$, the number of neighbors change to (3,17), (1,16), and
(6,19), respectively.

These structural variations lead to important changes on the properties of
these systems. Indeed, the most stable states change with respect to the non-
rotated systems, with the lowest energy structure for the R3 phase on the two
angles considered. The energy difference between the phases with higher and
lower energy is $E_{R3}-E_{R\bar{3}}$ = 0.3 meV/atom (for both
$\theta=21.79^{\circ}$ and 32.20∘).

More important, due to the relative rotation between the two layers,
transitions in the magnetic order in each of the phases are observed (see
Table 2). To explain theses changes, Figure 3(a) depicts the energy difference
between the FM and the AFM configurations ($\Delta E^{T}=E_{AFM}-E_{FM}$) as a
function of the twist angle, for the three phases (the white and the colored
regions represent the FM and the AFM states, respectively).

As a general trend, changes in magnetic order are observed as $\theta$
increases. At $\theta=0^{\circ}$, R$\bar{3}$ and R3 exhibit FM order with an
energy difference of 3.45 and 0.417 meV/Cr-atom, respectively, while C2/m
presents an AFM configuration with an energy difference of -0.23 meV/Cr-atom
in agreement with previous reports[35, 34, 41, 33]. By increasing the rotation
angle to $\theta=21.79^{\circ}$, the systems R$\bar{3}$ and C2/m become AFM
and FM, respectively, while R3 continues with the FM configuration. At
$\theta=31.20^{\circ}$, R$\bar{3}$ and R3 go to an FM and AFM state,
respectively, and C2/m continues with an FM configuration. The magnetic
moments in each system are $\mu_{Cr}=3.4\mu_{B}$ per Cr atom and
$\mu_{I}=0.1\mu_{B}$, which are computed within spheres of Wigner-Seitz radii
of 1.32 Å and 1.49 Å for Cr and I atoms, respectively. However, for the
ferromagnetic state (at all the studied angles) the magnetic moment per Cr
atom is obtained as 3.0 $\mu_{B}$, in perfect agreement with what is expected
within the crystal field theory when considering Cr+3 atoms in an octahedral
field. In summary, the following structural and magnetic changes are observed
in the non-rotated states and the moiré systems:

$\displaystyle E_{R\bar{3}}(FM)<E_{C2/m}(AFM)<E_{R3}(FM)\hskip
5.69046pt\theta=0^{\circ}~{}~{}~{}~{}~{}$ $\displaystyle
E_{R3}(FM)<E_{C2/m}(FM)<E_{R\bar{3}}(AFM)\hskip 5.69046pt\theta=21.79^{\circ}$
$\displaystyle E_{R3}(AFM)<E_{C2/m}(FM)<E_{R\bar{3}}(FM)\hskip
5.69046pt\theta=32.20^{\circ}$

To explain the changes in the magnetic configuration relative to the non-
rotated phases ($\theta=0^{\circ}$), we analyze the contributions to the total
energy, which are mainly given by the long- and short-range interactions
namely: $E^{H}$ (Hartree energy), $E^{II}$ (ion-ion interaction), $E^{XC}$
(exchange and correlation energy), EvdW (Van der Waals energy), and by the
energy band $E^{B}$. The first contributions,
$E^{S}=E^{H}+E^{II}+E^{XC}+E^{vdW}$, are directly related to the distribution
in space of the ions and electrons composing the system; while $E^{B}$ is
related to the quantum occupation of the electrons in the different energy
levels and it governs the electronic structure of the system. Thus, the total
energy can be written as $E^{T}=E^{S}+E^{B}$. In this framework, we can
understand the FM and AFM order as a due to the competence between $E^{B}$ and
$E^{S}$. According to our calculations, $E^{S}$ mainly contributes to
stabilize the FM order, whereas $E^{B}$ contributes to stabilize the AFM
configuration. In fact, the inset of Figure 3(a) shows that, by removing the
band energy, the original AFM systems became FM (see C2/m, R$\bar{3}$ and R3
in $\theta$ = $0^{\circ}$, $21.79^{\circ}$ and $32.20^{\circ}$, respectively),
and the phases with FM order continue with the FM configuration. On the other
hand, Figure 3(b) shows that, in $\Delta E^{B}$, the $d$ orbitals of Cr atoms
contribute to stabilize an AFM ordering and their contribution is greater than
that of the $s-p$ orbitals of the I atoms, which tend to stabilize an FM
ordering. Therefore, the following relations are fulfilled:

$\displaystyle\Delta E^{S}$ $\displaystyle=$ $\displaystyle
E^{S}_{AFM}-E^{S}_{FM}>0$ $\displaystyle\Delta E^{B}$ $\displaystyle=$
$\displaystyle E^{B}_{AFM}-E^{B}_{FM}<0.$

In this framework, we can observe that the AFM state arises when the absolute
value of the energy band change, $\mid\Delta E^{B}\mid$, is greater than the
energy difference $\Delta E^{S}$ (i.e. $-\Delta E^{B}>\Delta E^{S}$). In the
case of systems with FM state, the contribution of band energy does not
suffice to compensate $E^{S}$.

The structural and magnetic changes from the FM R$\bar{3}$ phase with
$\theta=0^{\circ}$ to the FM and AFM R3 phases with $\theta>0^{\circ}$ offer
an optimum opportunity to show the interplay between magnetic interaction and
crystalline stacking. To understand what determines this interplay, we start
analyzing the change in stability for $\theta=0^{\circ}$. The R$\bar{3}$ phase
has the lowest energy with respect to C2/m and R3 due to the smaller distance
among n.n. and n.n.n. of two magnetic atoms belonging to different layers
(interlayer distance), as one can see in the Table 2, $\theta=0^{\circ}$
column. Indeed, when the interlayer distance is smaller, the $E^{S}$ energy
becomes more negative mainly due to an increase in the attractive Coulomb
interaction respect to the repulsive one. This decrease in the interlayer
distance also generates a larger difference $\Delta E^{S}$ between the FM and
the AFM states, as it can be seen in the inset of Figure 3(a), resulting in a
FM order, as mentioned above. This picture agrees with the suggested by
previous work, where it is evidenced that the FM order of R$\bar{3}$ is due to
the contribution to n.n.n, favoring the FM interactions [35, 34]. The same
argument allows explaining why the R3 phase is more energetic and
ferromagnetic for $\theta=0^{\circ}$.

For the case $\theta=21.79^{\circ}$, the R3 phase has a lower energy than
R$\bar{3}$ due to the decrease of the n.n and n.n.n interlayer distances,
while R3 has a lower energy than C2/m because, although the interlayer
distances are equal, the number of n.n.n is larger (Table 2). The FM order of
R3 is due to the strong contribution of $E^{S}$. Or, from another viewpoint,
due to the increase of the n.n.n over the n.n, favoring the FM interactions
[35, 34]. For $\theta=32.20^{\circ}$, R3 has still a lower energy because of
the larger number of interlayer n.n. n.n. and n.n.n with respect to
R$\bar{3}$, and because of the smaller distance and larger amount of n.n. than
C2/m. For $\theta=32.20^{\circ}$, R3 has an AFM ordering because the increase
in the interlayer n.n. distance contributes mostly with AFM interactions [35,
34] favoring a larger contribution of $E^{B}$ and thereby satisfying the
condition $E^{B}<E^{S}$.

Although C2/m has always higher energy in both Bravais and Bravais-moiré, it
is worth understanding the origin of their magnetic transitions from the AFM
($\theta=0^{\circ}$) to the FM configuration at $\theta=21.79^{\circ}$ and
$32.20^{\circ}$ (Figure 3(a)). These are either due to the decreasing distance
between the interlayer n.n. and n.n.n regarding $\theta=0^{\circ}$, increasing
$E^{S}$, or the n.n.n favoring the FM ground state [35, 34]. Moreover, a
strong competition between the stability of C2/m and R3 (see binding energies
in Table 2) is observed, since both systems have similar neighbors (thus
similar $E^{T}$). However, R3 is more stable because it has a larger amount of
n.n. and n.n.n, allowing to increase the energy of the system, especially the
contribution of $E^{B}$ as compared to C2/m (see Figure 3(b) at
$\theta=21.79^{\circ}$ and $32.20^{\circ}$). With the $\Delta E^{T}$ values in
Figure 3(a), the ordering temperature $T_{ord}$ can be obtained by using a
Mean Field approximation [40]. For the structures of minimum energy we obtain
the $T_{ord}$ values 21.1, 3.7 and 1.95 K for $\theta=0^{\circ}$,
$21.79^{\circ}$ and $32.20^{\circ}$, respectively. For the unrotated case, a
value of 43.2 K was reported by León et.al [33] using an Ising model, in
agreement with our rough estimation of $T_{ord}$. We found a decreasing
behavior of ordering temperature as the rotation angle increases.

Despite the magnetic effects on moiré superlattices have not been extensively
explored, our results agree with previous studies indicating that changes in
the neighbour and relaxation mechanisms play a key role in changing the
electronic and structural properties of graphene [43, 44, 5, 6, 45] and metal
dichalcogenides systems [46, 47, 48, 49].

###  2.3 Electronic Structure

Figure 4 shows the total density of states (DOS) and the projected density of
states (PDOS) for the minimum energy phases in each case, normalized by the
number of atoms in the supercell used in these calculations. The projection of
DOS onto its different orbitals is done in the global coordinate system (with
the coordinate axes set by the unit cell [50]). The considered systems behave
as semiconductors with forbidden bandgaps of $E_{g}=0.927$ eV, $E_{g}=0.931$
eV and $E_{g}=1.028$ eV for $\theta=0^{\circ}$, $21.79^{\circ}$, and
$32.20^{\circ}$, respectively. For all the phases, in general terms, it is
observed that the valence and conduction bands are composed of $p$ orbitals of
I and $d$ orbitals of Cr (Figure 4(a)). In the valence band, there is a larger
contribution from the $p$-I near the top of the band and a large contribution
from the $d$-Cr in the middle of the band (between -3 and -2 eV,
approximately).

For $\theta=0^{\circ}$, the $d$-Cr states are characterized by a strong
contribution of $d_{z^{2}}$, in several energy intervals in the valence band,
and by degenerate states: $d_{x^{2}-y^{2}}$ with $d_{xy}$ and $d_{xz}$ with
$d_{yz}$ (Figure 4(b)). In the conduction band there is no contribution from
$d_{z^{2}}$ and it has the same degeneracy on the other states. On the other
hand, the $p$-I states are characterized by $p_{x}$-$p_{y}$ degeneracy but
with a similar contribution with $p_{z}$ (Figure 4(c)). These results are in
complete agreement with previous works [31, 30].

For $\theta$=$21.79^{\circ}$, we observe changes in the occupancy states of
the $d$-Cr states due to a break of the degeneracy $d_{x^{2}-y^{2}}$-$d_{xy}$
and $d_{xz}$-$d_{yz}$. The last one is due to reduction of symmetries when the
second layer is rotated at this angle, as can be seen in the moiré patterns
pictured in Figure 2(a) (disorder of the atoms projected on the first layer is
observed). Moreover, there is a small contribution of $d_{z^{2}}$ in the
conduction band. The $p$-I orbitals do not undergo appreciable changes with
respect to the non-rotated system. The degeneracy breakdown of the $d$-Cr
orbitals negatively increases the $E^{B}$ for the FM state but negatively
decreases the AFM state due to the change of the interlayer distance, as
discussed in the previous section.

The $\theta=32.20^{\circ}$ case is an AFM state and therefore the electronic
population distribution of up and down spins are different from that of the FM
cases. For this angle, the states become degenerate again such as
$\theta=0^{\circ}$, because the atoms of the second layer are spatially more
ordered with respect to the atoms of the first layer (see Figure 2(a)).

Band structures for the most stable phases are shown in Figure 5. It is
observed that the valence band maximum (VBM) is at the $\Gamma$ point, while
the conduction band minimum (CBM) changes when the second layer is rotated.
For $\theta=0^{\circ}$ (Figure 5(a)), VBM is mostly made up of $p_{y}$ states
of I, and the CBM is in the middle of the K-$\Gamma$ zone with an energy
difference of 7.5 meV with respect to the $\Gamma$ point. This result agrees
with calculations of Lado and Fernández-Rossier[32], but differs from that by
Gudelli and Guo[31] who report a direct gap. The VMB is mainly composed of
$p$-I and $t_{2g}$-Cr orbitals, with higher contribution from the latter. The
calculated effective masses for VMB and CBM are $-1.3m_{e}$ and $2.4m_{e}$,
respectively.

For $\theta=21.79^{\circ}$ (Figure 5(b)), CBM shifts to the M point and is
also composed of $p$-I and $t_{2g}$-Cr orbitals as in the previous case.
However, a break in the degeneracy of the states and changes in the occupancy
of the different orbitals are observed, and VBM is now dominated by the
$p_{x}$-I states and with less weight by the $p_{y}$-I states. In addition, a
strong decrease in the band dispersion and changes in their curvatures are
found, which increases the effective mass of the charge carriers. For this
angle, there are two bands reaching the gamma point with effective mass of
$-10.6m_{e}$ for the heavy holes and $-1.8m_{e}$ for the light holes. The
effective mass of the electrons in the CMB increases to $70.7m_{e}$, an order
of magnitude larger than the non-rotated system.

For $\theta=32.20^{\circ}$ (Figure 5(c)), CBM shifts again, this time toward
the middle of the M-K zone, and it is also composed of $p$-I and $t_{2g}$-Cr
orbitals as the previous cases. For this angle the break in the degeneracy of
the states observed in $\theta=21.79^{\circ}$ disappears, and VBM is now
mostly dominated by $p_{x}$-I states. Band dispersion still decreases and
effective masses of $-19.5m_{e}$ for the VBM and $15.5m_{e}$ for the CBM are
obtained. Since the magnetic state of this phase is AFM, Figure 5(c) shows the
degeneracy of up and down spin bands in the valence band.

The new features found in these Bravais-moiré systems are the result of the
strongest bonding originated from an enhancement of the direct interaction due
to a hybridization increase of $p_{x,y}$ and $p_{z}$ orbitals (see Figure 4).
Similar characteristic have been found in moiré systems for low angles such as
graphene [7], dicalgogenides systems [51, 46], few-layer graphite [52], carbon
natubes [53], among others. New studies on the electronic structure of
Bravais-moiré systems varying the angle $\theta$ between $0^{\circ}$ and
$360^{\circ}$ are necessary to have a clear trend regarding the electronic and
magnetic tuning behavior.

##  3 Conclusions

We present a mathematical approach to perform commensurable rotations in
shifted stacked systems for modeling moiré patterns. The method provides exact
formulae for commensurable cells, without using approximations for long-period
moiré patterns under small angles and large numbers of atoms. From a
mathematical point of view, the understanding of the algebra and geometry
behind the resulting commensurable angles, after structural relaxation, opens
up an interesting perspective for unknown non-Euclidean transformations and
applications.

We have applied this method on CrI3 bilayer systems to its two phases
R$\bar{3}$, C2/m and to one non-shifted phase (R3 symmetry). Through DFT
studies, we found that CrI3 moiré structures with R$\bar{3}$ and C2/m stacking
are metastable states, and the moiré non-shifted structure has lower energy at
$\theta=21.79^{\circ}$ and $\theta=32.20^{\circ}$. These stability changes are
directly related to the changes in the neighborhood due to the atomic
arrangement that arises in the moiré structures. Furthermore, the emergence of
moiré patterns on CrI3 leads to important changes in its electronic properties
with respect to the ground state.

On one hand, we found magnetic phase transition from R$\bar{3}$-FM at
$\theta=0^{\circ}$ to R3-FM and R3-AFM for $\theta=21.79^{\circ}$ and
$32.20^{\circ}$, respectively. This result is compatible with a recent
experimental work on this system [54]. The origin of these transitions are due
to the changes in the distribution of the n.n. and n.n.n. In addition, we
shown that the FM and AFM order can be understood as result of the competition
between n.n. contributing to enhance the EB, and satisfying the condition
$\Delta$EB $<$ $\Delta$ES, favoring the AFM order. This framework agrees with
results of previous works and offers a good opportunity to understand the AFM
and FM order in moiré structures.

On the other hand, moiré structures in CrI3 lead to changes in the band
spectrum. The bigger the angle $\theta$, the less disperse the band. A
increase of the electron mass in the valence band is obtained as a consequence
of the increase in the hybridization bands between px,y and pz orbitals of I
atoms. Our study suggests that the emergence of moiré patterns on CrI3 could
be a powerful tool for tuning magnetic and electronic states, opening new
possibilities to explore electronic properties on CrI3 and other related
compounds.

##  4 Computational Method

Physical magnitudes such as total energies, magnetization, density of states,
band structures, among others, are computed via First-Principles calculations
by using DFT [55, 56] as implemented in the Vienna ab initio simulation
package (VASP) [50] with the PBEsol functional [57] and the optB86-vdW for the
van der Waals correction [58]. A Hubbard on-site Coulomb parameter (U=3 eV) is
used for the Cr atoms to account for the strong electronic correlations, as
suggested in a previous work [30]. For the structural optimization of the
bilayers we include 20 Å of vacuum space to minimize the interaction between
periodically repeated images along the $z$-axis. The structural optimization
of the bilayers systems is performed within a force convergence of at least
10-3 eV/Å for each atom, and a plane-wave energy cutoff of 450 eV in order to
relax the internal positions and the lattice parameters. Regular Monkhorst
Pack grids of 10$\times$10$\times$1, 7$\times$7$\times$1 and
5$\times$5$\times$1, using supercells of 16, 112 and 208 atoms, are used to
perform the ion relaxation for $\theta=0^{\circ}$, $21.79^{\circ}$ and
$32.20^{\circ}$ cases, respectively. Increased grids of 12$\times$12$\times$1,
10$\times$10$\times$1 and 7$\times$7$\times$1 are used to perform the self-
consistent calculations. In addition, to discard any possible dependence of
our results on the DFT method, we performed the same calculations under the
PBE functional with the van der Waals (vdW) approximation optB86-vdW [58] and
vdW-DFT-D2 [59]. Our results show the same trends for the electronic and
structural properties, regardless of the method employed; which allows
confidence in both the discussions and conclusions of our study.

. The results show the same trends for the electronic and structural
properties regardless the method employed.

Acknowledgements

We acknowledge financial support from ANID/CONICYT FONDECYT Grant Nº 1210193,
“Financiamiento basal para centros científicos y tecnológicos de excelencia
AFB180001” and ANID/Becas Chile Postdoctorado Grant Nº 74190099. E. A.
Velásquez and F. J. Caro-Lopera thank the University of Medellín for their
support.

## References

  * [1] Yuan Cao, Valla Fatemi, Shiang Fang, Kenji Watanabe, Takashi Taniguchi, Efthimios Kaxiras, and Pablo Jarillo-Herrero.  Unconventional superconductivity in magic-angle graphene superlattices.  Nature, 556(7699):43–50, 2018.
  * [2] Matthew Yankowitz, Shaowen Chen, Hryhoriy Polshyn, Yuxuan Zhang, K Watanabe, T Taniguchi, David Graf, Andrea F Young, and Cory R Dean.  Tuning superconductivity in twisted bilayer graphene.  Science, 363(6431):1059–1064, 2019.
  * [3] Luis A Gonzalez-Arraga, JL Lado, Francisco Guinea, and Pablo San-Jose.  Electrically controllable magnetism in twisted bilayer graphene.  Physical review letters, 119(10):107201, 2017.
  * [4] Aaron L Sharpe, Eli J Fox, Arthur W Barnard, Joe Finney, Kenji Watanabe, Takashi Taniguchi, MA Kastner, and David Goldhaber-Gordon.  Emergent ferromagnetism near three-quarters filling in twisted bilayer graphene.  Science, 365(6453):605–608, 2019.
  * [5] Kunihiro Yananose, Giovanni Cantele, Procolo Lucignano, Sang-Wook Cheong, Jaejun Yu, and Alessandro Stroppa.  Chirality-induced spin texture switching in twisted bilayer graphene.  arXiv preprint arXiv:2103.10184, 2021.
  * [6] Procolo Lucignano, Dario Alfè, Vittorio Cataudella, Domenico Ninno, and Giovanni Cantele.  Crucial role of atomic corrugation on the flat bands and energy gaps of twisted bilayer graphene at the magic angle $\theta$ 1.08$\circ$.  Physical Review B, 99(19):195419, 2019.
  * [7] Fatemeh Haddadi, QuanSheng Wu, Alex J Kruchkov, and Oleg V Yazyev.  Moiré flat bands in twisted double bilayer graphene.  Nano letters, 20(4):2410–2415, 2020.
  * [8] Alfred JH Jones, Ryan Muzzio, Paulina Majchrzak, Sahar Pakdel, Davide Curcio, Klara Volckaert, Deepnarayan Biswas, Jacob Gobbo, Simranjeet Singh, Jeremy T Robinson, et al.  Observation of electrically tunable van hove singularities in twisted bilayer graphene from nanoarpes.  Advanced Materials, 32(31):2001656, 2020.
  * [9] Shuigang Xu, Mohammed M Al Ezzi, Nilanthy Balakrishnan, Aitor Garcia-Ruiz, Bonnie Tsim, Ciaran Mullan, Julien Barrier, Na Xin, Benjamin A Piot, Takashi Taniguchi, et al.  Tunable van hove singularities and correlated states in twisted monolayer-bilayer graphene.  Nature Physics, 17(5):619–626, 2021.
  * [10] Yuan Cao, Valla Fatemi, Ahmet Demir, Shiang Fang, Spencer L. Tomarken, Jason Y. Luo, Javier D. Sanchez-Yamagishi, Kenji Watanabe, Takashi Taniguchi, Efthimios Kaxiras, Ray C. Ashoori, and Pablo Jarillo-Herrero.  Correlated insulator behaviour at half-filling in magic-angle graphene superlattices.  Nature, 556:80–84, 2018.
  * [11] Ming Xie and Allan H MacDonald.  Nature of the correlated insulator states in twisted bilayer graphene.  Physical Review Letters, 124(9):097601, 2020.
  * [12] Artem Mishchenko, JS Tu, Y Cao, Roman V Gorbachev, JR Wallbank, MT Greenaway, VE Morozov, SV Morozov, MJ Zhu, SL Wong, et al.  Twist-controlled resonant tunnelling in graphene/boron nitride/graphene heterostructures.  Nature Nanotechnology, 9(10):808–813, 2014.
  * [13] Miao-Ling Lin, Qing-Hai Tan, Jiang-Bin Wu, Xiao-Shuang Chen, Jin-Huan Wang, Yu-Hao Pan, Xin Zhang, Xin Cong, Jun Zhang, Wei Ji, et al.  Moiré phonons in twisted bilayer MoS2.  Acs Nano, 12(8):8770–8780, 2018.
  * [14] Kyle L Seyler, Pasqual Rivera, Hongyi Yu, Nathan P Wilson, Essance L Ray, David G Mandrus, Jiaqiang Yan, Wang Yao, and Xiaodong Xu.  Signatures of moiré-trapped valley excitons in MoSe2/WSe2 heterobilayers.  Nature, 567(7746):66–70, 2019.
  * [15] Lei Wang, En-Min Shih, Augusto Ghiotto, Lede Xian, Daniel A Rhodes, Cheng Tan, Martin Claassen, Dante M Kennes, Yusong Bai, Bumho Kim, et al.  Correlated electronic phases in twisted bilayer transition metal dichalcogenides.  Nature materials, pages 1–6, 2020.
  * [16] Matthew R Rosenberger, Hsun-Jen Chuang, Madeleine Phillips, Vladimir P Oleshko, Kathleen M McCreary, Saujan V Sivaram, C Stephen Hellberg, and Berend T Jonker.  Twist angle-dependent atomic reconstruction and moiré patterns in transition metal dichalcogenide heterostructures.  ACS nano, 14(4):4550–4558, 2020.
  * [17] Philipp Parzefall, Johannes Holler, Marten Scheuck, Andreas Beer, Kai-Qiang Lin, Bo Peng, Bartomeu Monserrat, Philipp Nagler, Michael Kempf, Tobias Korn, et al.  Moiré phonons in twisted mose2–wse2 heterobilayers and their correlation with interlayer excitons.  2D Materials, 8(3):035030, 2021.
  * [18] Søren Ulstrup, Roland J Koch, Simranjeet Singh, Kathleen M McCreary, Berend T Jonker, Jeremy T Robinson, Chris Jozwiak, Eli Rotenberg, Aaron Bostwick, Jyoti Katoch, et al.  Direct observation of minibands in a twisted graphene/WS2 bilayer.  Science advances, 6(14):eaay6104, 2020.
  * [19] Kyle L Seyler, Pasqual Rivera, Hongyi Yu, Nathan P Wilson, Essance L Ray, David G Mandrus, Jiaqiang Yan, Wang Yao, and Xiaodong Xu.  Signatures of moiré-trapped valley excitons in mose2/wse2 heterobilayers.  Nature, 567(7746):66–70, 2019.
  * [20] Michael Förg, Anvar S Baimuratov, Stanislav Yu Kruchinin, Ilia A Vovk, Johannes Scherzer, Jonathan Förste, Victor Funk, Kenji Watanabe, Takashi Taniguchi, and Alexander Högele.  Moiré excitons in MoSe2-WSe2 heterobilayers and heterotrilayers.  Nature communications, 12(1):1–7, 2021.
  * [21] Elizabeth Marcellina, Xue Liu, Zehua Hu, Antonio Fieramosca, Yuqing Huang, Wei Du, Sheng Liu, Jiaxin Zhao, Kenji Watanabe, Takashi Taniguchi, et al.  Evidence for moiré trions in twisted mose2 homobilayers.  Nano Letters, 2021.
  * [22] Erfu Liu, Elyse Barré, Jeremiah van Baren, Matthew Wilson, Takashi Taniguchi, Kenji Watanabe, Yong-Tao Cui, Nathaniel M Gabor, Tony F Heinz, Yia-Chung Chang, et al.  Signatures of moiré trions in WSe2/MoSe2 heterobilayers.  Nature, 594(7861):46–50, 2021.
  * [23] Hongli Guo, Xu Zhang, and Gang Lu.  Moiré excitons in defective van der waals heterostructures.  Proceedings of the National Academy of Sciences, 118(32), 2021.
  * [24] S Shallcross, Sangeeta Sharma, and Oleg A Pankratov.  Quantum interference at the twist boundary in graphene.  Physical Review Letters, 101(5):056803, 2008.
  * [25] S Shallcross, S Sharma, E Kandelaki, and OA Pankratov.  Electronic structure of turbostratic graphene.  Physical Review B, 81(16):165105, 2010.
  * [26] Klaus Hermann.  Periodic overlayers and moiré patterns: theoretical studies of geometric properties.  Journal of Physics: Condensed Matter, 24(31):314210, 2012.
  * [27] HA Gómez-Urrea, MC Ospina-Medina, JD Correa-Abad, ME Mora-Ramos, and FJ Caro-Lopera.  Tunable band structure in 2d bravais–moiré photonic crystal lattices.  Optics Communications, 459:125081, 2020.
  * [28] HA Gómez-Urrea, J Bareño-Silva, FJ Caro-Lopera, and ME Mora-Ramos.  The influence of shape and orientation of scatters on the photonic band gap in two-dimensional bravais-moiré lattices.  Photonics and Nanostructures-Fundamentals and Applications, 42:100845, 2020.
  * [29] A Tiutiunnyk, CA Duque, FJ Caro-Lopera, ME Mora-Ramos, and JD Correa.  Opto-electronic properties of twisted bilayer graphene quantum dots.  Physica E: Low-dimensional Systems and Nanostructures, 112:36–48, 2019.
  * [30] Peiheng Jiang, Cong Wang, Dachuan Chen, Zhicheng Zhong, Zhe Yuan, Zhong-Yi Lu, and Wei Ji.  Stacking tunable interlayer magnetism in bilayer CrI3.  Physical Review B, 99(14):144401, 2019.
  * [31] Vijay Kumar Gudelli and Guang-Yu Guo.  Magnetism and magneto-optical effects in bulk and few-layer CrI3: a theoretical GGA+U study.  New Journal of Physics, 21(5):053012, 2019.
  * [32] Jose L Lado and Joaquín Fernández-Rossier.  On the origin of magnetic anisotropy in two dimensional CrI3.  2D Materials, 4(3):035002, 2017.
  * [33] AM León, JW González, J Mejía-López, F Crasto de Lima, and E Suárez Morell.  Strain-induced phase transition in CrI3 bilayers.  2D Materials, 7(3):035008, 2020.
  * [34] Seung Woo Jang, Min Yong Jeong, Hongkee Yoon, Siheon Ryee, and Myung Joon Han.  Microscopic understanding of magnetic interactions in bilayer cri3.  Physical Review Materials, 3(3):031001, 2019.
  * [35] Nikhil Sivadas, Satoshi Okamoto, Xiaodong Xu, Craig J Fennie, and Di Xiao.  Stacking-dependent magnetism in bilayer cri3.  Nano letters, 18(12):7658–7664, 2018.
  * [36] Feiping Xiao, Keqiu Chen, and Qingjun Tong.  Magnetization textures in twisted bilayer crx3 (x$=$ br, i).  Physical Review Research, 3(1):013027, 2021.
  * [37] J. Xhie, K. Sattler, M. Ge, and N. Venkateswaran.  Giant and supergiant lattices on graphite.  Physical Review B, 47:15835–15841, Jun 1993.
  * [38] Wing-Tat Pong and Colm Durkan.  A review and outlook for an anomaly of scanning tunnelling microscopy (stm): superlattices on graphite.  Journal of Physics D: Applied Physics, 38(21):R329, 2005.
  * [39] G Trambly de Laissardière, Didier Mayou, and Laurence Magaud.  Localization of dirac electrons in rotated graphene bilayers.  Nano letters, 10(3):804–808, 2010.
  * [40] Charles Kittel.  Introduction to solid state physics.  John Wiley & Sons Inc., New York, 2005.
  * [41] D Soriano, Claudia Cardoso, and Joaquín Fernández-Rossier.  Interplay between interlayer exchange and stacking in cri3 bilayers.  Solid State Communications, 299:113662, 2019.
  * [42] E Suarez Morell, Andrea León, R Hiroki Miwa, and P Vargas.  Control of magnetism in bilayer cri3 by an external electric field.  2D Materials, 6(2):025020, 2019.
  * [43] Nguyen NT Nam and Mikito Koshino.  Lattice relaxation and energy band modulation in twisted bilayer graphene.  Physical Review B, 96(7):075311, 2017.
  * [44] Giovanni Cantele, Dario Alfè, Felice Conte, Vittorio Cataudella, Domenico Ninno, and Procolo Lucignano.  Structural relaxation and low-energy properties of twisted bilayer graphene.  Physical Review Research, 2(4):043127, 2020.
  * [45] Mikito Koshino and Young-Woo Son.  Moiré phonons in twisted bilayer graphene.  Physical Review B, 100(7):075416, 2019.
  * [46] Felice Conte, Domenico Ninno, and Giovanni Cantele.  Electronic properties and interlayer coupling of twisted mos 2/nbse 2 heterobilayers.  Physical Review B, 99(15):155429, 2019.
  * [47] Mit H Naik, Sudipta Kundu, Indrajit Maity, and Manish Jain.  Origin and evolution of ultraflat bands in twisted bilayer transition metal dichalcogenides: Realization of triangular quantum dots.  Physical Review B, 102(7):075413, 2020.
  * [48] Marwa Mannaï and Sonia Haddad.  Twistronics versus straintronics in twisted bilayers of graphene and transition metal dichalcogenides.  Physical Review B, 103(20):L201112, 2021.
  * [49] Mattia Angeli and Allan H MacDonald.  $\gamma$ valley transition metal dichalcogenide moiré bands.  Proceedings of the National Academy of Sciences, 118(10), 2021.
  * [50] Georg Kresse and Jürgen Furthmüller.  Efficiency of ab-initio total energy calculations for metals and semiconductors using a plane-wave basis set.  Computational materials science, 6(1):15–50, 1996.
  * [51] Mit H Naik and Manish Jain.  Ultraflatbands and shear solitons in moiré patterns of twisted bilayer transition metal dichalcogenides.  Physical Review Letters, 121(26):266401, 2018.
  * [52] Zhen Ma, Shuai Li, Meng-Meng Xiao, Ya-Wen Zheng, Ming Lu, HaiWen Liu, Jin-Hua Gao, and XC Xie.  Moiré flat bands of twisted few-layer graphite.  arXiv preprint arXiv:2001.07995, 2020.
  * [53] Olga Arroyo-Gascón, Ricardo Fernández-Perea, Eric Suárez Morell, Carlos Cabrillo, and Leonor Chico.  One-dimensional moiré superlattices and flat bands in collapsed chiral carbon nanotubes.  Nano Letters, 20(10):7588–7593, 2020.
  * [54] Yang Xu, Ariana Ray, Yu-Tsun Shao, Shengwei Jiang, Daniel Weber, Joshua E. Goldberger, Kenji Watanabe, Takashi Taniguchi, David A. Muller, Kin Fai Mak, and Jie Shan.  Emergence of a noncollinear magnetic state in twisted bilayer cri3.  arXiv preprint arXiv 2103.09850, 2021.
  * [55] Robert G Parr.  Density functional theory of atoms and molecules.  In Horizons of quantum chemistry, pages 5–15. Springer, 1980.
  * [56] Walter Kohn and Lu Jeu Sham.  Self-consistent equations including exchange and correlation effects.  Physical Review, 140(4A):A1133, 1965.
  * [57] John P Perdew, Adrienn Ruzsinszky, Gábor I Csonka, Oleg A Vydrov, Gustavo E Scuseria, Lucian A Constantin, Xiaolan Zhou, and Kieron Burke.  Restoring the density-gradient expansion for exchange in solids and surfaces.  Physical Review Letters, 100(13):136406, 2008.
  * [58] Jiří Klimeš, David R Bowler, and Angelos Michaelides.  Van der waals density functionals applied to solids.  Physical Review B, 83(19):195131, 2011.
  * [59] Stefan Grimme.  Semiempirical gga-type density functional constructed with a long-range dispersion correction.  Journal of computational chemistry, 27(15):1787–1799, 2006.

Figure 1: (a) Hexagonal cell Lfix taken as a reference layer. (b) Bravais-
moiré and super hexagonal cell built with $r$=5, $s$=1 by using Equation (1) .
The commensurable rotation Lrot (red dots) under $21.79^{\circ}$ is shown
projected on the coincident reference system defined by $L_{fix}$ (purple
dots). The primitive cell (cyan lines) and the affine points of the two
layers, located at the vertices of the internal hexagon (light green dash
lines) are also shown. (c) Shifted Bravais-moiré (green dots) indexed by
$r$=5, $s$=1. This corresponds to a shifted cell from the hidden lattice which
has a commensurable rotation Lrot (gray dots) of $21.79^{\circ}$ with respect
the reference system $L_{fix}$ (purple dots). Figure 2: (a) Moiré patterns
formed by relaxed structures for the studied angles. Blue balls stand for Cr
atoms and light pink ones for I atoms. (b) Side view of corresponding
structures (c) Radial distribution function (RDF) for interlayer Cr atoms.
Only the lowest energy structure is reported for each $\theta$. Figure 3: (a)
Total energy difference $\Delta E^{T}$ per Cr atom ($\Delta E^{T}/N_{Cr}$,
where $N_{Cr}$ stands for the number of Cr atoms) between AFM and FM
configurations as function on the twist angle $\theta$. (b) Contributions of
$s+p$ and $d$ orbitals to the energy band $\Delta E^{B}$ per Cr atom ($\Delta
E^{B}/N_{Cr}$) computed from the projected density of states on each orbital.
The inset in (a) shows the energy difference, $\Delta E^{S}=\Delta
E^{T}-\Delta E^{B}$, per Cr atom ($\Delta E^{S}/N_{Cr}$). The purple region
represents an AFM ordering and the white one depicts the FM ordering.

Figure 4: Total and projected density of states for the lowest energy phases (FM R$\bar{3}$ at $\theta=0^{\circ}$, FM R3 at $\theta=21.72^{\circ}$ and AFM R3 at $\theta=32.20^{\circ}$): (a) Total DOS, and PDOS for Cr and I. (b) $d$-Cr PDOS, and (c) $p$-I PDOS.  Figure 5: Band structures for the lowest energy phases. (a) FM R$\bar{3}$ phase at $\theta=0^{\circ}$, (b) FM R3 phase at $\theta=21.79^{\circ}$ and (c) AFM R3 phase at $\theta=32.20^{\circ}$. A green circle shows the conduction band minimum (CBM) in each case. Blue (yellow) lines represent the spin up (down) channel. Moreover, the lower and upper panels correspond to the occupied and unoccupied bands, respectively. Table 1: Twisted commensurable angles following the equation 1 with the corresponding amount total of atoms (NTot) into the supercell and amount of Cr atoms (NCr) . $\theta$ | NTot | NCr | r | s
---|---|---|---|---
5.1 | 2032 | 508 | 20 | 6
6.0 | 1456 | 364 | 17 | 5
7.3 | 976 | 244 | 14 | 4
9.4 | 592 | 148 | 11 | 3
11.0 | 1744 | 436 | 19 | 5
13.2 | 304 | 76 | 8 | 2
16.4 | 784 | 196 | 13 | 3
17.9 | 1504 | 376 | 18 | 4
21.8 | 112 | 28 | 5 | 1
26.0 | 1264 | 316 | 17 | 3
27.8 | 640 | 160 | 12 | 2
32.2 | 208 | 52 | 7 | 1
35.6 | 1072 | 268 | 16 | 2
38.2 | 352 | 88 | 9 | 1
42.1 | 496 | 124 | 11 | 1
44.8 | 688 | 172 | 13 | 1
46.8 | 928 | 232 | 15 | 1
Table 2: Optimized values for R3, R$\bar{3}$ and C2/m phases at $\theta=0^{\circ}$, $21.79^{\circ}$ and $32.20^{\circ}$. The following quantities are shown in order for each phase: the lattice parameter $a$=$b$ (Å), the number of n.n. and the distance interval (Å) among Cr atoms, the number of n.n.n. and the distance interval (Å) among Cr atoms, the cohesive energy (eV), and the magnetic ordering. |  | $\theta=0^{\circ}$ | $\theta=21.79^{\circ}$ | $\theta=32.20^{\circ}$
---|---|---|---|---
R3 |  $a$ (Å) | 6.873 | 18.171 | 24.763
| n.n. [Interval (Å)] | 2 [6.60] | 1 [6.75] | 6 [6.85-6.89]
| n.n.n. [Interval (Å)] | 6 [7.70-7.711] | 16 [6.92-7.29] | 19 [6.97-7.10]
| Cohesive energy (eV) | 1.2150 | 1.2117 | 1.2118
| Magnetic ordering | FM | FM | AFM
C2/m |  $a$ (Å) | 6.865 | 18.162 | 24.762
| n.n. [Interval (Å)] | 4 [6.94-6.95] | 1 [6.75] | 1 [6.77].
| n.n.n. [Interval (Å)] | 4 [7.99-8.02 ] | 14 [6.92-7.29] | 16 [6.86-7.10]
| Cohesive energy (eV) | 1.2186 | 1.2116 | 1.2117
| Magnetic ordering | AFM | FM | FM
R$\bar{3}$ |  $a$ (Å) | 6.876 | 18.170 | 24.760
| n.n. [Interval (Å)] | 1 [6.52] | 10 [6.94-7.07] | 3 [6.85]
| n.n.n. [Interval (Å)] | 9 [6.63-6.65] | 6 [7.26-7.29] | 17 [6.94-7.10]
| Cohesive energy (eV) | 1.2197 | 1.2114 | 1.2115
| Magnetic ordering | FM | AFM | FM

Table of Contents

moiré patterns with commensurable rotation on CrI3 bilayer in its usual
stacking phases R3, R$\bar{3}$ and C2/m are investigated. These commensurable
rotations modify the magnetic ordering and the dispersion bands due to
variations in the interlayer distance of nearest and second nearest neighbors
of Cr atoms.


# Parity alternating permutations starting with an odd integer

Frether Getachew Kebede111Corresponding author. Department of Mathematics,
College of Natural and Computational Sciences, Addis Ababa University, P.O.Box
1176, Addis Ababa, Ethiopia; e-mail<EMAIL_ADDRESS>Fanja Rakotondrajao
Département de Mathématiques et Informatique, BP 907 Université
d’Antananarivo, 101 Antananarivo, Madagascar; e-mail<EMAIL_ADDRESS>
###### Abstract

A Parity Alternating Permutation of the set $[n]=\\{1,2,\ldots,n\\}$ is a
permutation with even and odd entries alternatively. We deal with parity
alternating permutations having an odd entry in the first position, PAPs. We
study the numbers that count the PAPs with even as well as odd parity. We also
study a subclass of PAPs being derangements as well, Parity Alternating
Derangements (PADs). Moreover, by considering the parity of these PADs we look
into their statistical property of excedance.

###### keywords:

parity , parity alternating permutation , parity alternating derangement ,
excedance

###### MSC:

[2020] 05A05 , 05A15 , 05A19

##  1 Introduction and preliminaries

A permutation $\pi$ is a bijection from the set $[n]=\\{1,2,\ldots,n\\}$ to
itself and we will write it in standard representation as
$\pi=\pi(1)\,\pi(2)\,\cdots\,\pi(n)$, or as the product of disjoint cycles.
The parity of a permutation $\pi$ is defined as the parity of the number of
transpositions (cycles of length two) in any representation of $\pi$ as a
product of transpositions. One way of determining the parity of $\pi$ is by
obtaining the sign of $(-1)^{n-c}$, where $c$ is the number of cycles in the
cycle representation of $\pi$. That is, if the sign of $\pi$ is -1, then $\pi$
is called an odd permutation, and an even permutation otherwise. For example,
the permutation $4\,2\,1\,7\,8\,6\,3\,5=(1\,\,4\,\,7\,\,3)(2)(5\,\,8)(6)$, of
length 8, is even since it has sign 1. All basic definitions and properties
not explained here can be found in for example [8] and [4].

According to [9], a Parity Alternating Permutation over the set $[n]$ is a
permutation, in standard form, with even and odd entries alternatively (in
this general sense). The set $\mathcal{P}_{n}$ of all parity alternating
permutations is a subgroup of the symmetric group $S_{n}$, the group of all
permutations over $[n]$. The order of the set set $\mathcal{P}_{n}$ has been
studied lately in relations to other number sequences such as Eulerian numbers
(see [10, 9]).

However, in this paper we will deal only with the parity alternating
permutations which in addition have an odd entry in the first position; and we
call them PAPs. It can be shown that the set $P_{n}$ containing all PAPs over
$[n]$ is a subgroup of the symmetric group $S_{n}$ and also of the group
$\mathcal{P}_{n}$. We consider this kind of permutations because, for odd $n$
there are no parity alternating permutations over $[n]$ beginning with an even
integer. Avi Peretz determined the number sequence that count the number of
PAPs (see A010551). Unfortunately, we could not find any details of his work.
In A010551, we can also find the exponential generating function of these
numbers due to Paul D. Hanna. Since there is no published proof of this
formula we prove it here, as Theorem 2.2. Moreover, the numbers that count the
PAPs with even parity and with odd parity (which were not studied before) are
determined.

By $p_{n}$ we denote the cardinality of the set $P_{n}$ of all PAPs over
$[n]$. Let $\phi_{n}$ denote a map from $P_{n}$ to
$S_{\lceil\frac{n}{2}\rceil}\times S_{\lfloor\frac{n}{2}\rfloor}$ that relates
a PAP $\sigma$ to a pair of permutations $(\sigma_{1},\sigma_{2})$ in the set
$S_{\lceil\frac{n}{2}\rceil}\times S_{\lfloor\frac{n}{2}\rfloor}$, in such a
way that $\sigma_{1}(i)=\frac{\sigma(2i-1)+1}{2}$ and
$\sigma_{2}(i)=\frac{\sigma(2i)}{2}$. It is easy to see that this map is a
bijection. For example, the PAPs $5\,2\,1\,4\,3\,6\,7$ and
$7\,4\,5\,6\,3\,2\,1$ over [7] are mapped to the pairs
$(3\,1\,2\,4,\,1\,2\,3)$ and $(4\,3\,2\,1,\,2\,3\,1)$, respectively. If we
consider a PAP $\sigma$ in cycle representations, then each cycle consists of
integers of the same parity. Thus, we immediately get cycle representation of
$\sigma_{1}$ and $\sigma_{2}$. For instance, the cycle form of the two PAPs
above are $(1\,5\,3)(7)(2)(4)(6)$ and $(1\,7)(3\,5)(2\,4\,6)$ which correspond
to the pairs $\left((1\,3\,2)(4),\,(1)(2)(3)\right)$ and
$((1\,4)(2\,3),\,(1\,2\,3))$, respectively. (Unless stated otherwise we will
always use (disjoint) cycle representation of permutations.) Another way of
looking at the mapping $\phi_{n}$ is that $\sigma_{1}$ and $\sigma_{2}$
correspond to the parts that contain the odd and even integers in $\sigma$,
respectively. Therefore, studying PAPs is similar to studying the two
permutations that correspond to the even and the odd integers in the PAP
separately and then combining the properties. In Table 1, we give a short
summary of properties that permutations and PAPs satisfy (for detailed
discussions, see Section 2).

| Permutations | PAPs
---|---|---
Seq |  $1,1,2,6,24,120,\ldots.$ (A000142) |  $1,1,1,2,4,12,\ldots.$ (A010551)
EGF | $\frac{1}{1-x}$ | $\frac{2\sqrt{4-x^{2}}+2\cos^{-1}\left(1-x^{2}/2\right)}{(2-x)\sqrt{4-x^{2}}}$
Even (seq) |  $1,1,1,3,12,60,\ldots.$ (A001710) | $1,1,1,1,2,6,18,72,\ldots$
Odd (seq) |  $1,1,1,3,12,60,\ldots.$ (A001710) | $0,0,0,1,2,6,18,72,\ldots$
Even (EGF) | $\frac{2-x^{2}}{2-2x}$ | $\frac{\sqrt{4-x^{2}}+\cos^{-1}\left(1-\frac{x^{2}}{2}\right)}{(2-x)\sqrt{4-x^{2}}}+\frac{x^{2}}{4}+\frac{x}{2}+\frac{1}{2}$
Odd (EGF) | $\frac{x^{2}}{2-2x}$ | $\frac{\sqrt{4-x^{2}}+\cos^{-1}\left(1-\frac{x^{2}}{2}\right)}{(2-x)\sqrt{4-x^{2}}}-\frac{x^{2}}{4}-\frac{x}{2}-\frac{1}{2}$
Table 1: A comparison table of permutations and PAPs (EGF mean exponential
generating function).

One interesting subset of $S_{n}$ is the set $D_{n}$ of derangements. For
$d_{n}=|D_{n}|$, we have a well known relation

$\displaystyle d_{n}=(n-1)[d_{n-1}+d_{n-2}],\,\,d_{0}=1\text{ and }d_{1}=0$
(1)

for $n\geq 2$. A proof of this relation may be found in any textbook on
combinatorics, but we will have later use of the following bijection due to
Mantaci and Rakotondrajao ([6]). They define $\psi_{n}$ to be the bijection
between $D_{n}$ and $[n-1]\times(D_{n-1}\cup D_{n-2})$ as follows: let
$D_{n}^{(1)}$ denote the set of derangements over $[n]$ having the integer $n$
in a cycle of length greater than 2, and $D_{n}^{(2)}$ be the set of
derangements over $[n]$ having $n$ in a transposition. These two sets are
disjoint and their union is $D_{n}$. Then for $\delta\in D_{n}$ define
$\psi_{n}(\delta)=(i,\delta^{\prime})$, where $i=\delta^{-1}(n)$ and
$\delta^{\prime}$ is the derangement obtained from

  1. $\bullet$

$\delta\in D_{n}^{(1)}$ by removing $n$ or

  2. $\bullet$

$\delta\in D_{n}^{(2)}$ by removing the transposition $(i\,\,n)$ and then
decreasing all integers greater than $i$ by 1.

For instance, the pairs $(2,(1\,5\,2)(3\,4))$ and $(2,(1\,2)(3\,4))$
correspond to the derangements $(1\,5\,2\,6)(3\,4)$ and $(1\,3)(4\,5)(2\,6)$,
respectively, for $n=6$. We denote the restricted bijections
$\psi_{n}|_{D_{n}^{(1)}}$ and $\psi_{n}|_{D_{n}^{(2)}}$ by $\psi_{n}^{(1)}$
and $\psi_{n}^{(2)}$, respectively.

Another important, and more difficult to prove, recurrence relation that the
numbers $d_{n}$ satisfy is

$\displaystyle d_{n}=n\,d_{n-1}+(-1)^{n},\,\,d_{0}=0$ (2)

for $n\geq 1$. We will later make a use of the bijection $\tau_{n}:([n]\times
D_{n-1})\backslash F_{n}\longrightarrow D_{n}\backslash E_{n}$ given by the
second author ([7]) proving the recurrence. Where $E_{n}$ is the set
containing the derangement $\Delta_{n}=(1\,2)(3\,4)\cdots(n-1\,\,\,n)$ for
even $n$, and is empty for odd $n$. $F_{n}$ is the set containing the pair
$(n,\,\Delta_{n-1})$ when $n$ is odd, and is empty when $n$ is even. Thus, the
inverse $\zeta_{n}$ of $\tau_{n}$ relates an element of $[n-1]\times D_{n-1}$
with every derangement over $[n]$ that has the integer $n$ in a cycle of
length greater than 2, and an element of $\\{n\\}\times D_{n-1}\backslash
F_{n}$ with every derangement over $[n]$ in which $n$ lies in a transposition.

Classifying derangements by their parity, we denote the number of even and odd
derangements over $[n]$ by $d^{e}_{n}$ and $d^{o}_{n}$, respectively. Clearly
$d_{n}=d^{e}_{n}+d^{o}_{n}$. Moreover, the numbers $d^{e}_{n}$ and $d^{o}_{n}$
satisfy the relations

$\displaystyle d^{e}_{n}=(n-1)[d^{o}_{n-1}+d^{o}_{n-2}]\quad\text{ and }\quad
d^{o}_{n}=(n-1)[d^{e}_{n-1}+d^{e}_{n-2}],$ (3)

for $n\geq 2$ with initial conditions $d^{e}_{0}=1$, $d^{e}_{1}=0$,
$d^{o}_{0}=0$, and $d^{o}_{1}=0$ ([6], Proposition 4.1).

We will put a major interest on Parity Alternating Derangements (PADs) which
are the derangements which also are parity alternating permutations starting
with odd integers. Let $\mathfrak{d}_{n}$ denote cardinality of the set of
PADs $\mathfrak{D}_{n}=D_{n}\cap P_{n}$. The restricted bijection
$\Phi_{n}=\phi_{n}|_{\mathfrak{D}_{n}}:\mathfrak{D}_{n}\longrightarrow
D_{\lceil\frac{n}{2}\rceil}\times D_{\lfloor\frac{n}{2}\rfloor}$ will let us
consider the odd parts and the even parts of any given PAD regarded as
ordinary derangements with smaller length than the length of the PAD. The
mapping $\Phi_{n}$ plays the central role in our investigations. In Table 2,
we display the connection of ordinary derangements and PADs (for detailed
discussions, see Section 3). Finding explicit expressions for some of the
generating functions are still open questions. On the other hand the EGF for
the PADs for example is the solution to an eighth order differential equation
with polynomial coefficients, and also is expressible in terms of Hadamard
products of some known generating functions.

| Derangements | PADs
---|---|---
Seq |  $1,0,1,2,9,44,\ldots$ (A000166) | $1,0,0,0,1,2,4,18,81,396,\ldots$
EGF | $\frac{e^{-x}}{1-x}$ | open
RR | $d_{n}=(n-1)[d_{n-1}+d_{n-2}]$ | relation (4)
RR | $d_{n}=nd_{n-1}+(-1)^{n}$ | relation (5)
Even (seq) |  $1,0,0,2,3,24,130,\ldots$ (A003221) | $1,0,0,0,1,0,4,6,45,192,976\ldots$
Odd (seq) |  $0,0,1,0,6,20,135,\ldots$ (A000387) | $0,0,0,0,0,2,0,12,36,204,960,\ldots$
Even (EGF) | $\frac{(2-x^{2})e^{-x}}{2(1-x)}$ | open
Odd (EGF) | $\frac{x^{2}e^{-x}}{2(1-x)}$ | open
Even (RR) | $d^{e}_{n}=(n-1)[d^{o}_{n-1}+d^{o}_{n-2}]$ | relation (6)
Odd (RR) | $d^{o}_{n}=(n-1)[d^{e}_{n-1}+d^{e}_{n-2}]$ | relation (7)
Even - Odd | $(-1)^{n-1}(n-1)$ | $(-1)^{n-2}\Big{\lceil}\frac{n-2}{2}\Big{\rceil}\Big{\lfloor}\frac{n-2}{2}\Big{\rfloor}$
Table 2: A comparison table of derangements and PAPs, RR represents recurrence
relation.

In section 4, we study excedance distribution over PADs by means of the
corresponding distributions for the two derangements obtained by $\Phi_{n}$.

##  2 Parity Alternating Permutations (PAPs)

As we stated in the introduction, we use splitting method by the mapping
$\phi_{n}$ in the study of PAPs. One application of this is that the number of
PAPs of length $n$ is

$\displaystyle
p_{n}=|S_{\lceil\frac{n}{2}\rceil}||S_{\lfloor\frac{n}{2}\rfloor}|=\lceil
n/2\rceil!\lfloor n/2\rfloor!.$

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
$p_{n}$ | 1 | 1 | 1 | 2 | 4 | 12 | 36 | 144 | 576 | 2880 | 14400
Table 3: First few terms of the sequence $\\{p_{n}\\}_{0}^{\infty}$.

######  Proposition 2.1.

The numbers $p_{n}$ satisfy the recurrence relation

$\displaystyle p_{n}=\lceil n/2\rceil p_{n-1},$

for $n\geq 1$ and $p_{0}=1$.

###### Proof.

First let us define a mapping $\omega_{n}:S_{n}\longrightarrow[n]\times
S_{n-1}$ by

$\displaystyle\omega_{n}(\pi)=(i,\pi^{\prime}),$

where $\pi^{\prime}$ is obtained from $\pi\in S_{n}$ by removing the integer
$n$, and $i=\pi^{-1}(n)$. One can easily see that $\omega_{n}$ is a bijection.

Now let us take a PAP $\sigma$ over $[n]$. Then $\phi_{n}$ maps $\sigma$ to a
pair $(\sigma_{1},\sigma_{2})$. Define then a mapping
$\Omega:P_{n}\longrightarrow\Bigl{[}\big{\lceil}\frac{n}{2}\big{\rceil}\Bigr{]}\times
P_{n-1}$ as follows: for $n=2m$

$\displaystyle\Omega(\sigma)=\left(i,\phi_{2m}^{-1}(\sigma_{1},\,\sigma_{2}^{\prime})\right),$

where $(i,\sigma_{2}^{\prime})=\omega_{m}(\sigma_{2})$, and for $n=2m+1$

$\displaystyle\Omega(\sigma)=\left(i,\phi_{2m+1}^{-1}(\sigma_{1}^{\prime},\,\sigma_{2})\right),$

where $(i,\sigma_{1}^{\prime})=\omega_{m+1}(\sigma_{1})$. The mapping $\Omega$
is a bijection since $\omega_{n}$ is a bijection for every $n\geq 1$. In any
case, there are $\big{\lceil}\frac{n}{2}\big{\rceil}$ possibilities for $i$. ∎

As a consequence, we get the following theorem.

######  Theorem 2.2.

The exponential generating function $P(x)=\sum_{n\geq 0}p_{n}\frac{x^{n}}{n!}$
of the sequence $\\{p_{n}\\}_{n=0}^{\infty}$ has the closed formula

$P(x)=\displaystyle\frac{2}{2-x}+\displaystyle\frac{\cos^{-1}(1-\displaystyle\frac{x^{2}}{2})}{(2-x)\sqrt{1-\displaystyle\frac{x^{2}}{4}}}.$

###### Proof.

Based on the recurrence relation in Proposition 2.1, we obtain the following
relations

$\displaystyle P_{0}(x)=\frac{x}{2}P_{1}(x)+1\quad\text{ and }\quad
P_{1}(x)=\frac{x}{2}P_{0}(x)+\frac{1}{2}\int_{0}^{x}P_{0}(t)\,dt,$

where $P_{0}(x)=\sum_{n\geq 0}p_{2n}\frac{x^{2n}}{(2n)!}$ and
$P_{2}(x)=\sum_{n\geq 0}p_{2n+1}\frac{x^{2n+1}}{(2n+1)!}$. Clearly,
$P(x)=P_{0}(x)+P_{1}(x)$. Additionally, $P_{0}(x)$ satisfies the differential
equation

$\displaystyle\left(1-\frac{x^{2}}{4}\right)P^{\prime}_{0}(x)=\frac{x^{2}+2}{2x}P_{0}(x)-\frac{1}{x}.$

Thus, we obtain the formulas

$\displaystyle
P_{0}(x)=\frac{4}{4-x^{2}}+\frac{4x\sin^{-1}\left(\frac{x}{2}\right)}{(4-x^{2})^{3/2}}\quad\text{
and }\quad
P_{1}(x)=\frac{8}{4x-x^{3}}+\frac{8x\sin^{-1}\left(\frac{x}{2}\right)}{x(4-x^{2})^{3/2}}-\frac{2}{x}.$

Therefore,

$P(x)=\displaystyle\frac{2}{2-x}+\displaystyle\frac{\cos^{-1}(1-\displaystyle\frac{x^{2}}{2})}{(2-x)\sqrt{1-\displaystyle\frac{x^{2}}{4}}}.\qed$

For classification of PAPs in terms of their parity, we use $P^{e}_{n}$ and
$P^{o}_{n}$ to denote the set of even PAPs and odd PAPs, respectively, and
$p_{n}^{e}$ and $p_{n}^{o}$ as their cardinality, respectively. Thus,

$\displaystyle p_{n}=p^{e}_{n}+p^{o}_{n}.$

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
$p_{n}^{e}$ | 1 | 1 | 1 | 1 | 2 | 6 | 18 | 72 | 288 | 1440 | 7200
$p_{n}^{o}$ | 0 | 0 | 0 | 1 | 2 | 6 | 18 | 72 | 288 | 1440 | 7200
Table 4: First few terms of the sequences $\\{p_{n}^{e}\\}_{0}^{\infty}$ and
$\\{p_{n}^{o}\\}_{0}^{\infty}$.

Our goal is now to study the relationships between these two sequences.

######  Theorem 2.3.

The numbers $p_{n}^{e}$ and $p_{n}^{o}$ satisfy the recurrence relations

$\displaystyle p_{n}^{e}=\lfloor(n-1)/2\rfloor p_{n-1}^{o}+p_{n-1}^{e}$
$\displaystyle p_{n}^{o}=\lfloor(n-1)/2\rfloor p_{n-1}^{e}+p_{n-1}^{o},$

for $n\geq 1$, with initial conditions $p^{e}_{0}=1$ and $p^{o}_{0}=0$.

###### Proof.

Let $S_{n}^{e}$ and $S_{n}^{o}$ be the set of even and odd permutations,
respectively. Define two mappings
$\omega_{n}^{e}:S_{n}^{e}\longrightarrow[n-1]\times S_{n-1}^{o}\cup
S_{n-1}^{e}$ and $\omega_{n}^{o}:S_{n}^{o}\longrightarrow[n-1]\times
S_{n-1}^{e}\cup S_{n-1}^{o}$ by

$\displaystyle\omega_{n}^{e}(\pi)=\begin{cases}(i,\pi^{\prime}),\text{ if
}i\neq n\\\ \pi^{\prime\prime},\text{ otherwise}\end{cases}\quad\text{ and
}\quad\omega_{n}^{o}(\pi)=\begin{cases}(j,\pi^{\prime}),\text{ if }j\neq n\\\
\pi^{\prime\prime},\text{ otherwise}\end{cases},$

respectively, where $i=\pi^{-1}(n)$, $\pi^{\prime}$ is obtained from $\pi$ by
removing the integer $n$, and $\pi^{\prime\prime}$ is obtained from $\pi$ by
removing the cycle $(n)$, for $\pi\in S_{n}^{e}$. Similarly for
$\omega_{n}^{o}$. It is easy to see that both mappings $\omega_{n}^{e}$ and
$\omega_{n}^{o}$ are bijections.

The mapping $\omega_{n}^{e}$ changes the parity of $\pi$ when it results in
$\pi^{\prime}$ and preserves when it results in $\pi^{\prime\prime}$. This is
because the signs of $\pi$, $\pi^{\prime}$ and $\pi^{\prime\prime}$ are
$(-1)^{n-c}$, $(-1)^{n-1-c}$, and $(-1)^{n-1-c+1}$, respectively, where $c$ is
the number of cycles in $\pi$. For the mapping $\omega_{n}^{o}$ we apply
similar argument.

Now consider a PAP $\sigma$ in $P_{n}$. Then $\phi_{n}$ maps $\sigma$ in to a
pair $(\sigma_{1},\sigma_{2})$. Following the notation in the proof of
Proposition 2.1, let us define two mappings
$\Omega^{e}:P_{n}^{e}\longrightarrow\Bigl{[}\big{\lfloor}\frac{n-1}{2}\big{\rfloor}\Bigr{]}\times
P_{n-1}^{o}\cup P_{n-1}^{e}$ and
$\Omega^{o}:P_{n}^{o}\longrightarrow\Bigl{[}\big{\lfloor}\frac{n-1}{2}\big{\rfloor}\Bigr{]}\times
P_{n-1}^{e}\cup P_{n-1}^{o}$ as follows:

  1. 1.

when $n$ is even

$\displaystyle\Omega^{e}(\sigma)=\begin{cases}\left(i,\,\phi_{n}^{-1}(\sigma_{1},\sigma_{2}^{\prime})\right),\text{
if }i\neq\frac{n}{2}\\\
\phi_{n}^{-1}(\sigma_{1},\sigma_{2}^{\prime\prime}),\text{
otherwise}\end{cases}\text{and }$
$\displaystyle\Omega^{o}(\sigma)=\begin{cases}\left(i,\,\phi_{n}^{-1}(\sigma_{1},\sigma_{2}^{\prime})\right),\text{
if }i\neq\frac{n}{2}\\\
\phi_{n}^{-1}(\sigma_{1},\sigma_{2}^{\prime\prime}),\text{
otherwise}\end{cases},$

where $i=\sigma_{2}^{-1}(\frac{n}{2})$, and both $\sigma^{\prime}_{2}$,
$\sigma^{\prime\prime}_{2}$ are obtained from $\sigma_{2}$ by the mapping
$\omega_{\frac{n}{2}}^{e}$ when $\sigma\in P_{n}^{e}$ and by the mapping
$\omega_{\frac{n}{2}}^{o}$ when $\sigma\in P_{n}^{o}$,

  2. 2.

when $n$ is odd

$\displaystyle\Omega^{e}(\sigma)=\begin{cases}\left(j,\,\phi_{n}^{-1}(\sigma_{1}^{\prime},\sigma_{2})\right),\text{
if }j\neq\frac{n+1}{2}\\\
\phi_{n}^{-1}(\sigma_{1}^{\prime\prime},\sigma_{2}),\text{
otherwise}\end{cases}\text{and }$
$\displaystyle\Omega^{o}(\sigma)=\begin{cases}\left(j,\,\phi_{n}^{-1}(\sigma_{1}^{\prime},\sigma_{2})\right),\text{
if }j\neq\frac{n+1}{2}\\\
\phi_{n}^{-1}(\sigma_{1}^{\prime\prime},\sigma_{2}),\text{
otherwise}\end{cases},$

where $j=\sigma_{1}^{-1}(\frac{n+1}{2})$, and both $\sigma^{\prime}_{1}$,
$\sigma^{\prime\prime}_{1}$ are obtained from $\sigma_{1}$ by the mapping
$\omega_{\frac{n+1}{2}}^{e}$ when $\sigma\in P_{n}^{e}$ and by the mapping
$\omega_{\frac{n+1}{2}}^{o}$ when $\sigma\in P_{n}^{o}$.

Since $\omega_{n}$ is bijection for $n\geq 2$, both $\Omega^{e}$ and
$\Omega^{o}$ are bijections too. Note that in both mappings there are
$\big{\lfloor}\frac{n-1}{2}\big{\rfloor}$ possibilities for $i$
($i\neq\frac{n}{2}$) and similarly for $j$ ($j\neq\frac{n+1}{2}$). ∎

######  Proposition 2.4.

For any positive integer $n\geq 3$, we have

$\displaystyle p_{n}^{e}=p_{n}^{o}.$

###### Proof.

Multiplying a PAP by a transposition $(1,n)$ if $n$ is odd, or by $(1,n-1)$ if
$n$ is even, we obtain a PAP having opposite parity. This multiplication means
swapping the first and the last odd integer of a PAP in standard
representation. It creates a bijection between $P^{e}_{n}$ and $P^{o}_{n}$. ∎

By applying Proposition 2.4 and considering $p(x)$, we get:

######  Corollary 2.5.

The exponential generating functions of the sequences $\\{p_{n}^{e}\\}_{n\geq
0}$ and $\\{p_{n}^{o}\\}_{n\geq 0}$ have the closed forms

$\displaystyle
P^{e}(x)=\displaystyle\frac{1}{2}\left(P(x)+\frac{x^{2}}{2}+x+1\right)\quad\text{
and }\quad
P^{o}(x)=\displaystyle\frac{1}{2}\left(P(x)-\frac{x^{2}}{2}-x-1\right).$

$\square$

##  3 Parity Alternating Derangements (PADs)

As a result of the bijection $\Phi_{n}$ in the introduction above, we can
determine the number $\mathfrak{d}_{n}$ of PADs over $[n]$ as follows:

$\displaystyle\mathfrak{d}_{n}=d_{\lceil n/2\rceil}d_{\lfloor
n/2\rfloor}=\sum_{j=0}^{\lceil n/2\rceil}\sum_{i=0}^{\lfloor n/2\rfloor}\lceil
n/2\rceil!\lfloor n/2\rfloor!\frac{(-1)^{i+j}}{j!\,i!}.$

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---|---
$d_{n}$ | 1 | 0 | 1 | 2 | 9 | 44 | 265 | 1854 | 14833 | 133496
$\mathfrak{d}_{n}$ | 1 | 0 | 0 | 0 | 1 | 2 | 4 | 18 | 81 | 396
Table 5: First few values of $d_{n}$ and $\mathfrak{d}_{n}$.

In the next theorem we give a formula for the number of PADs, connected to the
relation (1).

######  Theorem 3.6.

The number of PADs over $[n]$ satisfy the recurrence relation

$\displaystyle\mathfrak{d}_{n}=s\big{(}\mathfrak{d}_{n-1}+(n-2-s)\left(\mathfrak{d}_{n-3}+\mathfrak{d}_{n-4}\right)\big{)},$
(4)

where $s=\big{\lfloor}\frac{n-1}{2}\big{\rfloor}=\frac{2n-3-(-1)^{n}}{4}$, for
$n\geq 4$, with initial conditions $\mathfrak{d}_{0}=1$, $\mathfrak{d}_{1}=0$,
$\mathfrak{d}_{2}=0$ and $\mathfrak{d}_{3}=0$.

###### Proof.

The proof is splitted into two cases, for PADs over a set of odd and even
sizes. Let $(\delta_{1},\delta_{2})$ be the corresponding pair of a PAD
$\delta\in\mathfrak{D}_{n}$ under the mapping $\Phi_{n}$. Define a mapping
$\Psi:\mathfrak{D}_{n}\longrightarrow[s]\times\left(\mathfrak{D}_{n-1}\cup[n-2-s]\times(\mathfrak{D}_{n-3}\cup\mathfrak{D}_{n-4})\right)$
as follows:

Case I: for odd $n$, depending on the following two elective properties of
$\delta$, the mapping $\Psi$ will be defined as:

  1. 1.

in the event of the largest entry $\frac{n+1}{2}$ of $\delta_{1}$ being in a
cycle of length greater than 2, we let

$\displaystyle\Psi(\delta)=\left(i,\,\Phi_{n}^{-1}(\delta^{\prime}_{1},\,\delta_{2})\right),$

where $(i,\delta^{\prime}_{1})=\psi_{\frac{n+1}{2}}^{(1)}(\delta_{1})$;

  2. 2.

in the event when $\frac{n+1}{2}$ lies in a transposition in $\delta_{1}$, we
distinguish two cases:

     * (a)

if the largest entry $\frac{n-1}{2}$ of $\delta_{2}$ is contained in a cycle
of length greater than 2, then

$\displaystyle\Psi(\delta)=\left(i,\,j,\,\Phi_{n}^{-1}(\delta^{\prime}_{1},\,\delta^{\prime}_{2})\right),$

where $(i,\,\delta^{\prime}_{1})=\psi_{\frac{n+1}{2}}^{(2)}(\delta_{1})$ and
$(j,\,\delta^{\prime}_{2})=\psi_{\frac{n-1}{2}}^{(1)}(\delta_{2})$;

     * (b)

if $\frac{n-1}{2}$ is contained in a cycle of length 2 in $\delta_{2}$, then

$\displaystyle\Psi(\delta)=\left(i,\,j,\,\Phi_{n}^{-1}(\delta^{\prime}_{1},\,\delta^{\prime}_{2})\right),$

where $(i,\,\delta^{\prime}_{1})=\psi_{\frac{n+1}{2}}^{(2)}(\delta_{1})$ and
$(j,\,\delta^{\prime}_{2})=\psi_{\frac{n-1}{2}}^{(2)}(\delta_{2})$.

Case II: for even $n$,

  1. 1.

in the event of the largest entry $\frac{n}{2}$ of $\delta_{2}$ lies in a
cycle of length greater than 2, we let

$\displaystyle\Psi(\delta)=\left(i,\,\Phi_{n}^{-1}(\delta_{1},\,\delta^{\prime}_{2})\right),$

where $(i,\,\delta^{\prime}_{2})=\psi_{\frac{n}{2}}^{(1)}(\delta_{2})$;

  2. 2.

in the event when $\frac{n}{2}$ being in a transposition in $\delta_{2}$, we
distinguish two cases:

     * (a)

if the largest entry $\frac{n}{2}$ in $\delta_{1}$ contained in a cycle of
length greater than 2, then

$\displaystyle\Psi(\delta)=\left(i,\,j,\,\Phi_{n}^{-1}(\delta^{\prime}_{1},\,\delta^{\prime}_{2})\right),$

where $(i,\,\delta^{\prime}_{1})=\psi_{\frac{n}{2}}^{(1)}(\delta_{1})$ and
$(j,\,\delta^{\prime}_{2})=\psi_{\frac{n}{2}}^{(2)}(\delta_{2})$;

     * (b)

if $\frac{n}{2}$ contained in a cycle of length 2 in $\delta_{1}$, then

$\displaystyle\Psi(\delta)=\left(i,\,j,\,\Phi_{2n}^{-1}(\delta^{\prime}_{1},\,\delta^{\prime}_{2})\right),$

where $(i,\,\delta^{\prime}_{1})=\psi_{\frac{n}{2}}^{(2)}(\delta_{1})$ and
$(j,\,\delta^{\prime}_{2})=\psi_{\frac{n}{2}}^{(2)}(\delta_{2})$.

Since $\psi_{n}$ is a bijection for any $n\geq 2$, one can easily conclude
that $\Psi$ is a bijection too. Note that in both cases there are
$\big{\lfloor}\frac{n-1}{2}\big{\rfloor}=s$ possibilities for $i$ and
$\big{\lfloor}\frac{n-2}{2}\big{\rfloor}=n-2-s$ possibilities for $j$. Thus,
the formula in the Theorem follows. ∎

The next theorem is connected to the relation (2).

######  Theorem 3.7.

The number $\mathfrak{d}_{n}$ of PADs also satisfies the relation

$\displaystyle\mathfrak{d}_{n}=s\mathfrak{d}_{n-1}+(-1)^{s}d_{n-s},$ (5)

where $s=\big{\lceil}\frac{n}{2}\big{\rceil}=\frac{2n+1-(-1)^{n}}{4}$, for
$n\geq 1$ with $d_{1}=0$, $d_{0}=1$ and $\mathfrak{d}_{0}=1$.

###### Proof.

Distinguishing by means of the parity of $n$, we can write the relation (5)
as:

$\displaystyle\mathfrak{d}_{n}=d_{s}\big{(}s\,d_{s-1}+(-1)^{s}\big{)}\,\,\text{
when }n\text{ is even, and }$
$\displaystyle\mathfrak{d}_{n}=\big{(}s\,d_{s-1}+(-1)^{s}\big{)}\,d_{s-1}\,\,\text{
when }n\text{ is odd}.$

Now, take a PAD $\delta$ in $\mathfrak{D}_{n}$ and introduce two mappings as:

  * 1.

$Z_{0}:\big{(}D_{s}\backslash E_{s}\big{)}\times
D_{s}\longrightarrow[s]\times\big{(}D_{s-1}\backslash F_{s}\big{)}\times
D_{s}$ by

$\displaystyle\delta\xrightleftharpoons[\Phi^{-1}_{n}]{\Phi_{n}}(\delta_{1},\delta_{2})\xrightleftharpoons[id_{s}\times\tau_{s}]{id_{s}\times\zeta_{s}}\big{(}\delta_{1},(i,\delta^{\prime}_{2})\big{)}\xrightleftharpoons[h]{h}(i,(\delta_{1},\delta^{\prime}_{2}))\xrightleftharpoons[id\times\Phi_{n}]{id\times\Phi_{n}^{-1}}\big{(}i,\Phi_{n}^{-1}(\delta_{1},\delta^{\prime}_{2})\big{)},$

and

  * 2.

$Z_{1}:\big{(}D_{s}\backslash E_{s}\big{)}\times
D_{s-1}\longrightarrow[s]\times\big{(}D_{s-1}\backslash F_{s}\big{)}\times
D_{s-1}$ by

$\displaystyle\delta\xrightleftharpoons[\Phi^{-1}_{n}]{\Phi_{n}}(\delta_{1},\delta_{2})\xrightleftharpoons[\tau_{s}\times
id_{s-1}]{\zeta_{s}\times
id_{s-1}}\big{(}(i,\delta^{\prime}_{1}),\delta_{2}\big{)}\xrightleftharpoons[h_{2}]{h_{1}}\big{(}i,(\delta^{\prime}_{1},\delta_{2})\big{)}\xrightleftharpoons[id\times\Phi_{n}^{-1}]{id\times\Phi_{n}}\big{(}i,\Phi_{n}^{-1}(\delta^{\prime}_{1},\delta_{2})\big{)}.$

Note that $h$, $h_{1}$, and $h_{2}$ are the obvious recombination maps. Since
all the functions we used to define the two mappings $Z_{0}$ and $Z_{1}$ are
injective, both $Z_{0}$ and $Z_{1}$ are bijection mappings. ∎

In order to classify PADs with respect to their parity, we let
$\mathfrak{D}_{n}^{e}$ and $\mathfrak{D}_{n}^{o}$ denote the set of even and
odd PADs over $[n]$, respectively. Moreover,
$\mathfrak{d}^{e}_{n}=|\mathfrak{D}_{n}^{e}|$ and
$\mathfrak{d}^{o}_{n}=|\mathfrak{D}_{n}^{o}|$. Obviously,
$\mathfrak{d}_{n}=\mathfrak{d}^{e}_{n}+\mathfrak{d}^{o}_{n}$.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
$\mathfrak{d}_{n}^{e}$ | 1 | 0 | 0 | 0 | 1 | 0 | 4 | 6 | 45 | 192 | 976
$\mathfrak{d}_{n}^{o}$ | 0 | 0 | 0 | 0 | 0 | 2 | 0 | 12 | 36 | 204 | 960
Table 6: First few values of the number of even and odd PADs.

######  Proposition 3.8.

The numbers of even and odd PADs satisfy the relations

$\displaystyle\mathfrak{d}^{e}_{n}=d^{e}_{\lfloor\frac{n}{2}\rfloor}d^{e}_{\lceil\frac{n}{2}\rceil}+d^{o}_{\lfloor\frac{n}{2}\rfloor}d^{o}_{\lceil\frac{n}{2}\rceil},$
$\displaystyle\mathfrak{d}^{o}_{n}=d^{e}_{\lfloor\frac{n}{2}\rfloor}d^{o}_{\lceil\frac{n}{2}\rceil}+d^{e}_{\lceil\frac{n}{2}\rceil}d^{o}_{\lfloor\frac{n}{2}\rfloor},$

for $n\geq 0$, with initial conditions $d^{e}_{0}=1$, $d^{e}_{1}=0$,
$d^{o}_{0}=0$, and $d^{o}_{1}=0$.

###### Proof.

Let $\delta$ be a PAD over $[n]$. Then, there exist $\delta_{1}\in
D_{\lceil\frac{n}{2}\rceil}$ and $\delta_{2}\in D_{\lfloor\frac{n}{2}\rfloor}$
such that $\Phi_{n}(\delta)=(\delta_{1},\delta_{2})$. If
$\delta\in\mathfrak{D}_{n}^{e}$, then $\delta_{1}$ and $\delta_{2}$ must have
the same parity. Thus,
$\mathfrak{d}^{e}_{n}=d^{e}_{\lfloor\frac{n}{2}\rfloor}d^{e}_{\lceil\frac{n}{2}\rceil}+d^{o}_{\lfloor\frac{n}{2}\rfloor}d^{o}_{\lceil\frac{n}{2}\rceil}$.
If $\delta\in\mathfrak{D}_{n}^{e}$, then $\delta_{1}$ and $\delta_{2}$ must
have opposite parities. Hence,
$\mathfrak{d}^{o}_{n}=d^{e}_{\lfloor\frac{n}{2}\rfloor}d^{o}_{\lceil\frac{n}{2}\rceil}+d^{e}_{\lceil\frac{n}{2}\rceil}d^{o}_{\lfloor\frac{n}{2}\rfloor}$.
∎

######  Corollary 3.9.

The number of PADs with even parity and with odd parity satisfy the recurrence
relations

$\displaystyle\mathfrak{d}_{n}^{e}=s\left(\mathfrak{d}_{n-1}^{o}+(n-2-s)(\mathfrak{d}_{n-3}^{e}+\mathfrak{d}_{n-4}^{e})\right)$
(6)
$\displaystyle\mathfrak{d}_{n}^{o}=s\left(\mathfrak{d}_{n-1}^{e}+(n-2-s)(\mathfrak{d}_{n-3}^{o}+\mathfrak{d}_{n-4}^{o})\right),$
(7)

where $s=\big{\lfloor}\frac{n-1}{2}\big{\rfloor}=\frac{2n-3-(-1)^{n}}{4}$, for
$n\geq 4$ with initial conditions $\mathfrak{d}_{0}^{e}=1$,
$\mathfrak{d}_{0}^{o}=0$, and $\mathfrak{d}_{i}^{e}=\mathfrak{d}_{i}^{o}=0$
for $i=1,2,3$.

###### Proof.

It is enough to clarify the effect of the bijection $\psi_{n}$ on the parity
of a derangement over $[n]$, the rest is just applying the bijection $\Psi$
from the proof of Theorem 3.6.

Letting $\delta$ be in $D_{n}$, $\delta^{\prime}$ has sign either
$(-1)^{n-1-c}$ if $\delta\in D_{n}^{(1)}$, or $(-1)^{n-2-(c-1)}=(-1)^{n-1-c}$
if $\delta\in D_{n}^{(2)}$. Here $\delta^{\prime}$ is the derangement obtained
from $\delta$ by applying $\psi_{n}$, and $c$ is the number of cycles in the
cycle representation of $\delta$. This means, the bijection $\psi_{n}$ changes
the parity of a derangement. ∎

######  Definition 3.10.

Let $\delta$ be a derangement over $[n]$ in standard cycle representation and
let $C_{1}=(1\,\,a_{2}\,\,\cdots\,\,a_{m})$ be the first cycle. Following [3],
an extraction point of $\delta$ is an entry $e\geq 2$ if $e$ is the smallest
number in the set $\\{2,\ldots,n\\}\backslash\\{a_{2}\\}$ for which $C_{1}$
does not end with the numbers of $\\{2,\ldots,e\\}\backslash\\{a_{2}\\}$
written in decreasing order. The $(n-1)$ derangements,
$\delta_{n,i}=(1\,\,i\,\,n\,\,n-1\,\,\cdots\,\,i+2\,\,i+1\,\,i-1\,\,i-2\,\,\cdots\,\,3\,\,2)$
for $i\in[2,n]$, that do not have extraction points are called the exceptional
derangements and the set of exceptional derangements is denoted by $X_{n}$.
Note that the extraction point (if it exists) must belong to the first or the
second cycle.

Following this approach we may introduce:

######  Definition 3.11.

We call the PAD

$\displaystyle\Phi_{n}^{-1}(\delta_{\lceil\frac{n}{2}\rceil,i},\,\delta_{\lfloor\frac{n}{2}\rfloor,j}),\text{
for }i\in\big{[}2,\lceil n/2\rceil\big{]}\text{ and }j\in\big{[}2,\lfloor
n/2\rfloor\big{]}$

an exceptional PAD and we let $\mathcal{X}_{n}$ denote the set containing
them.

######  Example 3.12.

If $n=8$, then

$\displaystyle\mathcal{X}_{8}$
$\displaystyle=\\{\Phi_{8}^{-1}(\delta_{4,2},\,\delta_{4,2}),\,\,\Phi_{8}^{-1}(\delta_{4,2},\,\delta_{4,3}),\,\,\Phi_{8}^{-1}(\delta_{4,2},\,\delta_{4,4}),\,\,\Phi_{8}^{-1}(\delta_{4,3},\,\delta_{4,2}),\,\,\Phi_{8}^{-1}(\delta_{4,3},\,\delta_{4,3}),$
$\displaystyle\quad\quad\Phi_{8}^{-1}(\delta_{4,3},\,\delta_{4,4}),\,\,\Phi_{8}^{-1}(\delta_{4,4},\,\delta_{4,2}),\,\,\Phi_{8}^{-1}(\delta_{4,4},\,\delta_{4,3}),\,\,\Phi_{8}^{-1}(\delta_{4,4},\,\delta_{4,4})\\}$
$\displaystyle=\\{(1\,3\,7\,5)(2\,4\,8\,6),\,\,(1\,3\,7\,5)(2\,6\,8\,4),\,\,(1\,3\,7\,5)(2\,8\,6\,4),\,\,(1\,5\,7\,3)(2\,4\,8\,6),\,\,(1\,5\,7\,3)$
$\displaystyle\quad\quad(2\,6\,8\,4),\,\,(1\,5\,7\,3)(2\,8\,6\,4),\,\,(1\,7\,5\,3)(2\,4\,8\,6),\,\,(1\,7\,5\,3)(2\,6\,8\,4),\,\,(1\,7\,5\,3)(2\,8\,6\,4)\\}.$

######  Remark 3.13.

Since the exceptional derangements over $[n]$ have sign $(-1)^{n-1}$, all the
exceptional PADs in $\mathcal{X}_{n}$ have the same parity, with sign
$(-1)^{n-2}=(-1)^{n}$.

######  Remark 3.14.

As it was proved in [3], the number of the exceptional derangements in $X_{n}$
is the difference of the number of even and odd derangements, i.e.,
$d_{n}^{e}-d_{n}^{o}=(-1)^{n-1}(n-1)$. Chapman ([5]) also provide a bijective
proof for the same formula. Below we give the idea of the proof due to
Benjamin, Bennett, and Newberger ([3]).

Let $f_{n}$ be the involution on $D_{n}\backslash X_{n}$ defined by

$\displaystyle
f_{n}(\pi)=f_{n}\big{(}(1\,\,a_{2}\,\,X\,\,e\,\,Y\,\,Z)\,\pi^{\prime}\big{)}=(1\,\,a_{2}\,\,X\,\,Z)(e\,\,Y)\,\pi^{\prime}$

for $\pi$ in $D_{n}\backslash X_{n}$ with the extraction point $e$ in the
first cycle; and vice versa for the other $\pi$ in $D_{n}\backslash X_{n}$
with the extraction point $e$ in the second cycle. $a_{2}$ is the second
element in the first cycle of $\pi$; $X$, $Y$, and $Z$ are ordered subsets of
$[n]$, $Y\neq\emptyset$ and $Z$ consist the elements of
$\\{2,3,\ldots,e-1\\}\backslash\\{a_{2}\\}$ written in decreasing order, and
$\pi^{\prime}$ is the rest of the derangement in $\pi$. Since the number of
the cycles in $\pi$ and $f_{n}(\pi)$ differ by one, they must have opposite
parity.

Labeling $\mathfrak{d}_{n}^{e}{-}\mathfrak{d}_{n}^{o}$ as $\mathfrak{f}_{n}$,
we have the following result.

######  Proposition 3.15.

The difference $\mathfrak{f}_{n}$ counts the number of exceptional PADs over
$[n]$ and its closed formula is given by

$\displaystyle\mathfrak{f}_{n}=(-1)^{n-2}\Big{\lceil}\frac{n-2}{2}\Big{\rceil}\Big{\lfloor}\frac{n-2}{2}\Big{\rfloor}.$
(8)

###### Proof.

Let $\delta$ be in $\mathfrak{D}_{n}\backslash\mathcal{X}_{n}$. Then
$\Phi_{n}$ map $\delta$ with the pair $(\delta_{1},\delta_{2})$. Define a
mapping $F$ from $\mathfrak{D}_{n}\backslash\mathcal{X}_{n}$ to itself as

$\displaystyle
F(\delta)=\begin{cases}\Phi_{n}^{-1}\left(f_{\lceil\frac{n}{2}\rceil}(\delta_{1}),\,\delta_{2}\right)\text{
if }n\text{ is odd}\\\
\Phi_{n}^{-1}\left(\delta_{1},\,f_{\lfloor\frac{n}{2}\rfloor}(\delta_{2})\right)\text{
otherwise}\end{cases}$

Since $f_{n}$ is a bijection and changes parity, $F$ is a bijection and also
$\delta$ and $F(\delta)$ have opposite parity. The leftovers, which are the
PADs in $\mathcal{X}_{n}$ with sign $(-1)^{n-2}$, are counted by
$\lceil\frac{n-2}{2}\rceil\lfloor\frac{n-2}{2}\rfloor$. ∎

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\mathfrak{f}_{n}$ | 1 | 0 | 0 | 0 | 1 | -2 | 4 | -6 | 9 | -12 | 16 | -20 | 25
Table 7: First few values the difference
$\mathfrak{f}_{n}=\mathfrak{d}_{n}^{e}-\mathfrak{d}_{n}^{o}$.

This sequence looks like an alternating version of A002620, to which Paul
Barry constructed an EGF. From [2], we learned that he used Mathematica to
generate the formulas by taking the Inverse Laplace Transform of the ordinary
generating function described in [1]. However, we propose the following more
direct, constructive proof.

######  Theorem 3.16.

The exponential generating function of the difference $\mathfrak{f}_{n}$ has
the closed form

$\displaystyle\frac{e^{x}}{8}+\frac{e^{-x}}{8}(2x^{2}+6x+7).$

###### Proof.

From the closed formula of $\mathfrak{f}_{n}$ in Proposition 3.15, we have

$\displaystyle(n-1)^{2}=\mathfrak{f}_{2n}$
$\displaystyle=\mathfrak{d}_{2n}^{e}-\mathfrak{d}_{2n}^{o}$ $\displaystyle
n(n-1)=\mathfrak{f}_{2n+1}$
$\displaystyle=-(\mathfrak{d}_{2n+1}^{e}-\mathfrak{d}_{2n+1}^{o}).$

Hence,

$\displaystyle\sum_{n\geq 0}\mathfrak{f}_{2n}\frac{x^{n}}{(2n)!}=\sum_{n\geq
0}(n-1)^{2}\frac{x^{2n}}{(2n)!}=\frac{x^{2}-3x+4}{8}e^{x}+\frac{x^{2}+3x+4}{8}e^{-x},\quad\text{
and }$ $\displaystyle\sum_{n\geq
0}\mathfrak{f}_{2n+1}\frac{x^{2n+1}}{(2n+1)!}=-\sum_{n\geq
0}n(n-1)\frac{x^{n}}{n!}=-\frac{x^{2}-3x+3}{8}e^{x}+\frac{x^{2}+3x+3}{8}e^{-x}$

Thus,

$\displaystyle\sum_{n\geq 0}\mathfrak{f}_{2n}\frac{x^{2n}}{(2n)!}+\sum_{n\geq
0}\mathfrak{f}_{2n+1}\frac{x^{2n+1}}{(2n+1)!}$
$\displaystyle=\frac{e^{x}}{8}+\frac{e^{-x}}{8}(2x^{2}+6x+7)$

is the desired formula. ∎

##  4 Excedance distribution over PADs

In this section, we focus on excedance distribution in PADs.

######  Definition 4.17.

We say that a permutation $\sigma$ has an excedance on $i\in[n]$ if
$\sigma(i)>i$. In this case, $i$ is said to be an excedant.

We give the notation below in the study of this property:

$\displaystyle\mathfrak{d}_{n,k}$
$\displaystyle=|\\{\delta\in\mathfrak{D}_{n}:\,\,\delta\text{ has }k\text{
excedances}\\}|,$ $\displaystyle\mathfrak{d}_{n,k}^{o}$
$\displaystyle=|\\{\delta\in\mathfrak{D}^{o}(n):\,\,\delta\text{ has }k\text{
excedances}\\}|,$ $\displaystyle\mathfrak{d}_{n,k}^{e}$
$\displaystyle=|\\{\delta\in\mathfrak{D}^{e}(n):\,\,\delta\text{ has }k\text{
excedances}\\}|.$

Mantaci and Rakotondrajao ([6]) studied the excedance distribution in
derangements, i.e., the numbers

$\displaystyle d_{n,k}$ $\displaystyle=|\\{\delta\in D_{n}:\,\,\delta\text{
has }k\text{ excedances}\\}|,$ $\displaystyle d^{e}_{n,k}$
$\displaystyle=|\\{\delta\in D_{n}:\,\,\delta\text{ is an even derangemnt and
}\text{ has }k\text{ excedances}\\}|,$ $\displaystyle d^{o}_{n,k}$
$\displaystyle=|\\{\delta\in D_{n}:\,\,\delta\text{ is an odd derangemnt and
}\text{ has }k\text{ excedances}\\}|.$

######  Remark 4.18.

Since the number of excedances in a derangement over $[n]$ is in the range
$[1,n-1]$, the number of excedances of a PAD over $[n]$ is at least 2 and at
most $n-2$.

######  Proposition 4.19.

The numbers $\mathfrak{d}_{n,k}$, $\mathfrak{d}_{n,k}^{e}$, and
$\mathfrak{d}_{n,k}^{o}$ are symmetric, that is

$\displaystyle\mathfrak{d}_{n,k}=\mathfrak{d}_{n,n-k},\,\,\mathfrak{d}^{e}_{n,k}=\mathfrak{d}^{e}_{n,n-k},\text{
and }\,\,\mathfrak{d}^{o}_{n,k}=\mathfrak{d}^{o}_{n,n-k}.$

###### Proof.

The bijection from $\mathfrak{D}_{n}$ to it self, defined as
$\delta\mapsto\delta^{-1}$ for $\delta\in\mathfrak{D}_{n}$, associates a PAD
having $k$ excedances with a PAD having $n-k$ exeedances and also preserves
parity. ∎

|  |  | $\mathfrak{d}_{n,k}$ |  |  |  |
---|---|---|---|---|---|---|---
$n\setminus k$ | 2 | 3 | 4 | 5 | 6 | 7 |
4 | 1 |  |  |  |  |  |
5 | 1 | 1 |  |  |  |  |
6 | 1 | 2 | 1 |  |  |  |
7 | 1 | 8 | 8 | 1 |  |  |
8 | 1 | 14 | 51 | 14 | 1 |  |
9 | 1 | 28 | 169 | 169 | 28 | 1 |
10 | 1 | 42 | 483 | 884 | 483 | 42 | 1
Table 8: First few terms of the number of PADs in terms of number of
excedances

|  |  | $\mathfrak{d}^{e}_{n,k}$ |  |  |  |
---|---|---|---|---|---|---|---
$n\setminus k$ | 2 | 3 | 4 | 5 | 6 | 7 |
4 | 1 |  |  |  |  |  |
5 | 0 | 0 |  |  |  |  |
6 | 1 | 2 | 1 |  |  |  |
7 | 0 | 3 | 3 | 0 |  |  |
8 | 1 | 8 | 27 | 8 | 1 |  |
9 | 0 | 13 | 83 | 83 | 13 | 0 |
10 | 1 | 22 | 243 | 444 | 243 | 22 | 1

|  |  | $\mathfrak{d}^{o}_{n,k}$ |  |  |  |
---|---|---|---|---|---|---|---
$n\setminus k$ | 2 | 3 | 4 | 5 | 6 | 7 |
4 | 0 |  |  |  |  |  |
5 | 1 | 1 |  |  |  |  |
6 | 0 | 0 | 0 |  |  |  |
7 | 1 | 5 | 5 | 1 |  |  |
8 | 0 | 6 | 24 | 6 | 0 |  |
9 | 1 | 15 | 86 | 86 | 15 | 1 |
10 | 0 | 20 | 240 | 440 | 240 | 20 | 0

Table 9: First few values of $\mathfrak{d}_{n,k}$ in terms of their parity

######  Proposition 4.20.

The excedance distribution of a PAD is given by

$\displaystyle\mathfrak{d}_{n,k}=\begin{cases}\sum_{i=1}^{k-1}d_{\lceil\frac{n}{2}\rceil,i}\,d_{\lfloor\frac{n}{2}\rfloor,k-i},\,\,\text{
if }\,2\leq k\leq\lfloor\frac{n}{2}\rfloor\\\
\sum_{i=1}^{n-k-1}d_{\lceil\frac{n}{2}\rceil,i}\,d_{\lfloor\frac{n}{2}\rfloor,n-k+i},\,\,\text{
if }\,\lfloor\frac{n}{2}\rfloor<k\leq n{-}2\end{cases}.$

###### Proof.

To find the number of excedances of a PAD $\delta$ over $[n]$, we sum up the
number of exeedances in $\delta_{1}$ and in $\delta_{2}$, where
$(\delta_{1},\,\delta_{2})$ is the image of $\delta$ defined in $\Phi_{n}$.
Since there are $d_{m,i}$ derangements in $D_{m}$ having $i$ excedances, for
$i\in[1,\,\,m-1]$, the products $d_{m,i}\,d_{l,k-i}$, for
$m=\lceil\frac{n}{2}\rceil$ and $l=\lfloor\frac{n}{2}\rfloor$, determine the
number of PADs over $[n]$ having $k$ excedances. Summing up the products over
the range $i=1,2,\ldots,k{-}1$ will give the first formula. The second formula
follows from Proposition 4.19. ∎

######  Corollary 4.21.

The excedance distribution of PADs in terms of their parity is given by:

$\displaystyle\mathfrak{d}_{n,k}^{e}=\begin{cases}\sum_{i=1}^{k-1}(d^{e}_{\lceil\frac{n}{2}\rceil,i}\,d^{e}_{\lfloor\frac{n}{2}\rfloor,k-i}+d^{o}_{\lceil\frac{n}{2}\rceil,i}\,d^{o}_{\lfloor\frac{n}{2}\rfloor,k-i}),\,\,\text{
if }\,2\leq k\leq\lfloor n/2\rfloor\\\
\sum_{i=1}^{n-k-1}(d^{e}_{\lceil\frac{n}{2}\rceil,i}\,d^{e}_{\lfloor\frac{n}{2}\rfloor,n-k+i}+d^{o}_{\lceil\frac{n}{2}\rceil,i}\,d^{o}_{\lfloor\frac{n}{2}\rfloor,n-k+i}),\,\,\text{
if }\,\lfloor n/2\rfloor<k\leq n{-}2\end{cases},$
$\displaystyle\mathfrak{d}_{n,k}^{o}=\begin{cases}\sum_{i=1}^{k-1}(d^{e}_{\lceil\frac{n}{2}\rceil,i}\,d^{o}_{\lfloor\frac{n}{2}\rfloor,k-i}+d^{o}_{\lceil\frac{n}{2}\rceil,i}\,d^{e}_{\lfloor\frac{n}{2}\rfloor,k-i}),\,\,\text{
if }\,2\leq k\leq\lfloor n/2\rfloor\\\
\sum_{i=1}^{n-k-1}(d^{e}_{\lceil\frac{n}{2}\rceil,i}\,d^{o}_{\lfloor\frac{n}{2}\rfloor,n-k+i}+d^{o}_{\lceil\frac{n}{2}\rceil,i}\,d^{e}_{\lfloor\frac{n}{2}\rfloor,n-k+i}),\,\,\text{
if }\,\lfloor n/2\rfloor<k\leq n{-}2\end{cases}.$

$\square$

An immediate consequence of this Corollary is

######  Proposition 4.22.

We have

$\displaystyle\mathfrak{f}_{n,k}=\mathfrak{d}_{n,k}^{e}-\mathfrak{d}_{n,k}^{o}=(-1)^{n}\,\max\\{k-1,\,n{-}(k+1)\\}$

for $n\geq 4$ and $2\leq k\leq n{-}2$.

###### Proof.

Mantaci and Rakotondrajao (see [6]) have proved the identity
$d^{o}_{n,k}-d^{e}_{n,k}=(-1)^{n}$ using recursive argument. Applying this
with the Corollary 4.21, we get the desired formula. ∎

|  |  | $\mathfrak{f}_{n,k}$ |  |  |  |
---|---|---|---|---|---|---|---
$n\setminus k$ | 2 | 3 | 4 | 5 | 6 | 7 |
4 | 1 |  |  |  |  |  |
5 | -1 | -1 |  |  |  |  |
6 | 1 | 2 | 1 |  |  |  |
7 | -1 | -2 | -2 | -1 |  |  |
8 | 1 | 2 | 3 | 2 | 1 |  |
9 | -1 | -2 | -3 | -3 | -2 | -1 |
10 | 1 | 2 | 3 | 4 | 3 | 2 | 1
Table 10: The first few values of the difference
$\mathfrak{d}^{e}_{n,k}-\mathfrak{d}^{o}_{n,k}$.

######  Theorem 4.23.

The exponential generating function for the sequence
$\\{\mathfrak{f}_{n,k}\\}$ has the closed form

$\displaystyle\frac{1}{(1-u)^{2}}\left(u^{2}e^{-x}+e^{-ux}-2u\cosh{\sqrt{u}x}+\frac{u+u^{2}}{\sqrt{u}}\sinh{\sqrt{u}x}-(1-u)^{2}\right).$

###### Proof.

Let $\mathfrak{f}_{n}(u)=\sum_{k=2}^{n-2}\mathfrak{f}_{n,k}u^{k}$ and
$\mathfrak{f}(x,u)=\sum_{n\geq 4}\mathfrak{f}_{n}(u)\frac{x^{n}}{n!}$. From
Proposition 4.22, we have

$\displaystyle\mathfrak{f}_{2m,k}$
$\displaystyle=\begin{cases}k-1,\quad\text{if }2\leq k\leq m\\\
2m-k-1,\quad\text{if }m<k\leq 2m{-}2\end{cases},$
$\displaystyle\mathfrak{f}_{2m+1,k}$
$\displaystyle=\begin{cases}-(k-1),\quad\text{if }2\leq k\leq m\\\
-(2m-k),\quad\text{if }m<k\leq 2m{-}1\end{cases},$

for $m\geq 2$. So,

$\displaystyle\mathfrak{f}_{2m}(u)$
$\displaystyle=\sum_{k=2}^{m}(k-1)u^{k}+\sum_{k=m+1}^{2m-2}(2m-k-1)u^{k}=\frac{u^{2}-2u^{m+1}+u^{2m}}{(1-u)^{2}},$
$\displaystyle\mathfrak{f}_{2m+1}(u)$
$\displaystyle=\sum_{k=2}^{m}-(k-1)u^{k}+\sum_{k=m+1}^{2m-1}-(2m-k)u^{k}=\frac{u^{m+2}+u^{m+1}-u^{2}-u^{2m+1}}{(1-u)^{2}},$
$\displaystyle\mathfrak{f}(x,u)$ $\displaystyle=\sum_{m\geq
2}\mathfrak{f}_{2m}(u)\frac{x^{2m}}{(2m)!}+\sum_{m\geq
2}\mathfrak{f}_{2m+1}(u)\frac{x^{2m+1}}{(2m+1)!}$
$\displaystyle=\frac{1}{(1-u)^{2}}\left(u^{2}e^{-x}+e^{-ux}-2u\cosh{\sqrt{u}x}+\frac{u+u^{2}}{\sqrt{u}}\sinh{\sqrt{u}x}-(1-u)^{2}\right).$

∎

## Methodological remarks

In this paper, most of our results are obtained in a way of splitting the
permutations into two subwords. However, this method is not always applicable.
One example is the number of PADs avoiding the pattern $p=1\,2$. The only
derangement that avoid $p$ is
$(1\,\,n\,)(2\,\,\,n{-}1\,)\cdots(\frac{n}{2}\,\,\,\frac{n+2}{2})$, for even
$n$, that is, the derangement over $[n]$ with entries in decreasing order when
written in linear representation. However, it does not exist if $n$ is odd,
since $\frac{n+1}{2}$ is a fixed point. The PAD $\delta$ created from a pair
$(\delta_{1},\delta_{2})$, by the mapping $\Phi_{n}^{-1}$, of two even length
derangements that both avoids the pattern $p$ is
$\delta=(1\,\,n{-}1\,)(3\,\,\,n{-}3\,)\cdots\big{(}\frac{n-2}{2}\,\,\,\frac{n+2}{2}\big{)}(2\,\,n\,)(4\,\,\,n{-}2\,)\cdots\big{(}\frac{n}{2}\,\,\,\frac{n+4}{2}\big{)}$,
which is $n{-}1\,\,n\,\,n{-}3\,\,n{-}2\cdots 3\,\,4\,\,1\,\,2$ in linear form,
has length $n\equiv 0\pmod{4}$. However, each pair $i\,\,i{+}1$, where $i$ is
an entry in odd position, is a subword with the occurrence of the pattern $p$
in $\delta$. This indicates that $\delta_{1}$ and $\delta_{2}$ avoid $p$ but
$\delta$ doesn’t. Things get even more complicated with patterns of length
greater than 2.

Final Remarks: As for now, we have not been successful in finding the
recurrence relations and generating functions for the sequences
$\\{\mathfrak{d}_{n,k}\\}_{n=0}^{\infty}$,
$\\{\mathfrak{d}_{n,k}^{e}\\}_{n=0}^{\infty}$, and
$\\{\mathfrak{d}_{n,k}^{o}\\}_{n=0}^{\infty}$.

## Acknowledgements

The first author acknowledges the financial support extended by the
cooperation agreement between International Science Program at Uppsala
University and Addis Ababa University. Special thanks go to Prof. Jörgen
Backelin, Prof. Paul Vaderlind and Dr. Per Alexandersson of Stockholm
University - Dept. of Mathematics, for all their valuable inputs and
suggestions. Many thanks to our colleagues from CoRS - Combinatorial Research
Studio, for lively discussions and comments.

## References

  * [1] Paul Barry.  On a central transform of integer sequences.  arXiv preprint arXiv:2004.04577, 2020.
  * [2] Paul Barry.  Private communication to the first author, $14^{th}$, December 2020.
  * [3] Arthur T Benjamin, Curtis T Bennett, and Florence Newberger.  Recounting the odds of an even derangement.  Mathematics Magazine, 78(5):387–390, 2005.
  * [4] Miklós Bóna.  Combinatorics of permutations.  CRC Press, 2012.
  * [5] Robin Chapman.  An involution on derangements.  Discrete Mathematics, 231(1):121–122, 2001.
  * [6] Roberto Mantaci and Fanja Rakotondrajao.  Exceedingly deranging!  Advances in Applied Mathematics, 30(1-2):177–188, 2003\.
  * [7] Fanja Rakotondrajao.  k-fixed-points-permutations.  Integer: Electronic Jornal of Combinatorial Number Theory, 7(A36):A36, 2007.
  * [8] Richard P Stanley.  Enumerative combinatorics volume 1 second edition.  Cambridge studies in advanced mathematics, 2011.
  * [9] Shinji Tanimoto.  Combinatorics of the group of parity alternating permutations.  Advances in Applied Mathematics, 44(3):225–230, 2010.
  * [10] Shinji Tanimoto.  Parity alternating permutations and signed eulerian numbers.  Annals of Combinatorics, 14(3):355–366, 2010.