LAPTH-039/22

# Ultra-high energy neutrinos from high-redshift electromagnetic cascades

AmirFarzan Esmaeili<EMAIL_ADDRESS>Departamento de Física,
Pontifícia Universidade Católica do Rio de Janeiro, Rio de Janeiro 22452-970,
Brazil  Antonio Capanema<EMAIL_ADDRESS>Departamento de
Física, Pontifícia Universidade Católica do Rio de Janeiro, Rio de Janeiro
22452-970, Brazil  Arman Esmaili<EMAIL_ADDRESS>Departamento de Física,
Pontifícia Universidade Católica do Rio de Janeiro, Rio de Janeiro 22452-970,
Brazil  LAPTh, CNRS, USMB, F-74940 Annecy, France  Pasquale Dario Serpico
<EMAIL_ADDRESS>LAPTh, CNRS, USMB, F-74940 Annecy, France

###### Abstract

We study the impact of the muon pair production and double pair production
processes induced by ultra-high energy photons on the cosmic microwave
background. Although the muon pair production cross section is smaller than
the electron pair production one, the associated energy loss length is
comparable or shorter than the latter (followed by inverse Compton in the deep
Klein-Nishina regime) at high-redshift, where the effect of the astrophysical
radio background is expected to be negligible. By performing a simulation
taking into account the details of $e/\gamma$ interactions at high energies,
we show that a significant fraction of the electromagnetic energy injected at
$E\gtrsim 10^{19}\,$eV at redshift $z\gtrsim 5$ is channeled into neutrinos.
The double pair production plays a crucial role in enhancing the multiplicity
of muon production in these electromagnetic cascades. The ultra-high energy
neutrino spectrum, yet to be detected, can in principle harbour information on
ultra-high energy sources in the young universe, either conventional or exotic
ones, with weaker constraints from the diffuse gamma ray flux compared to
their low redshift counterparts.

##  I Introduction

The high-redshift and high-energy universe remains largely mysterious. The
hadronic component of ultra-high energy cosmic rays (UHECRs) suffers
significant energy losses, besides lacking directionality due to deflections
in extragalactic magnetic fields. Photons and electrons undergo fast
interactions with the cosmic microwave background (CMB), quickly degrading
their energy, eventually contributing only to the diffuse extragalactic
background below the TeV. Even gravitational wave signals at high-redshift
will have to wait next generation detectors in order to be properly explored
Kalogera  _et al._ (2019), and linking them to high-energy counterparts in
other messengers is far from evident. Neutrinos are thus the most promising
messengers, especially after the detection of astrophysical neutrinos by
IceCube Aartsen  _et al._ (2013); Schneider (2019); Stettner (2019); Aartsen
_et al._ (2020), currently up to $\sim{\cal O}(10)$ PeV Aartsen  _et al._
(2021), paving the way to explore the remote and violent universe through
these elusive particles. The near future improvements in the sensitivity of
neutrino telescopes will further promote this exploration, notably searching
for ultra-high-energy $\nu$’s ($E\gtrsim 10^{17}$ eV): Their presence is
guaranteed at least from interactions of UHECRs with the CMB (so-called
cosmogenic neutrinos Berezinsky and Zatsepin (1969)), but could also originate
from yet unknown astrophysical or exotic processes Abbasi  _et al._ (2021);
Fang  _et al._ (2017); Batista  _et al._ (2019).

Of particular interest for diagnostics is the interplay between these
messengers, especially between the photons and neutrinos. Gamma rays have long
been used to constrain ultra-high energy (UHE) neutrinos, see for instance
Waxman and Bahcall (1998); Mannheim  _et al._ (2000); Kalashev  _et al._
(2002). In the following, we revisit the link between these particles at
high-$E$ and high-$z$, since differing in some peculiar aspects from the
standard expectations. In particular, we will argue that electromagnetic
cascades drain some significant energy into the neutrino channel, altering the
usual expectation for the ratio of energy into neutrinos vs gamma-rays,
besides obviously modifying the expected spectra of UHE neutrinos. The fact
that the propagation of UHE photons/electrons may be quantitatively different
at high-$z$ was studied in Kusenko and Postma (2001); Postma (2001), where the
key process responsible for the drainage into the neutrino channel was thought
to be $e\gamma\to e\mu\mu$. Soon after, this process was reassessed and found
of negligible importance in Athar  _et al._ (2001). The same article also
suggested that the $\gamma\gamma\to\mu\mu$ process may however play a similar
role 111An early mention of this process can also be found in Berezinsky
(1970).. This process has been studied within some approximations in Wang  _et
al._ (2017), where it was concluded that at low redshift $0\leq z<5$, and due
to the interplay with the diffuse universal radiation background (URB)
222Furthermore, the $e^{\pm}$ in the cascade could also quickly lose energy
via synchrotron emission in intergalactic magnetic fields, if these are close
to the current upper limits at the nG level., only a relatively small fraction
of the initial energy of electromagnetic cascades ($\lesssim 10\%$) channels
into neutrinos. Similar considerations were also briefly exposed in Li and
Waxman (2007). Here we complement these studies by expanding the redshift
range and particularly improving on the microphysics of the cascade
development at high energies, leading us to somewhat different conclusions.

The basic idea is that muon pair production (MPP) is non-negligible in the
interaction of UHE photons with CMB, where the subsequent decay of muons
generates neutrinos. The MPP introduces an important deviation from the course
of well-studied electromagnetic cascade of high energy photons/electrons,
where it is the chain of electron pair production (EPP) and inverse-Compton
scattering (ICS) which leads to the degradation of initial photon/electron
energy and the production of a lower-energy photon spectrum. The large
inelasticity in both EPP and ICS renders the MPP feasible since effectively
the energy loss length in electromagnetic cascade is larger than the
interaction length of MPP. The picture is further altered by the role of the
double pair production (DPP), which constitutes an important energy-loss
channel and is responsible for lowering the drainage of energy via MPP, while
at the same time increasing the muon multiplicity in the cascade.

In section II we introduce the microphysics ingredients used to describe the
aforementioned processes, and justify qualitatively the importance of MPP. A
Monte Carlo simulation of processes and the corresponding distributions of
energy drainage and neutrino spectrum are given in section III. Section IV is
devoted to the discussions and conclusions, summarizing the take-home message
and commenting on possible applications. For the ease of reference, well-known
analytical formulae of neutrino spectra emitted in muon decay are reported in
Appendix A.

##  II Photon and electron interactions

The propagation of UHE photons and electrons in intergalactic space is
hindered by the interaction with background photon fields ($\gamma_{\rm b}$)
that permeate the Universe. Starting with an UHE photon, the main relevant
interactions are EPP ($\gamma\gamma_{\rm b}\to e^{+}e^{-}$) and ICS
($e\gamma_{\rm b}\to e\gamma$) where their successive iteration develops the
conventional “electromagnetic cascade”. At variance with low-$E$ and low-$z$
cascades, MPP ($\gamma\gamma_{\rm b}\rightarrow\mu^{-}\mu^{+}$) and DPP
($\gamma\gamma_{\rm b}\rightarrow e^{+}e^{-}e^{+}e^{-}$) are also of interest
for our analysis and will significantly contribute to the cascade development.
At low-$z$, UHE photons are dominantly interacting with the URB and electrons
are possibly affected by syncrhotron emission on extragalactic magnetic
fields, if close to the allowed upper limits of nG strength Lee (1998).
However, the URB is expected to drop at $z\gtrsim 2$, and by $z\sim 5$ it
should be vanishingly small compared to the CMB Lee (1998); Kusenko and Postma
(2001); Postma (2001). While the exact redshift at which the URB can be
neglected is poorly known, it is robust to assume that such a redshift exists,
since the URB is of astrophysical origin and, while the CMB density of photons
grows with $z$ as $(1+z)^{3}$, the density of astrophysical sources drops at
$z>2$ and should eventually be vanishing at $z\gtrsim 15$. Based on models in
the literature, we estimate that $z=5$ is a rather conservative assumption,
hence we will show results considering interactions solely with the CMB only
above this redshift.

The total and differential cross sections of EPP (also dubbed Breit-Wheeler
process Breit and Wheeler (1934)) are respectively Akhiezer and Berestetskii
(1965)

$\sigma_{\rm EPP}=\sigma_{\rm
T}\,\frac{3}{16}(1-\beta^{2})\bigg{[}(3-\beta^{4})\ln\frac{1+\beta}{1-\beta}\\\
-2\beta(2-\beta^{2})\bigg{]}~{},$ (1)

and

$\frac{{\rm d}\sigma_{\rm EPP}}{{\rm d}E_{e}}=\sigma_{\rm
T}\,\frac{3}{4}\,\frac{m_{e}^{2}}{s}\,\frac{1}{E_{\gamma}}\left[\frac{E_{e}}{E_{\gamma}-E_{e}}+\frac{E_{\gamma}-E_{e}}{E_{e}}\right.\\\
+E_{\gamma}\left(1-\beta^{2}\right)\left(\frac{1}{E_{e}}+\frac{1}{E_{\gamma}-E_{e}}\right)\\\
\left.-\frac{E_{\gamma}^{2}\left(1-\beta^{2}\right)^{2}}{4}\left(\frac{1}{E_{e}}+\frac{1}{E_{\gamma}-E_{e}}\right)^{2}\right]~{},$
(2)

where $m_{e}$ is the electron mass, $\sigma_{T}=8\pi\alpha^{2}/(3m_{e}^{2})$
is the Thomson cross section (in the whole paper, natural units are used),
$\alpha$ the fine structure constant, $\beta=\sqrt{1-4m_{e}^{2}/s}$ is the
velocity of outgoing electron in the CM frame, $s=2E_{\gamma}\epsilon(1-\mu)$
is the squared CM energy, $\epsilon$ and $E_{\gamma}$ are respectively the
energies of the target (here CMB photon) and high energy photons, $\mu$ is the
cosine of the angle between the momenta of the incoming photons, and $E_{e}$
is the energy of the produced electron (or positron) whose allowed range is
$(1-\beta)/2\leq E_{e}/E_{\gamma}\leq(1+\beta)/2$.

The ICS total and differential cross sections are given by Aharonian and
Atoyan (1981)

$\sigma_{\rm ICS}=\sigma_{\rm
T}\,\frac{3}{8}\,\frac{m_{e}^{2}}{\tilde{s}\tilde{\beta}}\left[\frac{2}{\tilde{\beta}(1+\tilde{\beta})}(2+2\tilde{\beta}-\tilde{\beta}^{2}-2\tilde{\beta}^{3})\right.\\\
\left.-\frac{1}{\tilde{\beta}^{2}}(2-3\tilde{\beta}^{2}-\tilde{\beta}^{3})\ln\frac{1+\tilde{\beta}}{1-\tilde{\beta}}\right]~{},$
(3)

and

$\frac{{\rm d}\sigma_{\rm ICS}}{{\rm d}E_{e}^{\prime}}=\sigma_{\rm
T}\,\frac{3}{8}\,\frac{m_{e}^{2}}{\tilde{s}}\,\frac{1}{E_{e}}\,\frac{1+\tilde{\beta}}{\tilde{\beta}}\left[\frac{E^{\prime}_{e}}{E_{e}}+\frac{E_{e}}{E^{\prime}_{e}}\right.\\\
\left.+\frac{2(1-\tilde{\beta})}{\tilde{\beta}}\left(1-\frac{E_{e}}{E^{\prime}_{e}}\right)+\frac{1-\tilde{\beta}^{2}}{\tilde{\beta}^{2}}\left(1-\frac{E_{e}}{E^{\prime}_{e}}\right)^{2}\right]~{},$
(4)

where $\tilde{\beta}=(\tilde{s}-m_{e}^{2})/(\tilde{s}+m_{e}^{2})$ is the
velocity of the outgoing electron in the CM frame,
$\tilde{s}=m_{e}^{2}+2\epsilon(E_{e}-\mu\sqrt{E_{e}^{2}-m_{e}^{2}})$ is the
squared CM energy, $E_{e}$ is the energy of the initial high-energy electron,
and $E^{\prime}_{e}$ is the energy of the outgoing electron, whose allowed
range is $(1-\tilde{\beta})/(1+\tilde{\beta})\leq E^{\prime}_{e}/E_{e}\leq 1$.

The threshold energy for EPP derives from the condition $s=4m_{e}^{2}$. For
$s\geq 4m_{\mu}^{2}$ ($m_{\mu}$ being the muon mass), MPP ($\gamma\gamma_{\rm
b}\rightarrow\mu^{-}\mu^{+}$) also becomes accessible. The MPP’s total cross
section, $\sigma_{\rm MPP}$, and differential cross section, ${\rm
d}\sigma_{\rm MPP}/{\rm d}E_{\mu}$, can be obtained by replacing $m_{e}\to
m_{\mu}$ in the formulae for EPP. For the MPP on the bulk of the CMB at
redshift $z$, the threshold energy is $E_{\rm MPP}^{\rm
thr}=m_{\mu}^{2}/\langle\epsilon\rangle\simeq 1.8\times 10^{19}/(1+z)$ eV, for
the benchmark value $\langle\epsilon\rangle\simeq 2.7(1+z)T_{0}$, where
$T_{0}=2.35\times 10^{-4}$ eV is the current CMB temperature.

At high energies the DPP becomes relevant. While a fully analytic expression
for $\sigma_{\rm DPP}$ is quite involved, it rapidly converges to the constant
value $\sigma_{\rm DPP}^{\infty}\simeq 6.45\times 10^{-30}~{}{\rm cm}^{2}$
above its threshold at $s=16m_{e}^{2}$, and its energy dependence can be
closely approximated by $\sigma_{\rm
DPP}\approx(1-4m_{e}^{2}/E_{\gamma}\epsilon)^{6}\sigma_{\rm DPP}^{\infty}$
Brown  _et al._ (1973). We will not employ the full expression for the DPP
differential cross section, but simply approximate the process in assuming
that one of the pairs carries the quasi-totality of the projectile photon
energy, sharing it equally. This captures the main quantitative effect of DPP
on the cascade development Demidov and Kalashev (2009).

Although MPP is suppressed with respect to EPP (for example, at
$s=10^{18}~{}\rm eV^{2}$, $\sigma_{\rm MPP}/\sigma_{\rm EPP}\approx 0.26$),
muon production is definitely relevant since EPP and ICS have large
inelasticities at high energies. The inelasticity of a given process, i.e. the
average fraction of energy transferred from the initial leading particle to
the produced leading particle, is given by

