Merging-Free Partitions and Run-Sorted Permutations

Fufa Beyene111Corresponding author.

Department of Mathematics, Addis Ababa University

P.O. Box 1176

Addis Ababa, Ethiopia

<EMAIL_ADDRESS>
Roberto Mantaci
IRIF, Université de Paris
8, Place Aurélie Nemours, 75013
Paris, France
<EMAIL_ADDRESS>
###### Abstract

In this paper, we study merging-free partitions with their canonical forms and
run-sorted permutations. We give a combinatorial proof of the conjecture made
by Nabawanda et al. We describe the distribution of the statistics of runs and
right-to-left minima over the set of run-sorted permutations and we give the
exponential generating function for their joint distribution. We show the
number of right-to-left minima is given by the shifted distribution of the
Stirling number of the second kind. We also prove that the non-crossing
merging-free partitions are enumerated by powers of $2$. We use one of the
constructive proofs given in the paper to implement an algorithm for the
exhaustive generation of run-sorted permutations by number of runs.

##  1 Introduction

Given a non-empty finite subset $A$ of positive integers, a _set partition_
$P$ of $A$ is a collection of disjoint non-empty subsets $A_{i}$ called
_blocks_ of $A$ such that $\cup_{i=1}^{k}A_{i}=A$ [5, 9]. We shall use the
notation $[n]:=\\{1,2,\ldots,n\\}$, where $n$ is a fixed positive integer. It
is well known that set partitions over $[n]$ and set partitions over $[n]$
having $k$ blocks are counted by the Bell numbers, $b_{n}$ and Stirling
numbers of the second kind, $S(n,k)$ respectively ([5, 15, 19]). Mansour [9]
defined the _block representation_ of a set partition where the elements in a
block are arranged increasingly and the blocks are arranged in increasing
order of their first elements. Mansour also gave a way to encode a set
partition (in its block representation) by its _canonical form_ , that is,
every integer is encoded by the number of the block it belongs to. We note
that canonical forms of set partitions coincide with the so-called _restricted
growth functions_ ($\operatorname{RGF}$).

Callan [6] introduced the “flattening” operation ($\operatorname{Flatten}$) on
set partitions, which acts in such a way that a permutation $\sigma$ is
obtained from a set partition $P$ by removing the separators enclosing the
different blocks of $P$ in its block representation. For example, the set
partition $P=126/3/48/57$ is in the block representation, and so we remove the
separators $``/"$ and obtain the permutation $\sigma=12634857$. As a result of
Callan’s work, such objects are getting the attention of different researchers
and several new findings are emerging, for example see [1, 10, 13].

In the literature permutations obtained this way are sometimes called
“flattened partitions”. We found this term somewhat confusing because these
objects are permutations and not partitions, consequently, since the runs of
the resulting permutations are sorted by the increasing values of their
respective minima, we chose to adopt the term run-sorted permutations already
used by Alexandersson and Nabawanda [1]. Run-sorted permutations are counted
by the shifted Bell numbers (see [13]).

The same permutation can be obtained by flattening several set partitions. For
instance, the permutation $\sigma=12634857$ can also be obtained by flattening
the set partition $P^{\prime}=126/348/57$. Among all the set partitions having
the same $\operatorname{Flatten}$, we will distinguish the only one whose
number of blocks is the same as the number of runs of the permutation obtained
by flattening it (this is the set partition $P^{\prime}$ for the permutation
$\sigma$). For obvious reasons we named these objects merging-free partitions.
The $\operatorname{Flatten}$ operation clearly becomes injective and hence a
bijection if restricted to the set of merging-free partitions.

In this article we study some properties of run-sorted permutations as well as
of merging-free partitions and their canonical forms, we compute the
distribution of some statistics (runs, right-to-left minima, $\ldots$) over
these sets, we relate these classes to the classes of separated partitions and
of non-crossing partitions and we provide an exhaustive generation algorithm
for the class of run-sorted permutations partitioned by number of runs. In
particular, in Section 2, we give the characterization of the canonical forms
of merging-free partitions, and show that they can be bijectively related to
$\operatorname{RGF}$s of one size smaller.

In Section 3, we give a combinatorial bijective proof of a recurrence relation
in Theorem 23 satisfied by run-sorted permutations over $[n]$ having $k$ runs,
a recurrence relation that was conjectured by Nabawanda et al. [13]. We also
give the interpretation of the proof of the same result by working on the
canonical forms of merging-free partitions.

In Section 4.1, we prove that the distribution of right-to-left minima over
run-sorted permutations is the same as the distribution of the number of
blocks over set partitions of one size smaller (and also given by the shifted
Stirling number of the second kind). We refine the recurrence relation
satisfied by the number of run-sorted permutations over $[n]$ having $k$ runs
by counting these permutations by number of runs and by number of right-to-
left minima simultaneously and we obtain an exponential generating function
for the associated three-variables formal series. Munagi [12] proved that the
set partitions over $[n]$ having $k$ blocks such that no two consecutive
integers in the same block are also counted by the shifted Stirling numbers of
the second kind. So, in this section we also show that these partitions
bijectively correspond to run-sorted permutations over $[n]$ having $k$ right-
to-left minima.

Non-crossing partitions are Catalan enumerated objects introduced in the
founding work of Becker [3] and later deeply studied by different eminent
scholars like Kreweras and Simion ([7, 17]). We characterize the class of non-
crossing merging-free partitions in Section 5 and we enumerate them according
to their number of blocks and show that the total number of such partitions is
counted by the power of $2$.

Finally, Section 6 presents an exhaustive generation algorithm for run-sorted
permutations partitioned by the number of runs, based on the recurrence
relation proved in Theorem 23 and using the classical dynamic programming
techniques.

###  1.1 Definitions, Notation, and Preliminaries

######  Definition 1.

A set partition $P$ of $[n]$ is defined as a collection $B_{1},\ldots,B_{k}$
of nonempty disjoint subsets such that $\cup_{i=1}^{k}B_{i}=[n]$. The subsets
$B_{i}$ will be referred to as “blocks”.

######  Definition 2.

A set partition $P=B_{1}/\cdots/B_{k}$ is said to be the _block
representation_ of $P$ if the blocks $B_{1},\ldots,B_{k}$ are sorted in such
way that $\min(B_{1})<\min(B_{2})<\cdots<\min(B_{k})$ and the elements of
every block are arranged in increasing order.

We will always write set partitions in their block representation. Let
$\mathcal{SP}(n)$ denote the set of all set partitions over $[n]$ and
$b_{n}=|\mathcal{SP}(n)|$ the $n$-th Bell number.

######  Definition 3.

The _canonical form_ of a set partition of $[n]$ is a $n$-tuple indicating the
block in which each integer occurs, that is, $f=f_{1}f_{2}\cdots f_{n}$ such
that $j\in B_{f_{j}}$ for all $j$ with $1\leq j\leq n$.

######  Example 4.

If $P=138/2/47/56\in\mathcal{SP}(n)$, then its canonical form is $f=12134431$.

######  Definition 5.

A _restricted growth function_ $(\operatorname{RGF})$ over $[n]$ is a function
$f:[n]\mapsto[n]$, where $f=f_{1}\cdots f_{n}$ such that $f_{1}=1$ and
$f_{i}\leq 1+\max\\{f_{1},\ldots,f_{i-1}\\}$ for $2\leq i\leq n$, or
equivalently, such that the set $\\{f_{1},f_{2},\ldots,f_{i}\\}$ is an integer
interval for all $i\in[n]$.

The canonical forms of set partitions are exactly the restricted growth
functions ($\operatorname{RGF}$). We let $\operatorname{RGF}(n)$ denote the
set of all restricted growth functions over $[n]$. We will note
$f\in\operatorname{RGF}(n)$ as a word $f_{1}f_{2}\cdots f_{n}$ over the
alphabet $[n]$, where $f_{i}=f(i)$. We define the statistic of the set of
left-to-right maxima of $f$ by

$\operatorname{LrMax}(f)=\\{i~{}:f_{i}>f_{j},1\leq i\leq n,j<i\\},$

and a statistic of the set of weak left-to-right maxima of $f$ by

$\operatorname{WLrMax}(f)=\\{i:~{}f_{i}\geq f_{j},1\leq i\leq n,j<i\\},$

We also use the notation $\operatorname{lrmax}(f):=|\operatorname{LrMax}(f)|$
and $\operatorname{wlrmax}(f):=|\operatorname{WLrMax}(f)|$.

######  Example 6.

If $f=121132342\in\operatorname{RGF}(9)$, then observe that
$\operatorname{LrMax}(f)=\\{1,2,5,8\\}$ and
$\operatorname{WLrMax}(f)=\\{1,2,5,7,8\\}$.

######  Definition 7.

Let $P=B_{1}/\cdots/B_{k}$ be a set partition. We say that $P$ is merging-free
if $\max(B_{i})>\min(B_{i+1}),1\leq i\leq k-1$.

A permutation $\pi$ over $[n]$ will be represented in the one-line notation,
$\pi=\pi_{1}\pi_{2}\cdots\pi_{n}$. In particular, every permutation can be
considered as a word of length $n$, with letters in $[n]$. We define the set
of right-to-left minima of $\pi$ by

$\operatorname{RlMin}(\pi)=\\{\pi_{i}~{}:~{}\pi_{i}<\pi_{j},j>i\\},$

and we use the notation
$\operatorname{rlmin}(\pi):=|\operatorname{RlMin}(\pi)|$.

######  Definition 8.

A maximal increasing subsequence of consecutive letters in the word of a
permutation $\pi$ is called a run.

######  Definition 9.

_Flattening_ a set partition is an operation by which we obtain a permutation
from the set partition $P=B_{1}/\cdots/B_{k}$ over $[n]$ by concatenating its
blocks. We denote the resulting permutation by
$\operatorname{Flatten}(P)=\pi$.

If a permutation is obtained by flattening a set partition, then its runs are
ordered in such a way that the minimum of the runs are increasing, therefore,
we will call all permutations in $\operatorname{Flatten}(\mathcal{SP}_{n})$
_run-sorted permutations_. We let $\mathcal{RSP}(n)$ denote the set of all
run-sorted permutations over $[n]$ and $r_{n}$ is its cardinality.

######  Remark 10.

Merging-free partitions over $[n]$ and run-sorted permutations over $[n]$ are
in bijection, because the restriction of $\operatorname{Flatten}$ to the
merging-free partitions is a bijection.

Nabawanda et al. [13] proved the following result.

######  Proposition 11.

The number of set partitions over $[n]$ and the number of run-sorted
permutations over $[n+1]$ (and therefore, the number of merging-free
partitions over $[n+1]$) are equal. That is, $r_{n+1}=b_{n}$ for all $n\geq
1$.

###### Proof.

We give a sketch of the proof. Let $P=B_{1}/\cdots/B_{k}\in\mathcal{SP}(n)$.
The corresponding run-sorted permutation in $\mathcal{RSP}(n+1)$ is
constructed as follows: move each minimum element of the block at the end of
its block, remove the slashes, increase every integer by 1, and finally attach
the integer 1 at the front. Conversely, we construct the set partition over
$[n]$ corresponding to a run-sorted permutation $\pi\in\mathcal{RSP}(n+1)$ as
follows. Put a slash after each right-to-left minimum of $\pi$, then delete
the integer $1$, and decrease every integer by 1, finally arrange the elements
of each block in increasing order.∎

######  Example 12.

If $P=14/258/37/6\in\mathcal{SP}(8)$, then by the above operation we obtain
the run-sorted permutation $\pi=152693847\in\mathcal{RSP}(9)$. Conversely, for
$\pi=152693847\in\mathcal{RSP}(9)$ we have
$\operatorname{RlMin}(\pi)=\\{1,2,3,4,7\\}$. So by putting a slash after each
right-to-left minimum we obtain $1/52/693/84/7\longrightarrow 14/258/37/6=P$.

##  2 Canonical forms of merging-free partitions

In this section we characterize the $\operatorname{RGF}$s corresponding to
merging-free partitions and we present some results related to these canonical
forms.

######  Remark 13.

Let $f=f_{1}\cdots f_{n}$ be the canonical form of a set partition
$P=B_{1}/\cdots/B_{k}$ over $[n]$ having $k$ blocks. We have
$i\in\operatorname{LrMax}(f)$ if and only if $i=\min(B_{f_{i}})$.

######  Proposition 14.

There is a bijection between the set of merging-free partitions over $[n]$ and
the set $T_{n}$ of $\operatorname{RGF}$s $f=f_{1}f_{2}\cdots f_{n}$ over $[n]$
satisfying the condition that every left-to-right maximum letter $s>1$ of $f$
has at least one occurrence of $s-1$ on its right.

###### Proof.

