# LayoutBERT: Masked Language Layout Model for Object Insertion

Kerem Turgutlu
Adobe
<EMAIL_ADDRESS>Sanat Sharma
Adobe
<EMAIL_ADDRESS>Jayant Kumar
Adobe
<EMAIL_ADDRESS>
###### Abstract

Image compositing is one of the most fundamental steps in creative workflows.
It involves taking objects/parts of several images to create a new image,
called a composite. Currently, this process is done manually by creating
accurate masks of objects to be inserted and carefully blending them with the
target scene or images, usually with the help of tools such as Photoshop or
GIMP. While there have been several works on automatic selection of objects
for creating masks, the problem of object placement within an image with the
correct position, scale, and harmony remains a difficult problem with limited
exploration. Automatic object insertion in images or designs is a difficult
problem as it requires understanding of the scene geometry and the color
harmony between objects.

We propose LayoutBERT for the object insertion task. It uses a novel self-
supervised masked language model objective and bidirectional multi-head self-
attention. It outperforms previous layout-based likelihood models and shows
favorable properties in terms of model capacity. We demonstrate the
effectiveness of our approach for object insertion in the image compositing
setting and other settings like documents and design templates. We further
demonstrate the usefulness of the learned representations for layout-based
retrieval tasks. We provide both qualitative and quantitative evaluations on
datasets from diverse domains like COCO, PublayNet, and two new datasets which
we call Image Layouts and Template Layouts. Image Layouts which consists of
5.8 million images with layout annotations is the largest image layout dataset
to our knowledge. We also share ablation study results on the effect of
dataset size, model size and class sample size for this task.

##  1 Introduction

With the recent rise in image and video creation for teaching, advertisement,
information sharing, and social

Figure 1: Iterative class conditional compositing using LayoutBert bounding
box predictions and alpha masking. At each step, object insertion orders are
re-sorted based on bottom bounding box coordinates to avoid unrealistic
occlusion.

influencing, the need for AI-based assistance in image and video editing is
greater than ever. Image Compositing is one of the most common tasks in
creative workflows. However, currently, it involves several manual steps such
as background and foreground selection, masking, refinement, placement, scale-
adjustment, and harmonization. Due to this tedious and multi-step process it
is difficult for creatives to try more than few new design ideas. Moreover,
the learning curve for beginners is quite steep making it inaccessible for the
majority of users who are interested in expressing themselves in a creative
way.

The success of self-attention and transformer networks on several key language
and vision learning tasks has led to several new explorations of these
architectures including layout understanding and generation. In this work, we
further push the state-of-the-art on layout understanding and show very
promising results on realistic images as well as on documents and templates.
We envision a future where layout input from the user is the exception rather
than the norm.

Figure 2: Masked input sequences during LayoutBert training. Random left-right
flip is applied during training as data augmentation. Later the 2D layout is
converted into the input sequence for modeling. A bounding box is selected for
masking with uniform sampling and each token of the selected bounding box is
masked iteratively and added to the batch. For each added sample, the model
predicts the left-most masked token (denoted by pink coloring).

Usually, creators/designers start with a blank canvas, initialize their work
with a base or background image and bring in parts from multiple images while
applying geometric and color transformations (edits) until the desired
creation is achieved. The final creation can be a personal family collage, an
advertisement photo, a sci-fi movie poster, a petting zoo fundraiser flyer,
etc.

There are many existing works based on automated color transformation learning
such as deep image harmonization [24, 19]. However, none of them discusses
geometric transformation learning for image compositing or the existing work
often limits the problem to certain classes or less complex datasets.

In this paper we propose a bidirectional likelihood based model which can
learn the most likely location and scale for a given object to be inserted
into an image. Our approach offers a solution at scale to automate both photo-
realistic and template-like object insertion conditioned on the desired class
using BERT [5] with a custom self-supervised optimization objective. We also
provide layout based retrieval results using the representations learned from
the self-supervised training. Our main contributions are:

  * •

A novel self-supervised masked language model LayoutBERT for layout
understanding,

  * •

Application to object insertion and layout retrieval using LayoutBERT,

  * •

State-of-the-art results on multiple datasets and ablation studies on the
largest known image layout dataset.

##  2 Related Work

There are several studies in the literature on deep image compositing [17, 15]
which use generative adversarial networks (GANs) [7] and specialized networks
such as spatial transformer networks (STNs) [9]. [17] trains sequential STN
generators: It iteratively applies geometric transformations (image warping)
on an initially placed foreground image and tries to generate a realistic
final composite image. [15] proposes two network modules, (1) _where_ and (2)
_what_ modules. The _where_ module generates realistic bounding boxes by
transforming a unit bounding box with a STN and the _what_ module uses that
bounding box to generate a semantic map for the desired class instance while
optimizing to make the final semantic map realistic. A separate model is
trained for each class, _e.g_. a pedestrian model and a car model in the case
of the Cityscapes dataset [4]. Unfortunately, neither of these approaches can
be scaled to larger model and to many classes.

Although GANs are proven to work very well on realistic image generation with
high fidelity, they are notoriously difficult to train and are not easily
scalable. Self-attention and transformer networks have been successfully used
to train billion parameter models and even a trillion parameters language
model [23]. Recently, multi-head self-attention has been used to train models
for layout generation and completion [8, 1]. An image can be represented as a
set of layout elements by extracting class and bounding box information of the
overall scene and of the objects in it. Similarly, a text document can be
represented by the bounding box information of different elements such as
titles, texts, graphs, and figures. The same idea can be extended to any
creative design like posters, flyers, invitation cards, etc. In this regard,
[8] trains an autoregressive model using a causal attention mask and maximizes
log-likelihood via a next token prediction task similar to [22] in a self-
supervised manner. [1] extends this idea by proposing a variational
autoencoder (VAE) to learn better representations using a BERT [5] like
encoder and a GPT [22] like decoder. Layout transformer models use only the
class and bounding box information extracted from the image pixel data. This
can be considered as a disadvantage over CNN-based models in terms of the
granularity of information, but this same property allows more efficient
training and inference, hence scalability.

Although previous layout transformer models can model the data likelihood and
the distribution, they are not optimal for the object insertion task. [8] can
generate or complete layouts but it can only attend to left context and cannot
see the whole scene at once, which is a major drawback for the object
insertion task. [1] can learn better representations and improve generation
diversity but that usually comes with the cost of likelihood. [15] directly
learns where to generate bounding boxes for object insertion with its _where_
module; however it requires training of a separate model for every class.
Also, a GAN objective makes it difficult to use ’too powerful’ discriminators
or generators. We argue that the object insertion task requires seeing the
whole scene at once, modeling long range dependencies in the scene with a
module like self-attention and large scale models. Our work combines and
extends ideas from prior art and can be considered similar to the _where_
module of [15] in terms of the task and to [8] in terms of the input
representation and multi-head self-attention mechanism. Layout understanding
is similar to scene understanding and using bidirectional context is a natural
choice for learning realistic layouts.

##  3 LayoutBERT

Our method treats image, document or template layouts as scene graphs and
tries to solve the object insertion task using a masked language modeling
objective. For this purpose we use a bidirectional transformer model like BERT
due to its popularity and name our method accordingly. That been said, our
custom masked language modeling objective for layout understanding can be used
with any of the transformer models like [14, 25, 3, 2] and even with a
bidirectional LSTM, GRU, or RNN. Original BERT model for NLP language modeling
is trained using two tasks: masked LM and next sentence prediction (NSP).
However, neither of these tasks are suitable for layout understanding and
object insertion. Masked LM objective picks individual tokens to be masked
during training, in contrast we iteratively mask a span of tokens which
correspond to a bounding box. Next Sentence Prediction is used for classifying
whether a sentence comes after another given sentence and cannot be used for
token generation in the context of the object insertion task. Also, [20] shows
that removing the NSP loss matches or slightly improves downstream NLP task
performance, hence not critical.

###  3.1 Layout Representation

To create input sequences for training we primarily follow the ideas from [8].
We use bounding box annotations of raw images, documents or templates
depending on the dataset. When bounding box annotations are not available and
during inference time we use a pretrained panoptic segmentation model [13] in
the case of images and an object detection model in the case of documents and
templates. We convert bounding boxes into a flat sequence using the raster
scan order. A sequence input is then represented as: _BOS,
$c_{1},x_{1},y_{1},w_{1},h_{1},c_{2},x_{2},y_{2},w_{2},h_{2}$, …, EOS_, where
_c,x,y,w,h_ stands for class token, top-left x coordinate, top-left y
coordinate, width and height tokens respectively. _BOS_ and _EOS_ are special
tokens: beginning and end of sentence. During tokenization each class id is
mapped to a unique class token, and _x,y,w,h_ tokens are mapped to discrete
space by splitting the 2D input into a $NXN$ grid similar to _anchors_ from
the object detection literature.

###  3.2 Model Architecture and Training

We use BERT architecture introduced in [5] and optimize it using a novel self-
supervised training objective for layout understanding. For the object
insertion task it is important to look at the whole context at once for
generating bounding boxes. This is where bidirectional attention comes to
play. During training we randomly select a bounding box and mask the 5 tokens
_c,x,y,w,h_ which represent it. We do it by creating 5 duplicates for each
sequence sample and masking all 5 tokens in the beginning and iteratively
unmasking the left-most token at each step as shown in 2. For each masked
sequence we try to predict the left-most masked token. This custom masked
language modeling objective allows our model to generate bounding boxes by
predicting c,x,y,w and h in a step-by-step fashion by mimicking autoregressive
likelihood models in the context of a single bounding box generation while
being able to attend to all the other bounding boxes with bidirectional
attention. During training time we also apply random left-right flip as data
augmentation on the 2D layout before converting it into a flat input sequence.

Instead of using teacher forcing with a decoder-only model like [8], we use a
BERT architecture with bidirectional attention and model the joint
distribution as:

$\displaystyle
p(\theta_{1:n_{i}})=\prod_{j=1}^{n_{i}}p(\theta_{j}|\theta_{1:j-1},\theta_{j+5-i+1:n_{i}})$
(1)

where $n_{i}=5(n-1)+i$ is the $i^{th}$ element of the $n^{th}$ box. For
example, $i=1$ for $c$, $i=2$ for $x$, $i=3$ for $y$, $i=4$ for $w$, and $i=5$
for $h$.

##  4 Experiments

In our evaluations, we refer to [8] as LayoutTransformer, our re-
implementation of [8] using GPT [22] model as LayoutGPT and all other methods
with their standard names.

###  4.1 Datasets

We evaluate our results on diverse datasets with natural scenes, documents,
and design templates. We use a separate hold-out set for training and validate
all models using the official validation splits for each dataset.

COCO [18] is a natural scene dataset with common objects which contains both
object class and _’stuff’_ class annotations. The object class contains a
predefined set of 80 common objects while the stuff class contains 92 non-
object annotations like sky, wall, grass and pavement. Stuff annotations are
as important as object annotations for understanding the overall scene and for
the object insertion task. We used COCO Panoptic 2017 dataset and followed the
same preparation steps as [8]. This resulted in 118,280 layouts in the
training split and 5,000 layouts in the validation split. The _other_ class in
the stuff annotations is ignored, resulting in final 80 thing and 91 stuff
classes.

PublayNet [27] is a public large scale dataset for document layout
understanding. It has 5 categories: text, title, figure, list and table.
Similarly, we followed [8] for data preparation steps including removing
layouts with more than 128 elements. This resulted in 335,682 and 11,245
documents layouts for training and validation splits respectively.

Image Layouts is a large scale image dataset with 5.8 million images crawled
from the web. Manually annotating such a large dataset is expensive and labor
intensive. For that reason we used a pretrained panoptic segmentation model
[13] available at [26] to generate stuff and object class bounding box
annotations. It has total of 133 stuff and object classes.

Template Layouts is a dataset with creative design templates such as posters,
flyers, collages, social media posts, ads and more. It has total of 45k
templates and 2 classes image and text.

The Image Layouts and Template Layouts datasets are not publicly available,
and are curated for experimentation on large scale layout understanding in
diverse domains.

###  4.2 Object Insertion

