# Blockwise Simple Permutations

###### Abstract.

A permutation is called block-wise simple if it contains no interval of the
form $p_{1}\oplus p_{2}$ or $p_{1}\ominus p_{2}$. We present this new set of
permutations and explore some of its combinatorial properties. We present a
generating function for this set, as well as a recursive formula for counting
block-wise simple permutations. Following Tenner, who founded the notion of
interval posets, we characterize and count the interval posets corresponding
to block-wise simple permutations. We also present a bijection between these
interval posets and certain tiling’s of the $n$-gon. Finally, we prove that
the bi-variate distribution of the descent and inverse descent numbers are
gamma-positive, provided the correctness of our recent conjecture on simple
permutations.

Eli Bagno, Estrella Eisenberg, Shulamit Reches and Moriah Sigron

##  1\. Introduction

This study focuses on a new set of permutations called block-wise simple
permutations, which we define in two different but equivalent ways. The first
definition is recursive and is stated here. The other, as well as the proof of
the equivalence of the two definitions, is presented in Section 3. The notions
and notations required are defined in Section 2.

######  Definition 1.1.

Let $\mathcal{S}_{n}$ be the group of permutations of the set
$\\{1,\dots,n\\}$.

  1. (1)

The identity permutation $\pi=1$ is block-wise simple.

  2. (2)

A permutation $\pi\in\mathcal{S}_{n}$ is block-wise simple if there is
$\sigma\in\mathcal{S}_{k}$ $(k\geq 4)$ which is a simple permutation (see
Definition 2.3), and there are $\alpha_{1},\dots,\alpha_{k}$ which are block-
wise simple permutations, such that $\pi=\sigma[\alpha_{1},\dots,\alpha_{k}]$,
the inflation of $\sigma$ by $\alpha_{1},\dots,\alpha_{k}$ (see Definition
2.7).

There are no block-wise simple permutations of orders $2$ and $3$. For
$n\in\\{4,5,6\\}$, a permutation is block-wise simple, if and only if it is
simple. One of the first nontrivial examples of block-wise simple permutations
is
$2413[3142,1,1,1]=4253716$.

The following table, the calculations leading to most of its values are
explained later in this paper, details the number of block-wise simple
permutations and the number of simple permutations for $n$ less than or equal
to $10$.
We denote by $W_{n}$ the set of all block-wise simple permutations of order
$n$ and by $Simp_{n}$ the set of simple permutations of order $n$.

$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
---|---|---|---|---|---|---|---|---|---|---|---|---
$|W_{n}|$ | 1 | 2 | 0 | 2 | 6 | 46 | 354 | 3034 | 29246 | 309174 | 3563562 | 44471970
$|Simp_{n}|$ | 1 | 2 | 0 | 2 | 6 | 46 | 338 | 2926 | 28146 | 298526 | 3454434 | 43286526

In Section 3 we define the block-wise simple permutations in an alternative
way and prove that the two definitions are equivalent (see Theorem 3.2).

Tenner [15] defined the concept of an interval poset of a permutation (see
Definition 4.1). This is an effective way of capturing all the intervals of a
permutation and the set of inclusions between them in one glance. An interval
poset might correspond to more than one permutation. For instance, all simple
permutations of a given order $n$ share the same interval poset. In this
study, we count the number of interval posets that correspond to block-wise
simple permutations. We prove that this number is exactly

$\frac{1}{n}\sum_{i=1}^{\lfloor\frac{n-1}{3}\rfloor}{n+i-1\choose
i}{n-2i-2\choose i-1}$

(for $n\geq 4$ ) (see Theorem 4.4).

We provide a bijection between the set of interval posets of block-wise
permutations of order $n$ and the set of ways to place non-crossing diagonals
in a convex ($n+1$)-gon to create no triangles or quadrilaterals. (see theorem
4.6). We also calculate the Möbius function of the interval posets of block-
wise simple permutations (see Theorem 4.8).

Owing to the recursive definition of block-wise simple permutations, we obtain
a generating function, the functional inverse of which is close to the
generating function of simple permutations. This is proven in Section 5.

The two-sided Eulerian numbers, studied by Carlitz, Roselle, and Scoville,
[12], count permutations according to their number of descents and inverse
descents. Gessel (see [4, Conjecture 10.2]) conjectured that the bi-variate
polynomial $\sum\limits_{\pi\in\mathcal{S}_{n}}s^{des(\pi)}t^{des(\pi^{-1})}$
can be written as a positive linear combination of elements of a certain
’gamma basis’. In [1], the authors of this paper, together with R. Adin,
proposed a similar conjecture related to the set of simple permutations. Here,
we show how to combinatorially prove ’gamma positivity’ for block-wise simple
permutations, based on the correctness of the conjecture on simple
permutations. This is discussed in Section 6.

##  2\. Background

######  Definition 2.1.

Let $\pi=a_{1}\cdots a_{n}\in\mathcal{S}_{n}$. An interval (or block) of $\pi$
is a non-empty contiguous sequence of entries $a_{i}a_{i+1}\cdots a_{i+k}$
whose values also form a contiguous sequence of integers. For $a<b$, $[a,b]$
denotes the interval of values that range from $a$ to $b$. Clearly,
$[n]:=[1,n]$ is an interval as well as $\\{i\\}$ for each $i\in[n]$. These are
called trivial intervals. The other intervals are called proper.

