Stirling Pairs of Permutations

Abstract

Stirling permutations are permutations $\pi$ of the multiset $\{1,1,2,2,\ldots ,n,n\}$ in which those integers between the two occurrences of an integer are greater than it. We identify a permutation $\pi$ of $\{1,1,2,2,\ldots ,n,n\}$ as a pair of permutations $(\pi _1,\pi _2)$ which we call a Stirling pair. We characterize Stirling pairs using the weak Bruhat order and the notion of a 312-avoiding permutation. We give two algorithms to determine if a pair of permutations is a Stirling pair.

1 Introduction

Let ${{\mathcal {S}}}_n$ denote the set of permutations of $\{1,2,\ldots ,n\}$, and let ${{\mathcal {T}}}_n$ denote the set of 2-permutations of$\{1,2,\ldots ,n\}$, that is, the set of permutations of the multiset $\{1,1,2,2,\ldots ,n,n\}$. A Stirling permutation of order n and length 2n is a 2-permutation in ${{\mathcal {T}}}_n$ such that the following Stirling property holds:

($*$) For each $k=1,2,\ldots ,n$, the integers between the two occurrences of k are greater than k.

In particular, in a Stirling permutation of order n, the two n’s must be adjacent. An example of a Stirling permutation of length 12 is

$$\begin{aligned} \pi =(1,2,2,4,5,6,6,5,4,3,3,1).\end{aligned}$$

(1)

The set of Stirling permutations in ${{\mathcal {T}}}_n$, that is, the set of Stirling permutations of ordernand length 2n, is denoted by ${{\mathcal {Q}}}_{n}$. Deleting the two n’s in a Stirling permutation of order n, we are left with a Stirling permutation of order $n-1$. Given a Stirling permutation of order $n-1$, there are $2n-1$ places to insert the n’s, and hence it follows by induction that the number of Stirling permutations of length 2n is $(2n-1)!!$ where double factorial$(2n-1)!!$ equals $(2n-1)(2n-3)(2n-5)\cdots 1$ [2]. The number of Stirling permutations of length 2 equals 1, the number of Stirling permutations of length 4 equals $3!!=3$, and the number of Stirling permutations of length 6 equals $5!!=5\cdot 3 \cdot 1=15$. Stirling permutations were introduced by Gessel and Stanley [4] in the context of Stirling polynomials. A number of recent papers [3, 5,6,7,8,9,10] have investigated enumerative and other properties of Stirling permutations.

Our purpose in this paper is to investigate Stirling permutations considered as a pair of permutations of $\{1,2,\ldots ,n\}$ and to discuss some of the consequences of this viewpoint. Each 2-permutation $\pi \in {{\mathcal {T}}}_n$ determines the unique pair of permutations $(\pi _1,\pi _2)$ of $\{1,2,\ldots ,n\}$ obtained, respectively, from the first, $\pi _1$, and second, $\pi _2$, occurrences (from left to right) of the integers $\{1,2,\ldots ,n\}$. We say that $\pi$induces$\pi _1$ and $\pi _2$, and we write $\pi \rightarrow (\pi _1,\pi _2)$. Thus we have a mapping

$$\begin{aligned} {{\mathcal {T}}}_n\rightarrow {{\mathcal {S}}}_n\times {{\mathcal {S}}}_n\end{aligned}$$

from the set of 2-permutations of $\{1,2,\ldots ,n\}$ to pairs of permutations of $\{1,2,\ldots ,n\}$. This mapping is surjective but not injective. For example, we have both

$$\begin{aligned} (1,1,2,2,3,3)\rightarrow ((1,2,3),(1,2,3))\quad \text{ and } \quad (1,2,3,1,2,3)\rightarrow ((1,2,3),(1,2,3)). \end{aligned}$$

If $\pi$ is a Stirling permutation of order n and $\pi \rightarrow (\pi _1,\pi _2)$, then we call $(\pi _1,\pi _2)$ a Stirling permutation pair of ordern corresponding to the Stirling permutation $\pi$. By restricting to ${{\mathcal {Q}}}_n$, we obtain a mapping

$$\begin{aligned} {{\mathcal {Q}}}_{n}\rightarrow {{\mathcal {S}}}_n\times {{\mathcal {S}}}_n.\end{aligned}$$

(2)

This mapping (2) is not surjective for $n\ge 3$. For instance, let $\pi _1=(1,2,3)$ and $\pi _2=(3,1,2)$ be permutations in ${{\mathcal {S}}}_n$. Since in a 2-permutation of order 3 with $\pi \rightarrow (\pi _1,\pi _2)$, 3 is repeated first followed by the repeat of 1, then that of 2. Thus the only permutation $\pi$ of $\{1,1,2,2,3,3\}$ such that $\pi \rightarrow (\pi _1,\pi _2)$ is (1, 2, 3, 3, 1, 2), and this is not a Stirling permutation since there is a 1 between the two 2’s.

We denote the set of Stirling permutation pairs of ordern by ${{\mathcal {S}}}_n^{\times 2}$ and we now write

$$\begin{aligned} \phi _n: {{\mathcal {Q}}}_n\rightarrow {{\mathcal {S}}}_n^{\times 2}\end{aligned}$$

(3)

to denote the surjective Stirling mapping$\phi _n$ from the set ${{\mathcal {Q}}}_n$ of Stirling permutations of order n to the set ${{\mathcal {S}}}_n^{\times 2}$ of Stirling permutation pairs of order n. Later we shall observe that $\phi _n$ is actually a bijection. From the example $\pi$ in (1) we get the Stirling permutation pair $(\pi _1,\pi _2)$ as follows:

$$\begin{aligned} \phi _6(\pi )=(\pi _1,\pi _2) \text{ where } \pi _1=(1,2,4,5,6,3)\quad \text{ and } \quad \pi _2=(2,6,5,4,3,1).\end{aligned}$$

(4)

By way of explanation, we note that e.g. the 4 in position 3 of $\pi _1$ implies that the first occurrence of 4 occurs after the first occurrences of 1 and 2 and before the first occurrences of 5, 6, and 3; the 5 in position 3 in $\pi _2$ implies that that the second occurrence of 5 occurs after the second occurrences of 2 and 6 and before the second occurrences of 4, 3, and 1.

Given any permutation $\pi _1=(i_1,i_2,\ldots ,i_n)$ of $\{1,2,\ldots ,n\}$, then $(\pi _1,\pi _1)$ is a Stirling permutation pair with corresponding Stirling permutation $(i_1,i_1,i_2,i_2,\ldots ,i_n,i_n)$. Thus every permutation of $\{1,2,\ldots ,n\}$ occurs as the first permutation of a Stirling permutation pair and, likewise, as the second permutation. The Stirling permutation $(1,1,2,2,\ldots ,n,n)$ is called the identity Stirling permutation of order n, and we have $\phi _n:(1,1,2,2,\ldots ,n,n)\rightarrow (\iota _n,\iota _n)$ where $\iota _n$ is the identity permutation$(1,2,\ldots ,n)$ of order n. For the Stirling permutation $(1,2,\ldots ,n,n,\ldots ,2,1)$ we have $\phi _n: (1,2,\ldots ,n,n,\ldots ,2,1)\rightarrow (\iota _n,\iota _n^*)$ where $\iota _n^*$ is the anti-identity permutation$(n,n-1,\ldots ,1)$.

A permutation pair $(\pi _1,\pi _2)$ of order n, obtained as the first and second occurrences of any 2-permutation $\pi \in {{\mathcal {T}}}_n$, determines an $n\times n$ (0, 1, 2)-matrix $E_{\pi }=E_{(\pi _1,\pi _2)}: = P_{\pi _1}+P_{\pi _2}$ where $P_{\pi _k}$ equals the $n\times n$ permutation matrix corresponding to the permutation $\pi _k$ ($k=1,2$). All row and column sums of $E_{\pi }$ equal 2. We call a (0, 1, 2)-matrix with all row and column sums equal to 2 a 2-permutation matrix, and we use Stirling permutation matrix if it arises in this way from a Stirling permutation.¹ Thus from example (4) we get the following Stirling permutation matrix $E_{\pi }$ without any 2’s:

$$\begin{aligned} \left[ \begin{array}{c|c|c|c|c|c} 1&{}&{}&{}&{}&{}\\ \hline &{}1&{}&{}&{}&{}\\ \hline &{}&{}&{}1&{}&{}\\ \hline &{}&{}&{}&{}1&{}\\ \hline &{}&{}&{}&{}&{}1\\ \hline &{}&{}1&{}&{}&{}\end{array}\right] + \left[ \begin{array}{c|c|c|c|c|c} &{}1&{}&{}&{}&{}\\ \hline &{}&{}&{}&{}&{}1\\ \hline &{}&{}&{}&{}1&{}\\ \hline &{}&{}&{}1&{}&{}\\ \hline &{}&{}1&{}&{}&{}\\ \hline 1&{}&{}&{}&{}&{}\end{array}\right] = \left[ \begin{array}{c|c|c|c|c|c} 1&{}1&{}&{}&{}&{}\\ \hline &{}1&{}&{}&{}&{}1\\ \hline &{}&{}&{}1&{}1&{}\\ \hline &{}&{}&{}1&{}1&{}\\ \hline &{}&{}1&{}&{}&{}1\\ \hline 1&{}&{}1&{}&{}&{}\end{array}\right] .\end{aligned}$$

(5)

Here and throughout, empty cells in a matrix are assumed to contain 0’s. For the identity Stirling permutation of order n we have $P_{\pi _1}=P_{\pi _2}=I_n$ and hence $E_{\pi }=2I_n$. The Stirling permutation matrix $E_{\pi }$ in (5) can also be written as a sum of two other permutation matrices, namely,

$$\begin{aligned}E_{\pi }=\left[ \begin{array}{c|c|c|c|c|c} 1&{}&{}&{}&{}&{}\\ \hline &{}1&{}&{}&{}&{}\\ \hline &{}&{}&{}&{}1&{}\\ \hline &{}&{}&{}1&{}&{}\\ \hline &{}&{}&{}&{}&{}1\\ \hline &{}&{}1&{}&{}&{}\end{array}\right] + \left[ \begin{array}{c|c|c|c|c|c} &{}1&{}&{}&{}&{}\\ \hline &{}&{}&{}&{}&{}1\\ \hline &{}&{}&{}1&{}&{}\\ \hline &{}&{}&{}&{}1&{}\\ \hline &{}&{}1&{}&{}&{}\\ \hline 1&{}&{}&{}&{}&{}\end{array}\right] \end{aligned}$$

corresponding to permutations $\pi _1'=(1,2,5,4,6,3)$ and $\pi _2'=(2,6,4,5,3,1)$ where, however, $(\pi _1',\pi _2')$ is not a Stirling permutation pair. The reason is that in a 2-permutation $\pi '$ such that $\phi _6: \pi '\rightarrow (\pi _1',\pi _2')$, 4 will occur between the two 5’s.

As we shall see later, given a Stirling permutation matrix $E_{\pi }$, there may be many ways to write E as a sum of permutation matrices but there is a unique Stirling pair $(\pi _1,\pi _2)$ so that $E_{\pi }=P_{\pi _1}+P_{\pi _2}$.

Before summarizing the contents of this paper we consider the following example.

Example 1.1

Consider the Stirling permutation $\pi =(1,2,2,4,5,6,6,5,4,3,3,1)$ of order 6 with corresponding Stirling permutation pair

$$\begin{aligned}\pi _1=(1,2,4,5,6,3)\quad \text{ and } \quad \pi _2=(2,6,5,4,3,1).\end{aligned}$$

The following four 2-permutations of $\{1,2,3,4,5,6\}$ have $\pi _1$ and $\pi _2$ as the permutations corresponding to the first and second occurrences of the integers 1, 2, 3, 4, 5, 6:

$$\begin{aligned}(1,2,2,4,5,6,6,5,4,3,3,1), (1,2,2,4,5,6,6,5,3,4,3,1),\end{aligned}$$

$$\begin{aligned}(1,2,2,4,5,6,6,3,5,4,3,1), (1,2,2,4,5,6,6,5,3,4,3,1).\end{aligned}$$

As is easily verified, only the first, namely the given $\pi$, is a Stirling permutation.$\square$

We now summarize the contents of this paper. In the next section we give some elementary properties of Stirling permutations and Stirling permutation pairs, and we give two algorithms for constructing a Stirling permutation from a Stirling permutation pair. We show, in particular, that the mapping $\phi _n: {{\mathcal {Q}}}_n\rightarrow {{\mathcal {S}}}_n^{\times 2}$ from Stirling permutations to Stirling permutation pairs in (3) is a bijection. As a consequence it follows that a Stirling permutation matrix can be uniquely decomposed into a sum of permutation matrices corresponding to a Stirling permutation pair. In Sect. 3 we review some elementary properties of permutations including the weak Bruhat order and discuss their connection to Stirling permutation pairs. In the final section we make some additional comments and discuss some questions currently being considered.

2 Stirling Permutation Pairs

To familiarize the reader with Stirling permutations and Stirling permutation pairs, in the next lemma we collect some elementary properties of Stirling permutations and Stirling permutation pairs.

We recall that a permutation $\sigma =(j_1,j_2,\ldots ,j_n)$ of $\{1,2,\ldots ,n\}$ is a 312-avoiding permutation² provided that there does not exist $1\le k<l<p\le n$ such that $j_k>j_l$, $j_k>j_p$ and $j_p>j_l$. It is known (see [2, pages 150–151]) that the number of 312-avoiding permutations of $\{1,2,\ldots ,n\}$ equals the nth Catalan number $C_n=\frac{1}{n+1} {{2n}\atopwithdelims ()n}$. As a permutation matrix, a 312-avoiding permutation is one that does not have any $3\times 3$ submatrix equal to

$$\begin{aligned}\left[ \begin{array}{ccc} 0&{}0&{}1\\ 1&{}0&{}0\\ 0&{}1&{}0\end{array}\right] .\end{aligned}$$

Lemma 2.1

Let n be a positive integer, and let $\pi$ be a Stirling permutation of order n with corresponding Stirling permutation pair $\pi _1=(i_1,i_2,\ldots ,i_n)$ and $\pi _2=(j_1,j_2,\ldots ,j_n)$. Then the following properties hold:

• (a) For any $1\le q<p\le n$, the subsequence of $\pi$ determined by p and q is not equal to any of

  $$\begin{aligned}p,q,p,q;\quad p,q,q,p; \quad q,p,q,p\end{aligned}$$

  and so equals one of

  $$\begin{aligned}p,p,q,q;\quad q,q,p,p; \quad q,p,p,q.\end{aligned}$$

• (b) Let $\pi _1=(1,2,\ldots ,n)$. Then $\pi _2$ is a 312-avoiding permutation.

• (c) Let $\pi _1=(1,2,\ldots ,n)$ and suppose that $\pi _2$ begins with n. Then $\pi _2=(n,n-1,\ldots ,1)$.

• (d) Let $i_k=n$ and $j_l=n$. Then $k\ge l$ and $\{j_1,j_2,\ldots ,j_l\}\subseteq \{i_1,i_2,\ldots ,i_k\}$. More generally, let $i_k=p$ and $j_l=p$. If p immediately follows p in $\pi$, then $\{j_1,j_2,\ldots ,j_l\}\subseteq \{i_1,i_2,\ldots ,i_p\}$.