Our custom masked language model objective allows bounding box generation
given a layout sequence. This is useful for the object insertion task since
our model can predict the most likely class, location and scale to be
inserted. LayoutBERT is designed with the object insertion task in mind and
can attend to all the bounding boxes in the scene at once. In contrast,
previous work [8] is trained using a decoder-only autoregressive transformer
model for generation and can only attend to the left context. During our
qualitative analysis we used our own implementation of [8], LayoutGPT, since
there were no open-source code or models available for conducting our
experiments. Our re-implementation outperforms the results reported in the
original paper.

Object Class Recommendation. We can make class recommendations about which
foreground objects are more likely to be inserted into a given image, document
or template. For this purpose, we feed the input sequence to the model and get
the output probabilities at each token which give us the most likely
predictions for the next token. In the case of the LayoutBERT model, we insert
5 sequential masked tokens in every possible sequence location and get the
output probabilities for the masked class token.

For a simple sequence like _BOS, c, x, y, w, h, EOS_ with only 1 bounding box,
all possible mask insertions can be seen as:

  * •

Predict at position 1: _BOS,[MASK], [MASK], [MASK], [MASK], [MASK], c, x, y,
w, h, EOS_

  * •

Predict at position 2: _BOS, c, x, y, w, h,[MASK], [MASK], [MASK], [MASK],
[MASK], EOS_

where we get output probabilities for the masked class tokens denoted in bold.
Using these probabilities, we identify the most likely classes that can be
inserted after a given partial sequence and later use it for class conditional
bounding box generation. We provide top-1 accuracy results for class
recommendations in Table 1. The bidirectional masked language objective allows
LayoutBERT to learn correct object classes in all three datasets, showing a
significant improvements compared to previous approach.

| COCO | PublayNet | Template Lay.
---|---|---|---
LayoutGPT | 0.30 | 0.80 | 0.78
Ours | 0.44 | 0.95 | 0.86
Table 1: Top-1 accuracy class recommendation on COCO, PublayNet and Template
Layouts. Higher is better.

Bounding Box Generation. When the target class to be inserted is known, either
provided or recommended by the model, we can use the model probability outputs
at each token to identify the most likely sequence of locations to insert the
class token for bounding box generation. For generation with the LayoutGPT
model, we use beam search with top-k and top-p sampling with values k=15 and
p=0.9. For generation with LayoutBERT model, we use top-k sampling where k=3.
These values can be modified to control the level of diversity in bounding box
generation. Since LayoutGPT uses a causal mask, it only attends to the
previous tokens and is not able to incorporate bidirectional context like
LayoutBERT does. To incorporate bidirectional context to LayoutGPT model
during generation, we apply left-right flip as a test time augmentation (TTA).
For a simple sequence like _BOS, c, x, y, w, h, EOS_ with only 1 bounding box,
class conditional iterative bounding box generation at index position 1 can be
seen as:

  * •

Predict x: _BOS, c,[MASK], [MASK], [MASK], [MASK], c, x, y, w, h, EOS_

  * •

Predict y: _BOS, c, x,[MASK], [MASK], [MASK], c, x, y, w, h, EOS_

  * •

Predict w: _BOS, c, x, y,[MASK], [MASK], c, x, y, w, h, EOS_

  * •

Predict h: _BOS, c, x, y, w,[MASK], c, x, y, w, h, EOS_

We provide mean intersection over union (mIoU) results on class conditional
bounding box generations in Table 2. It is calculated by taking the average of
predicted and ground truth bounding box IoUs for a given sequence.

| COCO | PublayNet | Template Lay.
---|---|---|---
LayoutGPT | 0.31 | 0.52 | 0.21
Ours | 0.36 | 0.78 | 0.27
Table 2: Class conditional bounding box generation mIoU on COCO, PublayNet and
Template Layouts. Higher is better.

Scoring and Post-Processing. Each bounding box generation has an associated
output probability. This allows us to score any predicted bounding box _x, y,
w, h_ and use this score for ranking. We apply non-maximum suppression (NMS)
on our bounding box generations similar to popular object detection models
[6]. This allows us to remove bounding boxes with lower scores that overlap
too much. The NMS threshold is another controllable parameter like top-k and
top-p. After top scoring bounding boxes are obtained we can use alpha
composition to insert the object into the image. An example of such
compositing is given in Figure 1 where the same steps are applied to place 3
new objects in the original image.

Quantitative Results. Negative log-likelihood (NLL) is a common metric used in
previous works for the layout generation task. It is also a good choice for
assessing the object insertion task performance since it can be considered as
a proxy for class recommendation and bounding box generation accuracy. We
outperform current state-of-the-art model [8] across all datasets in terms of
the NLL metric shown in Table 3. We also compare LayoutBERT to prior art on
COCO in Table 4. It can be seen that class (Table 1) and bounding box (Table
2) prediction performance correlates with NLL (Table 3).

| LayoutTransformer [8] | LayoutGPT | Ours
---|---|---|---
COCO [18] | 2.67 | 2.57 | 2.32
PublayNet [27] | 1.28 | 1.14 | 0.63
Image Layouts | - | 2.26 | 2.08
Template Layouts | - | 2.19 | 1.98
Table 3: NLL results on COCO, Publaynet, Image Layouts and Template Layouts datasets using 64x64 anchor resolution. Model | NLL
---|---
LayoutVAE [11] | 3.29
ObjGAN [16] | 5.24
sg2sim [10] | 3.4
LayoutTransformer [8] | 2.28
Ours | 1.91
Table 4: NLL results on COCO using 32x32 anchor resolution. Lower is better.

Qualitative Results. During qualitative analysis we use the steps described in
4.2 and generate composites to be visualized. We pick random samples from the
validation set of each dataset, identify top-k classes to be inserted to each
sample and then conditionally generate the bounding boxes. In Figure 3 and
Figure 4 we insert the most likely bounding box for the top-1 predicted class
on PublayNet and Template Layouts datasets respectively, and visualize samples
side-by-side before and after the object insertion. In Figure 5, we identify
the top-5 classes for each sample from COCO dataset and generate class
conditional bounding boxes with top-k sampling to show diverse results.

Figure 3: Side-by-side view of before and after top-1 class bounding box
generation on PublayNet validation documents as described in 4.2. Purple:
text, yellow: table, white: title, cyan: figure, blue: list. Best viewed in
color. Figure 4: Side-by-side view of before and after top-1 class bounding
box generation on Template Layouts validation templates as described in 4.2.
Yellow: text, green: image. Best viewed in color. Figure 5: Class
recommendations and bounding box generations conditioned on top-5 classes
using COCO validation images as described in 4.2. Predicted classes are sorted
from left to right by their associated probability scores. We use k=3 for
top-k sampling during bounding box generation. Lighter bounding box color
means lower ranking score. Best viewed in color.

###  4.3 Layout Retrieval

Each GPT [22] feature at a given layer is calculated by attending only to the
previous tokens from the previous layer. We tried both the last feature from
the last hidden state and the average of all the features from the last hidden
state for generating representations for a given layout in the case of the
LayoutGPT model. During the qualitative comparison, the average of the last
hidden state gave better results, so we use it for extracting representations
to be used in the quantitative evaluation. BERT [5] uses bidirectional self-
attention so every feature can attend to every other feature from the previous
layer. So we use the average of the last hidden state to extract
representations in the case of the LayoutBert model.

Quantitative Results. During quantitative analysis, mean average precision at
k is used since it is a common choice for retrieval tasks and is widely used
for assessing ranked recommendations. None of the datasets used during
training were designed for a retrieval-by-layout task in mind, so they do not
have relevancy information for a given pair of images, documents or layout
templates. We conducted an external assessment job using a data annotation
platform which has experienced taskers to manually assess the performance of
the models. We ran jobs for the COCO, PublayNet and Layout Templates datasets
and compare the retrieval performance of LayoutGPT and LayoutBERT models.
During the COCO evaluation, actual images are shown to taskers, and during the
PublayNet and Layout Templates evaluations, rendered layouts with color-coded
bounding boxes are shown to taskers.

We use cosine similarity for retrieving similar layouts and report our results
on mAP@5. For a given query the top 5 retrieved layouts are shown for
assessment. For each dataset, we use the official validation set for retrieval
evaluation. We use 1k random samples as the query set and the remaining as the
recall set. Each query is shown to 3 different experienced taskers for final
metric calculation which we report in Table 5. Final mAP@5 is calculated by
taking the weighted average using _tasker trust scores_ :

$\displaystyle
mAP@5=\frac{1}{Q}\sum_{q=1}^{Q=1000}\sum_{n=1}^{3}AP_{qn}ts_{n}$ (2)

where $Q$ is the total number of queries, $AP_{qn}$ is the average precision
at 5 for query $q$ calculated by tasker $n$, and $ts_{n}$ is the trust score
for tasker $n$ normalized to 1. Ease of Job is rated by taskers on a scale of
1 to 5.

| LayoutGPT | Ours | Ease of Job
---|---|---|---
COCO [18] | 0.51 | 0.50 | 3.0/5
PublayNet [27] | 0.29 | 0.33 | 3.6/5
Template Lay. | 0.46 | 0.47 | 2.5/5
Table 5: Retrieval results mAP@5.

Qualitative Results. During qualitative analysis we use the representations
extracted from both models, retrieve the top neighbors based on cosine
similarity and visualize them side-by-side. Again, we use actual images for
COCO and rendered layouts for PublayNet and Layout Templates datasets. An
example of retrieval by layout can be seen in Figure 6.

Figure 6: Retrieval results on COCO, PublayNet and Template Layouts using
LayoutGPT and LayoutBERT. Left-most image is the query and the others are
top-k neighbors. We show (a,b) LayoutGPT and LayoutBERT on COCO, (c,d)
LayoutGPT and LayoutBERT on PublayNet, (e,f) LayoutGPT and LayoutBERT on
Template Layouts. Best viewed in color.

##  5 Scaling Studies

Here we study the effect of the dataset, model and class sample size. We
report ablation study results using our large scale Image Layouts dataset.

Training Details. Our small model consists of $d=256$, $L=4$, $n_{head}=4$,
and $d_{ff}=1024$, medium model consists of $d=512$, $L=6$, $n_{head}=8$, and
$d_{ff}=2048$, and large model consists of $d=768$, $L=12$, $n_{head}=12$, and
$d_{ff}=3072$. We also use a dropout of 0.1 at the end of each feed-forward
layer for regularization and GELU activation. We use Adam optimizer [12] with
decoupled weight decay [21] with an initial learning rate of $1e{-}3$ using
cosine annealing starting after completing 0.75 of training.

###  5.1 Effect of Dataset and Model Size

We randomly sub-sampled training data in 20%, 60%, and 100% chunks, and 100%
corresponds to 5.8 million layouts from the Image Layouts dataset. Each model
is trained with an equal number of forward passes and backward updates, and
using the same training schedule for fair comparison. Models with 100% of the
training data are trained for 1.2 epochs, 60% of the training data are trained
for 3 epochs and 20% of the training data are trained for 6 epochs. We plot
results in Figure 7 which shows that small and medium sized models are not
able to tolerate an increased number of samples as well as the large sized
model. Also, the large model outperforms its smaller counterparts overall.
This supports our motivation for creating a large scaled dataset for this task
and increasing the model capacity with it. [8] mentions that they do not
observe significant improvements beyond a 6-layer transformer model: However
that is not the case with our large scale dataset where LayoutBERT-large shows
a 3% improvement.

Figure 7: NLL plots of different model scales and sample sizes on Image
Layouts dataset.

###  5.2 Effect of Class Sample Size

We study the performance of each class in our large scale Image Layouts
dataset by plotting the NLL per class. There is a positive correlation between
class sample size and performance as seen in Figure 8. Common stuff classes
like _sky, wall, sea, tree, grass_ and object classes like _person_ have low
error rates, while rare classes like _toaster_ and _parking meter_ have much
higher error rates.

Figure 8: Class sample size vs. NLL.

##  6 Conclusion

Recent works on context-aware object synthesis and layout generation motivated
us to find a scalable solution for the object insertion task. Our
contributions allow modeling likelihood of hundreds of classes that can be
inserted into a given scene by using a novel self-supervised masked language
modeling objective and a bidirectional transformer model. Our method pushes
the state-of-the-art further on diverse set of data domains like complex
scenes, documents and design templates. We also show that deep bidirectional
architectures achieve better results as training data size increases. One
drawback of our approach is the limited input representation. In the case of
the scene datasets, we lose information by transforming the input signal from
the RGB domain to a 2D layout domain by limiting inputs to bounding boxes. In
future, we will work on methods which can directly take the raw input data yet
leverage the power of transformer models .