$\eta(s)=\frac{1}{\sigma(s)}\int{\rm
d}E^{\prime}\,\frac{E^{\prime}}{E_{0}}\,\frac{{\rm d}\sigma}{{\rm
d}E^{\prime}}(E^{\prime},s)~{},$ (5)

where $E^{\prime}$ is the energy of the produced leading particle and $E_{0}$
is the energy of the initial leading particle. Due to the large inelasticities
in EPP and ICS, the initial UHE photon (or electron) undergoes a sequence of
EPP+ICS, at each step of which the leading particle emerges with an energy
close to the initial one. If MPP happens, this sequence is greatly altered
since the final-state $e^{\pm}$ from muon decay carry a comparatively small
fraction of the parent photon energy. For the DPP, we assume that each one of
the leptons in a pair $e^{+}e^{-}$ carries half of the initial photon energy,
which is very close to the actual (and much more involved) calculation Demidov
and Kalashev (2009).

To quantify the relative prominence of these processes, let us define the
interaction length (or mean free path)

$\lambda_{p}(E)=\frac{1}{\int{\rm d}\epsilon\int{\rm d}\mu\,P(\mu)\,n_{\rm
CMB}(\epsilon)\,\sigma_{p}(s)}~{},$ (6)

where $p=$ EPP, MPP or DPP, $n_{\rm CMB}$ is the number density of CMB photons
per unit energy, $s=s(E,\epsilon,\mu)$, $P(\mu)=(1-\mu)/2$ is the distribution
of collision angles (or flux factor), and the integral over $\mu$ extends up
to $1-2m^{2}/E_{\gamma}\epsilon$, with $m$ being either $m_{e}$ or $m_{\mu}$.
Similarly, one can define the energy loss length 333A more correct definition
in terms of stopping power ${\rm d}E/{\rm d}x$ would be $\Lambda=\int{\rm
d}x\,E/(-{\rm d}E/{\rm d}x)$, but for moderate energy dependence of the
integrand it leads to comparable results. We content ourselves with the
simplest definition of eq. (7), given the mere illustrative purpose of this
quantity in this section.

$\Lambda_{p}(E)=\frac{1}{\int{\rm d}\epsilon\int{\rm d}\mu\,P(\mu)\,n_{\rm
CMB}(\epsilon)\,\sigma_{p}(s)\,[1-\eta_{p}(s)]}~{}.$ (7)

For a catastrophic event like MPP, $\Lambda\simeq\lambda$, but whenever only a
small fraction of energy is lost at each interaction, as it is for the leading
particle in EPP/ICS cycles, $\Lambda\gg\lambda$.

Figure 1 compares $\Lambda_{\rm EPP}$ (blue color), $\lambda_{\rm
MPP}\simeq\Lambda_{\rm MPP}$ (green color) and $\lambda_{\rm DPP}$ (black
color) as functions of the UHE photon’s energy at the observation point. The
vertical and horizontal axes are scaled by $(1+z)^{3}$ and $(1+z)$,
respectively, thus the curves are valid for any redshift 444Since the
differential density $n_{\rm CMB}(\epsilon)$ scales as $(1+z)^{2}$, lengths
get contracted by $(1+z)$ and energies increase by $(1+z)$ with $z$, this
implies that $\lambda(E,z)=(1+z)^{-3}\,\lambda_{0}[E(1+z)]$. Ditto for
$\Lambda$.. Remarkably, $\lambda_{\rm MPP}<\Lambda_{\rm EPP}$ at high energies
indicates that we expect MPP to happen before the photons/electrons have lost
a significant fraction of their initial energy via the EPP/ICS cycle. On the
other hand, since $\lambda_{\rm DPP}\lesssim\Lambda_{\rm EPP}$ at high
energies, DPP affects the cascade development; similarly, $\lambda_{\rm
DPP}<\lambda_{\rm MPP}$ signals the relevance of DPP inclusion in the study of
MPP. Qualitatively, starting from a very high energy photon, we expect the
role of DPP is to split the initial photon energy into a pair $e^{\pm}$ almost
equally. This is followed by ICS events, where the upscattered photons
initiate a new multiplicative process via DPP and so on, until the photon
energies end-up close to the minimum of the MPP interaction length, around
$E_{\gamma}(1+z)\simeq 10^{20}{\rm eV}$. At that point, the particles are only
a factor $2-3$ less likely to undergo muon generation via MPP than to degrade
below MPP threshold via a final DPP event, or to start a “conventional”
cascade via EPP; this explains why MPP matters. Since in a MPP event about 65%
of the energy is carried by the neutrinos (see Appendix A), a rough
expectation is that, away from threshold effects, on average slightly below
$65\%/2\sim 30\%$ of $E_{\gamma}$ is drained into the neutrino flux. We also
expect that the higher the energy, the larger is the multiplicity of muons
through which the drainage is happening, with this number scaling
proportionally to $E_{\gamma}(1+z)/10^{20}{\rm eV}$. Finally, we can
anticipate that a significant spread around the average should be present due
to the stochastic nature of these events.

Also note that, as shown in Fig. 1, these interaction lengths are well below
the Hubble length 555$H(z)\simeq
H_{0}\sqrt{\Omega_{\Lambda}+\Omega_{M}(1+z)^{3}}$ being the Hubble expansion
rate, $H_{0}\simeq 70~{}$km/s/Mpc its current value, and $\Omega_{M}\simeq
0.3$ the matter density of the universe in terms of the critical one. Instead,
$\Omega_{\Lambda}\simeq 1-\Omega_{M}$ is the dimensionless energy density of
the cosmological constant, playing a negligible role at redshifts of interest
here.  $H(z)^{-1}$. Hence, particle dynamics rather than cosmology rules the
evolution in $E$-space, with the cascade development that can be considered
almost instantaneous in $z$.

Figure 1: Comparison between $\Lambda_{\rm EPP}$ (blue), $\lambda_{\rm
MPP}\simeq\Lambda_{\rm MPP}$ (green), $\lambda_{\rm DPP}$ (black) and Hubble
$1/H(z)$ (red) lengths rescaled by $(1+z)^{3}$ vs. energy of the UHE photon,
rescaled by $(1+z)$. The Hubble lengths are displayed for redshifts $z=5$
(solid red line) and $z=15$ (dashed red line).

These qualitative arguments motivate a more quantitative study of the effect
of this process, which we embark on in the next section. Before moving to
that, let us mention our rationale for ignoring some additional processes (a
synoptic description of which can be found in Lee (1998)). Charged pion
production ($\gamma\gamma_{\rm b}\rightarrow\pi^{+}\pi^{-}$) becomes possible
at $s\geq 4m_{\pi^{\pm}}^{2}$, but its cross section is only comparable to EPP
and MPP in a small window of energies (corresponding to the $f_{2}(1270)$
resonance) Boyer  _et al._ (1990); Morgan and Pennington (1987) and is
otherwise sub-leading. Including this process would only mildly strengthen the
conclusions of this article. The production of neutral pions, kaons and
heavier hadrons in $\gamma\gamma_{\rm b}$ scattering is even more suppressed
Whalley (2001); Morgan  _et al._ (1994), justifying that we neglect them.
Triplet pair production ($e\gamma_{\rm b}\rightarrow ee^{+}e^{-}$), has a
cross section comparable to that of ICS already at $\sim 10^{17}$ eV, but
leads to a negligible energy loss below $\sim 10^{22}$ eV since the energy
fraction carried by the produced pair is very small ($\sim 10^{-3}$) Lemoine
and Sigl (2001) and its inclusion is expected to change our conclusions at the
few percent level at most. Finally, we also neglect the synchrotron energy
losses of UHE electrons onto extragalactic magnetic fields. While these may be
of importance at low redshift, see Wang  _et al._ (2017), unless the fields
are of primordial origin, their role with respect to losses on CMB should
vanish going to high-$z$, with an argument qualitatively similar to what we
discussed for the URB. Note that, despite limited information on extragalactic
magnetogenesis, current evidence suggests indeed that extragalactic fields
grow at low-$z$ via an astrophysical dynamo mechanism, rather than being
primordial Pomakov  _et al._ (2022) (or implying much smaller primordial
seeds), consistent with the hypothesis done here.

##  III Simulation and results

To quantitatively assess the role of MPP at high energies, we proceed with a
Monte Carlo simulation. This is unavoidable if one is to take into account the
discrete and stochastic nature of the processes. As previously discussed, it
turns out that the mean free path between interactions is so short compared to
the cosmological scales that the change in the redshift of two successive
processes can be safely ignored. Thus, starting with a photon 666Starting with
an electron would not lead to appreciable differences. with specified energy
$E_{\gamma}$ and redshift $z$, only the evolution in $E-$space is relevant,
described as a sequence of interactions where the leading electromagnetically
interacting particle’s energy degrades, until the MPP process is no longer
kinematically open. At each photon interaction, we compare a random number in
[0,1] with the probability to yield a MPP

$p_{\rm MPP}=\frac{\lambda_{\rm MPP}^{-1}}{\lambda_{\rm EPP}^{-1}+\lambda_{\rm
MPP}^{-1}+\lambda_{\rm DPP}^{-1}}\,.$ (8)

As an example, at $z=15$ we estimate $p_{\rm MPP}\approx(0.07,0.07,0.02)$
respectively for $E_{\gamma}=(10^{19},10^{20},10^{21})$ eV. The probability of
DPP can be defined similarly to Eq. (8) by replacing $\lambda_{\rm MPP}^{-1}$
with $\lambda_{\rm DPP}^{-1}$ in the numerator, leading to $p_{\rm
DPP}\approx(0.18,0.62,0.93)$ for the same $E_{\gamma}$’s and $z$. Obviously,
for EPP we have $p_{\rm EPP}=1-p_{\rm DPP}-p_{\rm MPP}$. The cascade
development depends on the selected interaction at each step. When MPP is
chosen, the $e^{\pm}$ from the $\mu^{\pm}$ decay are injected again into the
simulation by performing ICS on CMB and creating an UHE photon which starts a
new branch of cascade. If DPP is chosen, an $e^{+}e^{-}$ pair will be followed
(the other pair carrying negligible energy); each member of the pair, assumed
to carry energy $E_{\gamma}/2$, initiates a new branch after a single ICS
event. Finally, the EPP case will be followed by ICS. The photon energy coming
from ICS events, or the $e^{+}/e^{-}$ ones from EPP events are sampled from
the corresponding differential cross sections reported in the previous
section.

(a)

(b)

(c)

Figure 2:  The fraction of energy channeling into neutrinos in the simulation
of $10^{4}$ photons with energies $E_{\gamma}=10^{19}$ eV, $10^{20}$ eV and
$10^{21}$ eV, respectively in panels (a), (b) and (c). The left, middle and
right panels are respectively for injection at $z=5$, 10 and 15.

The quantities of main interest for phenomenology are the fraction of the
initial photon energy channeled into neutrinos, $f_{\nu}$, and the neutrino
spectra resulting from this process. Figure 2 shows the distribution of
$f_{\nu}$ for $10^{4}$ injected photons with energy $E_{\gamma}=10^{19}$ eV,
$10^{20}$ eV and $10^{21}$ eV in panels (a), (b) and (c), respectively, from
top to bottom; the panels in the leftmost column report results at $z=5$, in
the middle one at $z=10$ and in the rightmost column at $z=15$. The plots show
that at 10${}^{19}\,$eV and $z=5$ only about 12% of the photons experience
MPP. This fraction grows to about 25% at $z=10$ and 35% at $z=15$. At
10${}^{20}\,$eV, well above 70% of photons experience MPP at $z\geq 5$, with
this fraction exceeding 94% at $z=15$. Eventually, for
$E_{\gamma}=10^{21}\,$eV, basically every cascade involves one or more MPP
events. This behaviour makes sense once realising that, at lower energy,
threshold effects reducing the importance of MPP are important. At the highest
energy, as discussed, the multiplicity of energetic $e^{\pm}$ due to DPP makes
the probability that none of them initiate a MPP vanishingly small. Note how
the distributions of $f_{\nu}$ are broad (and skewed), reflecting the
stochastic nature of the processes.

The mean value of $f_{\nu}$ is a strongly dependent function of energy near
the threshold, while being almost constant with energy at high-$E$, as
reported in Figure 3, for the initial photon energies $E_{\gamma}=10^{19}$ eV
(green), $10^{20}$ eV (red), and $10^{21}$ eV (blue). The bar around each
curve shows the standard deviation, calculated from the distributions in
Figure 2. It mildly shrinks with $E_{\gamma}$, since high multiplicities make
the process “more deterministic”.

Figure 4 illustrates the point that, especially at high-$E_{\gamma}$ and
high-$z$, the multiplicity of muons via MPP events is considerable, for the
reasons described in the previous section. For instance, at
$E_{\gamma}=10^{21}$ eV, on average $\sim 6,11$ and 15 MPPs will be realized
for injection at $z=5,10$ and 15, respectively. Even if the MPP process
typically intervenes only when the particles have degraded to energies
significantly lower than the injected ones, its multiplicity makes its impact
on the energy budget not negligible. Note that in the early study Li and
Waxman (2007) this aspect was completely missed “by construction”, since no
follow-up of the leptons produced via DPP was performed. Their estimate of
only $\sim$ few percent of the electromagnetic energy drainage into neutrinos
is thus not only due to the different conditions relevant at low-$z$, but also
to the fact that they did not include this important effect.

Figure 3: The mean fraction of the initial photon’s energy ending up in
neutrinos, $f_{\nu}$, for three different energies of the initial photon. The
bars show the standard deviation around the mean value depicted by solid
curves.

(a)

(b)

(c)

Figure 4:  The distribution of the number of MPP occurrence, for the energies
and redshifts as in Figure 2.