• (e) For any sequence $\sigma$ let ${\mathop {\sigma }\limits ^{\leftarrow }}$ be the sequence obtained by reversing the order of the terms of $\sigma$. Let $\pi$ be a Stirling permutation of order n with corresponding Stirling pair $(\pi _1,\pi _2)$.Then ${\mathop {\sigma }\limits ^{\leftarrow }}$ is a Stirling permutation with corresponding Stirling pair $({\mathop {\pi _2}\limits ^{\leftarrow }},{\mathop {\pi _1}\limits ^{\leftarrow }})$.

• (f) If $\pi _1=(n,n-1,\ldots ,2,1)$ and $(\pi _1,\pi _2)$ is a Stirling pair, then $\pi _2=\pi _1$.

• (g) If $\pi _2=(1,2,\ldots ,n)$ and $(\pi _1,\pi _2)$ is a Stirling pair, then $\pi _1=\pi _2$.

Proof

The simple proofs of the individual assertions are below.

• (a) This is an immediate consequence of the Stirling property.

• (b) Consider $1\le k<l<t\le n$. If $j_k>j_t>j_l$ then, since $\pi _1=(1,2,\ldots ,n)$, $\pi _1=(\ldots ,j_l,\ldots ,j_t,\ldots ,j_k,\ldots )$. Since $\pi _2=(j_1,j_2,\ldots ,j_n)$, then in $\pi$, $j_k$ is repeated before $j_l$ and $j_l$ is repeated before $j_t$. Thus

  $$\begin{aligned}\pi =(\ldots ,j_l,\ldots ,j_t,\ldots ,j_k,\ldots , j_k,\ldots , j_l,\ldots , j_t,\ldots ).\end{aligned}$$

  Since $j_l<j_t$, we contradict that $\pi$ is a Stirling permutation.

• (c) We have $\pi =(1,2,\ldots ,n,j_1=n,j_2,\ldots ,j_n)$. If $\pi _2$ were not in decreasing order, then we contradict the definition of a Stirling permutation.

• (d) Since $i_k=n=j_l$, n is the lth integer repeated in $\pi$ and must immediately follow the n in $\pi _1$. The integers $j_1,j_2,\ldots ,j_{l-1}$ are repeated before n is and so $\{j_1,j_2,\ldots ,j_{l-1}\}\subseteq \{i_1,i_2,\ldots ,i_{k-1}\}$ and hence $k\ge l$. The second assertion is the obvious generalization with n replaced with an arbitrary $p\in \{1,2,\ldots ,n\}$.

• (e) This follows in a straightforward way from the definitions.

• (f) Suppose to the contrary that $\pi _2=(\ldots ,a,\ldots ,b,\ldots )$ where $a<b$. Then in a Stirling permutation $\pi$ with Stirling pair $(\pi _1,\pi _2)$, a is repeated before b is repeated. Then $\pi =(\ldots ,b,\ldots ,a,\ldots ,a,\ldots ,b,\ldots )$, a contradiction since $a<b$.

• (g) Suppose to the contrary that $\pi _1=(\ldots ,a,\ldots ,b,\ldots )$ where $a>b$. Since $\pi _2=(1,2,\ldots ,n)$, in a Stirling permutation $\pi$ with Stirling pair $(\pi _1,\pi _2)$, b is repeated before a is repeated. Then $\pi =(\ldots ,a,\ldots ,b,\ldots ,b,\ldots ,a,\ldots )$, a contradiction since $b<a$.

$\square$

Before giving two algorithms to construct a Stirling permutation given a Stirling permutation pair $(\pi _1,\pi _2)$, we prove the following somewhat more substantial property of Stirling permutation pairs.

Lemma 2.2

Let $\pi _1=(i_1,i_2,\ldots ,i_n)$ and $\pi _2=(j_1,j_2,\ldots ,j_n)$ be a Stirling pair of permutations of $\{1,2,\ldots ,n\}$ with a corresponding Stirling permutation $\pi$. Let $i_1=p$ and let k be such that $j_k=p$. Then

• (a) $\{i_2,\ldots ,i_k\}=\{j_1,\ldots ,j_{k-1}\}$ and thus $\{i_{k+1},\ldots ,i_n\}=\{j_{k+1},\ldots ,j_n\}$;

• (b) $\pi =(i_1=p,a_1,a_2,\ldots ,a_{2(k-1)},j_k=p,b_1,b_2,\ldots ,b_{2(n-k)})$ where, $(a_1,a_2,\ldots ,a_{2(k-1)})$ is a 2-permutation of $\{i_2,\ldots ,i_k\}$ and $(b_1,b_2,\ldots ,b_{2(n-k)})$ is a 2-permutation of $\{i_{k+1},\ldots ,i_n\}$, both with the Stirling property.

• (c) $\{1,2,\ldots ,p-1\}\subseteq \{i_{k+1},i_{k+2},\ldots ,i_n\}\cap \{j_{k+1},j_{k+2},\ldots ,j_n\}$.

Proof

Since $\pi$ is a Stirling permutation, $j_1,j_2,\ldots ,j_{k-1}$ must all be repeated in $\pi$ before $j_k$ is repeated. Thus between the two p’s in $\pi$, each of $j_1,\ldots ,j_{k-1}$ appears twice. Suppose that in $\pi$ there is a q occuring between the two p’s where $q\not \in \{j_1,j_2,\ldots ,j_{k-1}\}$. Thus q is repeated in $\pi$ after $j_k$ is repeated. Then in $\pi$ we have the subsequence $i_1=p,i_r=q,j_k=p,j_s=q$ for some r and s with $1<r<k$ and $k<s\le n$. If $p<q$, then q, p, q contradicts that $\pi$ is a Stirling permutation while if $p>q$, then p, q, p contradicts that $\pi$ is a Stirling permutation. Thus (a) holds. Since $\pi$ is a Stirling permutation, the 2-permutation $(a_1,a_2,\ldots ,a_{2(k-1)})$ (regarded as a 2-permutation of $\{1,2,\ldots ,k-1\}$), and the 2-permutation $(b_1,b_2,\ldots ,b_{2(n-k)})$ (regarded as a 2-permutation of $\{1,2,\ldots ,n-k-1\}$), satisfy the Stirling property and thus are Stirling permutations of $\{1,2,\ldots ,k-1\}$ and $\{1,2,\ldots ,n-k\}$, respectively. Assertion (c) follows from (a) and (b). $\square$

Lemma 2.2 inductively gives the following corollary.

Corollary 2.3

Let $(\pi _1,\pi _2)$ be a Stirling pair of permutations. Then there is a unique corresponding Stirling permutation; equivalently, the mapping (3) given by $\phi _n: {{\mathcal {Q}}}_n\rightarrow {{\mathcal {S}}}_n^{\times 2}$ is a bijection.

Lemma 2.2 is the basis for an algorithm for construction of a Stirling permutation from a Stirling permutation pair.

Algorithm (I) for Construction of a Stirling permutation with $\pi _1=(i_1,i_2,\ldots ,i_n)$ and $\pi _2=(j_1,j_2,\ldots ,j_n)$

• (i) Begin with $\pi _1$.

• (ii) Let $i_1=p$ and let k be such that $j_k=p$. Put a $j_k=p$ immediately after $i_k$ in $\pi _1$.

• (iii) Repeat recursively with $\pi _1' =(i_2,\ldots ,i_k)$ and with $\pi _2'=(j_1,j_2,\ldots ,j_{k-1})$ (regarded as permutations of $\{1,2,\ldots ,k-1\}$) and then recursively with $\pi _1''=(i_{k+1},\ldots ,i_n)$ and $\pi _2''=(j_{k+1},\ldots ,j_n)$ (regarded as permutations of $\{k+1,k+2,\ldots ,n\}$).

• (iv) Output the resulting $\pi$.

Theorem 2.4

Let $\pi _1=(i_1,i_2,\ldots ,i_n)$ and $\pi _2=(j_1,j_2,\ldots ,j_n)$ be a Stirling permutation pair. Then Algorithm (I) produces the unique Stirling permutation with Stirling permutation pair $(\pi _1,\pi _2)$.