If $P=B_{1}/B_{2}/\cdots/B_{k}$ is a merging-free partition with $k$ blocks,
then $\min(B_{s-1})<\min(B_{s})$ and
$\max(B_{s-1})>\min(B_{s}),~{}s=2,\ldots,k$. Note that every leftmost
occurrence of a letter in $f$ is a left-to-right maximum letter. The positions
of the leftmost and rightmost occurrences of the letter $s$ in $f$ correspond
to the minimum and the maximum elements of the block $B_{s}$, respectively.
Thus, if $1<s\leq k$, then $f_{\min(B_{s})}=s$ and $f_{\max(B_{s-1})}=s-1$. ∎

######  Definition 15.

Let $f=f_{1}f_{2}\cdots f_{n}\in\operatorname{RGF}(n)$. If the occurrence of
the letter $f_{i}$ in $f$ has no repetition, then we say that $f_{i}$ is
unique in $f$, that is, $f_{i}$ is unique if and only if $i$ forms a singleton
block in the partition. A weak left-to-right maximum $i$ in $f$ for which
there exists $i_{0}<i$ such that $f_{i}=f_{i_{0}}$ is called a non-strict
left-to-right maximum.

We shall give a combinatorial proof of Proposition 11 in terms of canonical
forms. For each $i\in[n]$ we define $u_{i}$ as the number of unique left-to-
right maximum letters of $f$ in the positions $1,\ldots,i-1$ that are smaller
than $f_{i}$. We let $u=(u_{1},\ldots,u_{n})$. Let
$\delta=(\delta_{1},\ldots,\delta_{n})$, where

$\delta_{i}=\begin{cases}1,&\text{ if $f_{i}$ is a non-unique left-to-right
maximum letter of $f$;}\\\ 0,&\text{ otherwise}.\end{cases}$

Define a mapping $\alpha:\operatorname{RGF}(n)\mapsto T_{n+1}$, where
$T_{n+1}$ is the set of canonical forms of merging-free partitions over
$[n+1]$, by $\alpha(f)=1\cdot f^{\prime}$, that is, a concatenation of $1$ and
$f^{\prime}$, where $f^{\prime}=f^{\prime}_{1}\cdots f^{\prime}_{n}$ is
obtained from $f$ as follows:

$f^{\prime}=f-u+\delta.$

######  Example 16.

If $f=1213124$, then $f_{1}=1$ and $f_{2}=2$ are non-unique left-to-right
maximum letters, while $f_{4}=3$ and $f_{7}=4$ are the unique ones. So,
$u=(0,0,0,0,0,0,1)$ and $\delta=(1,1,0,0,0,0,0)$. Thus,
$f^{\prime}=f-u+\delta=2313123$ and $\alpha(f)=1\cdot f^{\prime}=12313123\in
T_{8}$.

######  Lemma 17.

If $f\in\operatorname{RGF}(n)$ and $f^{\prime}$ is obtained from $f$ as in the
above construction, then
$\operatorname{LrMax}(f)\subseteq\operatorname{WLrMax}(f^{\prime})$.

###### Proof.

Let $\operatorname{LrMax}(f)=\\{i_{1},\ldots i_{k}\\}$. We proceed by
induction on $k$. For $k=1$, note that $i_{1}=1$ and
$f_{1}^{\prime}=f_{1}-u_{1}+\delta_{1}=f_{1}+\delta_{1}\in\\{1,2\\}$. Thus,
the assertion is true for the basis step. Suppose that the assertion is true
for $k-1$, and we show that $i_{k}$ is a weak left-to-right maximum in
$f^{\prime}$. By definition we have

$u_{i_{k}}=\begin{cases}u_{i_{k-1}}+1,&\text{ if }f_{i_{k-1}}\text{ is
unique;}\\\ u_{i_{k-1}},&\text{ if }f_{i_{k-1}}\text{ is non-
unique.}\end{cases}$

If $f_{i_{k}}$ is unique, then $\delta_{i_{k}}=0$ and in either cases we have

$\displaystyle f_{i_{k}}^{\prime}=f_{i_{k}}-u_{i_{k}}=f_{i_{k-1}}^{\prime}.$

If $f_{i_{k}}$ is non-unique, then $\delta_{i_{k}}=1$ and in either cases we
have

$\displaystyle
f_{i_{k}}^{\prime}=f_{i_{k}}-u_{i_{k}}+1=f_{i_{k-1}}^{\prime}+1.$

Therefore, in all of the above cases we have $f_{i_{k}}^{\prime}\geq
f_{i_{k-1}}^{\prime}$. For the intermediate values, we already know them to be
non-weak left-to-right maximum letters, hence they are not greater than
$f_{i_{k-1}}^{\prime}$. Thus, by using the induction hypothesis we see that
$i_{k}$ is a weak left-to-right maximum in $f^{\prime}$. ∎

######  Lemma 18.

For all $f\in\operatorname{RGF}(n)$ we have that $\alpha(f)\in T_{n+1}$.

###### Proof.

By the above lemma it is easy to see that $1\cdot
f^{\prime}\in\operatorname{RGF}(n+1)$. Let
$f^{\prime}=f_{1}^{\prime}f_{2}^{\prime}\cdots f_{n}^{\prime}$ and let
$f_{i}^{\prime}>1$ be a left-to-right maximum letter in $1\cdot f^{\prime}$,
then $f_{i}$ is a non-unique left-to-right maximum letter in $f$. This implies
that there is some $j>i$ such that $f_{i}=f_{j}$, and hence
$u_{i}=u_{j},\delta_{j}=0$. So,
$\alpha(f(i))=f^{\prime}_{i}=f_{i}-u_{i}+1=f_{j}^{\prime}+1$. Therefore, every
left-to-right maximum letter $s>1$ of $1\cdot f^{\prime}$ has some occurrence
$s-1$ from its right and hence $1\cdot f^{\prime}\in T_{n+1}$. ∎

We now define a map $\beta:T_{n+1}\mapsto\operatorname{RGF}(n)$ which
associates each $1\cdot g=1\cdot g_{1}\cdots g_{n}\in T_{n+1}$ with a function
$\beta(1\cdot g)=g^{\prime}=g^{\prime}_{1}g^{\prime}_{2}\cdots
g^{\prime}_{n}$, where $g^{\prime}$ is obtained from $g$ as follows. For each
$i\in[n]$, we let $v_{i}$ denote the number of non-strict left-to-right
maximum letters in $g$ that are less than or equal to $g_{i}$ in the positions
$1,\ldots,i-1$. Let $v=(v_{1},\ldots,v_{n})$. Further, let
$\delta^{\prime}=(\delta^{\prime}_{1},\ldots,\delta^{\prime}_{n})$, where

$\delta^{\prime}_{i}=\begin{cases}1,&\text{ if $g_{i}$ is left-to-right
maximum of $g$};\\\ 0,&\text{ otherwise}.\end{cases}$

Then, $g^{\prime}$ is obtained from $g$ as follows:

$g^{\prime}=g+v-\delta^{\prime}.$

For instance, if $1\cdot g=122134321\in T_{9}$, then
$g=22134321,v=(0,0,0,1,1,1,1,0)$, and $\delta^{\prime}=(1,0,0,1,1,0,0,0)$.
Thus, $g^{\prime}=12134431\in\operatorname{RGF}(8)$. Note that
$\beta=\alpha^{-1}$ and as a result, we have the following proposition.

######  Proposition 19.

The mapping $\alpha$ from the set $\operatorname{RGF}(n)$ to the set $T_{n+1}$
is a bijection. ∎

######  Corollary 20.

If $f\in\operatorname{RGF}(n)$ and $\alpha(f)=1\cdot f^{\prime}$, then
$\operatorname{LrMax}(f)=\operatorname{WLrMax}(f^{\prime})$. ∎

We now evaluate the number $l_{n}$ of $f\in\operatorname{RGF}(n)$ having the
sequence $u=0$, that is, if $f=f_{1}f_{2}\cdots f_{n}$, then for each
$i\in[n]$ there is no unique left-to-right maximum letter smaller than $f_{i}$
on its left. The set partitions corresponding to such functions are exactly
those satisfying the condition that their blocks have size at least two except
for the last block, which may be singleton. The sequence of the numbers
$l_{n},n\geq 0$ is the same as the OEIS A346771.

######  Theorem 21.

For all $n\geq 1$ we have

$l_{n}=\sum_{k=1}^{n-1}{n-1\choose k}l_{n-k-1},l_{0}=l_{1}=1.$ (1)

###### Proof.

Let $f\in\operatorname{RGF}(n)$ satisfy the above condition. Since $f_{1}=1$
is the smallest integer, every such function has at least two $1$s. Suppose
that $f$ has $k+1$ occurrences of $1$s. If we delete all the $1$s and decrease
each of the remaining integers by $1$, then we obtain a $\operatorname{RGF}$
over $[n-k-1]$, with the same condition as $f$. So, there are $l_{n-k-1}$ such
functions. We now choose $k$ positions from $\\{2,3,\ldots,n\\}$ where $1$ can
be inserted, and this is possible in $\displaystyle{n-1\choose k}$ ways.
Therefore, by applying the product rule and then taking the sum over all
possible $k$ we have the right hand side of (1). ∎

##  3 Run distribution in run-sorted permutations

The following table presents the first few values $r_{n,k}$ of the number of
run-sorted permutations over $[n]$ having $k$ runs (see A124324).

$n\backslash k$ | 1 | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---|---
1 | 0 |  |  |  |  |  |
2 | 1 | 0 |  |  |  |  |
3 | 1 | 1 | 0 |  |  |  |
4 | 1 | 4 | 0 | 0 |  |  |
5 | 1 | 11 | 3 | 0 | 0 |  |
6 | 1 | 26 | 25 | 0 | 0 | 0 |
7 | 1 | 57 | 130 | 15 | 0 | 0 | 0
Table 1: The values of $r_{n,k}$ for $1\leq k,n\leq 7$

######  Remark 22.

The number $k$ of runs of a run-sorted permutation over $[n]$ satisfies the
condition

$1\leq k\leq\lceil\frac{n}{2}\rceil,~{}n\geq 1,$

because each run except the last has length at least $2$.

The following result was conjectured by Nabawanda et al. [13], who also gave a
justification of the first term of the right-hand side of (2). We were the
first to provide a combinatorial bijective proof justifying the second term
and thus prove the conjecture. We show a complete combinatorial proof of the
conjecture here using our bijection.

######  Theorem 23.

The number $r_{n,k}$ of run-sorted permutations of $[n]$ having $k$ runs
satisfies the recurrence relation

$r_{n,k}=kr_{n-1,k}+(n-2)r_{n-2,k-1},~{}~{}n\geq 2,~{}k\geq 1,$ (2)

where $r_{0,0}=1,~{}r_{1,0}=0,~{}r_{1,1}=1$.

In order to prove this result, we partition the set $\mathcal{RSP}(n,k)$ of
run-sorted permutations over $[n]$ having $k$ runs into two subsets:
$\mathcal{RSP}^{(1)}(n,k)$ and $\mathcal{RSP}^{(2)}(n,k)$, where
$\mathcal{RSP}^{(1)}(n,k)$ is the set of elements of $\mathcal{RSP}(n,k)$ in
which the removal of the integer $n$ does not decrease the number of runs and
$\mathcal{RSP}^{(2)}(n,k)$ is the set of elements of $\mathcal{RSP}(n,k)$ in
which the removal of the integer $n$ decreases the number of runs, this
happens when the integer $n$ occurs between two integers $x$ and $y$ with
$x<y$. For example, $12435\in\mathcal{RSP}^{(1)}(5,2)$ and
$15234\in\mathcal{RSP}^{(2)}(5,2)$. We will denote the cardinalities of these
subsets by $r^{(1)}_{n,k}$ and $r^{(2)}_{n,k}$, respectively.

Let $\phi:[k]\times\mathcal{RSP}(n-1,k)\mapsto\mathcal{RSP}^{(1)}(n,k)$
associating each element $(i,\sigma)\in[k]\times\mathcal{RSP}(n-1,k)$ with the
permutation $\sigma^{\prime}=\phi(i,\sigma)$ obtained from $\pi$ by inserting
$n$ at the end of the $i$-th run of the permutation $\sigma$. It is easy to
see that $\phi$ is a bijection (see [13], p. 6).

We now define the mapping
$\psi:[n-2]\times\mathcal{RSP}(n-2,k-1)\mapsto\mathcal{RSP}^{(2)}(n,k)$,
associating each element $(i,\pi)\in[n-2]\times\mathcal{RSP}(n-2,k-1)$ with
the permutation $\pi^{\prime}=\psi(i,\pi)$ obtained from $\pi$ by increasing
all integers greater than $i$ by 1 and inserting the subword $n~{}i{+}1$
immediately after the rightmost of the integers of the set
$\\{1,2,\ldots,i\\}$.

######  Example 24.