The average all-flavor neutrino spectrum at the Earth from a photon injected
at $z=10$ with energy $E_{\gamma}=10^{20}$ eV is depicted in Figure 5 by the
blue solid curve. This is based on the well-known analytical descriptions of
neutrino spectra from muon decay (see the formulae in Lipari (1993), also
summarised in Appendix A) which have been averaged over the $10^{4}$ injected
photons in our simulation. The wiggles at the peak come from multiple MPPs
which for the case of Figure 5 can be up to five MPPs, with $\sim 46\%$ of
cases leading to two or three MPPs. In a conventional scenario, UHE photons
are the product of decays of $\pi^{0}$’s, that are unavoidably accompanied by
$\pi^{\pm}$’s, whose decays produce neutrinos. In Figure 5 we also show, by
the black dotted curve, the neutrino spectrum from the decay chain
$\pi^{\pm}\to\mu^{\pm}\nu_{\mu}(\bar{\nu}_{\mu})\to
e^{\pm}\nu_{\mu}\bar{\nu}_{\mu}\nu_{e}(\bar{\nu}_{e})$ (see the formulae in
Appendix A) with the energy of $\pi^{\pm}$ equal to $2\times 10^{20}$ eV. The
little discontinuity in the dotted curve comes from the contribution of the
neutrino emitted directly from the pion decay
$\pi^{\pm}\to\mu^{\pm}\nu_{\mu}(\bar{\nu}_{\mu})$. Note how the neutrinos from
MPP emerge over those from $\pi^{\pm}$ in the low-energy part of the
distribution, where they dominate the flux by one order of magnitude.

At higher $E_{\gamma}$ and $z$, where the number of MPPs grows, yet more
pronounced features are expected in the neutrino spectrum, as can be seen in
Figure 6 which shows the case of $E_{\gamma}=10^{21}$ eV injected at $z=15$.
The same features of Figure 5 are now present in a more exacerbated form. This
clearly illustrates the relevance of the MPP process in shaping the UHE
neutrino spectra from high-$z$/high-$E$ sources.

Figure 5: Neutrino spectrum at the Earth from MPP (solid blue curve, this
work) and charged pions decay chain (dotted black curve), from a source at
redshift $z=10$ injecting photons at $E_{\gamma}=10^{20}$ eV. The solid red
curve is their sum. Figure 6: As Fig. 5, for a source at redshift $z=15$
injecting photons at $E_{\gamma}=10^{21}$ eV

Another implication worth commenting upon is that the process discussed here
alters the multimessenger $\gamma$-$\nu$ correlation. Conventional production
scenarios arising from $pp$ or $p\gamma$ interactions in an UHE astrophysical
source predict that the neutrino and gamma-ray emission spectra are related by

$\varepsilon_{\gamma}\,\frac{{\rm d}N_{\gamma}}{{\rm
d}\varepsilon_{\gamma}}=\frac{1}{3K_{\pi}}\left[\varepsilon_{\nu}\,\frac{{\rm
d}N_{\nu}}{{\rm
d}\varepsilon_{\nu}}\right]_{\varepsilon_{\nu}=\varepsilon_{\gamma}/2}~{},$
(9)

where $K_{\pi}\approx 1\,(1/2)$ is the charged to neutral pion ratio in the
$pp\,(p\gamma)$ process. Integrating both sides of eq. (9) over energy implies
that, at the source, the ratio of total energies in $\gamma$’s and $\nu$’s
obeys ${\cal E}_{\gamma}\simeq 2/3\,(4/3)\,{\cal E}_{\nu}$. The net effect of
MPP is to alter this ratio towards the neutrino sector: For example, from
Figure 3 we read that for a source emitting $10^{21}$ eV gammas/neutrinos at
$z=5$, approximately $24\%$ of the initial photon energy is transferred to
neutrinos during the cascade above MPP threshold; naively, the new balance
would be ${\cal E}_{\gamma}^{\prime}\to 0.76{\cal E}_{\gamma}$, ${\cal
E}_{\nu}^{\prime}\to\left(1+0.24\times 2/3\,(4/3)\right){\cal E}_{\nu}$, hence
${\cal E}_{\gamma}^{\prime}/{\cal E}_{\nu}^{\prime}\simeq 0.44\,(0.77)$, i.e.
a ratio changed by about 40%. The actual energy budget ending up in the low
energy diffuse photon flux is more complicated to compute, since one must
account for the contribution seeded by $e^{\pm}$ from charged pion decays, as
well as the fraction of the electromagnetic cascade channelled away by
$e^{\pm}$. However, this simple calculation shows that the role of MPP is to
make UHE sources at high redshift darker than their low-$z$ counterparts even
in indirect electromagnetic signals, while making them correspondingly
brighter in the UHE neutrino signal.

##  IV Discussion and conclusions

Despite ongoing searches via instruments like IceCube Aartsen  _et al._ (2015)
or the Pierre Auger Observatory Aab  _et al._ (2015), ultra-high energy
neutrinos remain elusive. However, the existence of a guaranteed neutrino flux
of cosmogenic origin around $E\sim 10^{17}\,$eV and of viable technology to
measure it has stimulated a number of designs to achieve this goal. Even in
absence of an earlier serendipitous discovery, an instrument like GRAND
Álvarez-Muñiz  _et al._ (2020) would eventually open up this window in
neutrino astronomy, and stimulate further questions.

In this article, we studied some microphysics aspects associated to the UHE
$\nu$ flux production which has been largely neglected: The role of muon pair
production in draining energy from electromagnetic messengers at UHE and
altering the UHE $\nu$ flux, and its interplay with double pair production. We
argued that MPP is expected to be relevant at $E\gtrsim 10^{19}\,$eV and at
high redshift $z\gtrsim 5$. The resulting flux would fall at the Earth in the
$E\gtrsim 10^{17}\,$eV range of interest for an instrument like GRAND. The
physics of the process would somewhat loosen constraints from the diffuse
gamma ray flux, and spectral features in the neutrino flux, such as the
transition between muon and pion channel production around $10^{18}\,$eV,
visible in Figures 5 and 6, may be the least elusive of their signatures.

We have limited ourselves to generic considerations, to be as model-
independent as possible, and we did not attempt to link the electromagnetic
particles injected to primary UHECR fluxes, either. A few qualitative comments
can be however made: Naive expectations from energetics would suggest that the
UHE neutrino signal is dominated by relatively low-$z$ sources, making hard in
this case to dig such a signal out of a larger flux. However, so little is
known about UHECR sources at high-$z$, since energy losses make their flux
subleading to the low-$z$ one, that one cannot exclude that new classes of
very energetic UHE emitters could be unveiled, for which our considerations
are particularly relevant. One conceivable example is provided by the
processes associated to the birth and growth of supermassive black holes Woods
_et al._ (2019), which are still unsolved astrophysical problems Inayoshi  _et
al._ (2020). Additionally, if an astrophysical flux of UHECRs is present, it
is likely dominated by a light (proton-helium) composition, compared to the
local observations indicating a nuclear enriched CR composition above $\sim
10$ EeV Bellido (2018). This is due to the declining metallicity at high-$z$,
see e.g. Mannucci  _et al._ (2010). Also, reaching the highest energies
considered here clearly relies on the acceleration mechanism not being limited
by energy-losses on the CMB, which impose tighter constraints at high-$z$.
Another flux that would have likely escaped detection at low-$z$ could be due
to exotic supermassive relics produced in the early universe, if decaying with
a lifetime shorter than the Hubble time. Similar scenarios were considered in
the past as “top-down” models of UHECRs Kachelriess (2008) and are still
considered in relation to dark matter candidates Guépin  _et al._ (2021).
Related models would generally leave a major imprint in the UHE neutrino flux,
although the complementary sensitivity of cosmological probes remains to be
studied. For decays into hadronic final states, the prompt neutrinos and
gamma-rays are expected to originate from comparable numbers of
$\pi^{+},\pi^{0},\pi^{-}$, so that the spectral considerations made in the
previous section should roughly apply. A slightly more favourable situation
(in the sense of energetically enhancing the relevance of the effects
discussed here) could arise in models with preferentially leptonic final
states, with comparable energy budgets of prompt neutrinos (now leading to a
quasi-monochromatic spectrum, modulo the $z$-dependence of the source and
$Z,W-$strahlung corrections) and charged leptons. Once again, the modified
electromagnetic cascades would be visible in the lower energy part of the
spectrum. Of course, for definite scenarios which our results apply to, it
would be interesting to perform specific calculations, perhaps including also
sub-leading microphysics processes, and moving to full-fledged multimessenger
studies. Such tasks are left for future investigations.

In conclusion, if the past is of any guidance, it is wise to be ready to
possible surprises from the opening of any new astrophysical window. For the
UHE sky at high-$z$, one should be aware that differences are present with
respect to naive expectations valid at low-$z$, which is without doubts the
most important message of this article.

###### Acknowledgements.

A.F. E. thanks the support received by the Conselho Nacional de
Desenvolvimento Científico e Tecnológico (CNPq) scholarship No. 140315/2022-5
and by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
(CAPES)/Programa de Excelência Acadêmica (PROEX) scholarship No.
88887.617120/2021-00. A. C. thanks the support received by the CNPq
scholarship No. 140316/2021-3 and by the CAPES/PROEX scholarship No.
88887.511843/2020-00. During his stay at Laboratoire d’Annecy-Le-Vieux de
Physique Theorique (LAPTh), A. E. has been partially supported by the Centre
national de la recherche scientifique (CNRS) invited researcher program. A. E.
would like to acknowledge support from the International Centre for
Theoretical Physics (ICTP) through the Associates Programme (2018-2023). A. E.
thanks partial financial support by the Brazilian funding agency CNPq (grant
407149/2021).

##  Appendix A Neutrino spectra

Muon decay generates a neutrino spectrum whose shape depends on the energy
distribution of produced $\mu^{+}$ and $\mu^{-}$; for a monoenergetic UHE
photon, their distribution is given by ${\rm d}N_{\mu^{\pm}}/{\rm
d}E_{\mu^{\pm}}\equiv(1/\sigma_{\rm MPP}){\rm d}\sigma_{\rm MPP}/{\rm
d}E_{\mu^{\pm}}$. The total (all flavors) neutrino spectrum ${\rm
d}N_{\nu}/{\rm d}E_{\nu}$ from the decay of $\mu^{\pm}$ with spectrum ${\rm
d}N_{\mu^{\pm}}/{\rm d}E_{\mu^{\pm}}$ can be written as Lipari (1993)

$\frac{{\rm d}N_{\nu}}{{\rm d}E_{\nu}}(E_{\nu})=\int_{E_{\mu,\rm
min}}^{E_{\mu,\rm max}}{\rm d}E_{\mu}\,\frac{{\rm d}N_{\mu^{\pm}}}{{\rm
d}E_{\mu^{\pm}}}(E_{\mu})\\\
\times\left[F_{\mu^{\pm}\rightarrow\overset{(-)}{\nu}_{\mu}}(E_{\mu};E_{\nu})+F_{\mu^{\pm}\rightarrow\overset{(-)}{\nu}_{e}}(E_{\mu};E_{\nu})\right]~{},$
(10)

where

$F_{a\rightarrow b}(E_{a};E_{b})=\frac{1}{E_{a}}F_{a\rightarrow
b}\left(\frac{E_{b}}{E_{a}}\right)~{},$ (11)

and for unpolarized muons one has

$F_{\mu^{\pm}\rightarrow\overset{(-)}{\nu}_{\mu}}(y)=\frac{5}{3}-3y^{2}+\frac{4}{3}y^{3}~{},$
(12)

and

$F_{\mu^{\pm}\rightarrow\overset{(-)}{\nu}_{e}}(y)=2-6y^{2}+4y^{3}~{}.$ (13)

From these relations we can estimate the total energy drainage from the
initial photon to neutrinos. By a simple inspection of the above formulae, on
the average $\sim 65\%$ of the energy of a photon at the time of MPP goes to
neutrinos.

In Figures 5 and 6, we also show the neutrino spectra from a monoenergetic
charged pion decay. Given a pion spectrum ${\rm d}N_{\pi^{\pm}}/{\rm
d}E_{\pi^{\pm}}$, there are two contributions to the final neutrino flux: (i)
the (anti)muon neutrino emitted directly from the pion decay
$\pi^{\pm}\to\mu^{\pm}\nu_{\mu}(\bar{\nu}_{\mu})$,

$\frac{{\rm d}N_{\nu}}{{\rm d}E_{\nu}}(E_{\nu})=\int_{E_{\pi,\rm
min}}^{E_{\pi,\rm max}}{\rm d}E_{\pi}\,\frac{{\rm d}N_{\pi^{\pm}}}{{\rm
d}E_{\pi^{\pm}}}\,F_{\pi^{\pm}\rightarrow\overset{(-)}{\nu}_{\mu}}(E_{\pi};E_{\nu})~{},$
(14)

where

$F_{\pi^{\pm}\rightarrow\overset{(-)}{\nu}_{\mu}}(x)=\frac{1}{1-r_{\pi}}[1-\theta(x-1+r_{\pi})]~{},$
(15)

obeys the scaling (11) and $r_{\pi}=(m_{\mu}/m_{\pi})^{2}$, and (ii) the
neutrinos emitted in the subsequent muon decay. The latter can be obtained by
convoluting

$\frac{{\rm d}N_{\mu^{\pm}}}{{\rm d}E_{\mu^{\pm}}}(E_{\mu})=\int_{E_{\pi,\rm
min}}^{E_{\pi,\rm max}}{\rm d}E_{\pi}\,\frac{{\rm d}N_{\pi^{\pm}}}{{\rm
d}E_{\pi^{\pm}}}\,F_{\pi^{\pm}\rightarrow\mu^{\pm}}(E_{\pi};E_{\mu})~{},$ (16)

in Eq. (10), where

$F_{\pi^{\pm}\rightarrow\mu^{\pm}}(x)=\frac{1}{1-r_{\pi}}\theta(x-r_{\pi})~{}.$
(17)