Proof

Let $\pi$ be a Stirling permutation with Stirling pair $(\pi _1,\pi _2)$. By Lemma 2.2, $j_k$ immediately follows $i_k$ in $\pi$. Moreover, it follows from this lemma, that applying the algorithm recursively to the pairs $(\pi _1',\pi _2')$ and $(\pi _1'',\pi _2'')$ results in the unique Stirling permutation corresponding to $(\pi _1,\pi _2)$. $\square$

We now give a second algorithm to construct a Stirling permutation of order n from a Stirling permutation pair $(\pi _1,\pi _2)$. Both algorithms (I) and (II) show that a Stirling permutation pair is determined by a unique Stirling permutation.

Algorithm (II) for Construction of a Stirling permutation with $\pi _1=(i_1,i_2,\ldots ,i_n)$ and $\pi _2=(j_1,j_2,\ldots ,j_n)$.

• (i) Set $\tau _0$ equal to $\pi _1$.

• (ii) For $k=1,2,\ldots ,n$, let $\tau _k$ be obtained from $\tau _{k-1}$ by inserting a second $j_k$ into $\tau _{k-1}$ immediately following $j_k$ in $\tau _{k-1}$ and the second occurrence of $j_{k-1}$ in $\tau _{k-1}$ whichever comes later.

• (iii) Output the permutation $\tau _n$ of $\{1,1,2,2,\ldots ,n,n\}$.

Theorem 2.5

Let $\pi _1=(i_1,i_2,\ldots ,i_n)$, and let $\pi _1=(j_1,j_2,\ldots ,j_n)$ be a Stirling permutation pair with corresponding Stirling permutation $\pi$. Then Algorithm (II) produces the unique Stirling permutation with Stirling permutation pair $(\pi _1,\pi _2)$.

Proof

It follows from the algorithm that the second occurrences of the integers $1,2,\ldots ,n$ do occur in the required order $j_1,j_2,\ldots ,j_n$. The algorithm clearly produces a 2-permutation of $\{1,2,\ldots ,n\}$. We claim that $\tau _n$ is the Stirling permutation $\pi$ whose corresponding Stirling permutation pair is $(\pi _1,\pi _2)$. We show by induction on k that $\tau _k$ satisfies the Stirling property, that is, all integers between the two $j_k$’s in $\tau _k$ are greater than $j_k$, and hence that $\tau _n=\pi$.

First assume that $k=1$ and $j_1=p$. If there exists in $\pi$ an integer q with q between the two occurrences of p then, since q is repeated in $\pi$ after p and $\pi$ contains as a subsequence p, q, p, q violating the Stirling property. Thus in $\pi$, the two p’s are consecutive and this agrees with $\tau _1$.

We now proceed by induction and assume that $k>1$. If $j_k$ is placed in $\tau _{k}$ immediately following the $j_k$ in $\tau _{k-1}$, then $\tau _k$ satisfies the Stirling property since $\tau _{k-1}$ does. Assume that in $\pi$ the second $j_{k-1}$ follows the first $j_k$ in $\tau _{k-1}$ and that there exists an $i_q$ between the second $j_{k-1}$ and the second $j_k$. Then $i_q$ is repeated after the second $j_k$ and hence $\pi$ contains the subsequence $j_k,i_q,j_k,i_q$ contradicting again the Stirling property. Thus in this case, $j_k$ is repeated immediately following the second $j_{k-1}$ in $\pi$. Thus $\tau _k$ satisfies the Stirling property. Hence by induction $\tau _n=\pi$. $\square$

We now give two examples of these algorithms with $n=7$ one of which uses the the identity permutation as $\pi _1$.

Example 2.6

Let $\pi _1=(1,2,3,4,5,6,7)$ and $\pi _2=(4,3,2,1,6,7,5)$, a 312-avoiding permutation. Applying Algorithms (I) and (II) we get:

$$\begin{aligned}\begin{array}{l||l} \quad \text{ Algorithm } \text{(I) }\quad &{}\quad \text{ Algorithm } \text{(II) }\quad \\ \hline \hline 1234567&{}1234567\\ 12341567&{} 12344567\\ 123421567&{} 123443567\\ 1234321567&{} 1234432567\\ 12344321567&{} 12344321567\\ 123443215667&{}123443215667\\ 1234432156677&{} 1234432156677\\ 12344321566775&{}12344321566775\\ \end{array}.\end{aligned}$$

Now let $\pi _1=(3,4,6,5,7,1,2)$ and $\pi _2=(6,4,3,7,5,2,1)$. Applying Algorithms (I) and (II) we get:

$$\begin{aligned}\begin{array}{l||l} \quad \text{ Algorithm } \text{(I) }\quad &{}\quad \text{ Algorithm } \text{(II) }\quad \\ \hline \hline 3465712&{} 3465712\\ 34635712&{}34665712\\ 346435712&{}346645712 \\ 3466435712&{}3466435712\\ 34664357512&{}34664357712\\ 346643577512&{}346643577512\\ 3466435775122&{}3466435775122\\ 34664357751221&{}34664357751221\\ \end{array}. \end{aligned}$$

$\square$

Given a permutation $\pi _1$ of $\{1,2,\ldots ,n\}$, we define its Stirling right-multiplicity$|\pi _1|_r$ to be the number of permutations $\pi _2$ of $\{1,2,\ldots ,n\}$ such that $(\pi _1,\pi _2)$ is a Stirling permutation pair. We have $|\pi _1|_r\ge 1$ since $(\pi _1,\pi _1)$ is always a Stirling permutation pair. Let

$$\begin{aligned} M_r=\max \{|\pi _1|_r: \pi _1 \text{ a } \text{ permutation } \text{ of } \{1,2,\ldots ,n\}\},\end{aligned}$$

the maximum Stirling right-multiplicity of a permutation in ${{\mathcal {S}}}_n$. Similarly, we define the Stirling left-multiplicity of a permutation $\pi _2$ of $\{1,2,\ldots ,n\}$ to be the number $|\pi _2|_l$ of permutations $\pi _1$ of $\{1,2,\ldots ,n\}$ such that $(\pi _1,\pi _2)$ is a Stirling permutation pair. In investigating these numbers it follows from (e) of Lemma 2.1 that it is enough to consider Stirling right-multiplicities since $|\pi _2|_l= |{\mathop {\pi _1}\limits ^{\leftarrow }}|_r$. We begin with the following lemma concerning the minimum Stirling right multiplicity.

Lemma 2.7

Let $\pi _1=(i_1,i_2,\ldots ,i_n)$ be a permutation of $\{1,2,\ldots ,n\}$. Then $|\pi _1|_r\ge 1$ with equality if and only if $\pi _1$ is the anti-identity permutation $\iota _n^*=(n,n-1,\ldots ,1)$.

Proof

As already remarked, $(\pi _1,\pi _1)$ is always a Stirling permutation pair so that we have $|\pi _1|_r\ge 1$. Now assume that $\pi _1=(n,n-1,\ldots ,1)$ and let $\pi _2$ be a permutation such that $(\pi _1,\pi _2)$ is a Stirling permutation pair with corresponding Stirling permutation $\pi$. Since n always immediately follows n in a Stirling permutation of order n, $\pi _2$ must begin with n and $\pi =(n,n,\ldots )$. It now follows by induction that $\pi _2=(n,n-1,\ldots ,1)$ and $\pi =(n,n,n-1,n-1,\ldots ,1,1)$. Thus $|\pi _1|_r=1$.

Now let $\pi _1=(i_1,i_2,\ldots ,i_n)\ne (n,n-1,\ldots ,1)$. Then there exists a k such that $i_k<i_{k+1}$. With $\pi _2=(i_1,i_2,\ldots ,i_{k-1}, i_{k+1},i_{k},i_{k+2},\ldots ,i_n)$, we have $\pi _2\ne \pi _1$ where $(i_1,i_1,\ldots ,i_{k-1},i_{k-1},i_k,i_{k+1},i_{k+1},i_k, i_{k+2},i_{k+2}, \ldots ,i_n,i_n)$ is a Stirling permutation with corresponding Stirling permutation pair $(\pi _1,\pi _2)$. Hence $|\pi _1|_r\ge 2$. $\square$