Let $i=3$ and $\pi=13524\in\mathcal{RSP}(5,2)$. We construct $\psi(i,\pi)$ as
follows: increase each integer greater than 3 in $\pi$ by $1$ to get $13625$,
then insert the subword $7~{}(3{+}1)=7~{}4$ into the position after the
rightmost of the integers $1,2,3$, thus the subword must be inserted between
$2$ and $5$, hence,
$\psi(3,13524)=\pi^{\prime}=1362745\in\mathcal{RSP}^{(2)}(7,3)$.

######  Lemma 25.

For all $(i,\pi)\in[n-2]\times\mathcal{RSP}(n-2,k-1)$, we have
$\psi(i,\pi)\in\mathcal{RSP}^{(2)}(n,k)$.

###### Proof.

Since $\pi\in\mathcal{RSP}(n-2,k-1)$ and the procedure inserts the subword
$n~{}i{+}1$ immediately after the rightmost integer of the set
$\\{1,\ldots,i\\}$, all integers to the right of $i+1$ are greater than $i+1$
and $i+1$ is the first element of a new run. Thus the resulting permutation is
run-sorted with the number of runs increased by $1$. Furthermore, in the
resulting permutation the integer $n$ is immediately preceded by some integer
in the set $\\{1,\ldots,i\\}$ and immediately followed by $i+1$, hence its
removal decreases the number of runs, so
$\pi^{\prime}\in\mathcal{RSP}^{(2)}(n,k)$. ∎

######  Proposition 26.

The map $\psi$ defined above is a bijection.

###### Proof.

We prove that $\psi$ is both injective and surjective. First let us assume
that $(i_{1},\pi_{1})\neq(i_{2},\pi_{2})$ for $i_{1},i_{2}\in[n-2]$ and
$\pi_{1},\pi_{2}\in\mathcal{RSP}(n-2,k-1)$. Let
$\psi(i_{1},\pi_{1})=\pi_{1}^{\prime}$ and
$\psi(i_{2},\pi_{2})=\pi_{2}^{\prime}$. Then $\pi_{1}^{\prime}$ and
$\pi_{2}^{\prime}$ are run-sorted permutations in $\mathcal{RSP}^{(2)}(n,k)$
by the previous lemma. We consider two cases. If $i_{1}\neq i_{2}$, then in
one of the two resulting permutations $n$ is followed by $i_{1}+1$ while in
the other $n$ is followed by $i_{2}+1$. If $i_{1}=i_{2}$ and
$\pi_{1}\neq\pi_{2}$, then the two run-sorted permutations $\pi_{1}$ and
$\pi_{2}$ have at least two entries in which they differ. Thus inserting
$n~{}i_{1}{+}1=n~{}i_{2}{+}1$ after the rightmost element of the set
$\\{1,2,\ldots,i_{1}=i_{2}\\}$, produces two different permutations
$\pi_{1}^{\prime}$ and $\pi_{2}^{\prime}$. Thus, in both cases,
$\pi_{1}^{\prime}=\psi(i_{1},\pi_{1})\neq\psi(i_{2},\pi_{2})=\pi_{2}^{\prime}$,
hence $\psi$ is injective. Next, consider any
$\pi^{\prime}\in\mathcal{RSP}^{(2)}(n,k)$, then $n$ does not appear in the
last position. Let $j>1$ be the integer following $n$ in $\pi^{\prime}$. We
exhibit a pair $(i,\pi)\in[n-2]\times\mathcal{RSP}(n-2,k-1)$ such that
$\psi(i,\pi)=\pi^{\prime}$. Define $\pi$ to be the run-sorted permutation
obtained from $\pi^{\prime}$ by deleting the subword $n~{}j$ and by decreasing
by 1 every integer greater than or equal to $j+1$ in the resulting word. Note
that if $n$ follows the integer $i$ in $\pi^{\prime}$, then $i<j$ and hence
deleting the subword $n~{}j$ from $\pi^{\prime}$ reduces the number of runs by
$1$ and the size of the partition by 2, whence $\pi\in\mathcal{RSP}(n-2,k-1)$
and $\psi(j+1,\pi)=\pi^{\prime}$. Therefore, $\psi$ is a bijection. ∎

We are now ready to present the proof of Theorem 23.

###### Proof.

The left-hand side counts the number of run-sorted permutations in
$\mathcal{RSP}(n,k)$. The first term of the right-hand side counts the number
of elements in $\mathcal{RSP}^{(1)}(n,k)$. Since $\phi$ is a bijection, we
have $r_{n,k}^{(1)}=kr_{n-1,k}$. We show that the second term of the right-
hand side counts the number of elements in $\mathcal{RSP}^{(2)}(n,k)$. By
Proposition 26 the sets $[n-2]\times\mathcal{RSP}(n-2,k-1)$ and
$\mathcal{RSP}^{(2)}(n,k)$ have the same cardinality, that is,
$(n-2)r_{n-2,k-1}=r_{n,k}^{(2)}$. Thus by combining the two parts we obtain
$r_{n,k}=r_{n,k}^{(1)}+r_{n,k}^{(2)}$, and hence the recurrence relation in
(2). ∎

We also provide a bijective proof of Theorem 23 in terms of canonical forms.
Let $T_{n,k}=\\{f\in T_{n}:\operatorname{lrmax}(f)=k\\}$, so
$|T_{n,k}|=r_{n,k}$. Recall that $T_{n,k}$ is the set of the canonical forms
of merging-free partitions over $[n]$ having $k$ blocks.

###### Proof.

Firstly, if $f=f_{1}f_{2}\cdots f_{n-1}\in T_{n-1,k}$, then by concatenating
any integer $i\in[k]$ at the end of $f$ we obtain a $f^{\prime}\in T_{n,k}$.
This is because, $f^{\prime}$ satisfies the condition of Proposition 14 if and
only if $f$ does. This construction obviously produces $kr_{n-1,k}$ functions
of $T_{n,k}$ having the property that by erasing the last value $f_{n}$ we
obtain a function in $T_{n-1,k}$.

Secondly, if $f=f_{1}f_{2}\cdots f_{n-2}\in T_{n-2,k-1}$, let $i\in[n-2]$, and
let $m=\max_{1\leq j\leq i}\\{f_{j}\\}$, then we construct
$f^{\prime}=f^{\prime}_{1}f^{\prime}_{2}\cdots f^{\prime}_{n}\in T_{n,k}$
associated with $(i,f)$ as follows: increase by $1$ all $f_{j}$s such that
$f_{j}\geq m,j>i$, insert $m+1$ at the position $i+1$, and append $m$ at the
end. The functions obtained with the second construction are all different
from those obtained using the former one. Indeed, by erasing the last integer
from $f^{\prime}$ we do not obtain a function in $T_{n-1,k}$. The reason is
that the value $m+1$ in the position $i+1$ is a left-to-right maximum letter
because of the choice of $m$. Now, by construction, the only occurrence of $m$
in $f^{\prime}$ is at position $n$, by erasing this value the left-to-right
maximum letter $m+1$ in the position $i+1$ is left without an occurrence of
$m$ on its right. Therefore, $f_{1}^{\prime}f_{2}^{\prime}\cdots
f_{n-1}^{\prime}$ does not satisfy the property characterizing canonical forms
of merging-free partitions. So, this contributes $(n-2)r_{n-2,k-1}$ to the
number $r_{n,k}$ as there are $n-2$ possibilities for $i$ and the number of
image values of $f^{\prime}$ increases by $1$. ∎

######  Example 27.

Take $f=12132\in T_{5,3}$, and let $i=3$. We construct $(i,f)\mapsto
f^{\prime}$ as follows: we have $m=\max_{1\leq j\leq 3}\\{f_{j}\\}=\max_{1\leq
j\leq 3}\\{1,2,1\\}=2$, and
$f^{\prime}_{1}=f_{1}=1,f^{\prime}_{2}=f_{2}=2,f^{\prime}_{3}=f_{3}=1,f^{\prime}_{4}=m+1=3,f^{\prime}_{5}=f_{4}+1=4,f^{\prime}_{6}=f_{5}+1=3,f^{\prime}_{7}=m=2$.
Thus, $f^{\prime}=1213432\in T_{7,4}$.

##  4 Right-to-left minima in run-sorted permutations

###  4.1 The distribution of right-to-left minima over the set of run-sorted
permutations

The following proposition gives us the relation between the statistics of
right-to-left minima of run-sorted permutations and the weak left-to-right
maxima of the canonical forms of the corresponding merging-free partitions.

######  Proposition 28.

The set of right-to-left minima of a run-sorted permutation over $[n]$ and the
set of weak left-to-right maxima of the canonical form of the corresponding
merging-free partition are the same.

###### Proof.

Let $\operatorname{Flatten}(P)=\pi=\pi(1)\cdots\pi(n)\in\mathcal{RSP}(n)$,
where $P$ is a merging-free partition over $[n]$. Let $f=f_{1}\cdots f_{n}$ be
the canonical form of $P$ and let $\\{i_{1},\ldots,i_{r}\\}$ be the set of the
positions of the right-to-left minima of $\pi$, then by definition of right-
to-left minima
$\operatorname{RlMin}(\pi)=\\{1=\pi(i_{1})<\pi(i_{2})<\cdots<\pi(i_{r})=\pi(n)\\}$.
Furthermore, if $1\leq j_{1}<j_{2}\leq r$ and we let $B_{q_{1}}$ be the block
of $P$ containing $\pi(i_{j_{1}})$ and $B_{q_{2}}$ the block of $P$ containing
$\pi(i_{j_{2}})$, then $q_{1}\leq q_{2}$ and by the definition of canonical
form we have $f_{\pi(i_{1})}\leq f_{\pi(i_{2})}\leq\cdots\leq f_{\pi(i_{r})}$.
Assume that $\pi(j)\notin\operatorname{RlMin}(\pi)$, then there exists some
integer $s$ such that $\pi(j)>\pi(s),s>j$. Hence $f_{\pi(s)}>f_{\pi(j)}$ and
$\pi(j)\notin\operatorname{WLrMax}(f)$. Thus,
$\\{\pi(i_{1}),\ldots,\pi(i_{k})\\}\subseteq\operatorname{WLrMax}(f)$.

Conversely, if $\operatorname{WLrMax}(f)=\\{i_{1},\ldots,i_{s}\\}$, then for
each $i_{j}$ we have $f_{i_{j}}\geq f_{t},t<i_{j}$, that is, all integers
$t<i_{j}$ belong either to $f_{i_{j}}$-th block or to a preceding block of
$P$, therefore, in $\pi$ there is no integer smaller than $i_{j}$ on the right
of $i_{j}$. Hence $i_{j}\in\operatorname{RlMin}(\pi)$. Therefore,
$\operatorname{RlMin}(\pi)=\operatorname{WLrMax}(f)$. ∎

######  Example 29.

If $P=149/238/57/6$, then its canonical form is $f=122134321$, and
$\operatorname{Flatten}(P)=\pi=149238576$. Thus, we have
$\operatorname{RlMin}(\pi)=\\{1,2,3,5,6\\}=\operatorname{WLrMax}(f)$.

Let $h_{n,r}$ denote the number of run-sorted permutations over $[n]$ having
$r$ right-to-left minima.

######  Proposition 30.

For all positive integers $n$ and $r$ with $2\leq r\leq n$ we have

$h_{n,r}=h_{n-1,r-1}+(r-1)h_{n-1,r},~{}h_{1,1}=1.$ (3)

###### Proof.

A run-sorted permutation $\pi^{\prime}$ over $[n]$ can be obtained from a run-
sorted permutation $\pi$ over $[n-1]$ either by appending $n$ at its end, or
by inserting $n$ before any of its right-to-left minima that is different from
$1$. In the former case, the number of right-to-left minima increases by $1$,
hence this contributes $h_{n-1,r-1}$ to the number $h_{n,r}$. In the later
case, if
$\operatorname{RlMin}(\pi)=\\{\pi(i_{1}),\pi(i_{2}),\ldots,\pi(i_{r})\\}$,
then $1=\pi(i_{1})<\pi(i_{2})<\cdots<\pi(i_{r})$. So, inserting $n$ before any
$\pi(i_{j})$ for $j\neq 1$ makes $\pi(i_{j})$ to be the minimum element of its
run in $\pi^{\prime}$. Thus the permutation $\pi^{\prime}$ is run-sorted with
the same number of right-to-left minima as $\pi$, and this contributes
$(r-1)h_{n-1,r}$ as there are $r-1$ right-to-left minima different from $1$. ∎

We also give the interpretation of the bijective proof of the recursion
formula in (3) for the corresponding set of canonical forms of merging-free
partitions using Proposition 28. We interpret $h_{n,r}$ as the number of
canonical forms in $T_{n}$ having $r$ weak left-to-right maxima, that is,
$h_{n,r}=|\\{f\in T_{n}:\operatorname{wlrmax}(f)=r\\}|$. All the elements of
the set $\\{f\in T_{n}:\operatorname{wlrmax}(f)=r\\}$ are obtained in a unique
way

  1. 1.