## References

  * Kalogera  _et al._ (2019) V. Kalogera _et al._ , (2019), arXiv:1903.09220 [astro-ph.HE] .
  * Aartsen  _et al._ (2013) M. Aartsen _et al._ (IceCube), Phys.Rev.Lett. 111, 021103 (2013), arXiv:1304.5356 [astro-ph.HE] .
  * Schneider (2019) A. Schneider, in  _36th International Cosmic Ray Conference (ICRC 2019) Madison, Wisconsin, USA, July 24-August 1, 2019_ (2019) arXiv:1907.11266 [astro-ph.HE] .
  * Stettner (2019) J. Stettner (IceCube), in  _HAWC Contributions to the 36th International Cosmic Ray Conference (ICRC2019)_ (2019) arXiv:1908.09551 [astro-ph.HE] .
  * Aartsen  _et al._ (2020) M. G. Aartsen _et al._ (IceCube), (2020), arXiv:2001.09520 [astro-ph.HE] .
  * Aartsen  _et al._ (2021) M. G. Aartsen _et al._ (IceCube), Nature 591, 220 (2021), arXiv:2110.15051 [hep-ex] .
  * Berezinsky and Zatsepin (1969) V. S. Berezinsky and G. T. Zatsepin, Phys. Lett. B 28, 423 (1969).
  * Abbasi  _et al._ (2021) R. Abbasi _et al._ (IceCube-Gen2), in  _37th International Cosmic Ray Conference (ICRC 2021), Online – Berlin, Germany, July 12-23, 2021_ (2021) arXiv:2107.08910 [astro-ph.HE] .
  * Fang  _et al._ (2017) K. Fang _et al._ (GRAND), in  _35th International Cosmic Ray Conference (ICRC 2017), Bexco, Busan, Korea_ (2017) arXiv:1708.05128 [astro-ph.IM] .
  * Batista  _et al._ (2019) R. A. Batista, R. M. de Almeira, B. Lago, and K. Kotera, JCAP 01, 002 (2019), arXiv:1806.10879 [astro-ph.HE] .
  * Waxman and Bahcall (1998) E. Waxman and J. N. Bahcall, Phys. Rev. D 59, 023002 (1998), arXiv:hep-ph/9807282 .
  * Mannheim  _et al._ (2000) K. Mannheim, R. J. Protheroe, and J. P. Rachen, Phys. Rev. D 63, 023003 (2000), arXiv:astro-ph/9812398 .
  * Kalashev  _et al._ (2002) O. E. Kalashev, V. A. Kuzmin, D. V. Semikoz, and G. Sigl, Phys. Rev. D 66, 063004 (2002), arXiv:hep-ph/0205050 .
  * Kusenko and Postma (2001) A. Kusenko and M. Postma, Phys. Rev. Lett. 86, 1430 (2001), arXiv:hep-ph/0007246 .
  * Postma (2001) M. Postma, Phys. Rev. D 64, 023001 (2001), arXiv:hep-ph/0102106 .
  * Athar  _et al._ (2001) H. Athar, G.-L. Lin, and J.-J. Tseng, Phys. Rev. D 64, 071302(R) (2001), arXiv:hep-ph/0104185 .
  * Berezinsky (1970) V. Berezinsky, Yad. Fiz. 11, 399 (1970).
  * Wang  _et al._ (2017) K. Wang, R.-Y. Liu, Z. Li, and Z.-G. Dai, Phys. Rev. D 95, 063010 (2017), arXiv:1702.07566 [astro-ph.HE] .
  * Li and Waxman (2007) Z. Li and E. Waxman, in  _32nd International Cosmic Ray Conference_, Vol. 8 (2007) p. 262, arXiv:0711.4969 [hep-ph] .
  * Lee (1998) S. Lee, Phys. Rev. D 58, 043004 (1998), arXiv:astro-ph/9604098 .
  * Breit and Wheeler (1934) G. Breit and J. A. Wheeler, Phys. Rev. 46, 1087 (1934).
  * Akhiezer and Berestetskii (1965) A. I. Akhiezer and V. B. Berestetskii, in  _Quantum Electrodynamics_ (1965).
  * Aharonian and Atoyan (1981) F. A. Aharonian and A. M. Atoyan, Astrophysics and Space Science 79, 321 (1981).
  * Brown  _et al._ (1973) R. W. Brown, W. F. Hunt, and K. O. Mikaelian, Phys. Rev. D 8, 3083 (1973).
  * Demidov and Kalashev (2009) S. V. Demidov and O. E. Kalashev, J. Exp. Theor. Phys. 108, 764 (2009), arXiv:0812.0859 [astro-ph] .
  * Boyer  _et al._ (1990) J. Boyer, F. Butler, G. Gidal, G. Abrams, D. Amidei, A. R. Baden, _et al._ , Phys. Rev. D 42, 1350 (1990).
  * Morgan and Pennington (1987) D. Morgan and M. R. Pennington, Phys. Lett. B 192, 207 (1987).
  * Whalley (2001) M. R. Whalley, J. Phys. G: Nucl. Part. Phys. 27, A1 (2001).
  * Morgan  _et al._ (1994) D. Morgan, M. R. Pennington, and M. R. Whalley, J. Phys. G: Nucl. Part. Phys. 20, A1 (1994).
  * Lemoine and Sigl (2001) M. Lemoine and G. Sigl,  _Physics and Astrophysics of Ultra High Energy Cosmic Rays_, Vol. 576 (2001) pp. 196–254.
  * Pomakov  _et al._ (2022) V. P. Pomakov _et al._ , Mon. Not. Roy. Astron. Soc. 515, 256 (2022), arXiv:2208.01336 [astro-ph.CO] .
  * Lipari (1993) P. Lipari, Astropart. Phys. 195, 227 (1993).
  * Aartsen  _et al._ (2015) M. G. Aartsen _et al._ (IceCube), Astrophys. J. 809, 98 (2015), arXiv:1507.03991 [astro-ph.HE] .
  * Aab  _et al._ (2015) A. Aab _et al._ (Pierre Auger), Phys. Rev. D 91, 092008 (2015), arXiv:1504.05397 [astro-ph.HE] .
  * Álvarez-Muñiz  _et al._ (2020) J. Álvarez-Muñiz _et al._ (GRAND), Sci. China Phys. Mech. Astron. 63, 219501 (2020), arXiv:1810.09994 [astro-ph.HE] .
  * Woods  _et al._ (2019) T. E. Woods _et al._ , Publ. Astron. Soc. Austral. 36, e027 (2019), arXiv:1810.12310 [astro-ph.GA] .
  * Inayoshi  _et al._ (2020) K. Inayoshi, E. Visbal, and Z. Haiman, Ann. Rev. Astron. Astrophys. 58, 27 (2020), arXiv:1911.05791 [astro-ph.GA] .
  * Bellido (2018) J. Bellido, in  _35th International Cosmic Ray Conference (ICRC2017)_ (2018).
  * Mannucci  _et al._ (2010) F. Mannucci, G. Cresci, R. Maiolino, A. Marconi, and A. Gnerucci, Mon. Not. Roy. Astron. Soc. 408, 2115 (2010), arXiv:1005.0006 [astro-ph.CO] .
  * Kachelriess (2008) M. Kachelriess, in  _20th Rencontres de Blois on Challenges in Particle Astrophysics_ (2008) pp. 215–224, arXiv:0810.3017 [astro-ph] .
  * Guépin  _et al._ (2021) C. Guépin, R. Aloisio, A. Cummings, L. A. Anchordoqui, J. F. Krizmanic, A. V. Olinto, M. H. Reno, and T. M. Venters, Phys. Rev. D 104, 083002 (2021), arXiv:2106.04446 [hep-ph] .


# Flattened Stirling Permutations

Adam Buck  Department of Mathematical Sciences, University of Wisconsin,
Milwaukee, WI 53211
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Jennifer
Elder  Department of Computer Science, Mathematics and Physics, Missouri
Western State University, St. Joseph, MO 64507
<EMAIL_ADDRESS>Azia A. Figueroa  Department of
Mathematical Sciences, University of Wisconsin, Milwaukee, WI 53211
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Pamela
E. Harris  Department of Mathematical Sciences, University of Wisconsin,
Milwaukee, WI 53211
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Kimberly
J. Harry  Department of Mathematical Sciences, University of Wisconsin,
Milwaukee, WI 53211
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Anthony
Simpson  Greenwood, IN 46143
<EMAIL_ADDRESS>
###### Abstract

Recall that a Stirling permutation is a permutation on the multiset
$\\{1,1,2,2,\ldots,n,n\\}$ such that any numbers appearing between repeated
values of $i$ must be greater than $i$. We call a Stirling permutation
“flattened” if the leading terms of maximal chains of ascents (called runs)
are in weakly increasing order. Our main result establishes a bijection
between flattened Stirling permutations and type $B$ set partitions of
$\\{0,\pm 1,\pm 2,\ldots,\pm(n-1)\\}$, which are known to be enumerated by the
Dowling numbers, and we give an independent proof of this fact. We also
determine the maximal number of runs for any flattened Stirling permutation,
and we enumerate flattened Stirling permutations with a small number of runs
or with two runs of equal length. We conclude with some conjectures and
generalizations worthy of future investigation.

††footnotetext: 2020 Mathematics Subject Classification. Primary 05A05;
Secondary 05A10, 05A15, 05A17, 05A18.††footnotetext: Key words and phrases.
Stirling permutation, flattened Stirling permutation, type $B$ set partition,
recurrence relation, Dowling number.

##  1 Introduction

Throughout, let $n\in\mathbb{N}\coloneqq\\{1,2,3,\ldots\\}$,
$[n]\coloneqq\\{1,2,\cdots,n\\}$, and $\mathfrak{S}_{n}$ denote the set of
permutations of the set $[n]$. If $\sigma\in\mathfrak{S}_{n}$, then the _runs_
of $\sigma$ are the maximal contiguous increasing subwords of $\sigma$. If the
sequence of leading terms of the runs appear in increasing order, then we say
$\sigma$ is a flattened partition of length $n$. For example, $\sigma=135246$
is a flattened partition of length six while $\sigma=613425$ is not a
flattened partition, as the leading terms $6,1,2$ are not in increasing order.

Nabawanda, Rakotondrajao, and Bamunoba establish the following recursive
formula for $f_{n,k}$, the number of flattened partitions of length $n$ with
exactly $k$ runs [9, Theorem 1]:

$f_{n,k}=\sum_{m=1}^{n-2}\left({\binom{n-1}{m}}-1\right)f_{m,k-1},$

where $f_{n,1}=1$, for all $n\geq 1$, and $f_{n,k}=0$, for all $k\geq n\geq
2$. Elder, Harris, Markman, Tahir, and Verga, generalized the work of
Nabawanda et al. by giving recursive formulas for $\textbf{1}_{r}$-insertion
flattened parking functions. These are the flattened parking functions built
from permutations of $[n]$, with $r$ additional ones inserted, and which have
$k$ runs [3, Theorems 29, 30 and 35]. Motivated by the work of Nabawanda et
al. [9] and Elder et al. [3], we study flattened Stirling permutations, a
subset of Stirling permutations, which we define next.

We let $[n]_{2}\coloneqq\\{1,1,2,2,\ldots,n,n\\}$ denote the multiset with
each element in $[n]$ appearing twice. We recall that a Stirling permutation
of order $n$ is a word $w=w_{1}w_{2}\ldots w_{2n}$ on the multiset $[n]_{2}$,
in which every letter in $[n]$ appears exactly twice and any values between
the repeated instances of $i$ must be greater than $i$. We denote the set of
Stirling permutations of order $n$ as $\mathcal{Q}_{n}$, and recall that
$|\mathcal{Q}_{n}|=(2n-1)!!$ [6, Theorem 2.1]. For example,
$112299388346677455\in\mathcal{Q}_{9}$, while
$112293883946677545\notin\mathcal{Q}_{9}$ since the threes appears between the
two instances of the nine.

Stirling permutations were introduced by Gessel and Stanley, and they give a
combinatorial interpretation of the coefficients of the polynomial

${Q_{n}(t)=\frac{(1-t)^{2n+1}}{t}\sum_{m\geq 0}S(m+n,m)t^{m}},$

where $S(a,b)$ denotes the Stirling number of the second kind. They establish
that

$Q_{n}(t)=\sum_{w\in\mathcal{Q}_{n}}t^{\mathrm{des}(w)},$

where $\mathrm{des}(w)$ counts the number of descents of $w$, which are
indices $i$ such that $w_{i}>w_{i+1}$ [6, Theorem 2.3]. Since then, many have
studied statistics of Stirling permutations, including enumerating their
descents, ascents, ties, and mesa sets, as well as generalizing to quasi-
Stirling permutations and studying descents and $\gamma$-positivity [2, 4, 5,
7, 12].

We now define our main object of study. Given $w\in\mathcal{Q}_{n}$, we begin
by defining the _runs_ of $w$ to be the maximal contiguous weakly increasing
subwords of $w$. If the sequence of leading terms of the runs appear in weakly
increasing order, then we say $w$ is a flattened Stirling permutation of order
$n$. We denote the set of flattened Stirling permutations of order $n$ by
$\textnormal{flat}(\mathcal{Q}_{n})$, and we let
$\textnormal{flat}_{k}(\mathcal{Q}_{n})$ be the subset of
$\textnormal{flat}(\mathcal{Q}_{n})$, which have exactly $k$ runs. For
example, $112299388346677455\in\mathcal{Q}_{9}$ is flattened since the leading
terms of the runs appear in the order $1,3,3,4$; while
$123321445566778899\in\mathcal{Q}_{9}$ is not flattened, as the leading values
of the runs are $1,2,1$, which are not in weakly increasing order. Table 1
provides the cardinality of the sets $|\mathcal{Q}_{n}|$,
$|\textnormal{flat}(\mathcal{Q}_{n})|$, and
$|\textnormal{flat}_{k}(\mathcal{Q}_{n})|$ for $1\leq n\leq 10$ and $1\leq
k\leq 7$. The Sage code used to produce the data in this table can be found on
CoCalc.

$n$ | $|\mathcal{Q}_{n}|$ | $|\textnormal{flat}(\mathcal{Q}_{n})|$ | $|\textnormal{flat}_{1}(\mathcal{Q}_{n})|$ | $|\textnormal{flat}_{2}(\mathcal{Q}_{n})|$ | $|\textnormal{flat}_{3}(\mathcal{Q}_{n})|$ | $|\textnormal{flat}_{4}(\mathcal{Q}_{n})|$ | $|\textnormal{flat}_{5}(\mathcal{Q}_{n})|$ | $|\textnormal{flat}_{6}(\mathcal{Q}_{n})|$ | $|\textnormal{flat}_{7}(\mathcal{Q}_{n})|$
---|---|---|---|---|---|---|---|---|---
1 | 1 | 1 | 1 |  |  |  |  |  |
2 | 3 | 2 | 1 | 1 |  |  |  |  |
3 | 15 | 6 | 1 | 5 |  |  |  |  |
4 | 105 | 24 | 1 | 15 | 8 |  |  |  |
5 | 945 | 116 | 1 | 37 | 70 | 8 |  |  |
6 | 10395 | 648 | 1 | 83 | 374 | 190 |  |  |
7 | 135135 | 4088 | 1 | 177 | 1596 | 2034 | 280 |  |
8 | 2027025 | 28640 | 1 | 367 | 6012 | 15260 | 6720 | 280 |
9 | 34459425 | 219920 | 1 | 749 | 20994 | 93764 | 88732 | 15680 |
10 | 654729075 | 1832224 | 1 | 1515 | 69842 | 508538 | 866796 | 363132 | 22400