######  Example 2.2.

The permutation $\pi=314297856$ has $[5,9]=97856$ as a proper interval as well
as the following proper intervals: $[1,4],[5,6],[7,8],[7,9]$, $[5,8]$.

######  Definition 2.3.

A permutation $\pi\in\mathcal{S}_{n}$ is called simple if it does not have
proper intervals.

######  Example 2.4.

The permutation $3517246$ is simple.

######  Definition 2.5.

Let $\pi\in\mathcal{S}_{m}$ and $\sigma\in\mathcal{S}_{n}$. The direct sum of
$\pi$ and $\sigma$ is the permutation $\pi\oplus\sigma\in\mathcal{S}_{m+n}$
defined by

$(\pi\oplus\sigma)_{i}=\begin{cases}\pi_{i},&\text{if }i\leq m;\\\
\sigma_{i-m}+m,&\text{if }i>m,\end{cases}$

Their skew sum is the permutation $\pi\ominus\sigma\in\mathcal{S}_{m+n}$
defined by

$(\pi\ominus\sigma)_{i}=\begin{cases}\pi_{i}+n,&\text{if }i\leq m;\\\
\sigma_{i-m},&\text{if }i>m.\end{cases}$

######  Example 2.6.

If $\pi=132$ and $\sigma=4231$ then $\pi\oplus\sigma=1327564$ and
$\pi\ominus\sigma=5764231$.

The $\oplus$ and $\ominus$ operations are the simplest examples of inflation.

######  Definition 2.7.

Let $n_{1},\ldots,n_{k}$ be positive integers, with $n_{1}+\ldots+n_{k}=n$.
The inflation of a permutation $\pi\in\mathcal{S}_{k}$ by the permutations
$\alpha_{i}\in\mathcal{S}_{n_{i}}$ $(1\leq i\leq k)$ is the permutation
$\pi[\alpha_{1},\ldots,\alpha_{k}]\in\mathcal{S}_{n}$ obtained by replacing
for each $1\leq i\leq k$ the $i$-th entry of $\pi$ with a block that is order-
isomorphic to the permutation $\alpha_{i}$ on the numbers
$\\{s_{i}+1,\ldots,s_{i}+n_{i}\\}$ instead of $\\{1,\ldots,n_{i}\\}$, where
$s_{i}=n_{1}+\ldots+n_{i-1}$ $(1\leq i\leq k)$.

It should be noted that $\pi\oplus\sigma=12[\pi,\sigma]$ and
$\pi\ominus\sigma=21[\pi,\sigma]$.

######  Example 2.8.

The inflation of $2413$ by $213,21,132$ and $1$ is

$2413[213,21,132,1]=546\ 98\ 132\ 7.$

We present the following result from [9], which lays out the structure of
permutations as inflation’s of simple permutations.

######  Theorem 2.9.

For each $n\geq 2$ and any $\pi\in\mathcal{S}_{n}$ there exists a unique
simple permutation $\sigma\in\mathcal{S}_{k}$ such that
$\pi=\sigma[\alpha_{1},\dots,\alpha_{k}]$. Moreover, if $k\geq 4$ then
$\alpha_{1},...,\alpha_{k}$ are uniquely determined.

##  3\. Enumeration of block-wise simple permutations

###  3.1. An alternate definition of block-wise simple permutations

Recall Definition 1.1. We begin this section with another definition of block-
wise simple permutations.

######  Definition 3.1.

A permutation $\pi\in\mathcal{S}_{n}$ is block-wise simple if and only if it
has no interval of the form $p_{1}\oplus p_{2}$ or $p_{1}\ominus p_{2}$.

######  Theorem 3.2.

The two definitions of block-wise simple permutations are equivalent.

###### Proof.

If $\pi\in\mathcal{S}_{n}$ is block-wise simple according to definition 1.1,
it is clear that $\pi$ contains no interval of the form $p_{1}\oplus p_{2}$ or
$p_{1}\ominus p_{2}$.

On the other hand, let $\pi\in\mathcal{S}_{n},n>1$, be such that $\pi$ has no
interval of the form $p_{1}\oplus p_{2}$ or $p_{1}\ominus p_{2}$. Based on
theorem 2.9, we can write
$\pi=\sigma_{1}[\alpha_{1}^{1},\dots,,\alpha_{k}^{1}]$ with $\sigma_{1}\in
Simp_{k}$ and assume to the contrary that $\pi$ is not block-wise simple.
Because $\pi$ has no intervals of the form $p_{1}\oplus p_{2}$ or
$p_{1}\ominus p_{2}$, we must have $k\geq 4$ and there is some $1\leq i\leq k$
such that $\alpha_{i}^{1}$ is not block-wise simple. Assuming without loss of
generality that $i=1$, we can write
$\alpha_{1}^{1}=\sigma_{2}[\alpha_{1}^{2},\dots\alpha_{l}^{2}]$ . As $\pi$ has
no intervals of the form $p_{1}\oplus p_{2}$ or $p_{1}\ominus p_{2}$,
$\sigma_{2}$ is also simple of order $l\geq 4$. Without loss of generality,
$\alpha_{1}^{2}$ is not block-wise simple. Proceeding in this manner, we
obtain a sequence of non-block-wise simple permutations $(\alpha_{1}^{j})$
which are inflation’s of simple permutations, such that the sequence of the
orders $(|\alpha_{1}^{j}|)$ is strictly decreasing. Hence, some $j$ exists,
such that $|\alpha_{1}^{j}|=1$ whereas $\alpha_{1}^{j}$ is not block-wise
simple. However, this is a contradiction. ∎