Example 2.8

The 15 Stirling permutations $\pi$ of order 3 along with their corresponding Stirling permutation pairs $(\pi _1,\pi _2)$ are given in Table 1.

Table 1 Stirling permutations of order 3

Note that each pair $(\pi _1,\pi _2)$ in the Table 1 corresponds to exactly one Stirling permutation as verified by Corollary 2.3. Note also that for $\pi _1=(1,2,3)$ we are missing only $\pi _2=(3,1,2)$; for $\pi _2=(3,2,1)$ we are missing only (2, 1, 3). The numbers $|\pi _1|_r$’s and the numbers $|\pi _2|_l$’s are given in the Table 2.

Table 2 Left- and right-multiplicities

There are twenty-one $3\times 3$ 2-permutation matrices. The fifteen $3\times 3$ Stirling permutation matrices corresponding to each of the Stirling permutation pairs $(\pi _1,\pi _2)$ in Table 1 are given in Table 3.

Table 3 $3\times 3$ Stirling permutation matrices

The six $3\times 3$ 2-permutation matrices that are not Stirling permutation matrices are given in Table 4.

Table 4 $3\times 3$ Non-Stirling permutation matrices

$\square$

3 Stirling Permutation Pairs and the Weak Bruhat Order

We begin this section with an exposition of some fairly standard facts concerning permutations in order to make it easier for the reader to understand their implications for Stirling permutation pairs.

Let $\sigma =(k_1,k_2,\ldots ,k_n)$ be a permutation of $\{1,2,\ldots ,n\}$. Recall that an inversion of $\sigma$ is a pair $(k_p,k_q)$ such that $p<q$ but $k_p>k_q$. Note that an inversion is defined to be the ordered pair $(k_p,k_q)$, not the ordered pair (p, q) of positions; if $(k_p,k_q)$ is an inversion of $\pi$, then (p, q) is an inversion of its inverse $\pi ^{-1}$. Thus an inversion of $\sigma$ is a pair of integers in $\sigma$ that are out of their natural order. The set of inversions of the permutation $\sigma$ is denoted by ${{\mathcal {I}}}(\sigma )$. For the identity permutation $\iota _n$ we have ${{\mathcal {I}}}(\iota _n)=\emptyset$. The anti-identity permutation $\iota _n^*$ has the largest number of inversions, indeed has all possible inversions: ${{\mathcal {I}}}(\iota _n^*)=\{(a,b):n\ge a>b \ge 1\}$. The permutation $\sigma$ can be brought to the identity $\iota _n$ by a sequence of transpositions$(k_p,k_q)\rightarrow (k_q,k_p)$, each chosen in such a way as to reduce the number of inversions (not necessarily the set of inversions in general) by exactly 1. For example, we have $({{\mathbf {3}}},4,1,{{\mathbf {2}}})\rightarrow ({{\mathbf {2}}},4,1,{{\mathbf {3}}})$ reduces the number of inversions from 4 to 3, with the set of inversions changing from $\{(3,1), (3,2),(4,1),(4,2)\}$ to $\{(2,1), (4,1),(4,3)\}$.

An inversion of $\sigma =(k_1,k_2,\ldots ,k_n)$ of the form $(k_p,k_{p+1})$ is called an adjacent inversion. If $(k_p,k_{p+1})$ is an adjacent inversion of the permutation $\sigma$, then the transposition $(k_p,k_{p+1})\rightarrow (k_{p+1},k_p)$ is called an adjacent transposition. An adjacent transposition applied to a permutation $\sigma$ has the sole effect of removing exactly one inversion (an adjacent inversion) from ${{\mathcal {I}}}(\pi )$ and thus, in particular, reduces the number of inversions by exactly one.

For completeness, we note the following basic property of permutations.

Lemma 3.1

A permutation of $\{1,2,\ldots ,n\}$ is uniquely determined by its set of inversions. A permutation is not, in general, uniquely determined by its set of adjacent inversions.

Proof

Briefly, let $\pi =(i_1,i_2,\ldots ,i_n)$ be a permutation of $\{1,2\ldots ,n\}$ with inversion set ${{\mathcal {I}}}(\pi )$. If $i_1=1$, then 1 does not contribute to any inversions of $\pi$ and the first assertion follows by induction. Let $i_p=1$ for some $p>1$, and let $X_1=\{i_j:1\le j<p\}$ and $X_2=\{i_j:p<j\le n\}$. If $a\in X_1$ and $b\in X_2$ satisfy $a>b$, then $(a,b)\in {{\mathcal {I}}}(\pi )$. The first assertion now follows by applying induction to $(i_1,\ldots ,i_{p-1})$ and $(i_{p+1},\ldots ,i_n)$.

For the second assertion, the permutations (4, 1, 2, 3) and (2, 4, 1, 3) of $\{1,2,3,4\}$ have exactly one adjacent inversion, namely (4, 1) in both instances, and their sets of inversions are $\{(4,1),(4,2),(4,3)\}$ and $\{(2,1),(4,1),(4,3)\}$, respectively. $\square$

Inversions play a role in Stirling permutations.

Lemma 3.2

Let $\pi _1$ and $\pi _2$ be permutations of $\{1,2,\ldots ,n\}$ such that $(\pi _1,\pi _2)$ is a Stirling permutation pair. Then ${{\mathcal {I}}}(\pi _1)\subseteq {{\mathcal {I}}}(\pi _2)$.

Proof

Suppose $(a,b)=(i_p,i_q)\in {{\mathcal {I}}}(\pi _1)$. Thus a precedes b in $\pi _1$ and $a>b$. Suppose that b precedes a in $\pi _2$. Then in the Stirling permutation corresponding to $(\pi _1,\pi _2)$, b is repeated before a is repeated. Thus the relative positions of a and b in $\pi$ are a, b, b, a, a contradiction since $b<a$. Hence (a, b) is also an inversion in $\pi _2$. $\square$

Note that since ${{\mathcal {I}}}(\iota _n)=\emptyset$, Lemma 3.2 holds vacuously if $\pi _1=\iota _n$.

Corollary 3.3

Let $\pi _1$ and $\pi _2$ be permutations of $\{1,2,\ldots ,n\}$ such that both $(\pi _1,\pi _2)$ and $(\pi _2,\pi _1)$ are Stirling permutation pairs. Then $\pi _1=\pi _2$.

Proof

Lemma 3.2 implies that $\pi _1$ and $\pi _2$ have the same set of inversions, and hence by Lemma 3.1, $\pi _1=\pi _2$. $\square$

If $\pi _1$ and $\pi _2$ are permutations of $\{1,2,\ldots ,n\}$, then $\pi _2$ as a permutation relative to $\pi _1$ is the permutation $\pi _2\pi _1^{-1}$ ($\pi _1^{-1}$ followed by $\pi _2$). The cycles $\gamma$ of this permutation are the cycles of$\pi _2$relative to$\pi _1$. For example, let $n=8$ and let

$$\begin{aligned}\pi _1=(3,5,1,7,2,8,4,6) \text{ and } \pi _2=(6,8,5,3,1,2,4,7).\end{aligned}$$

Then

$$\begin{aligned}5 {\mathop {\rightarrow }\limits ^{\pi _1^{-1}}} 2{\mathop {\rightarrow }\limits ^{\pi _2}} 8 {\mathop {\rightarrow }\limits ^{\pi _1^{-1}}} 6{\mathop {\rightarrow }\limits ^{\pi _2}} 2 {\mathop {\rightarrow }\limits ^{\pi _1^{-1}}} 5 {\mathop {\rightarrow }\limits ^{\pi _2}} 1{\mathop {\rightarrow }\limits ^{\pi _1^{-1}}}3 {\mathop {\rightarrow }\limits ^{\pi _2}} 5.\end{aligned}$$