## References

  * [1] Diego Martin Arroyo, Janis Postels, and Federico Tombari.  Variational transformer networks for layout generation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13642–13652, 2021.
  * [2] Iz Beltagy, Matthew E Peters, and Arman Cohan.  Longformer: The long-document transformer.  arXiv preprint arXiv:2004.05150, 2020.
  * [3] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al.  Rethinking attention with performers.  arXiv preprint arXiv:2009.14794, 2020.
  * [4] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3213–3223, 2016.
  * [5] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [6] Ross Girshick.  Fast r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 1440–1448, 2015.
  * [7] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks.  Communications of the ACM, 63(11):139–144, 2020.
  * [8] Kamal Gupta, Justin Lazarow, Alessandro Achille, Larry S Davis, Vijay Mahadevan, and Abhinav Shrivastava.  Layouttransformer: Layout generation and completion with self-attention.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1004–1014, 2021.
  * [9] Max Jaderberg, Karen Simonyan, Andrew Zisserman, et al.  Spatial transformer networks.  Advances in neural information processing systems, 28:2017–2025, 2015.
  * [10] Justin Johnson, Agrim Gupta, and Li Fei-Fei.  Image generation from scene graphs.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1219–1228, 2018.
  * [11] Akash Abdu Jyothi, Thibaut Durand, Jiawei He, Leonid Sigal, and Greg Mori.  Layoutvae: Stochastic scene layout generation from a label set.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9895–9904, 2019.
  * [12] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [13] Alexander Kirillov, Kaiming He, Ross Girshick, Carsten Rother, and Piotr Dollár.  Panoptic segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9404–9413, 2019.
  * [14] Nikita Kitaev, Łukasz Kaiser, and Anselm Levskaya.  Reformer: The efficient transformer.  arXiv preprint arXiv:2001.04451, 2020.
  * [15] Donghoon Lee, Sifei Liu, Jinwei Gu, Ming-Yu Liu, Ming-Hsuan Yang, and Jan Kautz.  Context-aware synthesis and placement of object instances.  arXiv preprint arXiv:1812.02350, 2018.
  * [16] Wenbo Li, Pengchuan Zhang, Lei Zhang, Qiuyuan Huang, Xiaodong He, Siwei Lyu, and Jianfeng Gao.  Object-driven text-to-image synthesis via adversarial training.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12174–12182, 2019.
  * [17] Chen-Hsuan Lin, Ersin Yumer, Oliver Wang, Eli Shechtman, and Simon Lucey.  St-gan: Spatial transformer generative adversarial networks for image compositing.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9455–9464, 2018.
  * [18] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In European conference on computer vision, pages 740–755. Springer, 2014.
  * [19] Jun Ling, Han Xue, Li Song, Rong Xie, and Xiao Gu.  Region-aware adaptive instance normalization for image harmonization.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9361–9370, 2021.
  * [20] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  arXiv preprint arXiv:1907.11692, 2019.
  * [21] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  arXiv preprint arXiv:1711.05101, 2017.
  * [22] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever.  Improving language understanding by generative pre-training.  2018\.
  * [23] Adam Roberts, Colin Raffel, and Noam Shazeer.  How much knowledge can you pack into the parameters of a language model?  arXiv preprint arXiv:2002.08910, 2020.
  * [24] Yi-Hsuan Tsai, Xiaohui Shen, Zhe Lin, Kalyan Sunkavalli, Xin Lu, and Ming-Hsuan Yang.  Deep image harmonization, 2017.
  * [25] Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma.  Linformer: Self-attention with linear complexity.  arXiv preprint arXiv:2006.04768, 2020.
  * [26] Yuxin Wu, Alexander Kirillov, Francisco Massa, Wan-Yen Lo, and Ross Girshick.  Detectron2, 2019.
  * [27] Xu Zhong, Jianbin Tang, and Antonio Jimeno Yepes.  Publaynet: largest dataset ever for document layout analysis.  In 2019 International Conference on Document Analysis and Recognition (ICDAR), pages 1015–1022. IEEE, 2019.


# A Highly Efficient and Pure Few-Photon Source on Chip

Zhaohui Ma  Jia-Yang Chen, Malvika Garikapati, Zhan Li, Chao Tang, Yong Meng
Sua  Yu-Ping Huang<EMAIL_ADDRESS>Department of Physics, Stevens
Institute of Technology, 1 Castle Point Terrace, Hoboken, New Jersey, 07030,
USA  Center for Quantum Science and Engineering, Stevens Institute of
Technology, 1 Castle Point Terrace, Hoboken, New Jersey, 07030, USA

###### Abstract

We report on multi-photon statistics of correlated twin beams produced in a
periodic poled micro-ring resonator on thin-film lithium niobate. Owing to
high cavity confinement and near perfect quasi-phase matching, the photons
pairs are produced efficiently in single modes at rates reaching 27 MHz per
$\mu$W pump power. By using a pump laser whose pulse width impedance matches
with the cavity, those photons are further created in single longitudinal
modes with purity reaching 99%, without relying on later-on filtering. With a
dual-channel photon-number resolving detection system, we obtain directly the
joint detection probabilities of multi-photon states up to three photons, with
high coincidence to accidental contrast for each. Used as a single photon
source, it gives heralded $g_{H}^{(2)}(0)$ around 0.04 at a single photon rate
of 650 kHz on chip. The findings of our research highlight the potential of
this nanophotonic platform as a promising platform for generating non-
classical, few-photon states with ideal indistinguishability, for fundamental
quantum optics studies and information applications.

††preprint: APS/123-QED

##  I Introduction

Discrete photon-number and quantum entangled states are among the cornerstones
of quantum optics and its many information processing applications. Limited by
photon creation and measurement technology, most quantum applications hitherto
have been designed based on the uses of their lowest-order forms: single
photons or two of them in pairs. For example, quantum key distribution based
on BB84 uses antibunched single photon states[1], while quantum teleportation
takes advantage of two-photon entanglement[2]. Lately, the emergence of
photon-number resolving (PNR) capability in photon detection has open a door
to a new paradigm of quantum optics, where nonclassical states containing
multiple photons promise to offer significant advantages in computing and
sensing. In this pursuit, encouraging progress has been made in the generation
of multiphoton quantum states [3, 4], quantum interferometry using N00N states
[5, 6], quantum sensing using photon-number squeezing [7], and quantum
computing [8].

To capitalize on the quantum benefits of multiphoton states, it is desirable
to embed them in single optical modes. In bulky photon sources of spontaneous
parametric downconversion (SPDC) or four-wave mixing, to meet this condition
usually requires ultra-narrow band filtering or using ultra-short, broadband
pump pulses [4, 9, 10], either of which add significantly to system complexity
and footprint. In contrast, nanophotonic circuits with high Q cavities can
create photons intrinsically in single spatial and temporal modes of high
purity. For example, a $\chi^{(3)}$ microring was shown to produce squeezed
states in good single modes, albeit suffering parametric fluorescence emission
into multiple cavity lines [11].

Here, we demonstrate an on-chip $\chi^{(2)}$ source of multiphoton states in
quasi-phase matched microrings of lithium niobate on insulator (LNOI). Due to
subwavelength lateral confinement, the photons are created in single
transverse (spatial) modes of high purity. With a high cavity Q and by using a
pump laser whose pulse width impedance-matches with the cavity, those photons
are further created in single longitudinal (time-frequency) modes with purity
reaching 99%, without relying on later-on filtering. Such high purity in both
spatial and time-frequency modes gives rise to high indistinguishability, as
desirable for many quantum computing, teleportation, and sensing applications.
Aided by nearly perfect quasi phase matching through periodic poling, the
photon generation efficiency is exceptional, where only microwatt pump power
is required to create single, double, and triplet photon states of high
correlation and at megahertz rates. Such high purity and high efficiency
contribute to the device scaling and wide deployment. Together with narrow
cavity bandwidth, they suppress background noise created through, e.g., Raman
scattering or fluorescence emission. On detection, we use photon-number
resolving, superconducting nanowire single-photon detectors (PNR-SNSPDs) built
in a parallel circuit configuration to accurately characterize the photon
number statistics and time correlation of multiphoton states with picosecond
resolution. Our results show high coincident to accidental ratios for photon
counts in one, two, and three photon states. Finally, we show how this system
can be used for heralded single-photon generation at 10 MHz clock speed. [12,
13].

Device Calibration and Experiment Setup. Figure 1 gives device details of the
on-chip multiphoton source. As shown in Fig. 1.(a), it is a perodically poled
microring cavity fabricated on a Z-cut LNOI wafer (by NANOLN Inc.), with a
600-nm thick lithium niobate thin film bonded onto a 2-$\mu$m silicon dioxide
layer above a silicon substrate. Utilizing our standard fabrication method
[14], a top width of 1.6$\mu$m and a radius of 80$\mu$m perodically poled
lithium niobate (PPLN) microring is etched with a pulley bus wavguide as the
coupler. The loaded quality factor ($Q_{l}$) is measured for each mode, and
the coupling ($Q_{c}$) and intrinsic ($Q_{0}$) factors are each calculated by
fitting the resonance spectra; see result in Fig. 1.(b). The chip is fiber
coupled, with the fiber-chip-fiber coupling losses measured to be 9.2 ± 0.2 dB
at 1553.93 nm and 11.5 ± 0.3 dB at 776.96 nm, respectively. The overall
optical nonlinearity is characterized by second harmonic generation (SHG),
similarly to our previous measurement [15]. With an on-chip pump power $P_{p}$
of 4.78$\mu$W, $P_{\mathrm{SH}}=75$ nW of second harmonic light is coupled out
into the bus waveguide. The SHG efficiency is thus
$\eta_{\mathrm{SHG}}=P_{\mathrm{SH}}/P^{2}_{p}=0.33\%/\mu W$, thus supporting
highly efficient SPDC using only microwatt pumping.

In a single-mode cavity, the effective Hamiltonian describing quasi-phase
matched, non-degenerate spontaneous parametric downconversion can be written
as follows:

$\hat{H}_{\textbf{eff}}=\hbar\mathnormal{g}(\hat{a}_{s}\hat{a}_{i}\hat{b}_{p}^{\dagger}+\hat{a}_{s}^{\dagger}\hat{a}_{i}^{\dagger}\hat{b}_{p}),$
(1)

where $\\{$$\hat{a}_{s}$, $\hat{a}_{i}$, and $\hat{a}_{p}$$\\}$ each denotes
the annihilation operator for the signal, idler, and pump photons, and
$\mathnormal{g}$ is the nonlinear coupling coefficient between the pump and
photon pairs. By periodic poling, the current lithium niobate micro-ring
resonator can achieve phase matching while attaining the largest overlap
between the fundamental quasi-transverse magnetic (quasi-TM) cavity modes in
the infrared bands for the signal and idler photons and the visible band for
the pump. Meanwhile, it provides the access to the largest $\chi^{(2)}$
nonlinear tensor $d_{33}$ of lithium niobate. All contribute to a large
effective nonlinear coupling coefficient $g$, which is given by [14]

${g}=\sqrt{\frac{\hbar\omega_{p}\omega_{s}\omega_{i}}{2\epsilon_{0}\epsilon_{p}\epsilon_{s}\epsilon_{i}}}\frac{\frac{2}{\pi}d_{\mathrm{eff}}\zeta}{\sqrt{V_{\mathrm{eff}}}},$
(2)

where $\omega_{j}$ is the angular frequency, with $j$=$p$,$s$, and $i$
indicates the pump, signal, and idler modes, respectively. $\epsilon_{0}$ is
the vacuum permittivity. $\\{\epsilon_{j}\\}$ are the relative permittivities.
$d_{\mathrm{eff}}$ is the effective nonlinear susceptibility with the quasi
phase matching discount. $\zeta$ is the mode-overlapping factor.
$V_{\mathrm{eff}}$ is the effective mode volume. For the current microring
device, the calculated single-photon coupling strength $g$ is 2.98 MHz.