either from a $f=f_{1}f_{2}\cdots f_{n-1}\in T_{n-1,r-1}$ by concatenating
$\max_{1\leq j\leq n-1}\\{f_{j}\\}$ at its end;

  2. 2.

or from a $f=f_{1}f_{2}\cdots f_{n-1}\in T_{n-1,r}$ with weak left-to-right
maxima $\\{i_{1},i_{2},\ldots,i_{r}\\}$ as follows. For each $j=2,\ldots,r$ :

     * -

if $f_{i_{j}}$ is a non-strict left-to-right maximum letter of $f$, then
increase by $1$ every integer $f_{s}$ such that $f_{s}\geq f_{i_{j}}$ and
$s\geq i_{j}$, and

     * -

concatenate $f_{i_{j-1}}$ at the end of the resulting function.

Thus, the recurrence relation in (3) follows.

Recall that the recurrence relation satisfied by the Stirling numbers of the
second kind is $S(n,r)=S(n-1,r-1)+rS(n-1,r)$. It is easy to see that from
Corollary 20 of Section 2 and Proposition 28, the number of blocks in a set
partition over $[n-1]$ is one less than the number of right-to-left minima of
the corresponding run-sorted permutation over $[n]$ under the bijection in
Proposition 11. So, the values of $h_{n,r}$ given in (3) are the shifted
values of the Stirling numbers of the second kind, that is,
$h_{n,r}=S(n-1,r-1)$, for all $n\geq r\geq 1$.

###  4.2 The joint distribution of $\operatorname{run}$ and
$\operatorname{rlmin}$ over the set of run-sorted permutations

The statistics $\operatorname{run}$ and $\operatorname{rlmin}$ of a run-sorted
permutation are obviously related. In particular, each minimum element of a
run is always a right-to-left minimum, so
$\operatorname{run}(\pi)\leq\operatorname{rlmin}(\pi),\forall\pi\in\mathcal{RSP}(n)$.
We are interested in the joint distribution of these statistics. Let
$a_{n,k,r}$ denote the number of run-sorted permutations over $[n]$ having $k$
runs and $r$ right-to-left minima. If $n=0$, the only nonzero term is
$a_{0,0,0}=1$, if $n\geq 1$, then $a_{n,k,r}=0$, where
$k>\lceil\frac{n}{2}\rceil,r>n,r<k,k<,r<1$, or $r>n-k+1$.

######  Proposition 31.

For all integers $n,k,r$ such that $1\leq k,r\leq n$ the numbers $a_{n,k,r}$
of run-sorted permutations over $[n+2]$ having $k$ runs and $r$ right-to-left
minima satisfy

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

###### Proof.

Let $\pi\in\mathcal{RSP}(n+2)$. Let us suppose that the integers $1$ and $2$
are in the same run of $\pi$. Let $\pi^{\prime}$ be the permutation obtained
from $\pi$ by deleting $1$ and then decreasing each of the remaining integers
by $1$, then $\pi^{\prime}\in\mathcal{RSP}(n+1)$ and
$\operatorname{run}(\pi)=\operatorname{run}(\pi^{\prime})$ and
$\operatorname{rlmin}(\pi)=\operatorname{rlmin}(\pi^{\prime})+1$. This implies
that

$|\\{\pi\in\mathcal{RSP}(n+2):~{}\operatorname{run}(\pi)=k,\operatorname{rlmin}(\pi)=r,1\text{
and }2\text{ are in the same run}\\}|=a_{n+1,k,r-1}.$

Let us suppose now that $1$ and $2$ are in different runs of $\pi$ and that
the first run (containing $1$) has length $i+1,i\geq 1$, then we can choose
$i$ elements from the set $\\{3,4,\ldots,n+2\\}$ to include in the first run.
There are $\displaystyle{n\choose i}$ ways to do so. The remaining part of
$\pi$ is a run-sorted permutation over $[n-i+1]$ and there are $a_{n+1-i}$ of
them. In this case, the number of runs and the number of right-to-left minima
of $\pi$ each increase by $1$. This completes the proof. ∎

######  Theorem 32.

We have

$a_{n,k,r}=a_{n-1,k,r-1}+(k-1)a_{n-1,k,r}+(n-2)a_{n-2,k-1,r-1},n\geq 2,k,r\geq
1$ (4)

with the initial conditions $a_{0,0,0}=1,a_{1,1,1}=1$.

###### Proof.

The proof is based on the technique used in the proof of Theorem 23. Let
$\pi^{\prime}$ be a run-sorted permutation over $[n]$ obtained from
$\pi\in\mathcal{RSP}(n-1)$ by inserting $n$ at the end of any of its runs.
This operation preserves the number of runs. It also preserves the number of
right-to-left minima except when $n$ is inserted at the end of the last run of
$\pi$, in which case the number of right-to-left minima increases by $1$. So,
we get the first two terms of the right-hand side of the recurrence relation.
Again, if $\pi^{\prime}\in\mathcal{RSP}(n)$ is obtained from
$\pi\in\mathcal{RSP}(n-2)$ by the operation defined in Lemma 25, that is,
$\pi^{\prime}=\psi(i,\pi)$, where $i\in[n-2]$, then the number of runs and the
number of right-to-left minima each increases by $1$. We showed already that
this is true for the number of runs, let us show it for the number of right-
to-left minima. The operation increases by $1$ each integer greater than $i$
in $\pi$ and inserts the subword $n~{}i{+}1$ immediately after the rightmost
position of the integers of the set $\\{1,2,\ldots,i\\}$, then the newly
created run beginning at $i+1$ contributes one more right-to-left minimum
since the minima of the runs form an increasing subsequence. Thus, we have the
last term of the right-hand side of the recurrence. ∎

######  Theorem 33.

The exponential generating function

$A(x,y,z)=\sum_{n,k,r\geq 0}a_{n,k,r}\frac{x^{n}}{n!}y^{k}z^{r}$

satisfies the differential equation

$\frac{\partial A}{\partial x}=yze^{xz+yz(-x-1)+ye^{x}}$ (5)

with the initial condition $\frac{\partial A}{\partial x}|_{x=0}=yz$.

###### Proof.

From (4) we have

$\displaystyle\sum_{n\geq 2,k,r\geq 1}a_{n,k,r}\frac{x^{n}}{n!}y^{k}z^{r}$
$\displaystyle=\sum_{n\geq 2,k,r\geq
1}a_{n-1,k,r-1}\frac{x^{n}}{n!}y^{k}z^{r}+\sum_{n\geq 2,k,r\geq
1}(k-1)a_{n-1,k,r}\frac{x^{n}}{n!}y^{k}z^{r}+$
$\displaystyle~{}~{}~{}~{}\sum_{n\geq 2,k,r\geq
1}a_{n-2,k-1,r-1}\frac{x^{n}}{n!}y^{k}z^{r}.$

Using the notation $\frac{\partial A}{\partial y}=A_{y}$ and expressing the
above equation in terms of $A$ we obtain

$\displaystyle A$ $\displaystyle=z\left(\int Adx-x\right)+\int
yA_{y}dx-\left(\int Adx-x\right)+xyz\int Adx-$
$\displaystyle~{}~{}~{}~{}2yz\int\int Adxdx+1+xyz$ $\displaystyle=\int
yA_{y}dx-(1-z-xyz)\int Adx+x-xz-2yz\int\int Adxdx+1+xyz.$ (6)

By differentiating both sides of (6) with respect to $x$ we obtain the
following:

$\displaystyle A_{x}=yA_{y}-(1-z-xyz)A+1-z-yz\int Adx+yz.$

Again by differentiating the above equation with respect to $x$ we obtain

$\displaystyle A_{xx}=yA_{yx}-(1-z-xyz)A_{x}.$ (7)

By letting $A_{x}=B$ in (7) we obtain

$\displaystyle B_{x}-yB_{y}+(1-z-xyz)B=0.$ (8)

Then, the characteristic equation is $\frac{dy}{dx}=\frac{-y}{1}$ or $\ln
y+x=k$ with $k$ constant. We make the transformation with $\epsilon=x,\mu=\ln
y+x,\zeta=z$, and $w(\epsilon,\mu,\zeta)=B(x,y,z)$. Using the substitution we
find that (8) transforms to

$\displaystyle w_{\epsilon}+\left(1-\zeta-\epsilon\zeta
e^{\mu-\epsilon}\right)w=0.$

By the integrating factor method we have

$\displaystyle\frac{\partial}{\partial\epsilon}\left(e^{\int\left(1-\zeta-\epsilon\zeta
e^{\mu-\epsilon}\right)d\epsilon}w\right)=0$

and integrating it with respect to $\epsilon$ and simplifying

$\displaystyle w(\epsilon,\mu,\zeta)$
$\displaystyle=g(\mu,\zeta)e^{\int\left(1-\zeta-\epsilon\zeta
e^{\mu-\epsilon}\right)d\epsilon}$
$\displaystyle=g(\mu,\zeta)e^{-\epsilon+\zeta\epsilon+\zeta
e^{\mu-\epsilon}(-\epsilon-1)+h(\mu,\zeta)},$

where $g$ and $h$ are any differentiable functions of two variables. Using the
initial condition $B(0,y,z)=yz$ we have $x=0,\epsilon=0,\mu=\ln
y,\zeta=z,w(\epsilon=0,\mu=\ln y,\zeta=z)=yz$, and

$\displaystyle y$ $\displaystyle=g(\ln y,z)e^{-y+h(\ln y,z)}$ $\displaystyle
ye^{y}$ $\displaystyle=g(\ln y,z)e^{h(\ln y,z)}.$

Thus, we obtain $g(t,z)=ze^{t},h(t,z)=e^{t}$. Therefore, we back the
transformation in terms of $x,y,z$ so that

$\displaystyle B(x,y,z)$ $\displaystyle=g(\ln y+x,z)e^{-x+zx+yz(-x-1)+h(\ln
y+x,z)}$ $\displaystyle=yze^{xz+yz(-x-1)+ye^{x}}.$

∎

By specializing $z=1$ in (5) we obtain the result about the exponential
generating function counting run sorted permutations by the number of runs
[13]. Recall that $r_{n,k}$ is the number of run-sorted permutations over
$[n]$ having $k$ runs.

######  Corollary 34.

If $A(x,y)=\sum_{n,k\geq 1}r_{n,k}\frac{x^{n}}{n!}y^{k}$, then $A$ satisfies

$\displaystyle\frac{\partial A}{\partial x}=ye^{x+y(-x-1)+ye^{x}}$

with the initial condition $\frac{\partial A}{\partial x}|_{x=0}=y$.

By specializing $y=z=1$ in (5) we obtain the well-known result about the
exponential generating function counting the number of run sorted permutations
(merging-free partitions) [5, 19].

######  Corollary 35.

The exponential generating function $A(x)$ of the number of run sorted
permutations has the closed differential form

$A^{\prime}(x)=e^{e^{x}-1}.$

######  Corollary 36.

For all positive integer $n\geq 1$, the number $a_{n}$ of run sorted
permutations over $[n]$ is given by

$a_{n}=\frac{1}{e}\sum_{m\geq 0}\frac{m^{n-1}}{m!}.$

###  4.3 A bijection with separated partitions

We now consider set partitions with no two consecutive integers in the same
block. Such partitions have been studied, for instance, by Munagi [12], who
called them “separated” partitions and proved that separated partitions over
$[n]$ having $k$ blocks are counted by the shifted Stirling numbers of the
second kind (see A008277), like run sorted permutations over $[n]$ having $k$
right-to-left minima.

It is then natural to provide a bijection between these two equisized classes
of objects. Let $\mathcal{P}_{n}$ denote the set of all separated partitions
over $[n]$. Let $P=B_{1}/B_{2}/\cdots/B_{k}\in\mathcal{P}_{n}$ with $k$
blocks. Define a map $\theta:\mathcal{P}_{n}\mapsto\mathcal{RSP}(n)$ given by
$\pi=\theta(P)$, where $\pi$ is obtained as follows:

  * -

for $i=2,\ldots,k$ :

if $b\in B_{i},b\neq\min(B_{i})$ and $b-1\in B_{j}$ such that $j<i$, then

move $b$ to $B_{i-1}$ and rearrange the elements of $B_{i-1}$ in increasing
order;

  * -

flatten the resulting partition and set it to $\pi$.

######  Example 37.

If $P=1358/26/47$, then $1358/26/47\rightarrow 13568/2/47\rightarrow
13568/27/4~{}\rightarrow 13568274=\pi$.

######  Theorem 38.

The map $\theta$ is a bijection.

###### Proof.