determines the 4-cycle

$$\begin{aligned}5\rightarrow 8\rightarrow 2\rightarrow 1\rightarrow 5.\end{aligned}$$

of $\pi _2$ relative to $\pi _1$. Replacing in $\pi _2$ this cycle with its reverse cycle

$$\begin{aligned}5\rightarrow 1\rightarrow 2\rightarrow 8\rightarrow 5\end{aligned}$$

gives a new permutation $\pi _2'=(6,5,1,3,2,8,4,7)$. This operation is called cycle-substitution. In a similar way we obtain a new permutation $\pi _1'$ and we refer to a symmetric cycle-substitution of $\pi _1$ and $\pi _2$. In terms of the corresponding permutation matrices we have the following:

gives

If $\pi _2$ has several cycles relative to $\pi _1$, then one may simultaneously do more than one cycle substitution. Of course if one substitutes all of these cycles, then $\pi _2$ becomes $\pi _1$. Otherwise, we refer to a partial cycle substitution.

Lemma 3.4

Let $\pi _1=(i_1,i_2,\ldots ,i_n)$ and $\pi _2=(j_1,j_2,\ldots ,j_n)$ be two permutations of $\{1,2,\ldots ,n\}$ with $i_k\ne j_k$ for $k=1,2,\ldots ,n$ such that ${{\mathcal {I}}}(\pi _1)\subset {{\mathcal {I}}}(\pi _2)$. Let $\pi _1'$ and $\pi _2'$ be obtained from $\pi _1$ and $\pi _2$ by one or more, but not all, symmetric partial cycle substitutions. Then ${{\mathcal {I}}}(\pi _1')$ and ${{\mathcal {I}}}(\pi _2')$ are unrelated, that is, ${{\mathcal {I}}}(\pi _1')\not \subseteq {{\mathcal {I}}}(\pi _2')$ and ${{\mathcal {I}}}(\pi _2')\not \subseteq {{\mathcal {I}}}(\pi _1')$.

Proof

For ease of language we argue under the assumption of one symmetric cycle substitution $\gamma$. The assumptions imply that $\pi _2$ contains an inversion which is not an inversion of $\pi _1$ involving indices not belonging to the cycle $\gamma$. The cycle substitution interchanges certain, but not all, of the inversions of $\pi _1$ and $\pi _2$. It thus follows that ${{\mathcal {I}}}(\pi _2')\not \subseteq {{\mathcal {I}}}(\pi _1')$ and ${{\mathcal {I}}}(\pi _1')\not \subseteq {{\mathcal {I}}}(\pi _2')$. $\square$

Corollary 3.5

Let Q be an $n\times n$ Stirling permutation matrix. Then there is a unique Stirling permutation pair $(\pi _1,\pi _2)$ such that $Q=P_{\pi _1}+P_{\pi _2}$.

Proof

Since Q is a Stirling permutation, there is a Stirling permutation pair $(\pi _1,\pi _2)$ such that $Q=P_{\pi _1}+P_{\pi _2}$. Since any permutation matrix R such that $R\le Q$ (entrywise) is obtained by a cycle substitution involving $P_{\pi _1}$ and $P_{\pi _2}$, the corollary is a direct consequence of Lemmas 3.2 and  3.4. $\square$

Let $\pi _1$ and $\pi _2$ be two permutations of $\{1,2,\ldots ,n\}$. The weak Bruhat order (see e.g [1]) is a lattice order $\preceq _{\mathrm{b}}$ on the set ${{\mathcal {S}}}_n$ of permutations of $\{1,2,\ldots ,n\}$ defined by:

$$\begin{aligned}\pi _1\preceq _{\mathrm{b}} \pi _2 \text{ provided } \text{ that } {{\mathcal {I}}}(\pi _1)\subseteq {{\mathcal {I}}}(\pi _2).\end{aligned}$$

It is known [1, 11] that this is equivalent to: $\pi _1$ can be obtained from $\pi _2$ by a sequence of adjacent transpositions.³ If $\pi _1$ can be obtained from $\pi _2$ by a sequence of adjacent transpositions, then clearly ${{\mathcal {I}}}(\pi _1)\subseteq {{\mathcal {I}}}(\pi _2)$. For completeness we briefly verify the converse [11].

Lemma 3.6

Let $\pi _1$ and $\pi _2$ be two permutation of $\{1,2,\ldots ,n\}$ such that ${{\mathcal {I}}}(\pi _1)\subseteq {{\mathcal {I}}}(\pi _2)$. Then by a sequence of adjacent transpositions we may reduce $\pi _2$ to $\pi _1$.

Proof

Let $\pi _1=(r_1,r_2,\ldots ,r_n)$ and $\pi _2=(s_1,s_2,\ldots ,s_n)$. Let j be the minimum value of i such that $s_j\ne r_j$. Thus $r_1=s_1,\ldots ,r_{j-1}=s_{j-1}, r_j\ne s_j$. Define an integer $k>j$ by $r_j=s_k$. Thus

$$\begin{aligned}&\displaystyle \pi _1=(r_1=s_1,\ldots ,r_{j-1}=s_{j-1}, r_j=s_k,\ldots ,r_l=s_j,\ldots ) \text{(for } \text{ some } l) \text{ and } \\&\displaystyle \pi _2=(s_1=r_1,\ldots ,s_{j-1}=r_{j-1}, s_j\ne r_j,\ldots ,s_{k-1},s_k=r_j,\ldots ). \end{aligned}$$