Figure 1:  (a): Schematic of the Z-cut periodical poling microring resonator,
where the pump ($\omega_{P}$) couples into the microring and generates signal
($\omega_{S}$) and idler ($\omega_{I}$). A pulley coupler is designed for
overcoupling all light waves for high photon-extraction efficiency. Inset
shows an SEM image of the microring with the pulley waveguide. Figure 1 (b)
plots the typical spectra of interacting TM00 cavity modes at (i) 776.96 nm,
(ii) 1551.85 nm, and (iii) 1555.93 nm Figure 2:  Experiment setup. VA,
Variable Attenuator; DWDM, Dense wavelength-division multiplexing; TT, Time
Tagger unit; Sync, synchronise cable. Figure 3:  Photon number statistics for
different mean photon numbers.

Figure 2 illustrates the experiment setup for generating and detecting
photons. A visible pulse train with a pulse duration of $\tau$=300 ps and a
repetition rate of 10MHz is created with a bulk SHG system made of a periodic-
poled lithium niobate waveguide, to match the cavity lifetime and ensure
single-mode operations; see details in Appendix A. Its power is varied by
using a visible fiber attenuator (OZ OPTICS), and its polarization is
controlled using fiber polarization controllers (FPCs). The output is fed into
the microring cavity to excite the quasi-TM visible mode at 776.96 nm with a
bandwidth of 1.14 GHz. There, signal and idler photons are created through
SPDC into 1551.85 nm and 1555.93 nm quasi-TM modes, respectively, each in
bandwidth of 1.68 GHz. The SPDC efficiency is tracked and maximized by
temperature tuning using a temperature electronic controller (TEC).
Subsequently, the generated photon pairs are filtered using an inline long-
pass filter featuring an 80 dB extinction ratio and a 0.5 dB insertion loss
(IL) to eliminate the pump power while transmitting the generated photon
pairs.

In order to separate the signal and idler photons, cascaded dense wavelength
division multiplexing (DWDM) filters with a full width at half maximum (FWHM)
transmission bandwidth of 1.6 nm are employed, resulting in a transmission
loss of approximately 0.3 dB. A pair of FPCs are then utilized to
independently prepare the signal and idler photons in the best polarization
states to be detected by the SNSPDs with the maximum detection efficiency. The
two-channel PNR-SNSPDs (ID281, ID Quantique) feature a dark count rate of 50
to 100 Hz and detection efficiencies of 70% (corresponding to 1.55 dB loss)
and 82% (0.86 dB loss), respectively. The detector outputs are fed to a
synchronized time-tagging unit (Swabian Instrument). Accounting for all
insertion losses, chip-fiber coupling losses, and finite detection
efficiencies, the signal and idler channels experience a total loss of
$\eta_{\mathrm{S}}$=7.55 dB and $\eta_{\mathrm{I}}$=6.76 dB, respectively.

Figure 4:  (a) Detected photon distribution, thermal light and coherent light
fitting at a mean photon number of approximately 0.0137. (b) Detected photon
distribution, thermal light and coherent light fitting at a mean photon number
of approximately 0.008.

Photon Number Statistics. Upon carefully calibrating the chip device and
SNSPDs, we proceed to measure the photon number statistics of the signal and
idler photons while varying the input pump power. For the signal channel, the
measurement results are shown in Fig. 3, where the normalized probabilities of
detecting 0, 1, 2, and 3 photons are plotted along with error bar (assuming
shot noise) under various mean photon number. As shown, the overall photon
number distribution follows thermal distribution, as expected. As the mean
photon number increases, the relative probabilities of multiple photon events
increase. For example, when the mean photon number is 0.0028, the normalized
probabilities for one, two, and three photons are $2.80\times 10^{-3}$,
$7.85\times 10^{-6}$, and $3.03\times 10^{-7}$, respectively. As we increase
it to 0.0137, they each become $1.37\times 10^{-2}$, $1.91\times 10^{-4}$, and
$1.77\times 10^{-6}$. Because the SPDC saturated regime of multi-photon starts
at mean photon number of 0.0137, there will be no obvious increasing at three-
photon case. In the figure, the error bars for three-photon events are higher
because of much less detection events so that the Poissonian noise is more
pronounced.

To further show that our SPDC source indeed operates in the single-mode range,
in Fig. 4 we compare the measurement results with ideal thermal light
distribution (TLD) in a single mode for two mean photon number cases: 0.0137
and 0.008. The TLD follows $P(n)=\bar{n}^{n}/(1+\bar{n})^{n+1}$, where $n$ and
$\bar{n}$ denote the photon number and their mean, respectively. As seen, in
both cases the measurement results agree well with TLD for the one and two
photon cases. Compared with the coherent light distribution, there is a
clearly deviation. For the three photon case, there is noticeable discrepancy,
which can primarily be ascribed to the threshold sensitivity encountered in
higher photon situations for the present SNSPD system. These results verify
that our SPDC photons are in single modes, as desirable for many quantum
information and quantum computing processes.

Photon correlation. Next, we characterize the one-photon and two-photon pair
generation, by measuring their rates in each individual channel and jointly
over paired SPDC channels. Specifically, we record the events of detecting one
and two photons in the signal channel, with rates $N_{S}$ and $N_{SS}$,
respectively, and in the idler channel with $N_{I}$ and $N_{II}$.
Simultaneously, we record the one-photon coincident events where there is one
photon detected in each channel, with rate $N_{SI}$, as well as two-photon
coincident events for two photons per channel with rate $N_{SSII}$.

From these rates, the on-chip generation rate for the one-photon pairs is
estimated to the first order as $P_{SI}=N_{S}N_{I}/N_{SI}$. The results are
plotted as a function of the on-chip SPDC pump power in Fig. 5.(a). As shown,
$P_{SI}$ increases linearly with the power, as expected. Only 220 nW power is
needed to create 7 million pairs per second. By linear regression, the
brightness, defined as pair generation per unit pump power, is obtained as the
slope of the fitting curve as 27 MHz/${\mu}$W, which is among the highest
across all SPDC sources in various materials. The detection rate corresponds
to ten times higher than our previous result [16], which is ascribed to the
higher efficiencies in both photon pair generation and detection.

Similarly, for the two-photon pairs (i.e., two signal photons and two idler
photons generated simultaneously in pairs), the on-chip rate under first order
approximation is
$P_{\mathrm{SSII}}=N_{\mathrm{SS}}N_{\mathrm{II}}/N_{\mathrm{SSII}}$. The
results as a function of the on-chip pump power are plotted in Fig. 5.(b). In
contrast to the one-photon pair case, here the rate increases quadratically
over the power, because the underline process is of the second order in SPDC.
At 220 nW pumping, the two-photon pair on-chip rate is 8.6($10^{4}$), and
increase to 9.5($10^{6}$) at 1.12 $\mu$W.

Figure 5:  On-chip generation rates for one-photon pairs (a) and two-photon
pairs (b), respectively, along with their curve fitting results.

The above results are from simple calculations under the first order
approximation. To further characterize the mutliphoton correlation, we count
the joint events of mixed photon numbers and use loss inversion to calculate
the inferred joint states of photon numbers [4]. The results for 0.137 mean
photon number on chip are shown in Fig. 6, where we neglect the contributions
from detector dark counts and ambient photons (about 100 Hz). As seen, while
the photon numbers in the signal and idler channels are correlated, the
correlation is not strong. This is mainly due to the high total loss of each
channel (7.55 dB and 6.76 dB) and the low coincidence events of multiphoton
states, because of which the loss inversion calculation is not very accurate.

Figure 6:  Coincidence photon probability at average pump power around
1.1$\mu$W. Table 1: CAR measured at average power around 1.1$\mu$W

|  S(0) |  S(1) |  S(2) |  S(3)
---|---|---|---|---
I(0) |  $1.17\times 10^{9}$:$1.16\times 10^{9}$ |  $1.34\times 10^{7}$:$1.51\times 10^{7}$ |  $1.54\times 10^{5}$:$1.93\times 10^{5}$ | 296:373
I(1) |  $1.44\times 10^{7}$:$1.61\times 10^{7}$ |  $1.84\times 10^{6}$:$2.10\times 10^{5}$ |  $3.88\times 10^{4}$:$2.73\times 10^{3}$ | 77:5
I(2) |  $1.80\times 10^{5}$:$2.24\times 10^{5}$ |  $4.38\times 10^{4}$:$2.93\times 10^{3}$ |  $3.52\times 10^{3}$:35 |  8:0
I(3) |  $1.52\times 10^{3}$:$1.94\times 10^{4}$ |  412:22 |  35:0 |  3:0

To get a better measurement, we exam the coincident detection of the various
multiphoton states. The results for the same pump power as in Fig. 6 are given
in Table I as the coincidence-to-accidental counting rates of one, two, and
three photons in each channel. Here, the coincidence rates between S($n$) and
I($m$) are for event occurrences of simultaneously detecting $n$ signal
photons and $m$ idler photons in the same time slot (in this case each of 400
ps width). The accidental rates are for those events occuring in a different
slot, set by 100 ns apart to avoid any correlation. As seen, the coincidence
to accidental detection ratio is about 10 for single-photon pairs, and 100 for
two-photon pairs, which shows high correlation. Over our total acquistion
period of 120 seconds, we record 3 coincidence of three photon pairs, but no
accidental event. Interestingly, in the Figure, the coincident rates are not
maximized at diagonal. For example, the coincident detection of one signal
photon and two idler photons is more likely than that of two signal and two
idler photons. This is because although signal and idler photons are created
on chip with strong photon number correlation, the total loss is about 7 dB
per channel so that only a fraction of them can be detected thus blurring the
correlation.

From Table I, the mutual correlation function can be calculated
$g^{(n,m)}=\langle\hat{a}^{\dagger n}\hat{a}^{n}\hat{b}^{\dagger
m}\hat{b}^{m}\rangle/{\langle\hat{a}^{\dagger}\hat{a}\rangle}^{n}{\langle\hat{b}^{\dagger}\hat{b}\rangle}^{m}$.
To satisfy the non-classical criteria [3, 17], the following condition must be
met: $\gamma=g^{(1,2)}/\sqrt{g^{(2,2)}g^{(0,2)}}>1$. From the pump power
ranging from 220 nW to 1.12 $\mu$W, we have calculated $\gamma$ to between 1.3
and 1.6, indicating good quantum correlation.

Figure 7:  Heralded $g_{H}^{(2)}{(0)}$ for signal (a) and idler photons (b).  Table 2: Mode Purity in Various Photon Sources Reference | Material Structure | Quality Factor | Pulse Width | $g^{(2)}$ | $K$ | Purity
---|---|---|---|---|---|---
Eckstein[9] | PPKTP111Periodically Poled Potassium Titanyl Phosphate Waveguide | N/A | 1ps | 1.95 | 1.05 | 95%
Harder[4] | PPKTP Waveguide | N/A | 1ps | 1.89 | 1.12 | 89%
Stasi[13] | PPKTP Waveguide | N/A | 1ps | 1.99 | 1.01 | 99%
Vaidya[11] |  $Si_{3}N_{4}$ $\mu$-ring | $8(10^{5})$ | 1.5ns | 1.95 | 1.05 | 95%
This work | PPLN $\mu$-ring | $1.15(10^{5})$ | 300ps | 1.99 | 1.01 | 99%

We next study the prospective use of this source for heralded single photon
generation. Figure 7 plots the heralded photon correlation for both channels
under various pump power. In contrast to standard Hanbury Brown and Twiss
effect (HBT) measurement using a beamsplitter, here we utilize the collected
multiphoton statistics directly by the PNR-SNSPDs. In this case, the second-
order correlation function at $\tau$=0 without heralding, denoted as
$g^{(2)}(0)$, is given by $g^{(2)}(0)=\sum n(n-1)P(n)/(\sum nP(n))^{2}$. The
results are around 1.99 to 2.25 (see given in the Appendix B), verifying the
thermal statistics of each SPDC channel under the single-mode condition. In
the heralding case, on the other hand, the same statistics is taken only when
there is one photon clicking event in the paired channel. In this case, the
correlation becomes $g^{(2)}_{H}(0)=\sum n(n-1)P(n|1)/(\sum nP(n|1))^{2}$,
where $P(n|m)=P(n,m)/P(m)$ is the conditional probability of detecting $n$
photons in one channel upon detecting $m$ photons in the other, computed from
the joint detection probability of $m$ and $n$ photons in the two channels and
that of a single one. With the coincidence counts from two PNR-SNSPDs, we can
easily compute $P(n|1)$ for both signal and idler channels. As seem in the
figure, for both channels, $g^{(2)}_{H}(0)$ is about 0.01 when the mean photon
numbers are $0.003$ per pulse and increases to approaching 0.05 as the mean
photon numbers increase to $0.014$.