###  3.2. Counting block-wise simple permutations

We now discuss the counting of block-wise simple permutations, starting with
some values for low orders.

######  Example 3.3 ($n=7$).

Each simple permutation $\sigma$ of order $7$ induces a block-wise simple
permutation of the form $\pi=\sigma[1,1,1,1,1,1,1]$ which is obviously simple.
In this manner, we obtain $338$ block-wise simple permutations. (see Fig. 1,
right). Moreover, for each block-wise simple permutation $\tau$ of order $4$,
and for each simple permutation $\sigma$ of order $4$, all permutations

$\pi\in\\{\sigma[\tau,1,1,1],\sigma[1,\tau,1,1],\sigma[1,1,\tau,1],\sigma[1,1,1,\tau]\\}$

are block-wise simple. These results in $16$ new permutations, which sums up
to $354$ block-wise simple permutations, together with the simple permutations
of order $7$. (see Fig. 1, left).

$4$$4$$1$$1$$1$$|Simp_{4}|\cdot|Simp_{4}|\cdot
4=16$$7$$1$$1$$1$$1$$1$$1$$1$$|Simp_{7}|=338$ Figure 1.  $n=7$.

######  Example 3.4 ($n=8$).

For each simple permutation $\sigma$ of order $8$, we have the block-wise
simple permutation of the form $\pi=\sigma[1,1,1,1,1,1,1,1]$ . This
contributes $2926$ block-wise simple permutations which are also simple.
Moreover, for each block-wise simple permutation $\tau$ of order $5$ and for
each simple permutation $\sigma$ of order $4$, all the permutations

$\pi\in\\{\sigma[\tau,1,1,1],\sigma[1,\tau,1,1],\sigma[1,1,\tau,1],\sigma[1,1,1,\tau]\\}$

are block-wise simple. The contribution is $48$.

Moreover, for each block-wise simple permutation $\tau$ of order $4$ and for
each simple permutation $\sigma$ of order $5$, all the permutations:

$\pi\in\\{\sigma[\tau,1,1,1,1],\sigma[1,\tau,1,1,1],\sigma[1,1,\tau,1,1],\sigma[1,1,1,\tau,1],\sigma[1,1,1,1,\tau]\\}$

are block-wise simple. The total contribution is $60$. The total of block-wise
permutations of order $8$ is thus $3034$ (see Fig. 2).

$5$$4$$1$$1$$1$$1$$|Simp_{5}|\cdot|Simp_{4}|\cdot
5=60$$8$$1$$1$$1$$1$$1$$1$$1$$1$$|Simp_{8}|=2926$$4$$5$$1$$1$$1$$|Simp_{4}|\cdot|Simp_{5}|\cdot
4=48$ Figure 2. $n=8.$

From these two examples, we can determine the general pattern given by the
following recursion:

######  Observation 3.5.

Let $w_{n}=|W_{n}|$ and $s_{n}=|Simp_{n}|$. Then, for $n\geq 4$ we have

$w_{n}=\sum_{l=4}^{n}{s_{l}\sum_{\lambda=(\lambda_{1},\dots,\lambda_{l})\in
Comp(n,l)}w_{\lambda_{1}}\cdots w_{\lambda_{l}}}$ (1)

where $Comp(n,l)$ is the set of compositions of $n$ in $l$ parts.

Two remarks are now in order.

######  Remark 3.6.

Note that in Equation (1), simple permutations are counted where $l=n$.

######  Remark 3.7.

Note that in Example 3.3, we counted a limited number of compositions of $7$.
This is reflected in the fact that, for each $l\in\\{5,6\\}$, a composition of
$7$ of the form $\lambda=(\lambda_{1},\dots,\lambda_{l})$ contributes $0$
because each composition must contain some $\lambda_{i}\in\\{2,3\\}$ such that
$w_{\lambda_{1}}=0$.

##  4\. Counting the number of interval posets

Following Tenner [15], we define an interval poset for each permutation as
follows:

######  Definition 4.1.

The interval poset of a permutation $\pi\in S_{n}$ is the poset $P(\pi)$ whose
elements are the non-empty intervals of $\pi$; the order is defined by set
inclusion (see for example Figure 3). The minimal elements are the intervals
of size $1$.

In [15], the interval poset is embedded in the plane so that each node’s
direct descendants are increasingly ordered according to the minimum of each
interval from left to right. We note that in [11] another embedding of the
same poset was presented.

$[1,7]$$[1,6]$$\\{7\\}$$[1,3]$$\\{4\\}$$\\{5\\}$$\\{6\\}$$\\{1\\}$$\\{2\\}$$\\{3\\}$
Figure 3. Interval poset of the permutations: 5123647, 5321647, 4612357,
4632157, 7463215, 7461235, 7532164, 7512364