Since ${{\mathcal {I}}}(\pi _1)\subseteq {{\mathcal {I}}}(\pi _2)$, we have that $s_j<r_j$; otherwise, $r_j>s_j$ and $(r_j,s_j)\in {{\mathcal {I}}}(\pi _2)$ but $(r_j,s_j)\not \in {{\mathcal {I}}}(\pi _2)$, a contradiction. We also have $s_{k-1}>s_k$; otherwise, $s_{k}>s_{k-1}$ and $(s_{k},s_{k-1})\in {{\mathcal {I}}}(\pi _1)$, but $(s_{k-1},s_k)\not \in {{\mathcal {I}}}(\pi _1)$. Applying the adjacent interchange $(s_{k-1},s_k)$ to $\pi _2$ gives a permutation $\pi _2'$ such that ${{\mathcal {I}}}(\pi _1)\subseteq {{\mathcal {I}}}(\pi _2')$ and ${{\mathcal {I}}}(\pi _2'){\setminus } {{\mathcal {I}}}(\pi _1)$ has one fewer adjacent inversion than ${{\mathcal {I}}}(\pi _2){\setminus } {{\mathcal {I}}}(\pi _1)$. The lemma now follows by induction.    $\square$

We now extend the definition of a 312-avoiding permutation. Being a 312-avoiding permutation places restrictions on the inversions of the permutation. In fact, the permutation $\sigma =(j_1,j_2,\ldots ,j_n)$ is 312-avoiding is equivalent to:

(312)  If $1\le k<l<p\le n$ and $(j_k,j_l)$ and $(j_k,j_p)$ are inversions, then $(j_l,j_p)$ is also an inversion, that is, $j_k,j_l,j_p$ is a decreasing subsequence of $\sigma$.

Now let $\pi _1=(i_1,i_2,\ldots ,i_n)$ and $\pi _2=(j_1,j_2,\ldots ,j_n)$ be two permutations of $\{1,2,\ldots ,n\}$. Then we define $\pi _2$ to be a 312-avoiding permutation relative to$\pi _1$ (or, $(\pi _1,\pi _2)$ is a 312-avoiding permutation pair) provided the following hold:

• (312-i) ${{\mathcal {I}}}(\pi _1)\subseteq {{\mathcal {I}}}(\pi _2)$, and

• (312-ii) If $1\le k<l<p\le n$ and $(j_k,j_l)$ and $(j_k,j_p)$ are inversions in ${{\mathcal {I}}}(\pi _2){\setminus } {{\mathcal {I}}}(\pi _1)$, then $(j_l,j_p)$ is also an inversion in ${{\mathcal {I}}}(\pi _2){\setminus } {{\mathcal {I}}}(\pi _1)$.

If (312-i) and (312-ii) hold, then

• (312-iii) $j_k,j_l,j_p$ is a decreasing subsequence of $\pi _2$ and $j_p,j_l,j_k$ is an increasing subsequence of $\pi _1$.

Lemma 3.7

Let $\pi _1$ and $\pi _2$ be two permutations of $\{1,2,\ldots ,n\}$ such that $(\pi _1,\pi _2)$ is a Stirling pair of permutations. Then $\pi _2$ is 312-avoiding permutation relative to $\pi _1$.

Proof

Let $\pi _1=(i_1,i_2,\ldots ,i_n)$ and $\pi _2=(j_1,j_2,\ldots ,j_n)$ with corresponding Stirling permutation $\pi$. First suppose (312-i) does not hold. Then there exists $k<l$ such that $i_k>i_l$ but $i_l$ comes before $i_k$ in $\pi _2$. Thus $i_l$ is repeated before $i_k$ in $\pi$, and hence $\pi$ contains $i_k,i_l,i_l,i_k$ as a subsequence. Since $i_l<i_k$, this contradicts that $\pi$ is a Stirling permutation. Hence (312-i) holds.

Now suppose that (312-ii) does not hold. Then there exists $1\le k<l<p\le n$ and inversions $(j_k,j_l)$ and $(j_k,j_p)$ in ${{\mathcal {I}}}(\pi _2){\setminus } {{\mathcal {I}}}(\pi _1)$ such that either

• (a) $(j_l,j_p)$ is not an inversion in ${{\mathcal {I}}}(\pi _2)$, or

• (b) $(j_l,j_p)$ is an inversion in both ${{\mathcal {I}}}(\pi _2)$ and ${{\mathcal {I}}}(\pi _1)$.

First suppose that (a) holds. Then $j_k,j_l,j_p$ is a subsequence of $\pi _2$ with $j_l<j_p$, and either $j_p,j_l,j_k$ or $j_l,j_k,j_p$ is a subsequence of $\pi _1$. Hence $j_p,j_l,j_k,j_k,j_l,j_p$ or $j_l,j_p,j_k,j_k,j_l,j_p$ is a subsequence of $\pi$ which, because $j_l<j_p$, contradicts that $\pi$ is a Stirling permutation.

Now suppose that (b) holds. Since $(j_l,j_p)$ is an inversion in $\pi _2$, $j_l>j_p$. Since $(j_l,j_p)$ is also an inversion in $\pi _1$, $j_l$ comes before $j_p$ in $\pi _1$. Since $(j_k,j_l)$ and $(j_k,j_p)$ are not inversions in $\pi _1$, $j_l$ precedes $j_k$ in $\pi _1$ and $j_p$ precedes $j_k$ in $\pi _1$. Thus in $\pi _1$ we have the subsequence $j_l,j_p,j_k$. Thus $j_l,j_p,j_k,j_k,j_l,j_p$ is a subsequence of $\pi$ with $j_p<j_l$ contradicting that $\pi$ is a Stirling permutation.

Thus (312-i) and (312-ii) hold. $\square$

We now characterize Stirling permutations in general by characterizing Stirling permutation pairs.

Theorem 3.8

Let $\pi _1=(i_1,i_2,\ldots ,i_n)$ and $\pi _2=(j_1,j_2,\ldots ,j_n)$ be permutations of $\{1,2,\ldots ,n\}$. Then $(\pi _1,\pi _2)$ is a Stirling permutation pair if and only if $(\pi _1,\pi _2)$ is a 312-avoiding pair of permutations. Moreover, if $(\pi _1,\pi _2)$ is a Stirling permutation pair, then both Algorithm (I) and Algorithm (II) produce the corresponding Stirling permutation.

Proof

By Lemma 3.7, if $(\pi _1,\pi _2)$ is a Stirling permutation pair, then $(\pi _1,\pi _2)$ is a 312-avoiding permutation pair. Now assume that $(\pi _1,\pi _2)$ is a 312-avoiding permutation pair.

We show by induction on k that under this assumption, the permutations $\tau _k$ produced by Algorithm (II) satisfy the Stirling property and thus $\pi =\tau _n$ is a Stirling permutation with corresponding Stirling permutation pair $(\pi _1,\pi _2)$. One should keep in mind the obvious that $\{i_1,i_2,\ldots ,i_n\}=\{j_1,j_2,\ldots ,j_n\}=\{1,2,\ldots ,n\}$.

It is instructive to first argue the case where $j_1=i_n$. Since $\pi _2=(j_1,j_2,\ldots ,j_n)$ and $j_1=i_n$, Algorithm (II) gives the 2-permutation

$$\begin{aligned} \pi =(i_1,i_2,\ldots ,i_n,i_n=j_1, j_2,\ldots ,j_n),\end{aligned}$$

(6)

and this is the only possibility for a Stirling permutation corresponding to $(\pi _1,\pi _2)$. We need to show that (6) is a Stirling permutation. We must have $i_n=n$, for otherwise $(n,i_n)$ is an inversion of $\pi _1$ but not of $\pi _2$.

Assume to the contrary that (6) is not a Stirling permutation. Then there exists $a=i_r$ and $a=j_s$ and an integer b either from $\pi _1$ or $\pi _2$ such that $b<a$ with b between the two a’s. So $b=i_p$ for some p with $r<p< n$, or $b=j_q$ for some integer q with $1<q<s$.

Suppose first that $b=i_p$ with $r<p< n$. Then (a, b) is an inversion of $\pi _1$ and hence of $\pi _2$. So $b=j_k$ for some $k>s$. We thus have $n=j_1>a=j_s>b=j_k$ but $i_n=n>i_r=a>i_p=b$. Then (n, a) and (n, b) are inversions in ${{\mathcal {I}}}(\pi _2){\setminus } {{\mathcal {I}}}(\pi _1)$ and so (a, b) must be an inversion in ${{\mathcal {I}}}(\pi _2){\setminus } {{\mathcal {I}}}(\pi _1)$. This contradicts (312-ii) since (a, b) is an inversion in ${{\mathcal {I}}}(\pi _1)$.

Now suppose that $b=j_q$ with $1\le q<s$. Then (a, b) is not an inversion of $\pi _2$ and so is not an inversion of $\pi _1$. Thus $b=i_k$ for some $k<p$. Thus (n, a), (n, b) are inversions in ${{\mathcal {I}}}(\pi _2){\setminus } {{\mathcal {I}}}(\pi _1)$; moreover, (a, b) is not an inversion in ${{\mathcal {I}}}(\pi _1)$ but also not an inversion in ${{\mathcal {I}}}(\pi _2)$, contradicting (312-ii).

We now consider the general case.

In Algorithm II, $\tau _1$ is obtained from $\pi _1$ by inserting $j_1$ immediately after the occurrence of $j_1$ in $\pi _1$ and this implies that $\tau _1$ satisfies the Stirling property. Now let $k>1$. By induction $\tau _{k-1}$ satisfies the Stirling property. We now insert $j_k$ into $\tau _{k-1}$ according to rule (ii) of Algorithm (II). There are two cases to consider.

Case 1  $j_{k-1}$ was inserted in $\tau _{k-1}$ somewhere before the occurrence of $j_k$ in $\pi _1$. Hence $j_k$ is inserted into $\tau _{k-1}$ immediately after the occurrence of $j_k$ in $\tau _{k-1}$. Since the $j_k$’s occur consecutively in $\tau _k$ and $\tau _{k-1}$ satisfies the Stirling property, $\tau _k$ satisfies the Stirling property.

Case 2   $j_{k-1}$ was inserted in $\tau _{k-1}$ somewhere after the occurrence of $j_k$ in $\pi _1$. Hence, in constructing $\tau _k$, $j_k$ is inserted in $\tau _{k-1}$ immediately after the second occurrence of $j_{k-1}$ in $\tau _{k-1}$. So we have $\pi _1=(\ldots ,j_k,\ldots ,j_{k-1},\ldots )$ and $\tau _{k}=(\ldots ,j_k,\ldots ,j_{k-1},\ldots ,j_{k-1},j_k,\ldots )$. If $j_k>j_{k-1}$, then $(j_k,j_{k-1})\in {{\mathcal {I}}}(\pi _1)$ but, since $j_{k-1}$ precedes $j_k$ in $\pi _2$, $(j_k,j_{k-1})\not \in {{\mathcal {I}}}(\pi -1)$, a contradiction. Thus $j_{k-1}>j_k$.

Consider an integer a in $\tau _k$ between the two $j_{k-1}$’s:

$$\begin{aligned}\tau _{k}=(\ldots ,j_k,\ldots ,j_{k-1},\ldots ,a,\ldots ,j_{k-1},j_k,\ldots ).\end{aligned}$$

Since $\tau _{k-1}$ satisfies the Stirling property, $a>j_{k-1}$ and hence $a>j_k$.

Now consider an integer b in $\tau _k$ between the first $j_k$ and first $j_{k-1}$ in $\tau _k$

$$\begin{aligned}\tau _{k}=(\ldots ,j_k,\ldots ,b,\ldots ,j_{k-1},\ldots ,j_{k-1},j_k,\ldots ).\end{aligned}$$

(So this $j_k$ and $j_{k-1}$ belong to $\pi _1$.) Suppose to the contrary that $b<j_k$. Then $j_{k-1}>j_k>b$. First consider the possibility that b comes from $\pi _1$. Then $(j_k,b)\in {{\mathcal {I}}}(\pi _1)$ and so we must have $(j_k,b)\in {{\mathcal {I}}}(\pi _2)$, that is, $b=j_l$ for some $l>k$. In $\pi _1$ we have the subsequence $j_k,j_l=b,j_{k-1}$, while in $\pi _2$ we have the subsequence $j_{k-1},j_k,j_l=b$ where $j_{k-1}>j_k>b$. This contradicts property (312-iii) of a 312-avoiding pair of permutations.

Hence b must come from $\pi _2$ and, in addition, b must now occur in $\pi _1$ before $j_k$ giving:

$$\begin{aligned}\tau _{k}=(\ldots ,b,\ldots ,j_k,\ldots ,b,\ldots ,j_{k-1},\ldots ,j_{k-1},j_k,\ldots ).\end{aligned}$$

The fact that $b=j_l$, where $l>k$, was inserted after the $j_k$ in $\pi _1$ and that $j_k$ is not yet repeated contradicts Algorithm (II). We conclude that there are no integers in $\tau _k$ between the two $j_k$’s which are smaller than $j_k$. Hence $\tau _k$ satisfies the Stirling property, and Algorithm (II) produces a Stirling permutation with Stirling permutation pair $(\pi _1,\pi _2)$. Since Algorithm (I) produces a Stirling permutation when $(\pi _1,\pi _2)$ is a Stirling permutation pair, Algorithm (I) also produces a Stirling permutation when $(\pi _1,\pi _2)$ is a Stirling permutation pair. $\square$

4 Coda

We conclude with a number of examples and questions.

Let n be a positive integer and let $\pi _1$ and $\pi _2$ be in ${{\mathcal {S}}}_n$. In order that $(\pi _1,\pi _2)$ be a Stirling pair of permutations we must have ${{\mathcal {I}}}(\pi _1)\subseteq {{\mathcal {I}}}(\pi _2)$ and so $\pi _1\preceq _b \pi _2$. Suppose that ${{\mathcal {I}}}(\pi _1)\subseteq {{\mathcal {I}}}(\pi _2)$ and $|{{\mathcal {I}}}(\pi _2){\setminus } {{\mathcal {I}}} (\pi _1)|=1$ so that $\pi _2$ covers $\pi _1$ in the weak Bruhat order. Then it follows from Theorem 3.8 that, by default, $(\pi _1,\pi _2)$ is a 312-avoiding pair of permutations. Suppose we define a new relation $\preceq _*$ on ${{\mathcal {S}}}_n$ by $\pi _1\preceq _* \pi _2$ provided $(\pi _1,\pi _2)$ is a Stirling pair. Then all the cover relations $\pi _1\preceq _b \pi _2$ in the weak Bruhat order on ${{\mathcal {S}}}_n$ automatically satisfy $\pi _1\preceq _* \pi _2$. But the relation $\preceq _*$ is not a partial order on ${{\mathcal {S}}}_n$ because, as shown in the next example, it is not transitive.

Example 4.1

Let $n=4$ and consider the following maximal chain in the weak Bruhat order on ${{\mathcal {S}}}_4$:

$$\begin{aligned} (1,2,3,4)&\preceq _b&(1,2,4,3)\preceq _b(1,4,2,3)\preceq _b (4,1,2,3)\preceq _b (4,2,1,3)\\&\preceq _b&(4,2,3,1)\preceq _b (4,3,2,1).\end{aligned}$$

Then we also have

$$\begin{aligned} (1,2,3,4)&\preceq _*&(1,2,4,3)\preceq _*(1,4,2,3)\preceq _* (4,1,2,3)\preceq _* (4,2,1,3)\\&\preceq _*&(4,2,3,1)\preceq _* (4,3,2,1).\end{aligned}$$

But transitivity fails. For instance, as is easily checked, $(1,2,4,3)\not \preceq _* (4,1,2,3)$ but we do have $(1,2,4,3)\preceq _* (4,2,1,3)$. $\square$

Example 4.2

We know that $|(1,2,3,4)|_r=14$ but with one transposition increasing the number of inversions we get (1, 3, 2, 4) where $|(1,3,2,4)|_r=9$. The $\pi _2$’s that work for (1, 2, 3, 4) are:

$$\begin{aligned}&\displaystyle (4,3,2,1), (3,4,2,1), (3,2,1,4), (3,2,4,1),(2,1,3,4), (2,1,4,3),(2,3,1,4), \\&\displaystyle (2,3,4,1), (2,4,3,1), (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,3,2). \end{aligned}$$

Those that work for (1, 3, 2, 4) are

$$\begin{aligned}&\displaystyle (1,3,2,4), (1,3,4,2),(3,1,2,4), (3,1,4,2), (3,2,1,4), (3,2,4,1),\\&\displaystyle (3,4,1,2), (3,4,2,1), (4,2,3,1). \end{aligned}$$

Now let $\pi _1=(1,3,2,4)$ also with one inversion. Then there are seven $\pi _2$’s that give Stirling permutations, namely,

$$\begin{aligned}1324,1342,3124,3142,3214,3241,3421.\end{aligned}$$

$\square$

Question 4.3

Is there a type of Bruhat order on Stirling permutations of the multiset $\{1,1,2,2,\ldots ,n,n\}$ in terms of their corresponding Stirling pairs and associated (0, 1, 2)-matrix with row and column sums equal to 2. (A permutation pair $\pi _1$ and $\pi _2$ gives a (0, 1, 2)-matrix A with all row and column sums equal to 2.) $\square$

Question 4.4

Is there an algorithm that allows one to generate all Stirling permutations of order n from the identity Stirling permutation $(1,1,2,2,\ldots ,n,n)$ of order n. What kinds of transformations take a Stirling permutation matrix into another Stirling permutation matrix?$\square$

Finally, we mention that Stirling permutations have been extended to more general r-permutations of $\{1,2,\ldots ,n\}$ [5, 9].