We first prove that $\pi\in\mathcal{RSP}(n)$, for every $P\in\mathcal{P}_{n}$.
The procedure never moves $\min(B_{i})$ for all $i$. Thus, the minima remain
in increasing order and hence $\pi$ is a run-sorted permutation. We now show
that if $P$ has $k$ blocks, then $\pi$ has $k$ right-to-left minima.
Obviously, the minimum of each block of $P$ becomes a right-to-left minimum of
$\pi$. Let $b$ be in the block $B_{i}$ with $b\neq\min(B_{i})$. The integer
$b-1$ is in different block, say $B_{j}$. If $j<i$, then the procedure moves
$b$ to the block $B_{i-1}$ leaving $\min(B_{i})$ on its right in $\pi$.
Therefore, $b$ cannot be a right-to-left minimum of $\pi$. Suppose that $j>i$.
Since $b-1\geq\min(B_{j})$ we have $b>\min(B_{j})$, so the procedure moves
neither $b$ nor $\min(B_{j})$ which implies that $b$ cannot be a right-to-left
minimum of $\pi$. Therefore, $b$ is a right-to-left minimum of $\pi$ if and
only if $b=\min(B_{i}),i=1,\ldots,k$. We next prove that $\theta$ is one-to-
one. Suppose that $P\neq P^{\prime}$, where $P,P^{\prime}\in\mathcal{P}_{n}$.
If the number of blocks of $P$ and the number of blocks of $P^{\prime}$ are
different, then we are done since $\theta(P)$ and $\theta(P^{\prime})$ have
different number of right-to-left minima. Let $P=B_{1}/\cdots/B_{k}$ and
$P^{\prime}=B^{\prime}_{1}/\cdots/B^{\prime}_{k}$, and assume that there
exists an element $b\in B_{i}$ and $b\in B^{\prime}_{j}$ such that $B_{i}$ is
the block of $P$ and $B^{\prime}_{j}$ is the block of $P^{\prime}$ with $i\neq
j$. We take the minimal of these elements. Up to exchanging of $P$ and
$P^{\prime}$ we can suppose $i<j$.

  1. 1.

If $b=\min(B_{i})$, then $b$ is the $i$-th right-to-left minimum of
$\theta(P)$ and it would not be the case for $\theta(P^{\prime})$.

  2. 2.

Let $b\neq\min(B_{i})$ and let $b-1\in B_{m}$. Note that $b-1\in
B^{\prime}_{m}$ for the minimality of $b$. Three sub-cases are possible:

     * •

if $m<i<j$, then $\theta$ moves $b$ to the block $B_{i-1}$ of $P$ and moves
$b$ to the block $B^{\prime}_{j-1}$ of $P^{\prime}$;

     * •

if $i<m<j$, then $\theta$ leaves $b$ in the block $B_{i}$ in $P$ while it
moves $b$ to the block $B_{j-1}^{\prime}$ in $P^{\prime}$. Note that $j-1\neq
i$, because $i\lneq m\lneq j$;

     * •

if $i<j<m$, then $\theta$ leaves $b$ in the block $B_{i}$ in $P$ and leaves
$b$ in the block $B^{\prime}_{j}$ in $P^{\prime}$.

In all cases we have $\theta(P)\neq\theta(P^{\prime})$. Therefore, $\theta$ is
a bijection. ∎

We now present the inverse of $\theta$. Let $\pi\in\mathcal{RSP}(n)$ with $k$
right-to-left minima. We construct $P=\theta^{-1}(P^{\prime})$ as follows:

  * -

insert a slash before each right-to-left minimum of $\pi$ and let
$B_{1}/\cdots/B_{k}$ be the resulting partition;

  * -

for $i=k,\ldots,1$:

for $b$ in $B_{i}\setminus\\{\min(B_{i})\\}$ taken in increasing order

if $b-1\in B_{j},j\leq i$, then

move $b$ to $B_{i+1}$ and rearrange the elements in each block in increasing
order.

It can be easily checked that $\theta^{-1}$ constructs a separated partition.
For instance, if $\pi=13625784$, then by inserting slashes before each right-
to-left minimum we have the partition $136/2578/4$, and we move $7$ to $B_{3}$
since $6\in B_{1}$. So, $P=136/258/47$.

##  5 Non-crossing merging-free partitions

A non-crossing partition of a set $A=[n]$ is a partition in which no two
blocks “cross” each other, that is, if $a$ and $b$ belong to one block and $x$
and $y$ to another, then they cannot be arranged in the order $axby$. If one
draws an arc connecting $a$ and $b$, and another arc connecting $x$ and $y$,
then the two arcs cross each other if the order is $axby$ but not if it is
$axyb$ or $abxy$. In the latter two orders the partition
$\\{\\{a,b\\},\\{x,y\\}\\}$ is non-crossing [17].

######  Example 39.

In the following figure, the diagrams of
$P=1~{}2~{}5~{}7/~{}3~{}9~{}10/~{}4~{}6~{}8$ and of
$P^{\prime}=1~{}2~{}3~{}9~{}10/~{}4~{}6~{}7~{}8/~{}5$, respectively crossing
and non-crossing partitions.

Figure 1: Crossing and non-crossing merging-free partitions

We are interested in non-crossing merging-free partitions over $[n]$. We let
$\mathcal{M}_{n}$ denote the set of all non-crossing merging-free partitions
over $[n]$, and $\mathcal{M}_{n,t}:=\\{P\in
M_{n}:\operatorname{blocks}(P)=t\\}$, where $\operatorname{blocks}(P)$ denote
the number of blocks of the partition $P$.

######  Theorem 40.

For all integers $n\geq 1$ we have

$\sum_{P\in\mathcal{M}_{n}}q^{\operatorname{blocks}(P)}=\sum_{t=1}^{\frac{n+1}{2}}{n-1\choose
2(t-1)}q^{t}.$ (9)

###### Proof.

We use strong induction on $n$, and provide a recursive construction for the
merging-free partitions of $\mathcal{M}_{n}$. For $n=1$ the assertion is
trivially true (initial condition). Assume that $n\geq 2$ and the assertion is
true for all integers smaller than $n$. We distinguish two cases, depending on
if $n$ is in the same block of a merging-free partition $P$ as $n-1$ or not.
Suppose that $P$ has $t$ blocks.

Case-1. If $n$ is in the same block as $n-1$, then we delete $n$ and obtain a
non-crossing merging-free partition $P^{\prime}$ in $\mathcal{M}_{n-1,t}$. The
induction hypothesis implies that

$\displaystyle\sum_{\begin{subarray}{c}P\in\mathcal{M}_{n}\\\ n\text{ and
}n-1\text{ are in}\\\ \text{the same block of
}P\end{subarray}}q^{\operatorname{blocks}(P)}$
$\displaystyle=\sum_{\begin{subarray}{c}P^{\prime}\in\mathcal{M}_{n-1}\end{subarray}}q^{\operatorname{blocks}(P^{\prime})}$
$\displaystyle=\sum_{t=1}^{\frac{n}{2}}{n-2\choose 2(t-1)}q^{t}.$ (10)

Case-2. Suppose that $n$ is not in the same block as $n-1$ in $P$ and, that
$n$ is in the same block as a certain $i$, with $i<n-1$. Let $i$ be the
maximum of such elements. In this case, as we shall see, all the integers
$1,2,\ldots,i,n$ are in the first block of $P$. Assume for a contradiction
that there is $j\in\\{1,2,\ldots,i-1\\}$ such that $j$ is not in the same
block as $i$. We can choose $j$ such that $j+1$ is in the same block as $i$.
If $j$ is not the maximum element of its block, then the arc relating it to
its successor in the partition creates a crossing.

Figure 2:

If instead $j$ is the maximum element of its block, then there is an integer
$k>i$ such that $k$ is in the same block as an integer $j^{\prime}<j$ (and
hence creates a crossing with the arc $(i,n)$), because otherwise, the block
containing $j$ should be merged with one of the blocks containing integers of
$[i+1,n-1]$ and hence the partition would not be merging-free.

Figure 3:

Thus, the first block is uniquely determined by the integer $i$ and the
remaining $n-i-1$ integers must form a non-crossing merging-free partition. So
let $P^{\prime\prime}$ be the partition obtained by deleting the first block
of $P$ and then standardizing the resulting partition, that is, subtract $i$
from each of the remaining integers, so we have
$P^{\prime\prime}\in\mathcal{M}_{n-i-1,t-1}$. Thus by the induction hypothesis
and taking the sum over all possible $i$ we have

$\displaystyle\sum_{\begin{subarray}{c}P\in\mathcal{M}_{n}\\\ n\text{ and
}n-1\text{ are not}\\\ \text{in the same block of
}P\end{subarray}}q^{\operatorname{blocks}(P)}$
$\displaystyle=\sum_{i=1}^{n-2}q\sum_{\begin{subarray}{c}P^{\prime\prime}\in\mathcal{M}_{n-i-1}\end{subarray}}q^{\operatorname{blocks}(P^{\prime\prime})}$
$\displaystyle=\sum_{i=1}^{n-2}q\sum_{t=2}^{\frac{n-i+2}{2}}{n-i-2\choose
2(t-2)}q^{t-1}.$ (11)

Therefore, putting (5) and (5) together we have

$\displaystyle\sum_{P\in\mathcal{M}_{n}}q^{\operatorname{blocks}(P)}$
$\displaystyle=\sum_{t=1}^{\frac{n}{2}}{n-2\choose
2(t-1)}q^{t}+\sum_{i=1}^{n-2}q\sum_{t=2}^{\frac{n-i+2}{2}}{n-i-2\choose
2(t-2)}q^{t-1}$ $\displaystyle=\sum_{t=1}^{\frac{n}{2}}{n-2\choose
2(t-1)}q^{t}+\sum_{t=2}^{\frac{n+1}{2}}q^{t}\sum_{i=1}^{n-2t+2}{n-i-2\choose
2t-4}$ $\displaystyle=\sum_{t=1}^{\frac{n}{2}}{n-2\choose
2(t-1)}q^{t}+\sum_{t=2}^{\frac{n+1}{2}}{n-2\choose 2t-3}q^{t}$
$\displaystyle=q+\sum_{t=2}^{\frac{n+1}{2}}\left[{n-2\choose 2t-2}+{n-2\choose
2t-3}\right]q^{t}=\sum_{t=1}^{\frac{n+1}{2}}{n-1\choose 2t-2}q^{t}.$

∎

######  Corollary 41.

The number $m_{n}$ of non-crossing merging-free partitions over $[n]$ is equal
to $2^{n-2}$, where $n\geq 2$ and $m_{1}=m_{2}=1$.

###### Proof.

This follows from putting $q=1$ in (9) and using the well-known identity

$\sum_{k\geq 0}{n\choose 2k}=2^{n-1}.$

∎

A function $f\in\operatorname{RGF}(n)$ is said to avoid a pattern $212$ if
there does not exist some indices $a<b<c$ such that $f_{a}=f_{c}>f_{b}$. Let
$f$ be the canonical form of a set partition $P$ over $[n]$, then $P$ is non-
crossing if and only if $f$ is $212$-avoiding (see [8, 16]). A function
$f=f_{1}f_{2}\cdots f_{n}$ is said to be weakly uni-modal if there exists a
value $m\leq n$ for which it is weakly increasing for $i\leq m$ and weakly
decreasing for $i\geq m$, that is, $f_{1}\leq f_{2}\leq\cdots\leq f_{m}\geq
f_{m+1}\geq\cdots\geq f_{n}$. Thus, we have the following result.

######  Proposition 42.

Let $f$ be the canonical form of a merging-free partition $P$, then $f$ is
$212$-avoiding if and only if it is weakly uni-modal.

###### Proof.

Consider the forward implication. Since $f$ is a $\operatorname{RGF}$, if it
is not weakly uni-modal, although it is $212$-avoiding, then it contains
either a pattern $312$ or $213$. If $f$ contains a $312$, then before the $3$
there is a $2$ and hence it contains $212$. This is a contradiction. Suppose
that $f$ contains a pattern $213$ in the positions $a<a+1<b$, where $b$ is the
smallest such integer. If $f_{b}$ is a left-to-right maximum letter in $f$,
then there exists some integer $c>b$ such that $f_{c}=f_{b}-1$ because $P$ is
merging-free. Since $f$ is a $\operatorname{RGF}$ there exists an integer
$d\leq a$ such that $f_{d}=f_{c}$ because of the choice of $b$. Thus, $f$
contains the pattern $212$ in $d<a+1<c$ and this is a contradiction. If
$f_{b}$ is not a left-to-right maximum letter, then we have some integer $e<a$
such that $f_{e}=f_{b}$, hence $f$ contains the pattern $212$ in $e<a+1<b$ and
this is also a contradiction. Therefore, $f$ is weakly uni-modal. The converse
implication is clearly true. ∎

##  6 The Exhaustive Generation

We used the results presented here – and in particular the construction shown
in the proof of the recurrence relation for the sets $\mathcal{RSP}(n,k)$ – to
implement an algorithm to generate these objects, that is, an algorithm which,
for any fixed integer $n$, solves the following problem:

Problem: Run-Sorted-Permutations-Generation

Input: an integer $n$