Finally, we compare the time-frequency mode purity obtained here with
competing sources. The results are summarized in Table II. In waveguides, it
typically requires to use picosecond pump pulses so as to match the optical
filters for the generated photons, to obtain single modes. In comparison,
those based on resonators, such as the present microrings, the pump pulses can
be much longer, ranging from a few hundred picoseconds to nanoseconds in order
to match with the cavity’s lifetime for single modes. In this device, the
effective mode number $K=1/[g^{(2)}(0)-1]$ is at 1.01, which is very close to
the ideal case with $K=1$ [4]. This represents a mode purity of $1/K=99\pm
4.9\%$, indicating an optimal condition for single mode photon production, as
desirable for many applications.

In conclusion, we have demonstrated photon statistics with a two-channel PNR-
SNSPD system, characterizing single-photon and multiphoton pair generation.
Utilizing an ideally quasi phase matched lithium niobate microring in Z cut,
we have scored a ten-fold enhancement in the SPDC generation rate of single-
photon pairs [16]. We measured joint photon probabilities of multiphoton
states up to three photons in a channel. Also, we have performed coincident to
accidental photon detection for multiphoton states using time-delayed
measurement, for the first time. Our results highlight a SPDC source for
multiphoton entanglement with both high efficiency and mode purity, as needed
for many quantum information processing applications with multiphoton states.
This work paves the way for the development of advanced quantum photonic
devices and systems with good performance and versatility.

Figure 8:  Setup for generate the SPDC pump. Blue and red lines depict the
telecom light path and visible path, respectively. FPC, fiber-polarization
controller; EOM, Electro-Optic modulator; PM, power meter; EDFA, Erbium-Doped
Fiber Amplifier; WDM, wavelength division multiplexing module; LP, Low pass
filter; BP, bandpass filter; DUT, device under test.

###### Acknowledgements.

The research was supported in part by the Office of Naval Research (Award No.
N00014-21-1-2898) and by ACC-New Jersey (Contract No. W15QKN-18-D-0040).
Device fabrication was performed at ASRC, CUNY.

##  Appendix A SPDC Pump Generation

Figure 9:  Pulse width measurement

To create the SPDC pump pulses in the visible band, a single-channel
picosecond EOM (electro-optical modulator) driver (Highland Technology T130,
250ps-30ns pulse width, 0-50MHz pulse rate) supplies Radiofrequency
pulse(10MHz) to the EOM. An IR power meter monitors the EOM output. An erbium-
doped fiber amplifier (EDFA) in the telecom C band further amplifies the weak
signal, followed by two DWDM filters to clean the beam. The resulted signal
then couples into a bulk PPLN crystal to create the visible pulsed light as
the SPDC pump. Two low-pass-filters(IL $\sim$ 0.5 dB; extinction ratio, ER
$\sim$ 50 dB) and narrow-band-pass-filters(Alluxa, 3 nm, IL$\sim$ 1 dB, ER $>$
120 dB) reject the pump signal and passing largest light at 776.96nm.

In Figure 9, we measure the cross-correlation between photons created by the
signal cavity and the synchronized electronic pulse from EO Driver by using a
time tagger. The full width at half maximum is around 320 ps. Due to the EO
Driver jitter(10 ps) and PNR-SNSPDs jitter(54 ps), it is slightly wider than
the electronic pulse(300 ps).

##  Appendix B Signal and Idler $g^{(2)}{(0)}$ Measurement

Figure 10(a) and 3(b) plot the photon correlation measurement of the signal
and idler channel using two PNR-SNSPDs, before heralding. Here the second-
order correlation function is calculated from the PNR-SNSPD results as
$g_{\mathrm{unc}}^{(2)}(0)=\sum n(n-1)P(n)/(\sum nP(n))^{2}$. As seen, for
both channels $g^{(2)}_{\mathrm{unc}}(0)\approx 2$ for each channel at
different mean photon number.

Figure 10:  (a) and (b): Unheralded two-photon correlation in signal and idler
channels.

## References

  * Bennet [1984] C. Bennet, Quantum cryptography: Public key distribution and coin tossing, in  _Proc. of IEEE Int. Conf. on Comp. Sys. and Signal Proc., Dec. 1984_ (1984).
  * Bennett  _et al._ [1993] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels, Physical review letters 70, 1895 (1993).
  * Avenhaus  _et al._ [2010] M. Avenhaus, K. Laiho, and M. Chekhova, Accessing higher order correlations in quantum optical states by time multiplexing, Physical review letters 104, 063602 (2010).
  * Harder  _et al._ [2016] G. Harder, T. J. Bartley, A. E. Lita, S. W. Nam, T. Gerrits, and C. Silberhorn, Single-mode parametric-down-conversion states with 50 photons as a source for mesoscopic quantum optics, Physical review letters 116, 143601 (2016).
  * Thekkadath  _et al._ [2020] G. Thekkadath, M. Mycroft, B. Bell, C. Wade, A. Eckstein, D. Phillips, R. Patel, A. Buraczewski, A. Lita, _et al._ , Quantum-enhanced interferometry with large heralded photon-number states, NPJ quantum information 6, 89 (2020).
  * Qin  _et al._ [2023] J. Qin, Y.-H. Deng, H.-S. Zhong, L.-C. Peng, H. Su, Y.-H. Luo, J.-M. Xu, D. Wu, S.-Q. Gong, H.-L. Liu, _et al._ , Unconditional and robust quantum metrological advantage beyond n00n states, Physical Review Letters 130, 070801 (2023).
  * Frascella  _et al._ [2021] G. Frascella, S. Agne, F. Y. Khalili, and M. V. Chekhova, Overcoming detection loss and noise in squeezing-based optical sensing, npj Quantum Information 7, 72 (2021).
  * Arrazola  _et al._ [2021] J. Arrazola, V. Bergholm, K. Brádler, T. Bromley, M. Collins, I. Dhand, A. Fumagalli, T. Gerrits, A. Goussev, L. Helt, _et al._ , Quantum circuits with many photons on a programmable nanophotonic chip, Nature 591, 54 (2021).
  * Eckstein  _et al._ [2011] A. Eckstein, A. Christ, P. J. Mosley, and C. Silberhorn, Highly efficient single-pass source of pulsed single-mode twin beams of light, Physical Review Letters 106, 013603 (2011).
  * Avenhaus  _et al._ [2008] M. Avenhaus, H. Coldenstrodt-Ronge, K. Laiho, W. Mauerer, I. Walmsley, and C. Silberhorn, Photon number statistics of multimode parametric down-conversion, Physical review letters 101, 053601 (2008).
  * Morrison  _et al._ [2020] B. Morrison, L. Helt, R. Shahrokshahi, D. Mahler, M. Collins, K. Tan, J. Lavoie, A. Repingon, M. Menotti, _et al._ , Broadband quadrature-squeezed vacuum and nonclassical photon number correlations from a nanophotonic device, Science advances 6, eaba9186 (2020).
  * Davis  _et al._ [2022] S. I. Davis, A. Mueller, R. Valivarthi, N. Lauk, L. Narvaez, B. Korzh, A. D. Beyer, O. Cerri, M. Colangelo, K. K. Berggren, _et al._ , Improved heralded single-photon source with a photon-number-resolving superconducting nanowire detector, Physical Review Applied 18, 064007 (2022).
  * Stasi  _et al._ [2022] L. Stasi, P. Caspar, T. Brydges, H. Zbinden, F. Bussières, and R. Thew, Enhanced heralded single-photon source with a photon-number-resolving parallel superconducting nanowire single-photon detector, arXiv preprint arXiv:2210.16005 (2022).
  * Chen  _et al._ [2021] J.-Y. Chen, Z. Li, Z. Ma, C. Tang, H. Fan, Y. M. Sua, and Y.-P. Huang, Photon conversion and interaction in a quasi-phase-matched microresonator, Physical Review Applied 16, 064004 (2021).
  * Chen  _et al._ [2019] J.-Y. Chen, Z.-H. Ma, Y. M. Sua, Z. Li, C. Tang, and Y.-P. Huang, Ultra-efficient frequency conversion in quasi-phase-matched lithium niobate microrings, Optica 6, 1244 (2019).
  * Ma  _et al._ [2020] Z. Ma, J.-Y. Chen, Z. Li, C. Tang, Y. M. Sua, H. Fan, and Y.-P. Huang, Ultrabright quantum photon sources on chip, Physical Review Letters 125, 263602 (2020).
  * Vogel [2008] W. Vogel, Nonclassical correlation properties of radiation fields, Physical review letters 100, 013605 (2008).


Run Distribution Over Flattened Partitions
Olivia Nabawanda111Corresponding author.
Department of Mathematics
Makerere University
P.O.Box 7062
Kampala, Uganda
<EMAIL_ADDRESS>

Fanja Rakotondrajao
Département de Mathématiques et Informatique
Université d’Antananarivo, Antananarivo
Antananarivo, Madagascar
<EMAIL_ADDRESS>

Alex Samuel Bamunoba
Department of Mathematics
Makerere University
P.O.Box 7062
Kampala, Uganda
<EMAIL_ADDRESS>

###### Abstract

The study of flattened partitions is an active area of current research. In
this paper, our study unexpectedly leads us to the OEIS numbers A124324. We
provide a new combinatorial interpretation of these numbers. A combinatorial
bijection between flattened partitions over $[n+1]$ and the partitions of
$[n]$ is also given in a separate section. We introduce the numbers $f_{n,k}$
which count the number of flattened partitions over $[n]$ having $k$ runs. We
give recurrence relations defining them, as well as their exponential
generating function in differential form. It should be appreciated if its
closed form is established. We extend the results to flattened partitions
where the first $s$ integers belong to different runs. Combinatorial proofs
are given.

##  1 Introduction and preliminaries

The study of the different statistics of permutations such as descents,
ascents, excedances and runs has a long history and has been an area of
intensive research in the past years. A lot of work is available in the
literature [6, 11, 14, 17, 18]. These statistics play an important role in
combinatorics and mathematics as a whole.

For a given positive integer $n$, we will denote the set $\\{1,2,\ldots,n\\}$
by $[n]$. A permutation $\sigma$ over $[n]$ will be represented as a word
$\sigma(1)\sigma(2)\cdots\sigma(n)$. We say that $\sigma$ has an ascent
(descent) at position $i$ if $\sigma(i)<\sigma(i+1)\,(\sigma(i)>\sigma(i+1))$,
where $i\in[n]$. A run in a permutation $\sigma$ is a subword
$\sigma(i)\sigma(i+1)\cdots\sigma(i+p)\sigma(i+p+1)$ where $i,i+1,\ldots,i+p$
are consecutive ascents. In this case, $i-1$ (if it does exist) and $i+p+1$
are non ascents, where $i\in[n]$. For example, in $\sigma=526134$, we have
ascents at positions $2,4$ and $5$. It also has descents at positions $1$ and
$3$. The last element $4$ of $\sigma$ at position $6$ is neither an ascent nor
a descent. A right to left minimum of a permutation $\sigma$ is an element
$\sigma(i)$ such that $\sigma(i)<\sigma(j)$ for all $j>i$. For example, in
$\sigma=1246357$, the right to left minima are $\\{1,2,3,5,7\\}$.

Counting permutations according to the number of runs has been studied from
various perspectives in enumerative combinatorics. Canfield and Wilf [4]
considered a run as a subsequence of a permutation $\sigma$, whose values
either increase on the interval (run up) or decrease on the interval (run
down). More related work on permutation runs can also be found in articles [2,
9, 10, 20]. A permutation $\pi$ is said to be a flattened partition if it
consists of runs arranged from left to right such that their first entries are
in increasing order. It is clear that the first run always starts with $1$,
and so all flattened partitions start with the integer $1$. For example,
consider a permutation $\sigma=139278456$. This is a flattened partition with
three runs namely: $139,278,456$ whose first entries $1,2,4$ are in increasing
order. However, the permutation $\sigma=139456287$ is not a flattened
partition since the first entries $1,4,2,7$, of the runs $139,456,28,7$ are
not in increasing order. Given a non-empty finite subset $S$ of positive
integers, a set partition $P$ of $S$ is a collection of disjoint non-empty
subsets $B_{1},B_{2},\ldots,B_{k}$ of $S$ (called blocks) such that
$\displaystyle\cup_{i=1}^{k}B_{i}=S$ [12, 16]. We shall maintain the name and
notion of “flattened partition” introduced by Callan [3]. Callan borrowed the
notion “flatten” from $Mathematica^{\textregistered}$ programming language,
where it acts by taking lists of sets arranged in increasing order, removes
their parentheses, and writes them as a single list [19]. Mansour et al. [13]
also used the same notion. To generate flattened partitions, the elements of
each block are written as increasing subsequences, and blocks arranged from
left to right in increasing order of their first entries. Carlitz [5] also
applied the notion “flatten” to permutations expressed in cycle notation.