If $\pi$ is a simple permutation, the interval poset of $\pi$ comprises the
entire interval $[1,\dots,n]$ with minimal elements $\\{1\\},\dots,\\{n\\}$ as
its only descendants. Hence, all simple permutations of a given order $n$
share the same interval poset (see for example Figure 4).

$[1,4]$$\\{1\\}$$\\{2\\}$$\\{3\\}$$\\{4\\}$ Figure 4. Interval poset of
permutations 3142 and 2413.

######  Definition 4.2.

Given a poset $P$, the permutations, whose interval poset is $P$ are called in
[15] the generators of $P$. Formally, a set of such permutations is defined as

$I(P):=\\{w\in S_{n}:P(w)=P\\}.$

Following [15], we define a dual-claw poset as a poset that has a unique
maximal element and $k\geq 4$ minimal elements, which are all covered by the
maximal element. For our convenience, we omit the adjective ’dual’ and call it
here just claw poset .

A claw poset with $k$ minimal elements is an interval poset of a permutation
$\sigma$ if and only if $\sigma$ has no proper intervals; that is, $\sigma$ is
simple. Thus, its generators are the simple permutations of order $k$.

######  Remark 4.3.

A tree poset is a poset whose Hasse diagram is a tree. In [15] (Theorem 6.1),
the author claimed that $P(\sigma)$ is a tree interval poset if and only if
$\sigma$ contains no interval of the form $p_{1}\oplus p_{2}\oplus p_{3}$ or
$p_{1}\ominus p_{2}\ominus p_{3}$. Based on Theorem 3.2, it is evident that
the interval poset of a block-wise simple permutation is a tree. In fact, by
Definition 1.1, the interval poset of a block-wise simple permutation is a
claw of claws. This means that the root is a claw and every node is either a
claw or a leaf (see Figure. 5 for an example).

$[...]$$\\{\\}$$[...]$$\\{\\}$$\\{\\}$$\\{\\}$$\\{\\}$$\\{\\}$$\\{\\}$ Figure
5. Claw of claws

The first problem we tackle in this section is the enumeration of interval
posets that represent block-wise simple permutations of order $n$. As
described above, this problem reduces to counting claws of claws.

Let $\mathcal{C}$ be the combinatorial class of all claws of claws, so that
for each $n$, $\mathcal{C}_{n}$ is the set of all claws of claws having $n$
leaves. We apply the approach of symbolic combinatorics (see [13]) to count
claw of claws.

The class $\mathcal{C}$ is described by the following symbolic combinatorial
equation:

$\mathcal{C}=\\{\bullet\\}\biguplus Seq_{\geq 4}(\mathcal{C})$

where $\\{\bullet\\}$ represents a leaf and $Seq_{\geq 4}(\mathcal{C})$
represents a sequence of elements of $\mathcal{C}$ with at least four
components. The generating function is

$C(z)=z+\frac{C(z)^{4}}{1-C(z)}.$

Denoting $u=C(z)$, we have

$z=u-\frac{u^{4}}{1-u}=u(1-\frac{u^{3}}{1-u}).$

Subsequently, $u=z\phi(u)$ is obtained, where
$\phi(u)=\frac{1}{1-\frac{u^{3}}{1-u}}$.

According to Lagrange inversion formula (see for example [14][Theorem 5.4.2]),
we have

$C(z)=\sum_{n\geq 1}c_{n}z^{n}$

where $c_{n}=\frac{1}{n}[u^{n-1}]\phi(u)^{n}$.

To extract $[u^{n-1}]\phi(u)^{n}$ we compute:

$\phi(u)^{n}=\left(\frac{1}{1-\frac{u^{3}}{1-u}}\right)^{n}=$

$\sum_{i\geq 0}{n+i-1\choose
i}\frac{u^{3i}}{(1-u)^{i}}=1+\sum_{i>0}{n+i-1\choose
i}\frac{u^{3i}}{(1-u)^{i}}=$ $1+\sum_{i>0}{n+i-1\choose i}{u^{3i}}\sum_{j\geq
0}{i+j-1\choose j}u^{j}=1+\sum_{i>0}\sum_{j\geq 0}{n+i-1\choose
i}{i+j-1\choose j}u^{j+3i}.$

By extracting the coefficient of $u^{n-1}$, we obtain $j=n-1-3i$

$[u^{n-1}]\phi(u)^{n}=\sum_{i>0}{n+i-1\choose i}{i+n-2-3i\choose n-3i-1}=$
$\sum_{i>0}{n+i-1\choose i}{n-2i-2\choose n-3i-1}=$
$=\sum_{i=1}^{\lfloor\frac{n-1}{3}\rfloor}{n+i-1\choose i}{n-2i-2\choose i-1}$

Because we require $n-2i-2\geq i-1$, we obtain $i\leq\frac{n-1}{3}$.

From the above calculations, we obtain the following theorem:

######  Theorem 4.4.

The number of interval posets corresponding to block-wise simple permutations
of order $n\geq 4$ is

$\frac{1}{n}\sum_{i=1}^{\lfloor\frac{n-1}{3}\rfloor}{n+i-1\choose
i}{n-2i-2\choose i-1}.$