Output: the set of all run-sorted permutations $\mathcal{RSP}(n)$, partitioned
into the subsets $\mathcal{RSP}(n,k)$.

Compared to previous, more naive algorithms, this algorithm has allowed some
researchers to extend the range of calculations performed in acceptable time
and confirm various conjectures for a larger value of $n$. Rather than
implementing recursive algorithms we made use of dynamic programming and
obtained iterative algorithms. All algorithms implements a partition as a list
of integers and a set of partitions as a list of partitions and hence as a
list of lists of integers. Algorithm 1 is used to generate run-sorted
permutations in $\mathcal{RSP}^{(1)}(n,k)\subseteq\mathcal{RSP}(n,k)$ from
$\mathcal{RSP}(n-1,k)$ based on the idea presented in section 3.

Algorithm 1 Exhaustive Generation of Run-Sorted Permutations in
$\mathcal{RSP}^{(1)}(n,k)$ from the partitions of $\mathcal{RSP}(n-1,k)$

Procedure: FUNCTION_ONE$(\mathcal{RSP},n)$

$\mathcal{RSP}$ is a list of lists whose elements represent run-sorted
permutations of size $n-1$, and $n$ is the integer to be inserted so that the
number of blocks remains the same.

$L\longleftarrow[~{}]$

for $\pi$ in $\mathcal{RSP}$ do

for $t$ in $Range(Length(\pi)-1)$ do

if $\pi[t]>\pi[t+1]$ then

$\pi^{\prime}\longleftarrow\pi.Insert(t+1,n)$

$L.Append(\pi^{\prime})$

end if

end for

$\pi^{\prime}\longleftarrow\pi.Append(n)$

$L.Append(\pi^{\prime})$

end for

return $L$

The exhaustive generation of run-sorted permutations in
$\mathcal{RSP}^{(2)}(n,k)$ starts from the set
$[n-2]\times\mathcal{RSP}(n-2,k-1)$, that is, from a pair
$(i,\pi)\in[n-2]\times\mathcal{RSP}(n-2,k-1)$ we obtain a run-sorted
permutation $\pi^{\prime}\in\mathcal{RSP}^{(2)}(n,k)$ using Algorithm 2. The
idea is based on the operation given in section 3.

Algorithm 2 Generation of a run-sorted permutation of
$\mathcal{RSP}^{(2)}(n,k)$ from an element of
$[n-2]\times\mathcal{RSP}(n-2,k-1)$

Procedure: RUN_SORTED_PERMUTATION_SIZE_INC_BY_TWO($(\pi,p)$)

$\pi$ is a run-sorted permutation in $\mathcal{RSP}(n-2,k-1)$ and $p$ is an
integer in $[n-2]$.

for $t$ in $Range(Length(\pi))$ do

if $\pi[t]>p$ then

$\pi[t]\longleftarrow\pi[t]+1$

end if

end for

$pos=Length(\pi)-1$

while $\pi[pos]>p$ do

$pos\longleftarrow pos-1$

end while

$\pi.Insert(pos+1,Length(\pi)+2)$

$\pi.Insert(pos+2,p+1)$

return $(\pi)$

Algorithm 3 calls Algorithm 2 and gives us the exhaustive generation algorithm
for the set of run-sorted permutations in $\mathcal{RSP}^{(2)}(n,k)$.

Algorithm 3 Exhaustive Generation of Run-sorted Permutations in
$\mathcal{RSP}^{(2)}(n,k)$

Procedure: FUNCTION_TWO$(\mathcal{RSP})$

$\mathcal{RSP}$ is a list of lists whose elements represent a run-sorted
permutation of $\mathcal{RSP}(n-2,k-1)$.

$L\leftarrow[~{}]$

for $\pi$ in $\mathcal{RSP}$ do

for $p$ in $Range(1,Length(\pi)+1)$ do

$\pi^{\prime}\longleftarrow$ RUN_SORTED_PERMUTATION_SIZE_INC_BY_TWO$(\pi,p)$

$L.Append(\pi^{\prime})$

end for

end for

return $L$

Now we present the main exhaustive generation algorithm that generates all and
only those run-sorted permutations in $\mathcal{RSP}(n)$ for all possible $n$.
The algorithm returns a list of lists of lists of integers, namely the list
$\mathcal{RSP}(n)=[\mathcal{RSP}(n,1),\mathcal{RSP}(n,2),\ldots,\mathcal{RSP}(n,n)]$
where each element $\mathcal{RSP}(n,k)$ is the list of all run-sorted
permutations of $[n]$ having $k$ runs. Since $\mathcal{RSP}(n,k)=\varnothing$
if $k>\lceil{\frac{n}{2}}\rceil$, the algorithm can be optimized by competing
only those sets $\mathcal{RSP}(n,k)$ that are not empty. As we said, the
algorithm is based on dynamic programming. We stock the values of the lists
$\mathcal{RSP}(n-1)$ and $\mathcal{RSP}(n-2)$ and use them to compute the list
$\mathcal{RSP}(n)$. In order to save memory, only the last two lists are kept
at any time: the list $\mathcal{RSP}(n-1)$ will be stocked in a variable
called LastRow and the list $\mathcal{RSP}(n-2)$ will be stocked in a variable
called RowBeforeLast, while list $\mathcal{RSP}(n)$ will be affected to the
variable CurrentRow. At the end of each iteration, the three variables are
shifted.

Algorithm 4 Exhaustive Generation of Run-Sorted Permutations

Procedure: RUN_SORTED_PERMUTATIONS($n$)

$\mathcal{RSP}$ is a list of lists whose elements represent a run-sorted
permutation of $\mathcal{RSP}(n-2,k-1)$.

RowBeforeLast$\longleftarrow[[[1]]]$

LastRow$\longleftarrow[[[1,2]],[~{}]]$

for $i$ in $Range(3,n+1)$ do

CurrentRow$\longleftarrow[~{}]$

CurrentRow$.Append$(FUNCTION_ONE(LastRow$[0],i$))

for $j$ in $Range(1,\lceil\frac{i}{2}\rceil)$ do