We will let $\mathcal{F}_{n}$ denote the set of all flattened partitions over
$[n]$, $\mathcal{F}_{n,k}$ the set consisting of all flattened partitions over
$[n]$ having $k$ runs, $f_{n,k}$ the cardinality of the set
$\mathcal{F}_{n,k}$. In Table 1, we give the first few values of the numbers
$f_{n,k}$.

$n$ $k$ | $1$ | 2 | 3 | 4 | 5
---|---|---|---|---|---
$1$ | 1 |  |  |  |
2 | 1 |  |  |  |
3 | 1 | 1 |  |  |
4 | 1 | 4 | 0 |  |
5 | 1 | 11 | 3 | 0 |
6 | 1 | 26 | 25 | 0 | 0
Table 1: The numbers $f_{n,k}$

We notice that the terms in the column for $k=2$ of Table 1 correspond to the
Eulerian numbers. Foata and Schützenberger [7] gave the fundamental work on
these numbers. Mantaci and Rakotondrajao [15] gave a new combinatorial
interpretation to the same. Many other references concerning Eulerian numbers
can be found on the OEIS A000295. In Section 2, we establish different
recurrence relations of the numbers $f_{n,k}$ and give their combinatorial
proofs. We also define the exponential generating function $F(x,u)$ of the
numbers $f_{n,k}$ which is defined by

$F(x,u)=\sum_{n\geq 0}\sum_{k\geq 0}f_{n,k}x^{k}\frac{u^{n}}{n!}=\sum_{n\geq
0}\sum_{\sigma\in\mathcal{F}_{n}}x^{run(\sigma)}\frac{u^{n}}{n!},$

where $run(\sigma)$ is the number of runs in a flattened partition $\sigma$.
In Section 3, we generalize the results in Section 2 to flattened partitions
over $[n]$ whose first $s$ integers belong to different runs . We let
$f_{n,k}^{(s)}$ denote the number of flattened partitions over $[n]$ whose
first $s$ integers belong to different runs, and $F^{[s]}(x,u)$ the
exponential generating function for the numbers $f_{n,k}^{(s)}$. The first few
values of $f_{n,k}^{(s)}$ for $s=2$ and $s=3$ are shown in Table 3 and 3:

$n$ $k$ | $2$ | 3 | 4 | 5
---|---|---|---|---
$2$ | 0 |  |  |
3 | 1 | 0 |  |
4 | 3 | 0 |  |
5 | 7 | 3 | 0 |
6 | 15 | 22 | 0 |
7 | 31 | 106 | 14 | 0
Table 2: The numbers $f_{n,k}^{(2)}$

$n$ $k$ | $3$ | 4 | 5
---|---|---|---
4 | 0 |  |
5 | 2 | 0 |
6 | 12 | 0 |
7 | 50 | 12 | 0
8 | 180 | 139 | 0
Table 3: The numbers $f_{n,k}^{(3)}$

Mansour et al. [13] give a recursive formula for the number of flattened
partitions over $[n]$, and also mention that the number of distinct
permutations that can be obtained as flattened partitions over $[n]$ is the
Bell number $B_{n-1}$. Let $\mathcal{P}_{n}$ denote the collection of
partitions of $[n]$. Our study led us to the OEIS A124324 which counts the
number of partitions of $[n]$ having $k$ blocks of size greater than $1$.

The authors of the present paper were introduced to the OEIS A124324 by Heinz
[8] who gave a maple program for computing the terms of this sequence
recursively. The first maple program which computes this sequence using the
exponential generating function was given by Emeric Deutsch. A combinatorial
bijection between elements of $\mathcal{P}_{n}$ having $(k-1)$ blocks of size
greater than $1$ and $\mathcal{F}_{n+1,k}$ will be given in Section 4.

##  2 Flattened partitions and their behaviours on runs

###  2.1 Recurrence relations

We have $f_{n,1}=1$ for all $n\geq 1$ and $f_{n,k}=0$ for all $k\geq n\geq 2$.
It is not possible to have a flattened partition over $[n]$ whose number of
runs $k$ is greater or equal to its length.

######  Theorem 1.

For all integers $n$ and $k$ such that $2\leq k<n$, the numbers $f_{n,k}$ of
flattened partitions over $[n]$ with $k$ runs satisfy the recurrence relation

$f_{n,k}=\sum_{m=1}^{n-2}\bigg{(}{n-1\choose m}-1\bigg{)}f_{m,k-1}.$ (1)

###### Proof.

To construct a flattened partition $\pi$ over $[n]$ having $k$ runs, we
consider a flattened partition $\tau$ over $[m]$ having $k-1$ runs, for an
integer $m<n$. Since all flattened partitions start with element $1$, we
insert the word of length $n-m$ starting with $1$, before a flattened
partition $\tau$ to obtain $1\underbrace{\dots}_{n-m-1}\underbrace{\tau}_{m}$,
and then re-order the elements of $\tau$ making sure the number of runs
increase by one. The $n-m-1$ elements between $1$ and $\tau$ can be chosen
from the set $\\{2,3,4,\ldots,n\\}$ of $(n-1)$ terms in $\displaystyle
n-1\choose n-m-1$ ways. In order to increase the number of runs by one, we
avoid choosing the subset $\\{2,3,\ldots,n-m-1\\}$ of consecutive elements. We
thus have $\displaystyle\bigg{(}{n-1\choose n-m-1}-1\bigg{)}$ possible subsets
to be inserted after $1$. The minimum number of elements in the first run is
$2$, implying that the maximum length of $\tau$ is $n-2$. Since $n\geq 3$,
then the minimum length of $\tau$ is $1$. Thus we have that $1\leq m\leq n-2$.
Thus summing up over $1\leq m\leq n-2$ gives the recurrence relation in
Equation (1). ∎

######  Example 2.

Let us construct flattened partitions over $[6]$ having $3$ runs from a
flattened partition $\tau$ over $[3]$ having $2$ runs. We have $\tau=132$. The
favorable subsets of two terms from the set $\\{2,3,4,5,6\\}$ are:
$\\{2,4\\},\\{2,5\\},\\{2,6\\},\\{3,4\\},\\{3,5\\},\\{3,6\\},\\{4,5\\},\\{4,6\\},\\{5,6\\}$.
Consider the pair $(\\{3,4\\},\tau)$, we get $\pi=134265$. For the pair
$(\\{4,6\\},\tau)$, we get $\pi=146253$.

Let $a_{n}$ denote the maximum number of runs $k$ in a flattened partition of
$[n]$. From Table 1 above, we see that the maximum number of runs, $a_{n}$
results into a sequence $1,1,2,2,3,3,4,4,5,5,\ldots,$ for $n\geq 1$.

######  Proposition 3.

The maximal number $a_{n}$ of runs in a flattened partition over $[n]$
satisfies the relation

$a_{n}=a_{n-2}+1,$

for all $n\geq 2$, with initial conditions $a_{0}=0,a_{1}=1$.

###### Proof.

Let $n$ be an integer such that $n\geq 2$. Consider a flattened partition
$\tau$ over $[n-2]$ having maximal number of runs. Using the construction in
Theorem 1, inserting two elements $1x$ where $x=\\{3,4,\ldots,n\\}$ before
$\tau$ and re-ordering the elements of $\tau$ can only add a maximum of $1$
run. Hence we have $a_{n}\geq a_{n-2}+1$. On the other hand, inserting $n-2$
elements between $1$ and the identity $\tau=1$ from the construction in the
same theorem, we have $1\underbrace{\cdots}_{n-2}1$ and then re-ordering the
elements of $\tau$. This means the subsets between $1$ and $\tau$ can be
chosen from the set $\\{3,4,\ldots,n\\}$ of $n-2$ elements whose maximum
number of runs is $a_{n-2}$. Hence we have $a_{n}\leq a_{n-2}+1$. These two
inequalities, together with $a_{0}=0$ and $a_{1}=1$, yield $a_{n}=a_{n-2}+1$.
∎

As an obvious conclusion, we have the following corollary:

######  Corollary 4.

The maximal number of runs $a_{n}$ in a flattened partition over $[n]$ has the
closed form $\displaystyle\dfrac{1}{4}\big{(}2n+(-1)^{n+1}+1\big{)}$ and its
generating function $\displaystyle Y(x)=\sum_{n=0}^{\infty}a_{n}x^{n}$ is
given by $\dfrac{1}{(1-x)^{2}(1+x)}$.

If $a$ is a starting point of a run in a flattened partition $\pi$ and $x$ is
an integer such that $x<a$, then $\pi^{-1}(x)<\pi^{-1}(a)$. In other words,
all integers smaller than $a$ are on its left. By contradiction, suppose there
exists an $x<a$ on the right of $a$. Then $x$ is an element of another run.
This makes the starting points of the runs of $\pi$ not to be in increasing
order, which contradicts $\pi$ being a flattened partition. Hence $x$ should
be on the left of $a$.

Let $\mathcal{C}_{n,k}$ denote the set of flattened partitions over $[n]$ of
the form $1X2\cdots$, having $k$ runs, where $X\in\\{3,4,5,\ldots,n\\}$. More
precisely, each partition in $\mathcal{C}_{n,k}$ has only two elements in the
first run. For example, we have $\mathcal{C}_{5,2}=\\{13245,14235,15234\\}$.

From the construction in Theorem 1, we have the following corollary:

######  Corollary 5.

For all integers $n$ and $k$ such that $1\leq k<n$, the cardinality of the set
$\mathcal{C}_{n,k}$ is $(n-2)f_{n-2,k-1}$.

Let $\mathcal{K}_{n,k}$ denote the set of flattened partitions over $[n]$
having $k$ runs and containing either the subword $\mathbf{2n1}$ or the
integer $\mathbf{n}$ at the end. In other words, deleting the integer n does
not affect the number of runs. Let $\mathcal{L}_{n,k}$ denote the set of
flattened partitions over $[n]$ having $k$ runs and containing the subword
$\mathbf{1n2}$, the set where deleting the integer n reduces the number of
runs by $1$. For example, we have $\mathcal{L}_{5,2}=\\{12354,12534,15234\\}$
and $\mathcal{K}_{5,2}=\\{14523,14235,13524,13452,13425,13245,12453,12435\\}$.

######  Remark 6.

The sets $\mathcal{K}_{n,k}$ and $\mathcal{L}_{n,k}$ are mutually exclusive,
i.e., $\mathcal{K}_{n,k}\cap\mathcal{L}_{n,k}=\emptyset$ and form a partition
of the set $\mathcal{F}_{n,k}$, i.e.,
$\mathcal{F}_{n,k}=\mathcal{K}_{n,k}\cup\mathcal{L}_{n,k}$.

For all integers $n$ and $k$ such that $1\leq k<n$, the cardinalities of the
sets $\mathcal{C}_{n,k}$ and $\mathcal{L}_{n,k}$ are equal. We will use a
variation of the bijection defined by Beyene and Mantaci [1, p. 5] to
construct a combinatorial bijection between the two sets.

Let us consider the map $f:\mathcal{C}_{n,k}\rightarrow\mathcal{L}_{n,k}$
defined as follows: for each $\pi\in\mathcal{C}_{n,k}$, delete the subword
$1X$ and let $\tau$ be the standardized form of the remaining elements. Insert
the subword $n(X-1)$ after the smallest rightmost element to $(X-1)$ in $\tau$
and re- order to get $\sigma=f(\pi)\in\mathcal{L}_{n,k}$.

######  Example 7.