The first few values of the sequence of these numbers are
$1,1,1,5,10,16,45,109,222,540$. This is sequence A054514 from OEIS [16] which
also counts the number of ways to place non-crossing diagonals in a convex
$(n+4)$-gon such that there are no triangles or quadrilaterals.
Here, we provide a combinatorial proof presenting a bijection from the set of
interval posets corresponding to block-wise simple permutations to the above-
mentioned set.

We identify a polygon with its set of vertices and denote a diagonal from
vertex $i$ to vertex $j$ by $(i,j)$.

Figure 6. Right: the interval poset P. Left: the polygon $\Phi(P)$

We let $P$ be the interval poset corresponding to a block-wise simple
permutation $\pi$ of order $n$. We set $\Phi(P)$ as the convex ($n+1$)-gon
whose set of diagonals is

$\\{(a,b+1)|\,[a,b]\text{ is an internal node of }P\\}.$

(see Figure 6 for an example).

Note that by Remark 4.3:

  1. (1)

For every two nodes $[a,b],[c,d]$ of $P$, either $[a,b]\subset[c,d]$ or
$[c,d]\subset[a,b]$ or $[a,b]\cap[c,d]=\emptyset$.

  2. (2)

Each node $[a,b]$ of $P$ is an interval of size at least $4$ so $b-a\geq 3$.

  3. (3)

Each node $[a,b]$ of $P$ covers at least $4$ nodes, which are pairwise
disjoint.

According to (1), the polygon $\Phi(P)$ has no crossing diagonals. By (3),
each direct descendant of an interval $[a,b]$ which is itself an interval, say
$[c,d]$, creates a sub-polygon $\\{c,\dots,d,d+1\\}$ of size $d-c+2>4$. There
is an additional sub-polygon created by the direct descendants of $[a,b]$ that
are not intervals, together with the first elements of each interval and the
vertex $b+1$. By (2), this sub-polygon also has at least $5$ vertices. We
conclude that the diagonals of the sub-polygon associated with each interval
$[a,b]$ create no triangles or quadrilaterals.

######  Example 4.5.

Consider $[a,b]=[1,17]$ in Figure 6. The corresponding polygon is
$E=\\{1,\dots,18\\}$. The descendants of $[1,17]$ are $[1,10]$, $\\{11\\}$,
$[12,15]$, $\\{16\\}$ and $\\{17\\}$.

The interval $[1,10]$ creates the sub-polygon $\\{1,\dots,11\\}$ of order
$11$. The interval $[12,15]$ creates the sub-polygon $\\{12,\dots,16\\}$. Both
are of size greater than $4$ by the condition on the size of intervals. The
additional sub-polygon $\\{1,11,12,16,17,18\\}$ is of size greater than $4$
because each of the descendants of $[1,17]$ contributes at least one vertex
(its first vertex if it is an interval, or itself if it is a singleton) and
including the vertex $18$ makes it greater than $4$.

From the discussion above one can prove the following:

######  Theorem 4.6.

The number of interval posets that represent a block-wise simple permutation
of order $n$ is equal to the number of ways to place non-crossing diagonals in
a convex ($n+1$)-gon such that no triangles or quadrilaterals are present.

######  Remark 4.7.

In [11], the authors calculated the generating function of the number of tree
interval posets using generating functionology and mentioned that this is
equal to the number of ways to place non-crossing diagonals in a convex
$(n+2)$-gon such that no quadrilaterals are created (sequence A054515 from
OEIS [17]). The function $\Phi$ defined above can be slightly amended so that
it would provide a combinatorial proof of this equivalence.

We end this section with a simple consequence of Theorem 2.8 of [11],
concerning Möbius function of the interval poset of a block-wise simple
permutation.

######  Proposition 4.8.

Let $\sigma=\pi[\alpha_{1},\dots,\alpha_{k}]$ be a block-wise simple
permutation and let $P(\sigma)$ be its closed interval poset. For each
interval $I$ of $P(\sigma)$ we have