CurrentRow$.Append($FUNCTION_ONE(LastRow$[j],i$)

CurrentRow$.Append($FUNCTION_TWO$($RowBeforeLast$[j-1]))$

end for

RowBeforeLast$\longleftarrow$ LastRow

LastRow$\longleftarrow$ CurrentRow

end for

All these algorithms have been implemented in Python.

######  Example 43.

When RUN_SORTED_PERMUTATIONS($n$) is executed for $n=5$ we get the list
$\mathcal{RSP}(5)$:

$\displaystyle[[[1,2,3,4,5]],$
$\displaystyle[[1,3,4,5,2],[1,3,4,2,5],[1,3,5,2,4],[1,3,2,4,5],[1,4,5,2,3],[1,4,2,3,5],[1,2,4,5,3],$
$\displaystyle[1,2,4,3,5],[1,5,2,3,4],[1,2,5,3,4],[1,2,3,5,4]],$
$\displaystyle[[1,5,2,4,3],[1,4,2,5,3],[1,3,2,5,4]],$ $\displaystyle[~{}]].$

Observe that $a_{5,1}=1,a_{5,2}=11,a_{5,3}=3,a_{5,4}=0$, and
$a_{5}=1+11+3+0=15$.

##  7 Acknowledgements

The first author is grateful for the financial support extended by IRIF, the
cooperation agreement between International Science Program (ISP) at Uppsala
University and Addis Ababa University, and the support by the Wenner-Gren
Foundations. We appreciate the hospitality we got from IRIF during the
research visits of the first author. We also thank our colleagues from CoRS
(Combinatorial Research Studio) for valuable discussions and comments, and in
particular we thank Dr. Per Alexandersson and Prof. Jörgen Backelin for their
useful discussions and suggestions.

## References

  * [1] P. Alexandersson and O. Nabwanda, Peaks are preserved under run-sorted, Enumerative Combinatorics and Applications, 2:1 (2022), Article #S2R2.
  * [2] J. Baril and V. Vajnovszki, A permutation code preserving a double Eulerian bistatistic, Discrete Applied Mathematics, 224 (2017), 9-15.
  * [3] H. W. Becker, Planar rhyme schemes, Bull. Amer. Math. Soc., 58 (1952), 39. Math. Mag., 22 (1948-49), 23-26.
  * [4] F. Beyene and R. Mantaci, “Nom” code and pattern avoidance in a Catalan numbered class of permutations, 2021, https://arxiv.org/abs/2111.11527v1.
  * [5] M. Bona, Introduction to Enumerative Combinatorics, The McGraw Hill Companies, 2007.
  * [6] D. Callan, Pattern avoidance in “flattened” partitions. Discrete Math., 309(2009), 4187-4191.
  * [7] G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Mathematics, 4 (1972), 333-350.
  * [8] Z. Lin and Sh. Fu, On 1212-avoiding restricted growth functions, Electronic Journal of Combinatorics, 24(1) (2017), $\\#$P1.53.
  * [9] T. Mansour, Combinatorics of Set Partitions. Taylor & Francis Group, LLC, 2013.
  * [10] T. Mansour, M. Shattuck and S. Wagner, Counting subwords in flattened partitions of sets, Discrete Mathematics 338 (2015), 1989-2005.
  * [11] R. Mantaci and F. Rakotondrajao, A permutation representation that knows what “Eulerian” means, Discrete Mathematics and Theoretical Computer Science, 4 (2001), 101-108.
  * [12] A. O. Munagi, Set partitions and separations, International Journal of Mathematics and Mathematical Sciences 3 (2005), 451-463.
  * [13] O. Nabawanda, F. Rakotondrajao, and A.S. Bamunoba, Run distribution over flattened partitions, Journal of Integer Seq., 23 (2020), Article 20.9.6
  * [14] M. Orlov, Efficient generation of set partitions, (2002).
  * [15] G. Rota, The number of partitions of a set, Amer. Math. Monthly 71 (1964), 498-504.
  * [16] R. Simion, Combinatorial statistics on non-crossing partitions, Journal of Combinatorial Theory, 66 (1994), 270-301.
  * [17] R. Simion, Non-crossing partitions, Discrete Mathematics, 217 (2000), 367-409.
  * [18] N. J. A. Sloane et al. , The on-line encyclopedia of integer sequences, Available at http://oeis.org, 2019.
  * [19] R. P. Stanley, Enumerative Combinatorics, 1, Cambridge Studies of Advanced Mathematics, 2011.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A15,
05A19.

_Keywords:_ merging-free partition, canonical form, run-sorted permutation,
non-crossing partition, algorithm.


Enhancing Quantum Support Vector Machines through Variational Kernel Training

###### Abstract

Quantum machine learning (QML) has witnessed immense progress recently, with
quantum support vector machines (QSVMs) emerging as a promising model. This
paper focuses on the two existing QSVM methods: quantum kernel SVM (QK-SVM)
and quantum variational SVM (QV-SVM). While both have yielded impressive
results, we present a novel approach that synergizes the strengths of QK-SVM
and QV-SVM to enhance accuracy. Our proposed model, quantum variational kernel
SVM (QVK-SVM), leverages the quantum kernel and quantum variational algorithm.
We conducted extensive experiments on the Iris dataset and observed that QVK-
SVM outperforms both existing models in terms of accuracy, loss, and confusion
matrix indicators. Our results demonstrate that QVK-SVM holds tremendous
potential as a reliable and transformative tool for QML applications. Hence,
we recommend its adoption in future QML research endeavors.

Quantum Machine Learning, Quantum Support Vector Machine, Kernel, Quantum
Variational Algorithm, Classification.

##  I Introduction

Quantum computing is an exciting and quickly growing field that could change
many areas of science and technology. Machine learning (ML) is one of the most
promising quantum computing applications, where quantum algorithms can
potentially provide exponential speedups over classical algorithms. This field
is known as Quantum machine learning (QML). Quantum machine learning is an
emerging field of research that combines the principles of quantum computing
and machine learning. QML algorithms can solve complex problems more
efficiently and cost-effectively than classical machine learning algorithms.
One of the most promising QML algorithms is the quantum support vector machine
(QSVM), an extension of the classical support vector machine (SVM) to the
quantum realm.
The classical SVMs are a powerful class of ML algorithms for classification
and regression analysis. The development of SVMs can be traced back to the
early $1960$s when Vladimir Vapnik and his colleagues began working on a new
approach to pattern recognition [1, 2]. However, only in the $1990$s did SVMs
gain widespread attention in the ML community [3], thanks to Corinna Cortes
and Vladimir Vapnik’s pioneering work at AT&T Bell Labs. They introduced the
idea of maximum-margin hyperplanes, decision boundaries that separate data
points from different classes with the most significant possible margin [4].
This approach allowed SVMs to perform excellent generalization, even with
small training datasets. Since then, SVMs have become one of the most
extensively used and popular machine learning models and have been
successfully applied to various fields, including image recognition, text
classification, and bioinformatics. However, as the size of the dataset
increases, the computational complexity of SVM also increases, making it
difficult to handle large datasets. Still, the QSVM aims to overcome this
limitation by leveraging the principles of quantum computing to accelerate the
SVM algorithm. Over the years, there has been significant research in the
field of QSVM, exploring various theoretical and practical aspects of the
algorithm. Researchers have developed several techniques to enhance the
performance of QSVM, including the development of quantum kernel methods,
quantum feature maps, and quantum optimization techniques.
One of the early works in QSVM was proposed by Rebentrost et al. in $2014$
[5], which introduced a quantum algorithm for SVM classification that provides
an exponential speedup over classical algorithms. Another essential aspect of
QSVM is its robustness to noise. In $2015$, Li et al. demonstrated a QML
algorithm for handwriting recognition on a four-qubit nuclear magnetic
resonance (NMR) test bench [6]; the authors argued that quantum speedup would
be highly attractive for tackling significant data challenges. However, this
algorithm was specific to NMR-based systems and could not be easily applied to
other QML platforms.
And after different interesting works, in $2019$, Havlicek et al. demonstrated
that supervised quantum machine learning models, including QSVM [7], can be
robust to noise, increasing their practicality for real-world applications.
Subsequently, several studies have been conducted to improve the performance
of QSVM, including using quantum feature maps for kernel-based learning, as
proposed by Park et al. in $2020$ [9]. Another interesting research explores
the potential use of quantum state encoding as a nonlinear feature map,
enabling efficient computations in a large Hilbert space efficiently and
proposes two approaches for building a quantum model for classification,
illustrated with mini-benchmark datasets [8].
In contrast, Liu et al. established a rigorous quantum speedup for supervised
classification using a general-purpose quantum learning algorithm that only
requires classical access to data. This algorithm represents a significant
advancement [10]. In the same year, Schuld et al. investigated the impact of
quantum data encoding strategies on the efficacy of parametrized quantum
circuits in approximating functions [11], and the authors showed that quantum
models could realize all possible sets of Fourier coefficients. Therefore, if
the accessible frequency spectrum is asymptotically rich enough, such models
are universal function approximators. This result has significant implications
for developing QML algorithms to tackle complex data challenges.
In another $2021$ paper [12], Schuld, M explored the theoretical foundations
of the link between quantum computing and kernel methods in machine learning,
systematically rephrased supervised QML models as kernel methods, replacing
many near-term and fault-tolerant QML models with a general SVM whose kernel
computes distances between data-encoding quantum states. This approach has the
potential to significantly reduce the complexity of QML algorithms and improve
their performance.
In $2022$, Zhang et al. proposed a new quantum optimization algorithm for QSVM
that can improve the efficiency and scalability of QSVM on large datasets
[13]. These advancements in QSVM and its related techniques have made it a
promising candidate for solving complex problems in various fields, including
bioinformatics, finance, image recognition, and material physics. One of the
recent works in QSVM was proposed by Jiang et al. in $2023$ [14], which
introduced a quantum algorithm for SVM classification that leverages the
quantum phase estimation algorithm to estimate the kernel matrix. This
approach leads to significant speedup compared to classical SVM algorithms,
making QSVM a more efficient choice for large-scale datasets.
In this paper, we build upon these studies and suggest a new QML model for
classification that merges the two more accurate approaches identified by
Schuld, M and the different works mentioned above. Our model leverages the
expressive power of parametrized quantum circuits as function approximators
and uses a kernel method to compute distances between data-encoding quantum
states. We present theoretical analyses and numerical simulations to
demonstrate the potential of our model for tackling classification tasks. Our
results suggest that our model outperforms existing QML algorithms,
highlighting its potential for future real-world problems and applications.
This paper is divided as follows:
In §II, We provide an overview of classical support vector machines,
highlighting their principal features and limitations that motivate the
exploration of more accurate implementations in quantum machine learning.
In §III, we describe the quantum model for support vector machines and explain
the three implementations, including our proposed approach, the quantum
variational kernel SVM.
In §IV, we present the results obtained using Pennylane by comparing the
accuracy, loss, and confusion matrix indicators of the three quantum SVM
models on the Iris dataset.
In §V, we discuss our findings’ implications and highlight future research
directions in this field.

##  II Classical Support Vector Machine

In classical machine learning, SVMs are used in supervised models to analyze
data for classification and regression. By using this algorithm, we can also
perform binary classification and multi-classification. To understand this, we
are taking an example. For simplicity, we are taking a binary classification
example. Suppose we have a collection of circles and rectangles in a 2D plane.
Our job is to classify the circles and rectangles. This problem has two types,
(a) linear and (b) non-linear, as shown in Fig.1.

(a) A linear problem

(b) A Non-linear problem

Figure 1: Graphical representation of linear and non-linear SVMs problems.

###  II.1 Linear SVMs

First of all, we are discussing linear SVMs. We take a dataset of $n$ points
of the form $(x_{1},y_{1}),(x_{2},y_{2}),...(x_{n},y_{n})$. Here $y_{i}$ are
either $1$ or $-1$, and each $x_{i}$ is a p-dimensional real vector. We have
to draw the positive hyperplane $(H_{+})$, negative hyperplane $(H_{-})$, and
margin as shown in Fig.2. We can find the margin using the formula
$=H_{+}+H_{-}$.

Given a $D$-dimensional vector $\textbf{X}_{0}\in\mathbb{R}^{D\times 1}$, and
a $(D-1)$-dimensional linear hyperplane $\mathcal{H}\mathrel{\mathop{\mathchar
58\relax}}\textbf{W}^{T}\textbf{X}+\textbf{B}-\mathbf{Y}=\boldsymbol{0}$,
where $\mathbf{W}=\left(w_{1},w_{2},\ldots,w_{n}\right)$ is the weights
vector, $\mathbf{B}$ is the bias vector, and $\Phi(\mathbf{X}_{n})$ is the
projection of the point $\mathbf{X}_{n}$ into the nonlinear feature space. The
goal is to ascertain the hyperplane that optimally separates the vectorial
points into classes while maximizing the margin between the hyperplane and the
closest datapoints from each class. Mathematically, we translate this as a
quadratic programming problem with linear constraints, whereby our goal is to
determine the value of the weights that will maximize the margin

$\mathbf{W}^{*}=\underset{\mathbf{W}}{\text{arg
max}}\;\frac{1}{||\mathbf{W}||_{2}}\left\\{\underset{n}{\min}\;\mathbf{Y}_{n}\left[\mathbf{W}^{T}\Phi(\mathbf{X}_{n})+\mathbf{B}\right]\right\\},$
(1)

where $||\mathbf{W}||_{2}=\left(\sum_{i=1}^{n}w_{i}^{2}\right)^{1/2}$.
Mathematically, we can translate this into the primal form SVM optimization
problem $\underset{n}{\min}\;\frac{1}{2}||\mathbf{W}||_{2}\quad\text{subject
to}\;\mathbf{Y}_{n}\left[\mathbf{W}^{T}\Phi(\mathbf{X}_{n})+\mathbf{B}\right]\geq\mathbf{1}\;\text{for
every}\;n.$

Figure 2: Geometric components of support vector machines.

###  II.2 Non-linear SVMs

As shown in Fig.2, the support vectors are the vectors utilized to generate
both the positive and negative hyperplanes. Maximizing the margin length in
this specific model is imperative to achieve precise classification and high
accuracy.

In order to effectively tackle the non-linear problem we are facing, the
kernel trick presents a compelling solution. This technique involves using a
kernel function with data points, acquiring higher-dimensional vector points
in our feature space. A plethora of kernel functions exists, each tailored to
solve different problems. Below, we present a comprehensive list of some of
these kernel functions:

  * •

Polynomial (Homogeneous): denoted as $K(a_{i},a_{j})=(a_{i}\cdot a_{j})^{d}$,
where $d$ is a positive integer that determines the degree of the polynomial.
By setting $d$ to $1$, it becomes a linear kernel that is particularly useful
for linearly separable data.

  * •

Polynomial (Inhomogeneous): which incorporates a constant term $r$ to the dot
product of the input vectors, resulting in $K(a_{i},a_{j})=(a_{i}\cdot
a_{j}+r)^{d}$. This kernel is well-suited for capturing nonlinear
relationships between the data.

  * •

Sigmoid function (Hyperbolic tangent): based on the hyperbolic tangent
function, takes the form $K(a_{i},a_{j})=\tanh(ka_{i}\cdot a_{j}+c)^{d}$,
where $k$ and $c$ are kernel parameters. This kernel can be used to model data
that exhibits sigmoidal behavior and has been applied in various applications
such as image classification and text mining.

After applying the kernel function to our data points, we have to do the same
operation as in linear. Then we can complete the classification successfully.
We modify the primal form of the linear SVM to include the slack variables
$\boldsymbol{\xi}\geq\boldsymbol{0}$
$\underset{n}{\min}\;\frac{1}{2}||\mathbf{W}||_{2}+\mathbf{C}\sum_{n}\boldsymbol{\xi}_{n}\quad\text{subject
to}\;\mathbf{Y}_{n}\left[\mathbf{W}^{T}\Phi(\mathbf{X}_{n})+\mathbf{B}\right]\geq
1-\boldsymbol{\xi}_{n}\;\text{for every}\;n.$ In addition to quadratic
programming, numerous alternative techniques exist for resolving this problem.
These include the approaches of Lagrange multipliers, sequential minimal
optimization, interior point methods, gradient descent (GD), stochastic
gradient descent (SGD), and kernel methods.

###  II.3 Disadvantages of Classical SVMs

Despite the popularity of classical SVMs, they have certain limitations that
constrain their optimal performance. One of the significant limitations is
handling high-dimensional feature spaces, which can result in slow training
times and overfitting problems. Another area for improvement is the dependence
on kernel functions, which may not effectively capture complex data
relationships. Furthermore, classical SVMs are not easily scalable to large
datasets and demand extensive parameter tuning for accurate results.
Researchers have turned to quantum machine learning to overcome these
limitations and explore more precise and efficient alternatives. In the next
section, we examine how quantum support vector machines can effectively tackle
these challenges and provide a promising solution for enhancing classification
performance.

##  III Quantum Support Vector Machine

Quantum Support Vector Machine is a burgeoning area of research in quantum
machine learning that offers promising potential for enhanced computational
performance in classification and regression tasks. While classical SVM has
been widely utilized in machine learning, QSVM exploits the unique properties
of quantum mechanics to outperform classical SVM in specific applications. The
QSVM algorithm involves mapping input data onto a quantum state, which is
subsequently subjected to quantum circuit processing to generate the
classification outcome. The described circuit comprises a sequence of quantum
gates that manipulate the quantum state and execute the SVM algorithm. The
classification outcome is obtained by measuring the circuit’s output.
In previous works, as mentioned in the introduction sections (I), QSVMs have
been implemented using various approaches, such as the quantum kernel method,
the quantum matrix inversion method, and the quantum feature mapping method.
Nevertheless, these methodologies possess certain constraints, such as high
error rates, enormous computational resources, and scalability issues. This
section will focus on three recent approaches to QSVM: the quantum kernel
approach, the quantum variational approach, and a novel hybrid approach that
combines the quantum kernel approach with the quantum variational circuit.
These approaches have shown promising results and offer potential accuracy,
scalability, and robustness improvements. The following subsections will
describe each approach, highlighting the steps and circuits used to develop
the QSVM models.

In each approach, the first step in our methodology involves the conversion of
our classical datapoints into quantum states. To achieve this, we begin by
encoding the data points using a quantum circuit, as depicted in Fig.3.
Subsequently, we establish our data set and opt for the iris data set for
simplicity. Our selection of qubits is based on the features outlined in our
data set. We utilize a quantum model represented as follows:

$f(x)=\langle\phi(x)|M|\phi(x)\rangle.$ (2)

Here $|\phi(x)\rangle$ is prepared using an encoding circuit, and $M$ is the
measurement operator. $M$ is observable that is defined as:

$M(\theta)=G^{\dagger}(\theta)\sigma^{0}_{z}G(\theta).$ (3)

Figure 3: Quantum circuit architecture for QSVMS: Generalized model
description.

###  III.1 Quantum Kernel Support Vector Machine

We propose implementing support vector machines with a kernel computed by a
quantum circuit in this approach. Specifically, we utilize the angle-embedding
template in conjunction with a SWAP test to evaluate the quantum kernel; this
method reduces the number of required qubits by half, rendering it more viable
for real-world implementations.
The kernel function is a central concept in SVMs, which are a popular class of
ML algorithms for classification and regression tasks; this kernel function is
a measure of similarity between two data points in a high-dimensional feature
space and is used to map the data into a space where a linear classifier can
separate the classes. This method can be used with any kernel function, like
the linear kernel and radial basis function (RBF) kernel, computed using a
quantum circuit, and we call it the quantum kernel. Mathematically, the
quantum kernel is represented by the following equation:

$k(x_{1},x_{2})=|\langle\phi(x_{1})|\phi(x_{2})\rangle|^{2},$ (4)

Where $x_{1}$ and $x_{2}$ are the input feature vectors, and
$\phi(x_{i})_{i=1,2}$ denotes the quantum embedding of $x$ into a quantum
state with the angle encoding routines $S(x_{1})$ and $S(x_{2})$, we then
apply the inverse embedding to one of the states and compute the overlap
between the two states using a SWAP test, and the SWAP test is a simple
quantum protocol that measures the overlap between two quantum states, we can
represent this step by the following equation:

$\langle
SWAP\rangle=|\langle\phi(x_{1})\otimes\phi(x_{2})|SWAP|\phi(x_{1})\otimes\phi(x_{2})\rangle|^{2},$
(5)

$SWAP$ is the swap gate, and $|\langle SWAP\rangle|^{2}$ represents the
probability of measuring the two quantum embeddings in the same state.
Finally, we use the Hermitian observable to measure the projector onto the
initial state $|0...0\rangle\langle 0...0|$, and Fig.4 present this circuit.

Figure 4: QK-SVM circuit.

The advantage of this approach is that it has the potential to scale to larger
datasets by utilizing quantum hardware with more qubits. As we mentioned, it
also requires only half the number of qubits as the number of features, and
this is because we can prepare the two data points on the same set of qubits
using the angle-embedding template and then apply the inverse embedding to one
of the states, as shown in Fig.5 using Pennylane [15].

Figure 5: QK-SVM circuit using Pennlyne.

###  III.2 Quantum Variational Support Vector Machine

In this method, we propose a novel approach for training data directly by
utilizing an ansatz for the variational circuit. This ansatz, a quantum
operation applied in multiple layers, enhances expressivity. Although the
variational circuit cannot optimize the exact cost, similar to SVMs, we have
incorporated a bias term termed hinge loss in our quantum model to minimize
the gap between the two. And in the quantum node, we explicitly apply the
parameter shift differentiation method. The variational quantum circuit is
given in Fig.3. We have given our method’s encoding, processing, and
measurement steps in this circuit. The quantum variational method is a key
concept in quantum machine learning, a rapidly growing field that aims to
leverage quantum computing to develop robust machine learning algorithms. This
answer will discuss the quantum variational method and its applications in
quantum machine learning.

Mathematically, the quantum variational method can be described as follows:
Suppose we have a parameterized quantum circuit that can be represented by the
unitary operator $U(\theta)$, where $\theta$ is a vector of parameters. Given
a set of training data (x1, y1), (x2, y2), …, (xn, yn), where xi is an input
and yi is the desired output. We want to find the values of $\theta$ that
minimize the cost function:

$f(\theta)=\frac{1}{n}\sum_{i=1}^{n}L(y_{i},U(\theta)x_{i}).$ (6)

Here, $L(y,y^{\prime})$ measures the difference between the desired output y
and the actual output y’ produced by the quantum circuit. This cost function
is typically chosen to be a function that can be efficiently computed on a
classical computer. We use an iterative optimization algorithm such as
gradient descent to find the optimal values of $\theta$ that minimize the cost
function. Starting from an initial guess for $\theta$, we compute the gradient
of the cost function concerning each parameter and update the parameters in
the direction of the negative gradient. This process is repeated until the
cost function converges to a minimum. The circuit structure is given below in
Fig.6.

Figure 6: QV-SVM circuit using Pennlyne.

###  III.3 Quantum Variational Kernel Support Vector Machine

This study proposes a new approach for quantum support vector machines, which
we call Quantum Variational Kernel Support Vector Machine (QVK-SVM). It
combines two distinct methods to enhance the performance of quantum kernels
and variational circuits. The first method utilizes the angle-embedding
template to prepare the quantum states used to compute the kernel, as we
explained in subsection III.1. The overlap between the two states is measured
using a SWAP test, which requires only half the qubits.

The second method involves utilizing a variational circuit trained through the
variational training principle, as outlined in Subsection III.2. The ansatz of
the circuit can be improved by adding more layers, thereby enhancing its
ability to express itself. Additionally, a bias term is incorporated into the
quantum model to facilitate training on the hinge loss. The quantum node
utilizes the parameter-shift differentiation method, which is very efficient
on hardware.

The proposed circuit of the new approach consists of three main components:
AngleEmbedding, the adjoint of AngleEmbedding, and StronglyEntanglingLayers,
as shown in Fig.7.

The AngleEmbedding is used to prepare the quantum states of the data points,
which are then fed into the adjoint of the AngleEmbedding to prepare the
inverse embedding. The StronglyEntanglingLayers component is used to apply the
variational circuit, which is trained using the hinge loss.

The proposed approach has several advantages. First, it combines the strengths
of both methods to enhance the performance of QSVMs. Second, it utilizes the
variational training principle, allowing greater control over the training
process. Third, it uses the parameter-shift differentiation method, which
works well on hardware. Finally, the proposed circuit is simple and easy to
implement, making it suitable for practical applications.

The proposed approach for quantum SVMs combines the angle-embedding kernel and
the variational circuit to enhance the performance of QSVMs. The proposed
approach has several advantages over the existing methods, including greater
control over the training process, better hardware compatibility, and ease of
implementation. Future research could explore the application of the proposed
approach to other datasets and investigate the potential of the approach for
solving more complex problems.

Figure 7: QVK-SVM circuit using Pennlyne.

##  IV Results and Discussion

The results and discussion of the three models in this research demonstrate
the potential of quantum machine learning in enhancing binary classification
tasks, particularly the quantum support vector machine. The first model, QK-
SVM, employed a quantum kernel approach and delivered an impressive overall
accuracy of $96.34\%$ on the test set. The second model, QV-SVM, utilized
variational training with a quantum support vector machine and achieved a
maximum accuracy of $95.43\%$ on the test set. The third and final model, QVK-
SVM, combined quantum kernel and variational training to yield the most
promising results, with an accuracy of $98.48\%$ on the test set, as evidenced
by the data presented in Table 1.

Table 1: Comparison of confusion matrix indicators for QK-SVM, QV-SVM, and QVK-SVM models. Model | Accuracy | Precision | Recall | Specificity | F1 Score
---|---|---|---|---|---
QK-SVM | 96.34% | 93.77% | 89.64% | 95.11% | 91.64%
QV-SVM | 95.43% | 90.89% | 89.11% | 92.88% | 89.99%
QVK-SVM | 98.48% | 96.27% | 92.35% | 97.85% | 94.24%

Table 1 displays the performance metrics for the three models: QK-SVM, QV-SVM,
and QVK-SVM. Our findings indicate that QK-SVM achieved high precision and
recall rates, indicating the robustness of the model in correctly identifying
the different classes of Iris flowers. QV-SVM achieved high specificity and F1
score values, further validating the effectiveness of the quantum support
vector machine using the variational algorithm. QVK-SVM achieved high
precision, recall, and specificity; these results confirm the efficacy of QVK-
SVM and highlight its potential as a reliable tool for ML applications.

The QK-SVM model achieved a maximum accuracy of $96.34\%$, high precision and
recall rates, and a corresponding specificity and F1 score. Fig.9 and Fig.9
illustrate the loss and accuracy curves for both the training and testing
sets, demonstrating a clear improvement in the model’s performance during
training.

Figure 8: Graph of loss function of the QK-SVM.

Figure 9: Accuracy line graph of the QK-SVM.

The QV-SVM model achieved a steady improvement in performance as the number of
iterations increased, with training losses ranging from $1.00$ to $0.49$ and
testing losses ranging from $0.98$ to $0.47$. The model achieved an absolute
accuracy of $95.43\%$, with high precision and recall rates. Fig.11 and Fig.11
illustrate the loss and accuracy plots, respectively, highlighting the model’s
optimization over the iterations.

Figure 10: Graph of loss function of the QV-SVM.

Figure 11: Accuracy line graph of the QV-SVM.

Our suggested model represents a novel approach that combines the quantum
kernel and variational algorithm used in QV-SVM and QK-SVM, respectively. The
results of our QVK-SVM model indicate that this combined approach is highly
effective for solving classification problems, even on relatively small
datasets.

The proposed QVK-SVM model achieved an impressive accuracy of $98.48\%$ on the
test set, with a corresponding F1 score of $91.64\%$. Fig.13 shows the
convergence of the training and testing losses throughout the experiment,
demonstrating that the model could optimize the loss function to achieve high
accuracy. Fig.13 displays the corresponding training and testing accuracies,
showing that the model’s accuracy improved steadily throughout the experiment,
reaching a peak of $98\%$ accuracy on the test set.

Figure 12: Graph of loss function of the QVK-SVM.

Figure 13: Accuracy line graph of the QVK-SVM.

Furthermore, the superior performance of QVK-SVM, compared to QV-SVM and QK-
SVM, suggests that the combination of these approaches can provide a more
robust and reliable solution to binary classification tasks.

The results show the potential of quantum machine learning in enhancing binary
classification tasks, especially the quantum support vector machine. As
demonstrated in our novel method, combining the quantum kernel and variational
algorithm represents a promising approach that could be extended to other
datasets and classification problems.

##  V Conclusion

This study delved into applying quantum support vector machines for binary
classification tasks. Specifically, two pre-existing methods, the quantum
kernel support vector machine and the quantum variational support vector
machine, were compared and evaluated for their respective strengths and
limitations. In addition, a novel approach was developed by combining these
two methods, resulting in the quantum variational kernel support vector
machine. The proposed QVK-SVM approach demonstrated exceptional accuracy and
loss reduction performance, offering a promising solution for binary
classification tasks in quantum machine learning. These findings hold
significant potential for advancing the field of quantum machine learning and
its diverse applications. The QVK-SVM approach represents a noteworthy
contribution to this field’s development and has clear implications for future
research endeavors.
The proposed method presents an opportunity for further research to explore
its efficacy in resolving intricate issues across various datasets. Advanced
optimization techniques and the development of new quantum algorithms can
enhance the efficiency and scalability of the approach. Furthermore, the
potential of quantum machine learning can be investigated by extending the
proposed method to other machine learning models, such as neural networks and
decision trees. Through these efforts, the proposed approach can advance the
field of quantum machine learning and unlock new opportunities for addressing
complex real-world problems. Its potential to do so is significant and
warrants further academic investigation.

## References

  * [1] Vapnik, V. N., & Lerner, A. Y. (1963). Recognition of patterns with help of generalized portraits. Avtomat. i Telemekh, 24(6), 774-780.
  * [2] Vapnik, V., & Chervonenkis, A. Y. (1964). A class of algorithms for pattern recognition learning. Avtomat. i Telemekh, 25(6), 937-945.
  * [3] Boser, B. E., Guyon, I. M., & Vapnik, V. N. (1992, July). A training algorithm for optimal margin classifiers. In Proceedings of the fifth annual workshop on Computational learning theory (pp. 144-152).
  * [4] Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine learning, 20, 273-297.
  * [5] Rebentrost, P., Mohseni, M., & Lloyd, S. (2014). Quantum support vector machine for big data classification. Physical review letters, 113(13), 130503.
  * [6] Li, Z., Liu, X., Xu, N., & Du, J. (2015). Experimental realization of a quantum support vector machine. Physical review letters, 114(14), 140504.
  * [7] Havlicek, V., Corcoles, A. D., Temme, K., Harrow, A. W., Kandala, A., Chow, J. M., & Gambetta, J. M. (2019). Supervised learning with quantum-enhanced feature spaces. Nature, 567(7747), 209-212.
  * [8] Schuld, M., & Killoran, N. (2019). Quantum machine learning in feature hilbert spaces. Physical review letters, 122(4), 040504.
  * [9] Park, J. E., Quanz, B., Wood, S., Higgins, H., & Harishankar, R. (2020). Practical application improvement to Quantum SVM: theory to practice. arXiv preprint arXiv:2012.07725.
  * [10] Liu, Y., Arunachalam, S., & Temme, K. (2021). A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 17(9), 1013-1017.
  * [11] Schuld, M., Sweke, R., & Meyer, J. J. (2021). Effect of data encoding on the expressive power of variational quantum-machine-learning models. Physical Review A, 103(3), 032430.
  * [12] Schuld, M. (2021). Supervised quantum machine learning models are kernel methods. arXiv preprint arXiv:2101.11020.
  * [13] Zhang, R., Wang, J., Jiang, N., Li, H., & Wang, Z. (2022). Quantum support vector machine based on regularized Newton method. Neural Networks, 151, 376-384.
  * [14] Zhang, R., Wang, J., Jiang, N., & Wang, Z. (2023). Quantum support vector machine without iteration. Information Sciences.
  * [15] Bergholm, V., Izaac, J., Schuld, M., Gogolin, C., Ahmed, S., Ajith, V., … & Killoran, N. (2018). Pennylane: Automatic differentiation of hybrid quantum-classical computations. arXiv preprint arXiv:1811.04968.