Let us illustrate the map $f$ with $n=5$ and $k=2$. We have
$C_{5,2}=\\{13245,14235,15234\\}$. For $\pi=13245$, then $\tau=123$ and
$\sigma=15234$ i.e., $f(13245)=15234$. Similarly, $f(14235)=12534$,
$f(15234)=12354$.

######  Proposition 8.

The map $f:\mathcal{C}_{n,k}\rightarrow\mathcal{L}_{n,k}$ is a bijection.

###### Proof.

We will prove that $f$ is surjective and injective.

  * (i)

Surjectivity. Let $g:\mathcal{L}_{n,k}\rightarrow\mathcal{C}_{n,k}$ be defined
as follows: for each $\sigma\in\mathcal{L}_{n,k}$, delete the subword $nX$ and
let $\tau$ be the standardized form of the remaining. Insert the subword
$1(X+1)$ before $\tau$ and re-order to get $\pi\in\mathcal{C}_{n,k}$. It is
obvious that $g$ is the inverse map of $f$.

  * (ii)

Injectivity. Let $\pi_{1}$ and $\pi_{2}$ be two elements in
$\mathcal{C}_{n,k}$ such that $f(\pi_{1})=f(\pi_{2})$. Necessarily,
$\tau_{1}=\tau_{2}$ and hence $\pi_{1}=\pi_{2}$.

∎

Let us illustrate the map $f^{-1}$ with $n=5$ and $k=2$. We have
$\mathcal{L}_{n,k}=\\{12354,12534,15234\\}$. For $\sigma=12354$, then
$\tau=123$ and $\pi=15234$ i.e., $f^{-1}(12354)=15234$. Similarly,
$f^{-1}(12534)=14235$, $f^{-1}(15234)=13245$.

######  Theorem 9.

For all integers $n$ and $k$ such that $1\leq k<n$, the cardinality of the set
$\mathcal{K}_{n,k}$ is $kf_{n-1,k}$.

###### Proof.

Let us construct the elements of $\mathcal{K}_{n,k}$. Let
$\pi\in\mathcal{F}_{n-1,k}$. Inserting $n$ at the end of a run of $\pi$ does
not change the number of runs. There are $k$ possibilities of such insertions.
This generates $k$ flattened partitions in the set $\mathcal{K}_{n,k}$. Thus
$|\mathcal{K}_{n,k}|=kf_{n-1,k}$. ∎

######  Theorem 10.

For all integers $n$ and $k$ such that $1\leq k<n$,
$f_{n,k}=kf_{n-1,k}+(n-2)f_{n-2,k-1}$.

###### Proof.

From Remark 6, we have that
$|\mathcal{F}_{n,k}|=|\mathcal{K}_{n,k}|+|\mathcal{L}_{n,k}|$. Using Theorem
9, Proposition 8 and Corollary 5, we then have that

$f_{n,k}=kf_{n-1,k}+(n-2)f_{n-2,k-1}.$ (2)

∎

######  Corollary 11.

For all integers $n$ and $k$ such that $1\leq k<n$, we have

$kf_{n,k}=\sum_{m=1}^{n-2}\bigg{(}\binom{n}{m}-1\bigg{)}f_{m,k-1}.$

###### Proof.

Considering Equation (1) and Equation (2), we deduce the result. ∎

We still do not have a direct combinatorial proof of Corollary 11, and it
remains an open problem worth investigating.

######  Theorem 12.

For all integers $n$ and $k$ such that $1\leq k\leq n$, the numbers
$f_{n+2,k}$ of flattened partitions over $[n+2]$ having $k$ runs satisfy the
recurrence relation

$f_{n+2,k}=f_{n+1,k}+\sum_{i=1}^{n}\binom{n}{i}f_{n+1-i,k-1}.$ (3)

###### Proof.

To construct a flattened partition $\pi$ over $[n+2]$ for all $n\geq 0$ having
$k$ runs, we use the property that the first two terms $1$ and $2$ of $\pi$
are either in the same run or in different runs. We consider these two
possibilities to enumerate $f_{n+2,k}$.

  1. 1.

If $1$ and $2$ are in the same run, by the construction in Theorem 1, $\pi$ is
of the form $\pi=1\underbrace{\tau}_{n+1}$, where $\tau$ is a subword of
length $n+1$ whose starting integer is $2$. Deleting $1$ of $\pi$ and reducing
each of the remaining terms by $1$ gives a flattened partition of length
$n+1$, with the same number of runs $k$ i.e., $f_{n+1,k}$.

  2. 2.

If $1$ and $2$ are in different runs, suppose the first run has $(i+1)$ terms
including the first term $1$. Using Theorem 1, the remaining $(i+1)-1=i$ terms
in the first run can be chosen from the set $\\{3,4,\ldots,n+2\\}$ of
$(n+2)-2=n$ terms. This is because the positions of $1$ and $2$ in $\pi$ are
already known. There are $\displaystyle{n\choose i}$ ways to do this. The
remaining $k-1$ runs have length $(n+2)-(i+1)=n+1-i$. Hence we have
$f_{n+1-i,k-1}$ flattened partitions over $[n+1-i]$ with $k-1$ runs. Since the
length of the first run including $1$ varies between $2$ and $n+1$, the number
of flattened partitions over $[n+2]$ with $1$ and $2$ in different runs is
given by $\displaystyle\sum_{i=1}^{n}{n\choose i}f_{n+1-i,k-1}$.

Adding these two cases together gives

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

∎

###  2.2 Generating function

######  Theorem 13.

The exponential generating function $F(x,u)$ of the run distribution over
flattened partitions has the closed differential form

$\frac{\partial F(x,u)}{\partial u}=x\exp(x(\exp(u)-1)+u(1-x)),$ (4)

with initial condition $\dfrac{\partial F(x,0)}{\partial u}=x$.

###### Proof.

We have

$F(x,u)=\sum_{n\geq 1}\sum_{k\geq 1}f_{n,k}x^{k}\frac{u^{n}}{n!}=\sum_{n\geq
1}f_{n}(x)\frac{u^{n}}{n!}.$

where $f_{n}(x)$ is the polynomial defined by $\displaystyle\sum_{k\geq
1}f_{n,k}x^{k}=f_{n}(x)$.

From Equation (3), multiplying by $\displaystyle x^{k}\frac{u^{n}}{n!}$ and
summing over $k$ and $n$ gives

$\sum_{n\geq 1}\sum_{k\geq 1}f_{n+2,k}x^{k}\frac{u^{n}}{n!}=\sum_{n\geq
1}\sum_{k\geq 1}\bigg{(}f_{n+1,k}+\sum_{i=1}^{n}{n\choose
i}f_{n+1-i,k-1}\bigg{)}x^{k}\frac{u^{n}}{n!}.$ (5)

Equation (5) can be rewritten as $A=B+C$, where

$A=\sum_{n\geq 1}\sum_{k\geq 1}f_{n+2,k}x^{k}\frac{u^{n}}{n!},$ $B=\sum_{n\geq
1}\sum_{k\geq 1}f_{n+1,k}x^{k}\frac{u^{n}}{n!},$

and

$C=\sum_{n\geq 1}\sum_{k\geq 1}\bigg{(}\sum_{i=1}^{n}{n\choose
i}f_{n+1-i,k-1}x^{k}\frac{u^{n}}{n!}\bigg{)}.$

We have

$A=\frac{\partial^{2}F}{\partial u^{2}},\ B=\frac{\partial F}{\partial u}.$
(6)

Fixing $i$ and summing over $k$ in $C$ gives

$C=\sum_{n\geq 1}\sum_{i=1}^{n}{n\choose i}\bigg{(}\sum_{k\geq
1}f_{n+1-i,k-1}x^{k}\bigg{)}\frac{u^{n}}{n!}.$ (7)

Equation (7) can be re-written as

$C=x\sum_{n\geq 1}\sum_{i=1}^{n}{n\choose i}\bigg{(}\sum_{k\geq
1}f_{n+1-i,k-1}x^{k-1}\bigg{)}\frac{u^{n}}{n!}.$ (8)

Expanding the binomial coefficient $\displaystyle{n\choose i}$ in Equation (8)
and simplifying gives

$\displaystyle C$ $\displaystyle=x\sum_{n\geq
1}\sum_{i=1}^{n}\frac{u^{i}}{i!}\bigg{(}\sum_{k\geq
1}f_{(n-i)+1,k-1}x^{k-1}\frac{u^{(n-i)}}{(n-i)!}\bigg{)}$
$\displaystyle=x\sum_{i=1}^{\infty}\frac{u^{i}}{i!}\bigg{(}\sum_{n\geq
i}\sum_{k\geq 1}f_{(n-i)+1,k-1}x^{k-1}\frac{u^{(n-i)}}{(n-i)!}\bigg{)}$
$\displaystyle=x\sum_{i=1}^{\infty}\frac{u^{i}}{i!}\bigg{(}\sum_{n\geq
i}f_{(n-i)+1}(x)\frac{u^{n-i}}{(n-i)!}\bigg{)}.$

We have

$\displaystyle C$
$\displaystyle=x\sum_{i=1}^{\infty}\frac{u^{i}}{i!}\frac{\partial
F(x,u)}{\partial u}$ $\displaystyle=x(\exp(u)-1)\frac{\partial
F(x,u)}{\partial u}.$

Substituting Equation (6) and $C=x(\exp(u)-1)\dfrac{\partial F(x,u)}{\partial
u}$ into Equation (5) gives

$\frac{\partial^{2}F(x,u)}{\partial u^{2}}=\frac{\partial F(x,u)}{\partial
u}+x(\exp(u)-1)\frac{\partial F(x,u)}{\partial u}.$ (9)

Let $V=\dfrac{\partial F(x,u)}{\partial u}$. Then

$\frac{\partial V}{\partial u}=\frac{\partial^{2}F(x,u)}{\partial u^{2}}.$

Substituting $V$ into Equation (9) gives

$\frac{\partial V}{\partial u}=V\big{(}x(\exp(u)-1)+1\big{)}$ (10)

with initial condition $V(x,0)=x$. Solving for $V$ in Equation (10) gives

$V=\frac{\partial F(x,u)}{\partial u}=x\exp(-x)\exp({(x(\exp(u)-u)+u)}).$

∎

##  3 Flattened partitions with the first $s$ terms in different runs

We recall that $f_{n,k}^{(s)}$ and $F^{[s]}(x,u)$ are the number of flattened
partitions over $[n]$ whose first $s$ integers belong to different runs and
the exponential generating function for the numbers $f_{n,k}^{(s)}$
respectively.

######  Theorem 14.

For all integers $s,k$ and $n$ such that $1\leq s\leq k<n$, the numbers
$f_{n+s,k}^{(s)}$ satisfy the relation

$f_{n+s,k}^{(s)}=\sum_{i_{1},i_{2},\ldots,i_{s}\geq
1}\binom{n}{i_{1}}\binom{n-i_{1}}{i_{2}}\cdots\binom{n-\sum_{j=1}^{s-1}i_{j}}{i_{s}}f_{n-\sum_{j=1}^{s}i_{j},k-s}.$
(11)

###### Proof.

Let $\pi$ be a flattened partition over $[n+s]$ having $k$ runs. Let
$i_{1}+1,i_{2}+1,i_{3}+1,\ldots,i_{s}+1$ be the lengths of the $s$ first runs
whose starting points are $1,2,\ldots,s$ respectively. Since the first run,
including $1$ has length $i_{1}+1$, we have $i_{1}$ terms to arrange out of
the $(n+s)-s=n$ terms. There are ${n\choose i_{1}}$ ways. For the second run,
it remains to arrange $i_{2}$ terms out of $n-i_{1}$ terms. There are
$\displaystyle{n-i_{1}\choose i_{2}}$ ways. Repeating the same process up to
the $s^{th}$ run inductively gives $\displaystyle{n-i_{1}-i_{2}-\cdots-
i_{s-1}\choose i_{s}}={n-\sum_{j=1}^{s-1}i_{j}\choose i_{s}}$ possibilities.
The remaining $k-s$ runs have length
$(n+s)-((i_{1}+1)+(i_{2}+1)+\cdots(i_{s}+1))=\displaystyle
n-\sum_{j=1}^{s}i_{j}$. So we have $\displaystyle{n\choose
i_{1}}{n-i_{1}\choose i_{2}}\cdots{n-\sum_{j=1}^{s-1}i_{j}\choose
i_{s}}f_{n-\sum_{j=1}^{s}i_{j},k-s}$. Summing over all possibilities of
$i_{1},i_{2},\ldots,i_{s}\geq 1$ gives the result. ∎