Table 1: Counts for flattened Stirling permutations based on number of runs.

Nabawanda et al. give a combinatorial bijection between flattened partitions
over $[n+1]$ and set partitions of $[n]$ [9, Theorem 19]. Elder et al. also
establish a bijection between $\textbf{1}_{r}$-insertion flattened parking
functions with set partitions of $[n+r]$ with exactly $k$ blocks having two or
more elements [3, Theorem 37]. Given these results, it is natural to ask
whether flattened Stirling permutations are in bijection with some type of set
partitions. This is in fact true, and is the content of our main result, which
we state below and illustrate in Figure 1 for $n=3$.

######  Theorem 1.1.

For $n\geq 1$, the set $\textnormal{flat}(\mathcal{Q}_{n+1})$ of flattened
Stirling permutations of order $n+1$ is in bijection with the set of type $B$
set partitions on the interval of integers $[-n,n]$.

$0|1|2|3$$11223344$$0|1|23$$11223443$$0|\bar{2}1|3$$11332244$$02|1|3$$13312244$$0|13|2$$11244233$$03|1|2$$14412233$$0|12|3$$11233244$$0|\bar{3}1|2$$11442233$$0|1|\bar{3}2$$11224433$$01|2|3$$12213344$$01|\bar{3}2$$12214433$$012|3$$12233144$$01|23$$12213443$$0|123$$11233442$$02|13$$13312442$$023|1$$13344122$$0|\bar{2}13$$11332442$$02|\bar{3}1$$13314422$$0|\bar{2}\bar{3}1$$11334422$$03|\bar{2}1$$14413322$$013|2$$12244133$$03|12$$14412332$$0|\bar{3}12$$11442332$$0123$$12233441$

Figure 1: Hasse diagram for type $B$ set partitions of $[-3,3]$, illustrated
in black, and the corresponding flattened Stirling permutations in
$\mathcal{Q}_{4}$, listed in blue.

We recall that the Dowling numbers, denoted $D_{n}$ (OEIS A007405), enumerate
type $B$ set partitions [1, Statement 6]. Thus, Theorem 1.1 readily implies
that the set of flattened Stirling permutations of order ${n+1}$ are
enumerated by the $n$th Dowling number (Corollary 3.11). Utilizing our
bijection between type $B$ set partitions and flattened Stirling permutations,
we give a proof for the following formula (Theorem 4.6):

$D_{n}=|\textnormal{flat}(\mathcal{Q}_{n+1})|=\displaystyle\sum_{i=0}^{n}\binom{n}{i}\sum_{k=0}^{n-i}2^{n-i-k}S(n-i,k),$

where $S(a,b)$ denote the Stirling numbers of the second kind with $S(a,0)=0$
for all $a\geq 0$.

Our paper is organized as follows. In Section 2, we provide the necessary
background to make our approach precise, including definitions and examples of
type $B$ set partitions. In Section 3, we prove Theorem 1.1. In Section 4, we
give enumerative formulas for

  1. 1.

the number of runs in a flattened Stirling permutation of order $n$ (Lemma
4.1),

  2. 2.

the maximal number of runs in a flattened Stirling permutation of order $n$
(Lemma 4.2),

  3. 3.

the number of flattened Stirling permutations of order $n$ with one or two
runs (Proposition 4.4),

  4. 4.

the total number of flattened Stirling permutations of order $n$ (Theorem
4.6).

In Section 5, we conclude by presenting a few conjectures and a generalization
of our work worthy of future study.

##  2 Background on type $B$ set partitions

We remark that the study of type $B$ set partitions began with the work of
Montenegro, where he investigates the type $B$ analog of noncrossing set
partitions from which he constructs the type $B$ associahedron [8]. Using this
construction, Reiner [10] develops a definition for type $B$ set partitions.
Adler expands Reiner’s work and creates a notation for type $B$ set partitions
as canonical words [1]. In this section, we provide the necessary definitions
and adopt Adler’s notation for type $B$ set partitions for our purposes.

######  Definition 2.1.

A type $B$ set partition of $[-n,n]$ is a collection of sets (also referred to
as blocks),
$\mathcal{B}=\\{\beta_{0},\beta_{1},\beta_{2},\ldots,\beta_{k}\\}$, satisfying
the following conditions:

  1. 1.

$\beta_{i}$ is a subset of $[-n,n]$ for all $0\leq i\leq k$,

  2. 2.

$\beta_{i}\cap\beta_{j}=\emptyset$ whenever $i\neq j$,

  3. 3.

$\displaystyle\cup_{i=0}^{k}\,\beta_{i}=[-n,n]$,

  4. 4.

if $\beta\in\mathcal{B}$, then
$-\beta\coloneqq\\{-b:b\in\beta\\}\in\mathcal{B}$, and

  5. 5.

there is exactly one block $\beta\in\mathcal{B}$ satisfying $\beta=-\beta$.

Note that Conditions 1-3 are the definition of a “standard” set partition of
$[-n,n]$. We say the blocks $\beta$ and $-\beta$, described in Condition 4,
are a block pair of $\mathcal{B}$. The unique block described in Condition 5,
satisfying $\beta=-\beta$, must contain $0$ and is called the _zero-block of_
$\mathcal{B}$. We let $\Pi^{B}_{n}$ denote the collection of all type $B$ set
partitions of $[-n,n]$, and we let $\Pi^{B}_{n,m}$ denote the collection of
all type $B$ set partitions having exactly $m$ block pairs.

We illustrate these definitions next.

######  Example 2.2.

Consider the following collections of subsets of $[-4,4]$:

$\mathcal{B}_{1}=\left\\{\\{-4,3\\},\\{1,-2,0,-1,2\\},\\{-3,4\\}\right\\}\mbox{
and
}\mathcal{B}_{2}=\left\\{\\{3,-4,2\\},\\{1\\},\\{-1\\},\\{-2,4,-3\\},\\{0\\}\right\\}$

Notice that, $\mathcal{B}_{1}$ has zero-block $\\{1,-2,0,-1,2\\}$ and a block
pair consisting of $\\{3,-4\\}$ and $\\{-3,4\\}$. Thus,
$\mathcal{B}_{1}\in\Pi^{B}_{4,1}$. Whereas, $\mathcal{B}_{2}$ has zero-block
$\\{0\\}$ and two block pairs consisting of $\\{1\\}$, $\\{-1\\}$ and
$\\{-2,-3,4\\}$, $\\{2,3,-4\\}$. Thus, $\mathcal{B}_{2}\in\Pi^{B}_{4,2}$.

We adopt the notation of Adler, who encodes type $B$ set partitions through a
canonical sequence of words, which we describe below [1, p. 2].

######  Notation 2.3.

Given $\mathcal{B}\in\Pi_{n,m}^{B}$, perform the following steps:

  1. 1.

Of the $m$ block pairs in $\mathcal{B}$, keep only the block with minimal
positive element.

  2. 2.

Keep the $0$-block removing any negative elements and label the block
$\beta_{0}$.

  3. 3.

Order the remaining blocks by minimum positive elements and label them
$\beta_{1},\ldots,\beta_{m}$.

  4. 4.

Order the full subcollection of block as
$\beta_{0},\beta_{1},\ldots,\beta_{m}$.

  5. 5.

Within each block, order the elements by first placing the negatives in
decreasing order, followed by the positive numbers in increasing order.

  6. 6.

For notational simplicity, denote negatives with bars, i.e, barred elements
are just negative numbers.

  7. 7.

Encode the elements of $\beta_{i}$ as a word $\pi_{i}$ and denote the
collection of blocks by

$\pi=\pi_{0}|\pi_{1}|\pi_{2}|\cdots|\pi_{m}.$

We illustrate the use of Adler’s notation (as described in Notation 2.3) with
the following example.

######  Example 2.4.

The type $B$ set partitions from Example 2.2

$\mathcal{B}_{1}=\left\\{\\{-4,3\\},\\{1,-2,0,-1,2\\},\\{-3,4\\}\right\\}\mbox{
and
}\mathcal{B}_{2}=\left\\{\\{3,-4,2\\},\\{1\\},\\{-1\\},\\{-2,4,-3\\},\\{0\\}\right\\}$

are encoded by $012\;|\;\bar{4}3$ and $0\;|\;1\;|\;\bar{4}23$, respectively.
Consider the following element of $\Pi_{10,4}^{B}$:

$\mathcal{B}=\\{\\{0\\},\\{1\\},\\{-1\\},\\{2,7,-8\\},\\{-2,-7,8\\},\\{3,5,6,-9,-10\\},\\{-3,-5,-6,9,10\\},\\{4\\},\\{-4\\}\\}.$

In this case, applying Notation 2.3 yields
$0\,|\,1\,|\,\bar{8}27\,|\,\bar{9}(\overline{10})356\,|\,4.$

Henceforth, all of our type $B$ set partitions adopt Notation 2.3, and we
utilize the canonical sequence of words to denote them. Therefore, we write
$\pi\in\Pi_{n}^{B}$ to denote elements of the set for which we have
implemented Notation 2.3.

##  3 Main bijection

The main objective of this section is to prove Theorem 1.1, establishing a
bijection between flattened Stirling permutations of order $n+1$ and type $B$
set partitions of $[-n,n]$. To begin, we adapt Notation 2.3 for these
purposes.

######  Definition 3.1.

Let $\pi=\pi_{0}\,|\,\pi_{1}\,|\,\cdots\,|\,\pi_{m}$ be a type $B$ set
partition in $\Pi_{n,m}^{B}$. For every $0\leq i\leq m$ further partition
$\pi_{i}$ into $\pi_{i}=N_{i}P_{i}$, where:

  * •

$N_{i}$ consists of the barred elements in $\pi_{i}$ and

  * •

$P_{i}$ consists of the positive values in $\pi_{i}$.

Note that for any $\pi\in\Pi_{n,m}^{B}$, by Notation 2.3, we know $\pi_{0}$
always consists of nonnegative values. Thus, it is always the case that
$N_{0}=\emptyset$. Henceforth, we only consider $N_{i}$ with $1\leq i\leq m$.

######  Example 3.2.

Continuing Example 2.4, let
$\pi=0\,|\,1\,|\,\bar{8}27\,|\,\bar{9}(\bar{10})356\,|\,4$. Then

$\pi=\underbrace{0}_{P_{0}}\,|\,\underbrace{\emptyset}_{N_{1}}\underbrace{1}_{P_{1}}\,|\,\underbrace{\bar{8}}_{N_{2}}\underbrace{27}_{P_{2}}\,|\,\underbrace{\bar{9}(\bar{10})}_{N_{3}}\underbrace{356}_{P_{3}}\,|\,\underbrace{\emptyset}_{N_{4}}\underbrace{4}_{P_{4}}\,,$

where we include an empty set symbol whenever a block did not have any barred
elements.

We now provide the following technical result.

######  Lemma 3.3.

Let $\pi=\pi_{0}\,|\,\pi_{1}\,|\,\cdots\,|\,\pi_{m}$ be a type $B$ set
partition in $\Pi_{n,m}^{B}$. If $\pi_{i}=N_{i}P_{i}$ is as in Definition 3.1,
then for all $0\leq i\leq m$:

  1. 1.

$|N_{i}|\geq 0$,

  2. 2.

$|P_{i}|\geq 1$, and

  3. 3.

the minimal magnitude of the elements in $N_{i}$ is larger than the minimum
element in $P_{i}$, i.e., $\min(-N_{i})>\min(P_{i})$, where
$-N_{i}=\\{-\ell:\ell\in N_{i}\\}$.

###### Proof.

For (1): Any standard set partition would produce a type $B$ set partition in
which $N_{i}=\emptyset$ for all $0\leq i\leq m$. In any other case,
$|N_{i}|\geq 0$.

For (2): By definition, we always select a block pair by minimum of the
positive elements. Thus there is at least one element in the corresponding
$P_{i}$. Implying that $|P_{i}|\geq 1$.

For (3): If $N_{i}=\emptyset$, then by definition, the minimal magnitude of
the elements in $N_{i}$ is infinity. This is larger than the minimum element
in $P_{i}$. If $N_{i}\neq\emptyset$ and $\min(-N_{i})<\min(P_{i})$, then this
would contradict that $\pi_{i}=N_{i}P_{i}$ was the block pair which had the
smallest nonnegative positive value, as $-\pi$ would have been selected in
Step 1 of Notation 2.3. ∎

We now establish the following results, which will be used in our main
bijection.

######  Lemma 3.4.

Let $P([-n,n])$ denote the power set of the set of integers in the interval
$[-n,n]$. For any $i\in\mathbb{Z}$, let $|i|$ denote the absolute value of
$i$. Then the function $h:P([-n,n])\to P([n+1])$ defined by

$h(S)=\begin{cases}\\{|i|+1\,:\,i\in S\\}&\mbox{if $S\neq\emptyset$}\\\
\emptyset&\mbox{if $S=\emptyset$}\end{cases}$

is well-defined.

###### Proof.

Let $S\in P([-n,n])$ and note that $0\leq|S|\leq 2n+1$. If $S=\emptyset$, then
$h(S)=\emptyset$, which is well-defined. Suppose $1\leq|S|\leq k$. If $-i,i\in
S$, then $|-i|+1=i+1$ appears exactly once in $h(S)$, as $h(S)$ is a set and
not a multiset. Then $h(S)=\\{|i|+1\,:\,i\in S\\}$ has size at most $k$ and
whenever $j\in h(S)$ it satisfies $1\leq j\leq n+1$. Hence $h(S)\in P([n+1])$.
Implying that $h$ is well-defined. ∎

Let $\mathcal{W}([n+1])$ denote the set of all words of length $2k$, with
$0\leq k\leq n+1$, whose letters come from the alphabet $[n+1]$ and each
letter that appears in a word appears exactly twice. For example, if $n=1$,
then $\mathcal{W}([2])=\\{\emptyset,11,22,1122,1212,1221,2112,2121,2211\\}$,
where we let $\emptyset$ denote the empty word, which has length zero. Note
that $\mathcal{Q}_{n+1}\subseteq\mathcal{W}([n+1])$ for all $n\geq 0$.

######  Lemma 3.5.

Let $P([n+1])$ denote the power set of $[n+1]$. Then the functions
$f:P([n+1])\to\mathcal{W}([n+1])$ defined by