$\mu(I,[1,\dots,n])=\left\\{\begin{array}[]{lll}1&&I=[1,\dots,n]\\\
-1&&I\text{ is a coatom}\\\ k-1&&I=\emptyset\\\
0&&\text{Otherwise}\end{array}\right.$

##  5\. A generating function for block-wise simple permutations

Recall that a permutation $\pi$ is called ’simple’ if it has no blocks other
than the singletons and the entire permutation.

In most sources in the literature, permutations of orders $1$ and $2$ are
considered simple. However, there are cases in which simple permutation is
defined as having an order of at least $4$ (see for example [10]). In this
section, we adopt the latter approach.

Let $S(x)=\sum\limits_{n\geq 4}s_{n}x^{n}$ be the generating function of the
simple permutations and $W(x)=\sum\limits_{n\geq 1}w_{n}x^{n}$ be the
generating function of block-wise simple permutations. The following recursion
is a direct consequence of Definition 1.1.

$W(x)=x+(S\circ W)(x).$ (2)

Let $F(x)=\sum\limits_{k\geq 1}n!x^{n}$. By denoting $t=W(x)$ and thus
$x=W^{-1}(t)$ in Equation (2), we obtain for each $t$

$S(t)=t-W^{-1}(t).$ (3)

From Equation (2) of [10], we obtain

$S(t)=t-\frac{2t^{2}}{1+t}-F^{-1}(t)$ (4)

and by substituting Equation (4) in Equation (3) we obtain

$W^{-1}(t)=F^{-1}(t)+\frac{2t^{2}}{1+t}.$ (5)

Denoting the coefficient of $t^{n}$ in $F^{-1}(t)$ by $Com_{n}$ (in reference
to Comtet who was the first to consider this sequence OEIS(A059372)), and
letting $W^{-1}(t)=\sum\limits_{n=1}^{\infty}a_{n}t^{n}$, we obtain
$a_{1}=1,a_{2}=0,a_{3}=0$ and for $n\geq 4$:

$a_{n}=Com_{n}+2\cdot(-1)^{n}.$

From (3), we obtain for $n\geq 4$:

$a_{n}=-s_{n}.$

By applying the Lagrange inversion formula [14] [Theorem 5.42], we obtain an
expression for the $n-th$ coefficient of $W(t)$:

$[t^{n}]W(t)=\frac{1}{n}[t^{n-1}]\left(\frac{t}{W^{-1}(t)}\right)^{n}$

Thus,

$[t^{n}]W(t)=\frac{1}{n}[t^{n-1}]\left(\frac{t}{1+\sum\limits_{k=2}^{\infty}(Com_{k}+2\cdot(-1)^{k})t^{k}}\right)^{n}$

From (3), we can conclude that the sequence of block-wise simple permutations
is not polynomial recursive.

##  6\. gamma positivity

Eulerian numbers enumerate permutations according to their descent numbers.
The descent number of a permutation is defined as follows:

######  Definition 6.1.

Let $\pi\in\mathcal{S}_{n}$.

$\operatorname{des}(\pi)=|\\{i\in[n-1]\mid\pi(i)>\pi(i+1)\\}|.$

The descent number of the inverse of a permutation $\pi$ is defined as

$\operatorname{ides}(\pi)=\operatorname{des}(\pi^{-1}).$

For example, if $\pi=246135$ then the only descent of $\pi$ is $3$; thus, we
obtain $\operatorname{des}(\pi)=1$, whereas $\operatorname{ides}(\pi)=3$. Many
studies have been made on the distribution of descents on certain subsets of
$\mathcal{S}_{n}$ and on some other permutation groups.

The two-sided Eulerian numbers, studied by Carlitz, Roselle, and Scoville [12]
constitute a natural generalization. These numbers count permutations
according to their number of descents as well as the number of descents of the
inverse permutation.

Gessel conjectured that the corresponding generating function
$A_{n}(s,t)=\sum_{\pi\in S_{n}}s^{\operatorname{des}(\pi)}t^{ides(\pi)}$ has a
nice symmetry property, namely, gamma-positivity. His conjecture was proven in
[6]. To present the idea of gamma-positivity in a formal way, we present some
definitions.

A polynomial $f(q)$ is palindromic if its coefficients are the same when read
from left to right and from right to left. If
$f(q)=a_{r}q^{r}+a_{r+1}q^{r+1}+\cdots+a_{s}q^{s}$ with $a_{r},a_{s}\neq 0$
and $r\leq s$, then $a_{r+i}=a_{s-i}$ $(\forall i)$; equivalently,
$f(q)=q^{r+s}f(1/q)$.

Following Zeilberger [8], we define the darga of a palindromic polynomial
$f(q)$ as $r+s$; the zero polynomial is considered palindromic for each non-
negative darga. The set of palindromic polynomials of darga $n-1$ is a vector
space of dimension $\lfloor(n+1)/2\rfloor$, with a gamma basis

$\\{q^{j}(1+q)^{n-1-2j}\mid 0\leq j\leq\lfloor(n-1)/2\rfloor\\}.$

The (one-sided) Eulerian polynomial

$A_{n}(q)=\sum_{\pi\in S_{n}}q^{\operatorname{des}(\pi)}$

is palindromic of darga $n-1$ and thus there are real numbers $\gamma_{n,j}$
such that

$A_{n}(q)=\sum_{0\leq
j\leq\lfloor(n-1)/2\rfloor}\gamma_{n,j}q^{j}(1+q)^{n-1-2j}.$

See [7, pp. 72 - 79] for details.

For every set $\mathcal{C}$ of permutations, we define the two-sided Eulerian
polynomial of $\mathcal{C}$ as

$A_{\mathcal{C}}(s,t)=\sum_{\pi\in\mathcal{C}}s^{\operatorname{des}(\pi)}t^{\operatorname{ides}(\pi)}.$

Let $A_{Simp_{n}}(s,t)$ and $A_{W_{n}}(s,t)$ be the two-sided Eulerian
polynomials for simple permutations and block-wise simple permutations of
order $n$, respectively.

For each positive integer $n$, the set $Simp_{n}$ of simple permutations of
length $n$ is invariant under taking inverses and reverses. Consequently, the
set $W_{n}$ of blockwise simple permutations of length $n$ is also invariant
under taking inverses and reverses.

Thus, it can be easily proven that the bi-variate polynomial $A_{W_{n}}(s,t)$
satisfies

$A_{W_{n}}(s,t)=A_{W_{n}}(t,s)$ (6)

as well as

$A_{W_{n}}(s,t)=(st)^{n-1}A_{W_{n}}(1/s,1/t).$ (7)

In fact, (7) follows from the bijection from $W_{n}$ onto itself, transforming
a permutation to its reverse, whereas (6) follows from the bijection taking
each permutation to its inverse.

A bivariate polynomial satisfying Equations (6) and (7) is called (bivariate)
palindromic of darga $n-1$.

It can be proven (see [7, pp. 72-79]) that the set of bivariate palindromic
polynomials of darga $n-1$ is a vector space of dimension
$\lfloor(n+1)/2\rfloor\cdot\lfloor(n+2)/2\rfloor$ with bivariate gamma basis:

$\\{(st)^{i}(s+t)^{j}(1+st)^{n-1-j-2i}\mid i,j\geq 0,\,2i+j\leq n-1\\}.$

######  Definition 6.2.

A bivariate palindromic polynomial is called gamma-positive if all
coefficients in its expression in terms of the bivariate gamma basis are non-
negative integers.

######  Example 6.3.

Recall that

  1. (1)

$Simp_{4}=\\{2413,3142\\}$. The two-sided Eulerian polynomial

$A_{Simp_{4}}(s,t)=s^{2}t+st^{2}=(st)(s+t)$

is gamma-positive.

  2. (2)

The polynomial

$A_{Simp_{6}}(s,t)=st(s+t)^{2}(1+st)+5(st)^{2}(1+st)+14(st)^{2}(s+t)$

is also gamma-positive.

In our previous paper [1] we presented the following conjecture and used it
for reducing the problem of gamma-positivity of the entire group
$\mathcal{S}_{n}$ to that of $Simp_{n}$.

######  Conjecture 6.4.

For each positive $n\in\mathbb{N}$, the two-sided Eulerian polynomial,

$A_{Simp_{n}}(s,t)=\sum_{\sigma\in
Simp_{n}}s^{\operatorname{des}(\sigma)}t^{\operatorname{ides}(\sigma)}$

is gamma-positive.

Assuming that Conjecture 6.4 holds, we can prove the following theorem:

######  Theorem 6.5.

For each $n\geq 1$ there exist non-negative integers $\gamma_{n,i,j}$
$(i,j\geq 0,\,2i+j\leq n-1)$ such that

$A_{W_{n}}(s,t)=\sum\limits_{i,j}{\gamma_{n,i,j}(st)^{i}(s+t)^{j}(1+st)^{n-1-j-2i}}.$

To prove Theorem 6.5, we require some observations.

######  Observation 6.6.

Inflation is additive on both $\operatorname{des}$ and $\operatorname{ides}$.
Explicitly:

Let $\sigma=\pi[\tau_{1},\dots,\tau_{k}]$, then

$\operatorname{des}(\sigma)=\operatorname{des}(\pi)+\sum_{i=1}^{n}{\operatorname{des}(\tau_{i})}$

and

$\operatorname{ides}(\sigma)=\operatorname{ides}(\pi)+\sum_{i=1}^{n}{\operatorname{ides}(\tau_{i})}$

thus,

$s^{\operatorname{des}(\sigma)}t^{\operatorname{ides}(\sigma)}=s^{\operatorname{des}(\pi)}t^{\operatorname{ides}(\pi)}\prod_{i=1}^{n}s^{\operatorname{des}(\tau_{i})}t^{\operatorname{ides}(\tau_{i})}.$

######  Definition 6.7.

Let $\mathcal{A}\subset S_{k}$ and $\mathcal{B}_{1},\ldots,\mathcal{B}_{k}$ be
sets of permutations. Let us define

$\mathcal{A}[\mathcal{B}_{1},\ldots,\mathcal{B}_{k}]=\\{\alpha[\beta_{1},\ldots,\beta_{k}]\mid\alpha\in\mathcal{A},\,\beta_{i}\in\mathcal{B}_{i}\\}.$

If $\mathcal{B}_{i}\subset S_{n_{i}}$ ($i\in\\{1,\dots,k\\}$), then
$\mathcal{A}[\mathcal{B}_{1},\ldots,\mathcal{B}_{k}]\subset S_{n}$ where
$n=\sum n_{i}$.

######  Proposition 6.8.

The two-sided Eulerian polynomial of
$\mathcal{A}[\mathcal{B}_{1},\ldots,\mathcal{B}_{k}]$ is the product of the
two-sided Eulerian polynomials of $\mathcal{A}$ and
$\mathcal{B}_{1},\ldots,\mathcal{B}_{k}$.

###### Proof.

From Observation 6.6, the following can be obtained

$\displaystyle\sum_{\sigma=\pi[\tau_{1},\dots,\tau_{k}]\in\mathcal{A}[\mathcal{B}_{1},\ldots,\mathcal{B}_{k}]}s^{\operatorname{des}(\sigma)}t^{\operatorname{ides}(\sigma)}$
$\displaystyle=\sum_{\pi\in\mathcal{A},\tau_{1}\in\mathcal{B}_{1},\dots,\tau_{k}\in\mathcal{B}_{k}}\bigg{(}s^{\operatorname{des}(\pi)}t^{\operatorname{ides}(\pi)}\prod_{i=1}^{n}s^{\operatorname{des}(\tau_{i})}t^{\operatorname{ides}(\tau_{i})}\bigg{)}$
$\displaystyle=\sum_{\pi\in\mathcal{A}}s^{\operatorname{des}(\pi)}t^{\operatorname{ides}(\pi)}\prod_{i=1}^{n}\bigg{(}\sum_{\tau_{i}\in\mathcal{B}_{i}}s^{\operatorname{des}(\tau_{i})}t^{\operatorname{ides}(\tau_{i})}\bigg{)}$

as required. ∎

######  Observation 6.9.

If the two-sided Eulerian polynomials of $\mathcal{A}$ and
$\mathcal{B}_{1},\ldots,\mathcal{B}_{k}$ are gamma positive, then the two-
sided Eulerian polynomial of
$\mathcal{A}[\mathcal{B}_{1},\ldots,\mathcal{B}_{k}]$ is also gamma positive.

We proceed to the proof of Theorem 6.5.

###### Proof of Theorem 6.5.

Use induction on $n$. For $n=1$ and $n=4$ we have $A_{W_{1}}(s,t)=1$ and
$A_{W_{4}}(s,t)=(st)(s+t)$ which are gamma positive.

Let $n>4$ and assume that the polynomial $A_{W_{k}}(s,t)$ is gamma-positive
for every $k<n$. Note that $W_{n}=Simp_{n}\cup U_{n}$ where
$U_{n}=\bigcup\limits_{4\leq k\leq n-3\atop n_{1}+\cdots
n_{k}=n}Simp_{k}[W_{n_{1}}\ldots,W_{n_{k}}]$. Therefore, the two-sided
Eulerian polynomial of $W_{n}$ is the sum of the two-sided Eulerian polynomial
of $Simp_{n}$ and the two-sided Eulerian polynomials of
$Simp_{k}[W_{n_{1}}\ldots,W_{n_{k}}]$. By Conjecture 6.4, the induction
hypothesis, and Observation 6.9, these polynomials are gamma-positive and we
are done.

∎

##  7\. Asymptotics- an open question and a conjecture

One might use Equation (1) to obtain an upper bound for the proportion of the
number of blockwise simple permutations to the magnitude of the entire set of
permutations. Thus, we write for each $n\in\mathbb{N}$, $A_{n}=W_{n}-Simp_{n}$
and we are interested in the asymptotic behavior of
$R_{n}=\frac{|A_{n}|}{|S_{n}|}$. Experimental checks show that this ratio
tends to zero when $n$ tends to infinity as can be seen in the following
table. Actually, we have corroborating data up to $n=23$.

$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
---|---|---|---|---|---|---|---|---|---|---|---|---
$R_{n}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0.0031746 | 0.00267857 | 0.00303131 | 0.0029343 | 0.00273389 | 0.00247482

so we have the following conjecture:

######  Conjecture 7.1.

The proportion $R_{n}$ tends to $0$ when $n$ tends to infinity.

## Acknowledgments

The authors want to thank Ruth Hoffman and her team for helping us in the use
of their software that contributed a lot to the expermiental side of this
work.

## References

  * [1] R. Adin, E. Bagno, E. Eisenberg, S. Reches, M. Sigron , On Two-Sided Gamma-Positivity for Simple Permutations, The Electronic Journal of Combinatorics. Volume 25 Issue 2, 2018.
  * [2] T. K. Petersen, Eulerian numbers, Birkhauser, Basel, 2015.
  * [3] M. H. Albert, M. D. Atkinson and M. Klazar, The enumeration of simple permutations, J. Integer Sequences 6, Article 03.4.4, 2003.
  * [4] P. Brändén, Actions on permutations and unimodality of descent polynomials, European J. Combin. 29, 514–531, 2008.
  * [5] L. Carlitz, D. P. Roselle and R. A. Scoville, Permutations and sequences with repetitions by number of increases, J. Combinat. Theory 1, 350–374, 1966.
  * [6] Z. Lin, Proof of Gessel’s $\gamma$-positivity conjecture, Electronic J. Combinat. 23, #P3.15. 2016.
  * [7] T. K. Petersen, Eulerian numbers, Birkhauser, Basel, 2015.
  * [8] D. Zeilberger, A one-line high school proof of the unimodality of the Gaussian polynomials $\binom{n}{k}_{q}$ for $k<20$, in: D. Stanton (Ed.), $q$-Series and Partitions, Minneapolis, MN, 67-72, 1988.
  * [9] M. H. Albert and M. D. Atkinson. Simple permutations and pattern restricted permuta- tions. Discrete Math., 300:115, 2005.
  * [10] M. H. Albert, M. D. Atkinson and M. Klazar,The enumeration of simple permutations,Journal of Integer Sequences, Vol. 6 ,Article 03.4.4, 2003.
  * [11] M. Bouvel, L. Cionl and B. Izart ,The interval posets of permutations seen from the decomposition tree perspective
  * [12] L. Carlitz, D. P. Roselle and R. A. Scoville, Permutations and sequences with repetitions by number of increases, J. Combinat. Theory 1, 350–374, 1966.
  * [13] P. Flajolet and R. Sedgewick, Analytic Combinatorics. Cambridge University Press, 2008.
  * [14] R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.
  * [15] Tenner, B.E. Interval Posets of Permutations. Order. https://doi.org/10.1007/s11083-021-09576-1, 2022.
  * [16] Sloane, N. J. A., Sequence A054514.
  * [17] Sloane, N. J. A., Sequence A054515.