######  Theorem 15.

The exponential generating function $F^{[s]}(x,u)$ for the numbers
$f_{n,k}^{(s)}$ has the closed differential form

$\frac{\partial^{s}F^{[s]}(x,u)}{\partial u^{s}}=(\displaystyle
x(\exp(u)-1))^{s}F(x,u).$ (12)

###### Proof.

We have

$F^{[s]}(x,u)=\sum_{n=1}^{\infty}\sum_{k\geq
1}f_{n+s,k}^{(s)}x^{k}\frac{u^{n}}{n!}.$

From Equation (11), multiplying by $\displaystyle x^{k}\frac{u^{n}}{n!}$ and
summing over $k$ and $n$ gives

$\sum_{n\geq 1}\sum_{k\geq s}f_{n+s,k}^{(s)}x^{k}\frac{u^{n}}{n!}=\sum_{n\geq
1}\sum_{k\geq s}\bigg{(}\sum_{i_{1},i_{2},\ldots,i_{s}\geq 1}{n\choose
i_{1}}\cdots{n-\sum_{j=1}^{s-1}i_{j}\choose
i_{s}}f_{n-\sum_{j=1}^{s}i_{j},k-s}\bigg{)}x^{k}\frac{u^{n}}{n!}$ (13)

Let

$L=\sum_{n\geq 1}\sum_{k\geq s}f_{n+s,k}^{(s)}x^{k}\frac{u^{n}}{n!},$

and

$M=\sum_{n\geq 1}\sum_{k\geq s}\bigg{(}\sum_{i_{1},i_{2},\ldots,i_{s}\geq
1}{n\choose i_{1}}{n-i_{1}\choose i_{2}}\cdots{n-\sum_{j=1}^{s-1}i_{j}\choose
i_{s}}f_{n-\sum_{j=1}^{s}i_{j},k-s}\bigg{)}x^{k}\frac{u^{n}}{n!}.$

We have

$L=\dfrac{\partial^{s}F^{[s]}(x,u)}{\partial u^{s}}.$ (14)

Fixing $i$ and summing over $k$ gives

$\displaystyle M$ $\displaystyle=\sum_{n\geq
1}\sum_{i_{1},i_{2},\ldots,i_{s}\geq 1}\bigg{(}\sum_{k}x^{s}{n\choose
i_{1}}{n-i_{1}\choose i_{2}}\cdots{n-\sum_{j=1}^{s-1}i_{j}\choose
i_{s}}f_{n-\sum_{j=1}^{s}i_{j},k-s}x^{k-s}\bigg{)}\frac{u^{n}}{n!}$
$\displaystyle=x^{s}\sum_{i_{1},i_{2},\ldots,i_{s}=1}^{\infty}{n\choose
i_{1}}{n-i_{1}\choose i_{2}}\cdots{n-\sum_{j=1}^{s-1}i_{j}\choose
i_{s}}\bigg{(}\sum_{n\geq i_{1},i_{2},\ldots,i_{s}}\sum_{k\geq
s}f_{n-\sum_{j=1}^{s}i_{j},k-s}x^{k-s}\frac{u^{n}}{n!}\bigg{)}$
$\displaystyle=x^{s}\sum_{i_{1},i_{2},\ldots,i_{s}=1}^{\infty}\frac{n!}{(n-i_{1})!i_{1}!}\cdots\frac{(n-\sum_{j=1}^{s-1}i_{j})!}{(n-\sum_{j=1}^{s}i_{j})!i_{s}!}\bigg{(}\sum_{n\geq
i_{1},i_{2},\ldots,i_{s}}\sum_{k\geq
s}f_{n-\sum_{j=1}^{s}i_{j},k-s}x^{k-s}\frac{u^{n}}{n!}\bigg{)}$
$\displaystyle=x^{s}\sum_{i_{1},i_{2},\ldots,i_{s}=1}^{\infty}\frac{u^{i_{1}}}{i_{1}!}\frac{u^{i_{2}}}{i_{2}!}\cdots\frac{u^{i_{s}}}{i_{s}!}\bigg{(}\sum_{n\geq
i_{1},i_{2},\ldots,i_{s}}\sum_{k\geq
s}f_{n-\sum_{j=1}^{s}i_{j},k-s}x^{k-s}\frac{u^{n-\sum_{j=1}^{s}i_{j}}}{(n-\sum_{j=1}^{s}i_{j})!}\bigg{)}$
$\displaystyle=(\displaystyle x(\exp(u)-1))^{\normalsize s}F(x,u).$

Substituting Equation (14) and $M=(\displaystyle x(\exp(u)-1))^{\normalsize
s}F(x,u)$ into Equation (13) gives the result. ∎

##  4 Bijection between flattened partitions over $[n+1]$ and partitions of
$[n]$

Let $P\in\mathcal{P}_{n}$ be a partition of $[n]$, written as
$P=B_{1}|B_{2}|\cdots|B_{k}$ where the elements in each block $B_{i}$ are
written in increasing order. We will write $P$ as $P^{\prime}$ in such a way
that in each block, the smallest element appears at the end but still
maintaining the remaining elements. We construct a word $P_{+}$ from
$P^{\prime}$ by deleting the marks $``|"$ enclosing the different blocks of
$P^{\prime}$ and then increasing all the terms by $1$.

Let $f:\mathcal{P}_{n}\rightarrow\mathcal{F}_{n+1}$ be a map which associates
a partition $P$ of $[n]$ with a flattened partition defined by
$f(P)=\sigma=1P_{+}$. The map $f$ is well defined since if $P_{1}$ and $P_{2}$
are two set partitions over $[n]$ and assume that $P_{1}=P_{2}$, then
$f(P_{1})=1P_{1+}=1P_{2+}=f(P_{2})$.

######  Proposition 16.

The map $f:\mathcal{P}_{n}\rightarrow\mathcal{F}_{n+1}$ is a bijection.

###### Proof.

Since both $\mathcal{P}_{n}$ and $\mathcal{F}_{n+1}$ are finite with the same
size $B_{n}$, it suffices to prove that $f$ is injective. Let $P_{1}$ and
$P_{2}$ be two partitions of $[n]$. Assume that $f(P_{1})=f(P_{2})$. Then by
definition, $1P_{1+}=1P_{2+}$. Since the map $f$ is well defined, the strings
$P_{1+}$ and $P_{2+}$ are equal after deleting $1$ from the front. Thus
$P_{1}=P_{2}$. ∎

######  Example 17.

Consider a partition $P=12|3|45$ of $[5]$. Re-ordering $P$ such that in each
block, the smallest entry appears at the end of the partition gives
$P^{\prime}=21|3|54$. Then $P_{+}=32465$. And thus $\sigma=1P_{+}=132465$.

Let $\sigma\in\mathcal{F}_{n+1}$ having $k$ runs. Let us define
$P=f^{-1}(\sigma)$ as follows: Insert the mark $``|"$ at the end of each right
to left minimum of $\sigma$. Delete element $1$. Re-order to get the blocks of
the partition $P$.

######  Example 18.

Consider a flattened partition $\sigma=132465$ over $[6]$. Inserting the mark
$``|"$ at the end of each right to left minimum $1|32|4|65|$. Deleting $1$ and
re-ordering the remaining gives the partition $P=12|3|45$.

We now give a property of our bijection. This bijection preserves the number
of blocks of size greater than $1$ in a partition and the number of runs of
its corresponding flattened partition.

######  Theorem 19.

For any integer $n\geq 0$, if $P$ is a partition over $[n]$ and $\sigma$ its
corresponding flattened partition over $[n+1]$, then the following assertions
are equivalent:

  1. (i)

the number of blocks of size greater than $1$ of the partition $P$ is $k-1$,

  2. (ii)

the number of runs of the flattened partition $\sigma$ is equal to $k$.

###### Proof.

For $n=0$, $1$ is the only flattened partition corresponding to the empty set.
Consider a partition $P$ of $[n]$ having $(k-1)$ blocks of size greater than
$1$. Using the construction of the map $f$, we write each of the blocks in
such a way that the smallest elements of each block appear at the end. Thus
the smallest elements become the starting points for a run in a flattened
partition $\sigma=f(P)$ if the block has at least two elements as well as
integer $1$. The element of singleton blocks becomes a right to left minimum
in $\sigma$ and is not a starting point of a run. So $\sigma$ has $k$ runs.

Conversely, consider a flattened partition $\sigma$ having $k$ runs. Placing a
mark $``|"$ after the right to left minima will form a partition of $[n+1]$.
Since a starting point of a run is preceded by a greater element, except the
integer $1$, the blocks with two or more elements consist of those containing
a starting point. Deleting the integer $1$ and re-ordering the remaining
blocks will give $(k-1)$ blocks of size greater than $1$. ∎

In Example 17, the partition $P$ has $2$ blocks of size greater than $1$ and
the corresponding flattened partition, $\sigma$ has $3$ runs.

##  5 Acknowledgment

We would like to thank the editor and the anonymous referee for their comments
and useful suggestions. This work was financially supported by the Swedish
Sida bilateral program with Makerere University, 2015-2020, project 316
“Capacity building in Mathematics and its applications”. The first author
would like to thank in a special way Prof. Paul Vaderlind (Stockholm
University), Prof. Roberto Mantaci (University Paris Diderot 7) and the
Département de Mathématiques et Informatique, Université d’ Antananarivo for
hosting her during research visits.

## References

  * [1] F. Beyene and R. Mantaci, Exhaustive generation algorithm for flattened set partitions, preprint, 2020. Available at https://cutt.ly/xorkr2M.
  * [2] M. Bóna and R. Ehrenborg, A combinatorial proof of the log-concavity of the number of permutations with k runs, J. Combin. Theory Ser. A 90 (2000), 293–303.
  * [3] D. Callan, Pattern avoidance in “flattened” partitions, Discrete Math. 309 (2009), 4187–4191.
  * [4] E. R. Canfield and H.S. Wilf, Counting permutations by their alternating runs, J. Combin. Theory Ser. A 115 (2008), 213–225.
  * [5] L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University (1968), 8–15.
  * [6] R. Ehrenborg and E. Steingrimsson, The excedance set of a permutation, Adv. Appl. Math. 24 (2000), 284–299.
  * [7] D. Foata and M. P. Schützenberger, Théorie Géométrique des Polynômes Eulériens, Springer, 2006.
  * [8] A. Heinz, Personal communication to the second author.
  * [9] S. Ma, An explicit formula for the number of permutations with a given number of alternating runs, J. Combin. Theory Ser. A 119 (2012), 1660–1664.
  * [10] S. Ma, Enumeration of permutations by number of alternating runs, Discrete Math. 313 (2013), 1816–1822.
  * [11] P. A. MacMahon, Combinatorial Analysis, Academic Press, 1960.
  * [12] T. Mansour, Combinatorics of Set Partitions, CRC Press, 2012.
  * [13] T. Mansour, M. Shattuck, and S. Wagner, Counting subwords in flattened partitions of sets, Discrete Math. 338 (2015), 1989–2005.
  * [14] R. Mantaci and F. Rakotondrajao, Exceedingly deranging!, Adv. Appl. Math. 30 (2003), 177–188.
  * [15] R. Mantaci and F. Rakotondrajao, A permutation representation that knows what Eulerian means, Discrete Math. Theor. Comput. Sci. 4 (2001), 101–108.
  * [16] G. Rota, The number of partitions of a set, Amer. Math. Monthly 71 (1964), 498–504.
  * [17] N. J. A. Sloane et al., The on-line encyclopedia of integer sequences, Available at https://oeis.org, 2019.
  * [18] J. Steinhardt, Permutations with ascending and descending blocks, Electron. J. Combin. 17 (2010), #R14.
  * [19] S. Wolfram, The Mathematica Book, Cambridge University Press, 2000.
  * [20] Y. Zhuang, Counting permutations by runs, J. Combin. Theory Ser. A 142 (2016), 147–176.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A10,
05A15, 05A18. _Keywords:_ flattened partition, generating function, recurrence
relation, run, set partition.

(Concerned with sequence A000295 and A124324.)