$f(S)=\begin{cases}s_{1}~{}s_{1}~{}s_{2}~{}s_{2}~{}s_{3}~{}s_{3}~{}\cdots~{}s_{k}~{}s_{k}&\mbox{if
$S=\\{s_{1}<s_{2}<s_{3}<\cdots<s_{k}\\}$}\\\ \emptyset&\mbox{if
$S=\emptyset$}\\\ \end{cases}$

and $g:P([n+1])\to\mathcal{W}([n+1])$ defined by

$g(S)=\begin{cases}s_{1}~{}s_{2}~{}s_{2}~{}s_{3}~{}s_{3}~{}\cdots~{}s_{k}~{}s_{k}~{}s_{1}&\mbox{if
$S=\\{s_{1}<s_{2}<\cdots<s_{k}\\}$}\\\ \emptyset&\mbox{if $S=\emptyset$}\\\
\end{cases}$

are well-defined.

###### Proof.

If $S=\emptyset$, then $f(\emptyset)$ and $g(\emptyset)$ return the unique
output $\emptyset$, which is an element of $\mathcal{W}([n+1])$. Given a
nonempty subset $S$ of $[n+1]$, by the well-ordered property of the natural
numbers, we can uniquely order the elements of $S$ as
$s_{1}<s_{2}<s_{3}<\cdots<s_{k}$, where $k=|S|$. Then
$f(S)=s_{1}~{}s_{1}~{}s_{2}~{}s_{2}~{}\cdots~{}s_{k}~{}s_{k}$ and
$g(S)=s_{1}~{}s_{2}~{}s_{2}~{}\cdots~{}s_{k}~{}s_{k}~{}s_{1}$ are unique
outputs of these functions. These are words with letters in $[n+1]$, each
appearing twice. Thus, the words have length $2k$ and are elements of
$\mathcal{W}([n+1])$. Thus, the functions $f$ and $g$ are well-defined. ∎

######  Proposition 3.6.

Let $h$ be as defined in Lemma 3.4, and $f$, $g$ be as defined in Lemma 3.5.
Let $\pi=\pi_{0}\,|\,\pi_{1}\,|\,\cdots\,|\,\pi_{m}\in\Pi_{n}^{B}$ and, for
each $0\leq i\leq m$, let $\pi_{i}=N_{i}P_{i}$ be as in Definition 3.1. The
function $\varphi:\Pi_{n}^{B}\to\textnormal{flat}(\mathcal{Q}_{n+1})$ defined
by

$\varphi(\pi)=g(h(P_{0}))f(h(N_{1}))g(h(P_{1}))\cdots f(h(N_{m}))g(h(P_{m}))$
(1)

is well-defined.

###### Proof.

By Lemmas 3.4 and 3.5 and the fact that compositions of well-defined functions
are well-defined, we know the output of $\varphi(\pi)$ is unique and consists
of the concatenation of well-defined functions. Moreover, by the definition of
$\pi=\pi_{1}\,|\,\pi_{2}\,|\,\cdots\,|\,\pi_{m}$, we know that the numbers
$[0,n]$ appear exactly once in $\pi$, some of which might have bars.
Furthermore, for each $i\in[m]$, we have that $\pi_{i}=N_{i}P_{i}$ where
$N_{i}$ consists of the barred/negative elements in $\pi_{i}$ and $P_{i}$
consists of the positive values in $\pi_{i}$. Note that applying the function
$h$ to $N_{i}$ (for all $1\leq i\leq m$) and to $P_{i}$ (for all $0\leq i\leq
m$), returns all of the numbers in $[n+1]$ and each number appears exactly
once. Applying $g$ and $f$ as described in Equation (1) ensures that the
output $\varphi(\pi)$ is a word of length $2(n+1)$ in which the numbers in
$[n+1]$ appear exactly twice.

It suffices to show that $\varphi(\pi)$ is a Stirling permutation of order
$n+1$, which satisfies the flattened condition††For the interested reader, we
provide Example 3.7 illustrating this part of the proof.. We do this in that
order.

Step 1. Showing $\varphi(\pi)$ is in $\mathcal{Q}_{n+1}$.

To show that $\varphi(\pi)\in\mathcal{Q}_{n+1}$, fix $i\in[n+1]$ to be
arbitrary. There are two cases to consider:

  * •

The first case is if $i$ appears in an outcome of the form $f(h(N_{j}))$ for
some $1\leq j\leq m$, then $i\,i$ appears in $\varphi(\pi)$ with no values in
between the repeated instances of $i$. Thus, satisfying the needed condition
for a Stirling permutation.

  * •

The second case is if $i$ appears in an outcome of the form $g(h(P_{j}))$ for
some $0\leq j\leq m$. In which case, if $i=\min(P_{j})$, then we have that $i$
appears as the first and last letters in the subword $g(h(P_{j}))$. All values
between the repeated instances of $i$ (if any) are larger than $i$. Thus,
satisfying the needed condition for a Stirling permutation. If
$i\neq\min(P_{i})$, then we have that $i\,i$ appears in $\varphi(\pi)$ with no
values in between the repeated instance of $i$. We also note that $i$ is
larger than the $\min(P_{i})$. Thus, $\varphi(\pi)$ satisfies the needed
condition of a Stirling permutation.

Step 2. Showing that $\varphi(\pi)$ is flattened.

Recall from Notation 2.3, that we ordered the blocks of $\pi$ based on the
minimum positive values and placed the zero-block at the start. Moreover, each
block was then ordered by placing any negative values within a block at the
start of the block in decreasing order followed by the positive values in
increasing order (Step 5 in Notation 2.3).

We begin by claiming that no run can be started within a subword
$f(h(N_{i}))$, for any $1\leq i\leq m$. To establish this, note that the
subword $g(h(P_{i-1}))$ will always end with the minimum of $P_{i-1}$. Since
every element in $h(N_{i})$ is larger than the minimum of $h(P_{i})$, and
$\min(h(P_{i-1}))<\min(h(P_{i}))$. Then $f(h(N_{i}))$ (which is written in
weakly increasing order) will never start a run.

Fix $1\leq i\leq m$. We now consider the following exhaustive cases:

  1. 1.

If $|P_{i}|=1$ and $N_{i}=\emptyset$, then $g(h(P_{i}))$ does not begin a new
run because the $\min(P_{i-1})<\min(P_{i})$.

  2. 2.

If $|P_{i}|=1$ and $N_{i}\neq\emptyset$, then $f(h(N_{i}))g(h(P_{i}))$ is
equal to

$(|n_{1}|+1)\,(|n_{1}|+1)\,(|n_{2}|+1)\,(|n_{2}|+1)\,\cdots\,(|n_{|N_{i}|}|+1)\,(|n_{|N_{i}|}|+1)\,(p_{1}+1)\,(p_{1}+1),$

where $N_{i}=\\{n_{1}>n_{2}>\cdots>n_{|N_{i}|}\\}$, $P_{i}=\\{p_{1}\\}$, and
$p_{i}<|n_{|N_{i}|}|+1$. Thus, the first instance of $p_{1}+1=\min(P_{i})+1$
begins a new run, and the second instance continues this same run.

  3. 3.

If $|P_{i}|>1$ and $N_{i}=\emptyset$, then
$f(h(N_{i}))g(h(P_{i}))=g(h(P_{i}))$ is equal to

$(p_{1}+1)\,(p_{2}+1)\,(p_{2}+1)\,\cdots\,(p_{|P_{i}|}+1)\,(p_{|P_{i}|}+1)\,(p_{1}+1),$

where $P_{i}=\\{p_{1}<p_{2}<\cdots<p_{|P_{i}|}\\}$. Thus, the first occurrence
of $p_{1}+1=\min(P_{i})+1>\min(P_{i-1})+1$ and hence continues the previous
run (if any) and the second instance of $p_{1}+1=\min(P_{i})+1$ begins a new
run.

  4. 4.

If $|P_{i}|>1$ and $N_{i}\neq\emptyset$, then $f(h(N_{i}))g(h(P_{i}))$ is
equal to

$\begin{array}[]{c}\leavevmode\resizebox{433.62pt}{}{
$(|n_{1}|+1)\,(|n_{1}|+1)\,\cdots\,(|n_{|N_{i}|}|+1)\,(|n_{|N_{i}|}|+1)\,(p_{1}+1)\,(p_{2}+1)\,(p_{2}+1)\,\cdots\,(p_{|P_{i}|}+1)\,(p_{|P_{i}|}+1)\,(p_{1}+1),$
}\end{array}$

where $P_{i}=\\{p_{1}<p_{2}<\cdots<p_{|P_{i}|}\\}$ and
$N_{i}=\\{n_{1}>n_{2}>\cdots>n_{|N_{i}|}\\}$. Thus, each instance of
$p_{1}+1=\min(P_{i})+1$ begins a new run since $|n_{|N_{i}|}|+1>p_{1}+1$ and
$p_{|P_{i}|}+1>p_{1}+1$.

For the case where $i=0$, note that $N_{0}$ is empty and

$g(h(P_{0}))=\begin{cases}11&\mbox{if $P_{0}=\\{1\\}$}\\\
1\,p_{2}\,p_{2}\,\cdots p_{k}\,p_{k}\,1&\mbox{if
$P_{0}=\\{1<p_{2}<p_{3}<\cdots<p_{k}\\}$, with $k\geq 2$.}\\\ \end{cases}$

This ensures that $\varphi(\pi)$ begins with $11$ or that the first two runs
begin with the value $1$.

Note that by the Step 3 in Notation 2.3, we know that
$\min(P_{0})<\min(P_{1})<\cdots<\min(P_{m})$. Hence, ensuring that
$(\min(P_{0})+1)<(\min(P_{1})+1)<\cdots<(\min(P_{m})+1)$. As the only
locations at which runs may begin are at values equal to $\min(P_{i})+1$ (for
some $i$), we have that $\varphi(\pi)$ satisfies the flattened condition.
Thus, $\varphi(\pi)$ is a flattened Stirling permutation.

Together Steps 1 and Step 2 establishes that $\varphi$ is well-defined. ∎

We illustrate the proof technique for Proposition 3.6 below.

######  Example 3.7.

Continuing Example 3.2, if

$\pi=\underbrace{0}_{P_{0}}\,|\,\underbrace{\emptyset}_{N_{1}}\underbrace{1}_{P_{1}}\,|\,\underbrace{\bar{8}}_{N_{2}}\underbrace{27}_{P_{2}}\,|\,\underbrace{\bar{9}(\bar{10})}_{N_{3}}\underbrace{356}_{P_{3}}\,|\,\underbrace{\emptyset}_{N_{4}}\underbrace{4}_{P_{4}}$

then

$\varphi(\pi)=\underbrace{11}_{g(h(P_{0}))}\underbrace{22}_{g(h(P_{1}))}\underbrace{99}_{f(h(N_{2}))}\underbrace{3883}_{g(h(P_{2}))}\underbrace{(10)(10)(11)(11)}_{f(h(N_{3}))}\underbrace{466774}_{g(h(P_{3}))}\underbrace{55}_{g(h(P_{4}))}.$

Note that $\varphi(\pi)$ is an element of
$\textnormal{flat}(\mathcal{Q}_{11})$ and has five runs.

We now prove that the function defined in Proposition 3.6 is a bijection.

######  Remark 3.8.

Before proving the main result, we remark that an alternate proof may be given
using the language of “left-to-right minima.” However, our proof is
elementary, utilizes the least amount of technical language, and the use of
left-to-right minima does not necessarily shorten the arguments provided.

######  Theorem 3.9.

The function $\varphi:\Pi_{n}^{B}\to\textnormal{flat}(\mathcal{Q}_{n+1})$
defined in Proposition 3.6 is a bijection.

###### Proof.

For injectivity, assume that
$\pi=\pi_{0}\,|\,\pi_{1}\,|\,\pi_{2}\,|\,\cdots|\pi_{m}$ and
$\tau=\tau_{0}\,|\,\tau_{1}\,|\,\tau_{2}\,|\,\cdots\,|\,\tau_{k}$ are distinct
elements of $\Pi_{n}^{B}$. Further, suppose that the first index at which
$\pi$ and $\tau$ differ is $i$. Namely, $\pi_{j}=\tau_{j}$ for all $0\leq j<i$
and $\pi_{i}\neq\tau_{i}$. Let $\pi_{i}=N_{i}P_{i}$ and
$\tau_{i}=N_{i}^{\prime}P_{i}^{\prime}$ be as in Definition 3.1. If $N_{i}\neq
N_{i}^{\prime}$, then $h(N_{i})\neq h(N_{i}^{\prime})$. Hence $f(h(N_{i}))\neq
f(h(N_{i}^{\prime}))$, and so $\varphi(\pi)\neq\varphi(\tau)$. If
$N_{i}=N_{i}^{\prime}$, then it must be that $P_{i}\neq P_{i}^{\prime}$, hence
$h(P_{i})\neq h(P_{i}^{\prime})$. Hence $g(h(P_{i}))\neq
g(h(P_{i}^{\prime}))$, and so $\varphi(\pi)\neq\varphi(\tau)$. Thus $\varphi$
is injective.

For surjectivity,††For the interested reader, we provide Example 3.10
illustrating this part of the proof. let $w=w_{1}\,w_{2}\,\ldots
w_{2n}\in\textnormal{flat}(\mathcal{Q}_{n})$. We will construct the subwords
$N_{i}^{*}$ and $P_{i}^{*}$ as follows.

  1. 1.

Start at the right end of $w$, and consider the value $w_{2n}$.

  2. 2.

Find the smallest index $1\leq j\leq 2n-1$ for which $w_{j}=w_{2n}$. Note
$w_{j}$ is the left most occurrence of the value $w_{2n}$. Label the subword
beginning at $w_{j}$ and ending at $w_{2n}$, which we denote with $w_{j}\cdots
w_{2n}$, as $P_{1}^{*}$.

  3. 3.

Look at $w_{j-1}$.

    1. (a)

If $w_{j-1}<w_{j}$, then $N_{1}^{*}=\emptyset$

    2. (b)

If $w_{j-1}>w_{j}$, then find the longest contiguous subword $w_{j-m}\cdots
w_{j-1}$ such that $w_{x}>w_{j}$ for all $j-m\leq x\leq j-1$. Label the
subword beginning at $w_{j-m}$ and ending at $w_{j-1}$, which we denote with
$w_{j-m}\cdots w_{j-1}$, as $N_{1}^{*}$.

  4. 4.

Repeat this process to construct $P_{2}^{*}$ and $N_{2}^{*}$, starting at the
next available letter, $w_{j-m-1}$, which is not included in
$N_{1}^{*}P_{1}^{*}$. Continue constructing $P_{i}^{*}$ and $N_{i}^{*}$ in
this way, until you have labeled all of $w$ in this manner and included
$w_{1}$ in some $P_{k}^{*}$ for some $k\geq 1$.

Note that since $w\in\textnormal{flat}(\mathcal{Q}_{n})$, we will end after
$k\geq 1$ iterations of the steps above. We end with $P_{k}^{*}$ which is a
subword that begins and ends with the value $1$. We now have a partitioning of
$w$ into the subwords

$w=P_{k}^{*}N_{k-1}^{*}P_{k-1}^{*}\cdots N_{1}^{*}P_{1}^{*}.$

Create a type $B$ set partition from these subwords as follows:

  1. 5.

Start at $P_{k}^{*}$. Delete the right most occurrence of each letter. Replace
each remaining letter, $w_{i}$, with $(w_{i}-1)$. Draw a divider to the right
of these letters. Label this subword as $\pi_{0}=P_{0}$.

  2. 6.

If $k>1$, then consider $N_{k-1}^{*}P_{k-1}^{*}$.

    1. (a)

If $N_{k-1}^{*}=\emptyset$, then write $N_{1}=\emptyset$.

    2. (b)

If $N_{k-1}^{*}\neq\emptyset$, delete the right most occurrence of each
letter. Replace each remaining letter, $w_{i}$, with $\overline{(w_{i}-1)}$.
Label this subword as $N_{1}$.

    3. (c)

For each letter in $P_{k-1}^{*}$, delete the right most occurrence of each
letter. Replace each remaining letter, $w_{i}$, with $w_{i}-1$. Label this
subword as $P_{1}$.

    4. (d)

Draw a divider to the right of $P_{1}$, and label as $\pi_{1}=N_{1}P_{1}$.

  3. 7.

Repeat this process until $N_{1}^{*}P_{1}^{*}$ has been relabeled as
$\pi_{k-1}=N_{k-1}P_{k-1}$, omitting the part where the divider is added at
the end.

This yields the partition

$\pi=\pi_{0}\,|\,\pi_{1}\,|\,\pi_{2}\,|\,\cdots\,|\,\pi_{k-1},$

which we now show is a type $B$ set partition.

Having begun with $w\in\mathcal{Q}_{n}$ and being precise with the
construction of $\pi$, we ensure that (in absolute value) every number
$i\in[0,n]$ appears exactly once in $\pi$. In addition, we can ensure that
$\pi_{0}$ is the $0$-block, since $1$ was contained in $P_{k}^{*}$, as $w$ is
a flattened Stirling permutation. Based on Notation 2.3, this is sufficient to
be a type $B$ set partition of $[-n,n]$ as desired.

Furthermore, $\varphi(\pi)$ is defined as the concatenation

$\varphi(\pi)=g(h(P_{0}))f(h(N_{1}))g(h(P_{1}))\cdots
f(h(N_{k-1}))g(h(P_{k-1}))$ (2)

where $g(h(P_{0}))=P_{k}^{*}$ and
$f(h(N_{i}))g(h(P_{i}))=N_{k-i}^{*}P_{k-i}^{*}$ as described above. Hence,
Equation (2) is precisely the description of $w$, which implies that
$\varphi(\pi)=w$. ∎

The statement of Theorem 1.1 follows immediately from Theorem 3.9.

In the proof of Theorem 3.9, surjectivity was a complicated process. We
present the following example to illustrate the steps in that part of the
proof.

######  Example 3.10.

Consider the following element of $\textnormal{flat}(\mathcal{Q}_{11})$:

$w=1122993883(10)(10)(11)(11)46677455.$

To construct the pairs $N_{i}^{*}$ and $P_{i}^{*}$, we first label the
subwords (from right to left) as in Steps (1)-(4) in Theorem 3.9:

$\underbrace{11}_{P_{5}^{*}}\underbrace{22}_{P_{4}^{*}}\underbrace{99}_{N_{3}^{*}}\underbrace{3883}_{P_{3}^{*}}\underbrace{(10)(10)(11)(11)}_{N_{2}^{*}}\underbrace{466774}_{P_{2}^{*}}\underbrace{55}_{P_{1}^{*}}.$

Next, we create the pairs $N_{k-i}$ and $P_{k-i}$ for the set partition as in
Steps (5) - (7) in Theorem 3.9:

$\pi=\underbrace{0}_{P_{0}}\,|\,\underbrace{1}_{P_{1}}\,|\,\underbrace{\overline{8}}_{N_{2}}\underbrace{2\,7}_{P_{2}}\,|\,\underbrace{\overline{9}\,\overline{(10)}}_{N_{3}}\underbrace{3\,5\,6}_{P_{3}}\,|\,\underbrace{4}_{P_{4}}.$

We can verify that $\varphi(\pi)=w$, as desired.

Recall that the Dowling numbers (OEIS A007405) enumerate type $B$ set
partitions [1, Statement 6]. Thus, Theorem 1.1 readily implies the following.

######  Corollary 3.11.

If $n\geq 1$, then $|\textnormal{flat}(\mathcal{Q}_{n+1})|=D_{n}$, where
$D_{n}$ is the $n$th Dowling number.

In Subsection 4.3, we provide a formula for the Dowling numbers (Corollary
4.7).

##  4 Enumerating flattened Stirling permutations

In this section, we present enumerative results related to flattened Stirling
permutations.

###  4.1 Enumerating runs

We begin by giving a formula for the number of runs in a flattened Stirling
permutation and follow this with a formula for the maximum number of runs in a
flattened Stirling permutation.

######  Lemma 4.1.

Let $w\in\textnormal{flat}({\mathcal{Q}_{n}})$ and
$\pi=\pi_{0}\,|\,\pi_{1}\,|\,\cdots\,|\,\pi_{k}$ be its corresponding
partition in $\Pi_{n-1}^{B}$ (as in Theorem 3.9), with $\pi_{i}=N_{i}P_{i}$
(as in Definition 3.1) for all $0\leq i\leq k$. Then

$1+|\\{N_{i}:|N_{i}|\geq 1\\}|+|\\{P_{i}:|P_{i}|\geq 2\\}|$

is the number of runs in $w$.

###### Proof.

Let $w\in\textnormal{flat}(\mathcal{Q}_{n})$ and let $\mbox{runs}(w)$ denote
the number of runs in $w$, where $\mbox{runs}(w)=\mbox{des}(w)+1$. Let
$\pi=\pi_{0}\,|\,\pi_{1}\,|\,\ldots\,|\,\pi_{k}$ be the type $B$ set partition
corresponding to $w$ as given by Theorem 3.9. Recall that for all $0\leq i\leq
k$, we write $\pi_{i}=N_{i}P_{i}$ where $N_{i}$ and $P_{i}$ are as in
Definition 3.1. We claim that for every index $i$ satisfying $|N_{i}|\geq 1$
and for every index $j$ satisfying $|P_{j}|\geq 2$ in $\pi$ encodes a distinct
descent of $w$.

Case 1: If $P_{i}=\\{p_{1}\\}$ and $N_{i}=\emptyset$, then
$f(h(N_{i}))g(h(P_{i}))=p_{1}p_{1}$ creates no descents in $w$.

Case 2: Suppose $N_{i}=\emptyset$ and
$P_{i}=\\{p_{1}-1<p_{2}-1<\cdots<p_{j}-1\\}$ where $|P_{i}|\geq 2$. Then
$g(h(P_{i}))=p_{1}\,p_{2}\,p_{2}\,\cdots\,p_{j}\,p_{j}\,p_{1}$. By
construction, $p_{j}\,p_{1}$ creates a descent since $p_{1}<p_{j}$. Therefore,
any $P_{i}$ in $\pi$ satisfying $|P_{i}|\geq 2$ contributes a descent to $w$,
which in turn begins a new run.

Case 3: Suppose $N_{i}\neq\emptyset$. Recall that by construction, we have
that $P_{i}\neq\emptyset$, and the elements in $N_{i}$ satisfy
$\min(h(N_{i}))>\min(h(P_{i}))$. Then $f(h(N_{i}))g(h(P_{i}))$ has the
property that the last value in $f(h(N_{i}))$ is $\max(h(N_{i}))$, and the
first value in $g(h(P_{i}))$ is $\min(h(P_{i}))$. As
$\max(h(N_{i}))>\min(h(P_{i}))$, we note this contributes a descent to $w$.
Therefore, any $N_{i}$ in $\pi$ satisfying $|N_{i}|\geq 1$ contributes a
descent to $w$, which in turn begins a new run.

Thus, the number of runs in $w$ is given by

$\mbox{runs}(w)=\mbox{des}(w)+1=1+|\\{N_{i}:|N_{i}|\geq
1\\}|+|\\{P_{i}:|P_{i}|\geq 2\\}|.\qed$

We now provide a formula for the maximum number of runs in a flattened
Stirling permutation.

######  Lemma 4.2.

The maximum number of runs in an element of
$\textnormal{flat}(\mathcal{Q}_{n})$ is $\lceil\frac{2n}{3}\rceil$.

###### Proof.

Let $w\in\textnormal{flat}({\mathcal{Q}_{n}})$ and $\pi\in\Pi_{n-1}^{B}$ be
its corresponding type $B$ set partition. By Lemma 4.1, the total number of
runs is given by

$1+|\\{P_{i}:|P_{i}|\geq 2\\}|+|\\{N_{i}:|N_{i}|\geq 1\\}|.$

To maximize the number of runs, we must maximize the number of blocks,
$\pi_{i}=N_{i}P_{i}$ with $|P_{i}|=2$ and $|N_{i}|=1$. Suppose
$P_{i}=\\{p_{1}-1<p_{2}-1\\}$ and $N_{i}=\\{n_{1}-1\\}$. Then the subword
$f(h(N_{i}))g(h(P_{i}))$ has the form

$n_{1}\,n_{1}\,p_{1}\,p_{2}\,p_{2}\,p_{1}$

with $n_{1}>p_{1}$ and $p_{2}>p_{1}$. Hence, this contributes two descents,
which are three letters apart in the subword. As $w$ consists of $2n$ letters,
the maximum number of descents being contributed by blocks with $|N_{i}|=1$
and $|P_{i}|=2$ is given by $\frac{2n}{3}$. Starting at the beginning of the
word, we can create a descent at every third letter. This creates no more than
$\frac{2n}{3}-1$ descents, where the “$-1$” accounts for the fact that the
first possible index at which a descent may occur is index three.

To maximize the number of descents, we would construct $\pi$ to have descents
at indices $3k$ with $1\leq k\leq\lfloor\frac{2n-1}{3}\rfloor$, where the
numerator $2n-1$ accounts for not being able to have a descent at the last
index. Since $\mbox{runs}(w)=\mathrm{des}(w)+1$, we have established that the
maximum number of runs is given by
$\lfloor\frac{2n-1}{3}\rfloor+1=\lceil\frac{2n}{3}\rceil$. ∎

We now illustrate Lemma 4.2 with the following example.

######  Example 4.3.

We consider $n=6,7,8$ as these integers are congruent to $0,1,2\mod 3$,
respectively, and account for every case of Lemma 4.2. For each $n=6,7,8$, we
construct a flattened Stirling permutation having a maximal number of runs.

  * •

Let $n=6$ and note $\lceil\frac{2n}{3}\rceil=4$. To construct
$w_{1}\in\textnormal{flat}(\mathcal{Q}_{6})$ with four runs, we must maximize
the number of blocks, $\pi_{i}=N_{i}P_{i}$ with $|P_{i}|=2$ and $|N_{i}|=1$.
One such option is given by $\pi=13\,|\,\overline{4}25\,|\,6.$ Then
$\varphi(\pi)=w_{1}=1\,3\,3\,1\,4\,4\,2\,5\,5\,2\,6\,6,$ which has four runs.

  * •

Let $n=7$ and note $\lceil\frac{2n}{3}\rceil=5$. To construct
$w_{2}\in\textnormal{flat}(\mathcal{Q}_{7})$ with five runs, we must maximize
the number of blocks, $\pi_{i}=N_{i}P_{i}$ with $|P_{i}|=2$ and $|N_{i}|=1$.
One such option is given by
$\pi=1\,3\,|\,\overline{4}\,2\,5\,|\,\overline{7}\,6.$ Then
$\varphi(\pi)=w_{2}=1\,3\,3\,1\,4\,4\,2\,5\,5\,2\,7\,7\,6\,6$, which has five
runs.

  * •

Let $n=8$ and note $\lceil\frac{2n}{3}\rceil=6$. To construct
$w_{3}\in\textnormal{flat}(\mathcal{Q}_{8})$ with six runs, we must maximize
the number of blocks, $\pi_{i}=N_{i}P_{i}$ with $|P_{i}|=2$ and $|N_{i}|=1$.
One such option is given by
$\pi=1\,3\,|\,\overline{4}\,2\,5\,|\,\overline{7}\,6\,8$. Then
$\varphi(\pi)=w_{3}=1\,3\,3\,1\,4\,4\,2\,5\,5\,2\,7\,7\,6\,8\,8\,6$, which has
six runs.

We remark that flattened Stirling permutations with a maximal number of runs
are yet to be enumerated, and we pose this as an open problem in Section 5.

###  4.2 Flattened Stirling permutations with a small number of runs

We now give formulas for the number of flattened Stirling permutations with
one and two runs.

######  Proposition 4.4.

If $n\geq 1$, then

  1. 1.

$|\textnormal{flat}_{1}(\mathcal{Q}_{n})|=1$, and

  2. 2.

$|\textnormal{flat}_{2}(\mathcal{Q}_{n+1})|=2|\textnormal{flat}_{2}(\mathcal{Q}_{n})|+2n-1$,
with $|\textnormal{flat}_{2}(\mathcal{Q}_{1})|=0$.

###### Proof.

For (1): We note that

$w=1\,1\,2\,2\,\cdots(n-1)\,(n-1)\,n\,n$

is the only flattened Stirling permutation with one run.

For (2): We now construct the elements of
$\textnormal{flat}_{2}(\mathcal{Q}_{n+1})$ from those in
$\textnormal{flat}_{1}(\mathcal{Q}_{n})$ and
$\textnormal{flat}_{2}(\mathcal{Q}_{n})$.

  1. Case 1:

The set $\textnormal{flat}_{1}(\mathcal{Q}_{n})$ has a unique flattened
Stirling permutation with form $w=1122\cdots nn$. There are two distinct ways
of inserting $(n+1)(n+1)$ into $w$ to create a flattened Stirling permutation
of order $n+1$ with exactly two runs.

    1. (i)

For all $j\in[n]$ insert $(n+1)(n+1)$ between the repeated value $j$ to build
the Stirling permutation

$1\,1\,2\,2\cdots j\,(n+1)\,(n+1)\,j\cdots\,n\,n.$

The result of this insertion is a flattened Stirling permutation of order
$n+1$ with two runs.

    2. (ii)

For all $j\in[n-1]$ insert the $(n+1)(n+1)$ after the repeated values $jj$ to
build the Stirling permutation

$1\,1\,2\,2\cdots j\,j\,(n+1)\,(n+1)\,(j+1)\,(j+1)\cdots n\,n.$

The result of this insertion is a flattened Stirling permutation of order
$n+1$ with two runs.

This process exhausts all ways in which we can create flattened Stirling
permutations with two runs out of the flattened Stirling permutation with a
single run. If $n+1$ element is inserted anywhere else, it will create a
Stirling permutation that is not flattened. Subcases (i) gives $n$ elements
and (ii) yields $n-1$ elements of $\textnormal{flat}_{2}(\mathcal{Q}_{n+1})$.
Contributing a total of $2n-1$ elements in
$\textnormal{flat}_{2}(\mathcal{Q}_{n+1})$.

  2. Case 2:

Take any element $w=w_{1}w_{2}\cdots
w_{2n}\in\textnormal{flat}_{2}(\mathcal{Q}_{n})$. By definition, there exists
a unique index $i\in[2n-1]$ such that $w_{i}>w_{i+1}$. Inserting $(n+1)(n+1)$
immediately after $w_{i}$ creates an element of
$\textnormal{flat}_{2}(\mathcal{Q}_{n+1})$. Inserting $(n+1)(n+1)$ immediately
after the last value $w_{2n}$ of $w$ creates an element of
$\textnormal{flat}_{2}(\mathcal{Q}_{n+1})$. This process exhausts all the ways
in which we can create flattened Stirling permutations with two runs in
$\textnormal{flat}_{2}(\mathcal{Q}_{n+1})$ out of the flattened Stirling
permutation with two runs in $\textnormal{flat}_{2}(\mathcal{Q}_{n})$. If you
attempt to insert the $n+1$ element anywhere else, it will create a Stirling
permutation that is not flattened. Hence, there are
$2|\textnormal{flat}_{2}(\mathcal{Q}_{n})|$ ways to create a new element in
$\textnormal{flat}_{2}(\mathcal{Q}_{n+1})$.

Note that in Case 1, the constructed flattened Stirling permutations of order
$n+1$ has the numbers $1$ through $n$ appearing in order from left to right.
However, in Case 2, the constructed flattened Stirling permutations of order
$n+1$ has unique values $i,j$ satisfying $1\leq i<j\leq n$ with at least one
$j$ appearing to the left of at least one $i$. Thus, the set of elements in
$\textnormal{flat}_{2}(\mathcal{Q}_{n+1})$ created in Case 1 and Case 2 are
disjoint. Moreover, these are the only options to consider. Thus, the total
number of elements of $\textnormal{flat}_{2}(\mathcal{Q}_{n+1})$ is given by

$|\textnormal{flat}_{2}(\mathcal{Q}_{n+1})|=2|\textnormal{flat}_{2}(\mathcal{Q}_{n})|+2n-1,$

as desired. ∎

We now give a closed formula for $|\textnormal{flat}_{2}(\mathcal{Q}_{n})|$,
which aligns with OEIS A050488.

######  Corollary 4.5.

If $n\geq 1$, then $|\textnormal{flat}_{2}(\mathcal{Q}_{n+1})|=3(2^{n}-1)-2n$.

###### Proof.

When $n=1$, $|\textnormal{flat}_{2}(\mathcal{Q}_{2})|=1$ and
$3(2^{1}-1)-2(1)=3-2=1$. Assume for induction that
$|\textnormal{flat}_{2}(\mathcal{Q}_{n})|=3(2^{n-1}-1)-2(n-1)$. Utilizing the
recursion in Proposition 4.4 yields

$\displaystyle|\textnormal{flat}_{2}(\mathcal{Q}_{n+1})|$
$\displaystyle=2|\textnormal{flat}_{2}(\mathcal{Q}_{n})|+2n-1$
$\displaystyle=2(3(2^{n-1}-1)-2(n-1))+2n-1\qquad\mbox{(by induction
hypothesis)}$ $\displaystyle=3(2^{n}-1)-2n,$

as desired. ∎

###  4.3 Enumeration of $|\textnormal{flat}(\mathcal{Q}_{n})|$

We are now ready to provide a formula for the total number of flattened
Stirling permutations of order $n$.

######  Theorem 4.6.

If $n\geq 0$, then

$|\textnormal{flat}(\mathcal{Q}_{n+1})|=\displaystyle\sum_{i=0}^{n}\binom{n}{i}\sum_{k=0}^{n-i}2^{n-i-k}S(n-i,k),$

where $S(a,b)$ denote the Stirling numbers of the second kind with $S(a,0)=0$
for all $a\geq 0$.

###### Proof.

By Theorem 1.1, we know
$|\Pi_{n}^{B}|=|\textnormal{flat}(\mathcal{Q}_{n+1})|$. Hence, we prove this
result by constructing and thereby enumerating all $\pi$ which are type $B$
set partitions in $\Pi_{n}^{B}$.

To begin we construct a zero-block. Suppose that there are $i+1$ elements in
the zero-block. One of those elements is required to be zero. Thus, there are
$\binom{n}{i}$ ways to construct the zero-block so that it has size $i+1$. We
note that the zero-block always contains only positive elements, so, as $i$
ranges from $0$ to $n$, this construction yields all possible $\pi_{0}$.

We now construct all type $B$ set partitions with a fixed zero-block $\pi_{0}$
of size $i+1$. Suppose we have $k+1$ total blocks in $\pi$. We construct the
remaining $k$ blocks, $\pi_{1},\pi_{2},\ldots,\pi_{k}$, out of the remaining
$n-i$ elements (which are not in $\pi_{0}$). That is, first we must partition
the set $[0,n]\setminus\pi_{0}$ of size $n-i$ into $k$ nonempty subsets. There
are $S(n-i,k)$ ways to do this.

Once we know what elements are in each block, then in each of the $k$ blocks,
the minimal element must remain positive. However, the other $n-i-k$ remaining
elements in the blocks $\pi_{1},\pi_{2},\ldots,\pi_{k}$ may be positive or
negative. There are $2^{n-i-k}$ ways in which to select the signs for those
remaining values. Note we vary $k$ from $0$ to $n-i$, and thus there are
$\sum_{k=0}^{n-i}2^{n-i-k}S(n-i,k)$ ways to build a type $B$ set partition for
a fixed $\pi_{0}$.

Finally, we must vary over $0\leq i\leq n$, which yields

$\displaystyle\sum_{i=0}^{n}\binom{n}{i}\sum_{k=0}^{n-i}2^{n-i-k}S(n-i,k),$

as desired. ∎

Theorems 1.1 and 4.6 imply the following result.

######  Corollary 4.7.

If $n\geq 1$, then the $n$th Dowling number is given by

$D_{n}=\displaystyle\displaystyle\sum_{i=0}^{n}\binom{n}{i}\sum_{k=0}^{n-i}2^{n-i-k}S(n-i,k).$

##  5 Open problems and future directions

In our work, we were able to give a recursive formula for the total number of
flattened Stirling permutations of order $n$ (Theorem 4.6) and for the number
of flattened Stirling permutations of order $n$ with exactly $k=2$ runs
(Proposition 4.4). When $k=3$, we have the following conjecture, which was
computationally verified for $1\leq n\leq 12$.

######  Conjecture 5.1.

The number of Stirling permutations of order $n$ with exactly three runs is
$|\textnormal{flat}_{3}(\mathcal{Q}_{n})|=2\sum\limits_{k=1}^{n-1}\binom{n-1}{k}\left(\sum\limits_{j=2}^{n-1-k}\binom{n-1-k}{j}\right)+\sum\limits_{k=2}^{n-1}\binom{n-1}{k}\left(\sum\limits_{j=2}^{n-1-k}\binom{n-1-k}{j}\right)+\sum\limits_{k=3}^{n-1}(2^{k-1}-2)\binom{n-1}{k}.$

######  Open Problem 1.

Give a formula for the number of flattened Stirling permutations of order $n$
with exactly $k$ runs.

One small step toward solving Open Problem 1 is to consider the case where
$k=\lceil\frac{2n}{3}\rceil$ is the maximum number of runs.

######  Open Problem 2.

Let $\textnormal{flat}_{\max}(\mathcal{Q}_{n})$ denote the set of flattened
Stirling permutations of order $n$ with a maximal number of runs. Give a
formula for the cardinality of the set
$\textnormal{flat}_{\max}(\mathcal{Q}_{n})$, for all $n\geq 1$.

Moreover, one could consider restricting to having runs of equal length. In
which case we ask.

######  Open Problem 3.

Given $d$ a divisor of $n$, let
$\textnormal{flat}_{d,\,\mbox{equal}}(\mathcal{Q}_{n})$ denote the set of
flattened Stirling permutations with $d$ runs all of equal length $n/d$. What
is the cardinality of the set
$\textnormal{flat}_{d,\mbox{equal}}(\mathcal{Q}_{n})$ in terms of $n$ and $d$?

A starting point for Open Problem 3 is to consider the case $d=2$ where there
are two runs of equal length.

Another way to generalize our study is to consider the set of $m$-Stirling
permutations of order $n$ on the multiset $\\{1^{m},2^{m},\ldots,n^{m}\\}$,
which are permutations with each integer in $[n]$ appearing with multiplicity
$m$, and the values between every repeated instance of $i$ are larger than
$i$. We let $\mathcal{Q}_{n}^{m}$, denote the set of $m$-Stirling permutations
of order $n$. Table 2 provides data on the number of elements in
$\textnormal{flat}(\mathcal{Q}_{n}^{m})$ for $1\leq n\leq 7$ and $1\leq m\leq
5$. When possible, we give the OEIS sequence with which these values seem to
agree. Based on that data, we give the following conjecture.

$n\setminus m$ | 2 | 3 | 4 | 5
---|---|---|---|---
1 | 1 | 1 | 1 | 1
2 | 2 | 3 | 4 | 5
3 | 6 | 12 | 20 | 30
4 | 24 | 63 | 128 | 225
5 | 116 | 405 | 1008 | 2075
6 | 648 | 3024 | 9280 | 22500
7 | 4088 | 25515 | 96704 | 276875
OEIS | A007405 | A355164 | A355167 | No OEIS hit
Table 2: Number of flattened $m$-Stirling permutations of order $n$.

######  Conjecture 5.2.

If $m\geq 2$ and $n\geq 1$, then

$|\textnormal{flat}(\mathcal{Q}_{n}^{m})|=e^{-1/m}\displaystyle\sum_{k\geq
0}\frac{(mk+(m-1))^{n}}{k!m^{k}},$

and satisfy the recurrence relation

$|\textnormal{flat}(\mathcal{Q}_{n}^{m})|=(m-1)|\textnormal{flat}(\mathcal{Q}_{n-1}^{m})|+\sum_{k=1}^{n}\binom{n-1}{k-1}m^{k-1}|\textnormal{flat}(\mathcal{Q}_{n-k}^{m})|,$

with $|\textnormal{flat}(\mathcal{Q}_{0}^{m})|=1$.

Conjecture 5.2 motivates our next open problem.

######  Open Problem 4.

Prove Conjecture 5.2 in the affirmative or establish a correct formula for the
number of elements in $\textnormal{flat}(\mathcal{Q}_{n}^{m})$. If possible,
also give formulas for the number of elements in
$\textnormal{flat}(\mathcal{Q}_{n}^{m})$ with exactly $k$ runs.

######  Remark 5.3.

Since the submission of this article, Shankar [11] has provided a proof of
Conjecture 5.2 using generating functions.

## Acknowledgements

J. Elder was partially supported through an AWM Mentoring Travel Grant. P. E.
Harris was supported through a Karen Uhlenbeck EDGE Fellowship.

## References

  * [1] V. È. Adler.  Set partitions and integrable hierarchies.  Teoret. Mat. Fiz., 187(3):455–486, 2016.
  * [2] G.-H. Duh, Y.-C. (R.) Lin, S.-M. Ma, and Y.-N. Yeh.  Some statistics on Stirling permutations and Stirling derangements.  Discrete Math., 341(9):2478–2484, 2018.
  * [3] J. Elder, P. E. Harris, Z. Markman, I. Tahir, and A. Verga.  On flattened parking functions.  J. Integer Seq., 26:Article 23.5.8, 6 2023.
  * [4] S. Elizalde.  Descents on quasi-Stirling permutations.  J. Comb. Theory Ser. A., 180:105429, 2021.
  * [5] S. Elizalde.  Descents on nonnesting multipermutations.  Sémin. lothar., 89B(Article #2):12, 2023.
  * [6] I. Gessel and R. P. Stanley.  Stirling polynomials.  J. Comb. Theory Ser. A., 24(1):24–33, 1978.
  * [7] N. González, P. E. Harris, G. Rojas Kirby, M. Smit Vega Garcia, and B. E. Tenner.  Mesas of Stirling permutations.  arXiv preprint.
  * [8] C. Montenegro.  The fixed point non-crossing partition lattices, 1993.
  * [9] O. Nabawanda, F. Rakotondrajao, and A. Bamunoba.  Run distribution over flattened partitions.  J. Integer Seq., 23:Article 20.9.6, 10 2020.
  * [10] V. Reiner.  Non-crossing partitions for classical reflection groups.  Discrete Math., 177(1):195–222, 1997.
  * [11] Umesh Shankar.  Enumeration of flattened $k$-Stirling permutations with respect to descents, 2023.
  * [12] S. H. F. Yan, Y. Huang, and L. Yang.  Partial $\gamma$-positivity for quasi-Stirling permutations of multisets.  Discrete Math., 345(3):112742, 2022.