In this paper, we introduce the concept of the Over-inversion number, which counts the overlined permutations of length \(n\) with \(k\) inversions, allowing the first elements associated with the inversions to be independently overlined or not. We explore its properties and combinatorial interpretations through lattice paths, overpartitions, and tilings, and provide a combinatorial proof demonstrating that these numbers form a log-concave and unimodal sequence.
A permutation \(\pi=\left( \begin{array}{ccc} 1 & \cdots & n \\ \pi(1) & \cdots & \pi(n) \\ \end{array}\right)\) is an arrangement or reordering of a set of elements. For additional information on the permutations, refer to [3,21].
In mathematics, permutation statistics are functions that assign numerical values to permutations, often capturing combinatorial or algebraic properties. Some of the most studied statistics include:
Inversion: A pair of elements \((i,j)\) such that \(i<j\) but \(\pi(i)>\pi(j)\). This measures how “out of order” a permutation is.
Descent: An index \(i\) such that \(\pi(i)>\pi(i+1)\). A descent represents a local drop in the value sequence of the permutation.
Major index: The sum of all descent positions. For a permutation \(\pi\), it is defined as \[maj(\pi)=\sum_{i \text{\ is a descent}}i.\]
Fixed points: The number of indices \(i\) such that \(\pi(i)=i\).
Cycle structure: Permutations can be decomposed into disjoint cycles. The number and lengths of these cycles are key permutation statistics, with implications in algebra and combinatorics.
Excedance: An index \(i\) such that \(\pi(i)>i\).
These statistics have significant applications in algebra, geometry, and computer science, especially in studying the symmetric group \(S_n\), which consists of all permutations of a set with \(n\) elements.
The enumeration of permutations of length \(n\) by their number of inversions, along with the study of \(i(n,k)\), of permutations of length \(n\) with \(k\) inversions, is a foundational topic in combinatorics. The most famous result is given by the following equation [19]: \[\label{giv} \sum_{k=0}^{\binom{n}{2}}i(n,k)x^k=(1+x)\cdots(1+x+\cdots+x^{n-1}), \tag{1}\] where \(i(n,k)\) represents the Mahonian number. MacMahon [18] established that this number corresponds to the count of permutations of length \(n\) with a major index of \(k\).
Mahonian numbers can be extended to other finite reflection groups beyond the symmetric group. For example:
Coxeter groups: Permutations in these groups can have statistics analogous to inversions or major indices.
Signed permutations: In type \(B\) (also called hyperoctahedral group \(B_n\)) and type \(D\) Coxeter groups, corresponding Mahonian statistics are defined.
For a detailed exploration of the combinatorics of the final groups, we direct readers to Björner and Brenti’s book [2].
The recent generalization of Mahonian numbers through generalized symmetric groups has sparked significant interest among researchers specializing in combinatorics. This generalization is rooted in both classical and contemporary permutation statistics. For instance, the Mahonian numbers of type \(B\) extend the classical Mahonian numbers, which are associated with the symmetric group \(S_n\), to the hyperoctahedral group \(B_n\) using inversions of type \(B\): inversions that include both pairs and signs. The group \(B_n\) consists of signed permutations of \(n\) elements, where each element can independently be positive or negative. For more details about the Mahonian numbers of type \(B\), see [12,17].
If we consider overlined permutations, where each element can independently be overlined or not, rather than signed permutations, we remain entirely within the hyperoctahedral group \(B_n\). The hyperoctahedral groups have been extensively studied, as evidenced by works such as [5,8,13,16,15,24].
In our paper, we aim to introduce the concept of an overlined permutation \(\sigma\) of \(n\) elements, where the first elements associated with the inversions can be independently overlined or no. In such a permutation, each element \(\sigma(i)\), for \(1\leq i\leq n-1\), can independently be overlined or not, subject to the condition that there exists an index \(j>i\) such that \(\sigma(i)>\sigma(j)\). These permutations form a subgroup of the hyperoctahedral group \(B_n\), which we denote by \(B'_n\). We focus on counting such permutations with exactly \(k\) inversions, denoted by \(i_{B'}(n, k)\), and refer to these counts as Over-inversion numbers. Furthermore, we study their combinatorial interpretations, identities, and provide combinatorial proofs of their log-concavity and unimodality.
The paper is structured into four sections. In Section 2, we define the Over-inversion numbers as the counts of overlined permutations of length \(n\) with \(k\) inversions, where the first elements associated with the inversions can be independently overlined or not, within the hyperoctahedral group \(B_n\), and provide a combinatorial proof of several recurrence relations and identities associated with these numbers. We also present their generating function and derive a key identity involving the double factorial. Section 3 offers combinatorial interpretations of the Over-inversion numbers through lattice paths, overpartitions, and tilings. In Section 4, we prove combinatorially that these numbers form a log-concave and thus unimodal sequence, using an appropriate injection. Finally, in the fourth section, we pose a question regarding the number and positions of the modes in the sequence of Over-inversion numbers.
Let \([n]\) denote the set \(\{1,2,\ldots,n\}\), and let \(\sigma=\sigma_1\sigma_2\cdots\sigma_n\) represents a permutation of \([n]\) of length \(n\). The set of all such permutations forms the symmetric group \(S_n\), whose identity element is the permutation \(\iota=\iota_1\iota_2\cdots\iota_n\), defined by \(\iota_i=i\) for all \(1\leq i\leq n\).
Definition 2.1. The backward permutation of \(\sigma\) is the permutation \(\sigma'\) defined by \(\sigma'_i=\sigma_{n+1-i}\) for all \(1\leq i\leq n\).
Remark 2.2. The only permutation with no inversion is the identity permutation \(\iota\), while the permutation of length \(n\) with the maximum number of inversions is \(\alpha=\alpha_1\alpha_2\cdots\alpha_n\), where \(\alpha_i=n+1-i\), which has \(\binom{n}{2}\) inversions; furthermore, a permutation and its inverse have the same number of inversions.
Definition 2.3. A pair \((\sigma_i,\sigma_j)\) is termed a backward inversion of the permutation \(\sigma\) if \(i<j\) and \(\sigma_i<\sigma_j\).
Remark 2.4. For a permutation of length \(n\) with \(k\) inversions, the number of backward inversions is given by \(\binom{n}{2}-k\) [14].
Consider the set of \(2n\) symbols \[\Sigma_{2,n}:=\left\{1,\ldots,n,\overline{1},\ldots,\overline{n}\right\}.\]
An element denoted as \(\overline{i}\) is referred to as an overlined element. An overlined permutation \(\pi\) is a permutation defined on the set \(\Sigma_{2,n}\) that satisfies the property \(\pi(\overline{a}) = \overline{\pi(a)}\) for all \(a \in \Sigma_{2,n}\). For instance, the following is an example of an overlined permutation of \(\Sigma_{2,4}\): \[\pi=\left( \begin{array}{cccc} 1 & 2 & 3 & 4\\ \overline{4} & \overline{2} & 3& 1\\ \end{array}\right).\]
By omitting the first row, we obtain the one-line notation \(\overline{4}\text{\ }\overline{2}3 1\). Let \(G_{2,n}\) denote the group of all overlined permutations of \(\Sigma_{2,n}\). This group, \(G_{2,n}\), corresponds to the hyperoctahedral group \(B_n\), also known as the Coxeter group of type \(B\), and has cardinality \(|G_{2,n}| = 2^n n!\). In algebraic combinatorics, \(G_{2,n}\) is identified as the wreath product \(C_2 \wr S_n\), combining the symmetric group on \([n]\) with the cyclic group \(C_2\) on \(\{0,1\}\). However, the group structure of \(G_{2,n}\) is not directly relevant to this work.
To state our results, we define a subset \(B'_n\subset G_{2,n}\) of the group of overlined permutations \(G_{2,n}\) by imposing specific restrictions on the elements. Specifically, \(B'_n\) consists of all overlined permutations in which the first elements associated with inversions can independently be overlined or not. We then enumerate the elements of \(B'_n\) while accounting for the number of inversions. For example, the overlined permutations of \(B'_3\) are \[123,132, 1\overline{3}2,213,\overline{2}13,231,\overline{2}31,2\overline{3}1,\overline{2}\text{\ }\overline{3}1,312,\overline{3}12,321,\overline{3}21,3\overline{2}1,\overline{3}\text{\ }\overline{2}1.\]
A permutation \(\sigma\) on \(S_n\) is an involution if \(\sigma^2(i)=i\) for all \(i=1,\ldots,n\), and it is fixed-point-free if no element is mapped to itself, meaning \(\sigma(i)\neq i\) for all \(i\). Thus, the cardinality \(|B'_n|\) is equal to the number of fixed-point-free involutions in the symmetric group \(S_{2n}\). \(|B'_n|\) is equal also to the number of permutations in the symmetric group \(S_{2n}\) whose cycle decomposition is a product of \(n\) disjoint transpositions.
Based on the definition of \(B'_n\), in the next, we introduce the concept of Over-inversion numbers along with their fundamental properties.
Definition 2.5. Let \(i_{B'}(n,k)\) represent the number of overlined permutations in \(B'_n\) of length \(n\) that contain exactly \(k\) inversions. We refer to this quantity as the Over-inversion number.
Example 2.6. Consider the overlined permutations of \(B'_3\) with 2 inversions: \[312, \mathbf{\overline{3}}12, 231, \mathbf{\overline{2}}31, 2\mathbf{\overline{3}}1, \mathbf{\overline{2}}\hspace{0.05cm}\mathbf{\overline{3}}1.\]
Therefore, \(i_{B'}(3,2)=6\).
From Definition 2.5, we can derive the recurrence relation for the Over-inversion number \(i_{B'}(n,k)\) as follows:
Theorem 2.7. For positive integers \(n\) and \(k\), the Over-inversion number satisfies the recurrence relation \[\label{eq1} i_{B'}(n,k) = i_{B'}(n-1,k) + 2 \sum_{j=1}^{n-1} i_{B'}(n-1,k-j), \tag{2}\] with the initial conditions \(i_{B'}(n,0) = 1\) and \(i_{B'}(n,k) = 0\) unless \(0 \leq k \leq \binom{n}{2}\).
Proof. We prove this theorem combinatorially using the inversion combinatorial interpretation given in Definition 2.5.
Consider a permutation \(\sigma=\sigma_1\cdots \sigma_n\) of length \(n\) with \(k\) overlined inversions. Removing the first element \(\sigma_1\) form \(\sigma\) results in either:
a) A permutation of length \(n-1\) with \(k\) overlined inversions, if \(\sigma_1\) does not form an overlined inversion with any other element. This corresponds to \(i_{B'}(n-1,k\), or
b) A permutation of length \(n-1\) with \(k-j\) overlined inversions, if \(\sigma_1\) either forms \(j\) overlined inversions (where \(1\leq j\leq n-1\)) with other elements or is itself overlined and forms \(j\) overlined inversions with the others. In both cases, the corresponding interpretation is \(i_{B'}(n-1,k-j)\).
Summing these possibilities yields \(2 \sum_{j=1}^{n-1}i_{B'}(n-1,k-j)\), which leads to the equality (2). ◻
From Theorem 2.7, we derive the following recurrence relation for the Over-inversion numbers \(i_{B'}(n,k)\):
Proposition 2.8. For \(0\leq k \leq \binom{n}{2}\), the Over-inversion numbers satisfy the recurrence \[\label{rcc} i_{B'}(n,k)=i_{B'}(n,k-1)+i_{B'}(n-1,k)+i_{B'}(n-1,k-1)-2i_{B'}(n-1,k-n). \tag{3}\]
Proof. From relation (2), we have the following expressions: \[\label{eq11} i_{B'}(n,k)=i_{B'}(n-1,k)+2i_{B'}(n-1,k-1)+\cdots +2i_{B'}(n-1,k-n+1), \tag{4}\] and \[\label{eq12} i_{B'}(n,k-1)=i_{B'}(n-1,k-1)+2i_{B'}(n-1,k-2)+\cdots +2i_{B'}(n-1,k-n). \tag{5}\]
Using relation (5), we substitute into the equation for \(i_{B'}(n,k)\) : \[\begin{aligned} i_{B'}(n,k) &= i_{B'}(n-1,k) + i_{B'}(n-1,k-1) + [i_{B'}(n-1,k-1) + 2 i_{B'}(n-1,k-2) \\ &\quad +\cdots + 2 i_{B'}(n-1,k-n)]- 2 i_{B'}(n-1,k-n), \\ &= i_{B'}(n-1,k) + i_{B'}(n-1,k-1) + i_{B'}(n,k-1) – 2 i_{B'}(n-1,k-n), \\ &= i_{B'}(n-1,k) + i_{B'}(n-1,k) + i_{B'}(n-1,k-1) – 2 i_{B'}(n-1,k-n). \end{aligned}\]
This completes the proof. ◻
Based on Definition 2.5, we can also derive the following identities.
Proposition 2.9. For any integer \(n\geq 1\), the following hold:
a) \(i_{B'}(n,\binom{n}{2})=2^{n-1}\),
b) \(i_{B'}(n,1)=2\times(n-1)\),
c) \(i_{B'}(n,k)\) is even for \(n\geq 2\) and \(k\geq 1\).
Proof. a) The expression \(i_{B'}(n,\binom{n}{2})\) counts the number of permutations of length \(n\) that have \(\binom{n}{2}\) overlined inversions. This implies that the permutation is in the form \(\sigma_1 > \sigma_2 > \cdots > \sigma_{n-1} > \sigma_n\), where the entries \(\sigma_1, \ldots, \sigma_{n-1}\) may or may not be overlined. Thus, there are \(2^{n-1}\) possible permutations.
b) The expression \(i_{B'}(n,1)\) counts the number of permutations of length \(n\) that have exactly one overlined inversion. This corresponds to a permutation in the form \(\sigma_1 < \sigma_2 < \cdots < \sigma_j > \sigma_{j+1} < \cdots < \sigma_n\), where \(\sigma_j\) may or may not be overlined, for each \(1 \leq j \leq (n-1)\). Therefore, there are \(2 \times (n-1)\) possible permutations.
c) For \(n \geq 2\) and \(k \geq 1\), we can have overlined inversions. For each inversion \((\sigma_i, \sigma_j)\), there are two possibilities: either \(\sigma_i\) is overlined or it is not. Consequently, the total number of permutations of length \(n\) with exactly \(k\) overlined inversions is even. ◻
The Over-inversion numbers \(i_{B'}(n,k)\) satisfy the following row-generating function:
Theorem 2.10. For any positive integer \(n\), \[\sum_{k=0}^{\binom{n}{2}}i_{B'}(n,k)z^{k}=% \begin{cases} 1, & \text{if \ \ } n=1, \\ (1+2z)\cdots(1+2z+\cdots+2z^{n-1}), & \text{if \ \ }n>1.% \end{cases}%\]
Proof. Let \(f_{n}(z)=\sum_{k=0}^{\binom{n}{2}}i_{B'}(n,k)z^{k}\) be the row generating function of the Over-inversion number.
For \(n=1\), the result is trivial. For \(n\geq 2\), using equation (2), we have \[\begin{aligned} f_{n}(z) & =\sum_{k=0}^{\binom{n}{2}}i_{B'}(n,k)z^{k}= \sum_{k=0}^{\binom{n}{2}}\left( i_{B'}(n-1,k)+2\sum_{j=1} ^{n-1}i_{B'}(n-1,k-j)\right) z^{k}. \end{aligned}\]
This expands to \[\begin{aligned} f_{n}(z) & = \sum_{k=0}^{\binom{n}{2}}i_{B'}(n-1,k)z^{k}+2\sum_{k=0}^{\binom{n}{2}}\sum_{j=1}^{n-1}i_{B'}(n-1,k-j) z^{k}. \end{aligned}\]
The first term is simply \(f_{n-1}(z)\), and the second term can be written as \[\begin{aligned} 2\sum_{j=1}^{n-1}z^{j}\sum_{k=j} ^{\binom{n}{2}-j}i_{B'}(n-1,k-j)z^{k-j}&=2\sum_{j=1}^{n-1}z^{j}\sum_{k=0}^{\binom{n-1}{2}}i_{B'}(n-1,k)z^{k}. \end{aligned}\]
Thus, we have \[\begin{aligned} f_{n}(z)&= f_{n-1}(z)\left(1+2\sum_{j=1}^{n-1}z^j\right). \end{aligned}\]
Iterating this process, we obtain the final result: \[f_{n}(z)=(1+2z)\cdots(1+2z+\cdots+2z^{n-1}).\] ◻
By setting \(z=1\) in Theorem 2.10, we obtain the following interesting result:
Corollary 2.11. For any positive integer \(n\), the Over-inversion numbers satisfy the identity: \[|B'_n|=\sum_{k=0}^{\binom{n}{2}} i_{B'}(n,k) = (2n-1)!!,\] where \((2n-1)!!=1\times 3 \times\cdots \times (2n-1)\).
Consider the set of \(2n-1\) symbols \[\Sigma'_{2,n}:=\left\{1,2,\overline{2},\ldots,n,\overline{n}\right\}.\]
Let \(C_j=\{\sigma \in B'_n: \sigma(1)=j\}\) for \(j\in \Sigma'_{2,n}\). It is clear that \[\label{tmr} |C_j|=(2n-3)!!, \tag{6}\] with \(|C_1|=1\) when \(n=1\).
The set \(C_j\) gives the decomposition \[B'_n=\biguplus_{j\in \Sigma'_{2,n}}C_j.\]
Therefore, we have \[\label{bnn} \mathcal{B}'_n=\sum_{\omega\in B'_n}inv(\omega)=\sum_{j\in \Sigma'_{2,n}}\sum_{\sigma \in C_j}inv(\sigma), \tag{7}\] where \(\mathcal{B}'_n\) represents the total number of inversions of all overlined permutations in \(B'_n\).
Let \(\pi=\left( \begin{array}{cccc} 1 &2&\cdots & n \\ j &\pi(2) &\cdots & \pi(n)\\ \end{array}\right)\in C_j\) and \(\tau\) be is an overlined permutation in \(B'_{n-1}\) defined by \[\tau=\left( \begin{array}{ccc} a_1 & \cdots & a_{n-1} \\ \pi(2) & \cdots & \pi(n) \\ \end{array}\right)\in B'\left([n]\backslash\{|j|\}\right),\] where \(a_1,\ldots,a_{n-1}\) are an arrangement of elements of \([n]\backslash\{|j|\}\) in increasing order, and \(B'\left([n]\backslash\{|j|\}\right)\) is the group of all the overlined permutation of the set \([n]\backslash\{|j|\}\). So, if we set
\[\pi_{\tau,j}=\left( \begin{array}{cccc} 1 &2 &\cdots& n\\ j &\tau(a_1) & \cdots & \tau(a_{n-1}) \\ \end{array} \right),\] then we obtain \(\pi=\pi_{\tau,j}\). Hence by the definition of the statistic of the classical inversion, we conclude \[\label{eqt} inv(\pi)=(j-1)+inv(\tau). \tag{8}\]
Eq. (8) give us a recursive formula for \(\mathcal{B}'_n\) and we state it as a proposition.
Proposition 2.12. We have \(\mathcal{B}'_1=0\), and \[\label{eip} \mathcal{B}'_n=(2n-3)!!n(n-1)+(2n-1)\mathcal{B}'_{n-1}, \text{\ for\ }n\geq 2. \tag{9}\]
Proof. Since \(B'_1=\{\iota\}\), then \(\mathcal{B}'_1=inv(\iota)=0\). Now suppose \(n\geq 2\). We have two cases:
Case 1. For \(j=1\), we obtain \[\begin{aligned} \sum_{\pi\in C_j}inv(\pi)&=\sum_{\tau\in B'\left([n]\backslash\{|j|\}\right)}inv(\pi_{\tau,j})\\ &=\sum_{\tau\in B'\left([n]\backslash\{|j|\}\right)}inv(\tau)\\ &=\mathcal{B}'_{n-1}. \end{aligned}\]
Case 2. For \(j\in \Sigma'_{2,n}\backslash \{1\}\). From Eq. (6), we obtain \[\begin{aligned} \sum_{\pi\in C_j}inv(\pi)&=\sum_{\tau\in B'\left([n]\backslash\{|j|\}\right)}inv(\pi_{\tau,j})\\ &=\sum_{\tau\in B'\left([n]\backslash\{|j|\}\right)}[(j-1)+inv(\tau)]\\ &=(j-1)(2n-3)!!+\mathcal{B}'_{n-1}. \end{aligned}\]
From Eq. (7), we get \[\begin{aligned} \mathcal{B}'_{n}&=\mathcal{B}'_{n-1}+2\sum_{j=2}^{n}\left[(j-1)(2n-3)!!+\mathcal{B}'_{n-1}\right]\\ &=2(2n-3)!!\sum_{j=2}^{n}(j-1)+(2n-1)\mathcal{B}'_{n-1}\\ &=(2n-3)!!n(n-1)+(2n-1)\mathcal{B}'_{n-1}, \end{aligned}\] as desired. ◻
Note that \(\mathcal{B}'_{n}=\sum_{k=0}^{\binom{n}{2}}inv_B'(n,k)k\). The numbers \(i_{B'}(n,k)\) form a triangle known as the “Over-inversion triangle“, as shown in Table 1.
\(\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n\backslash k & \mathcal{B}'_{n} &\ \ 0 \ \ & \ \ 1 \ \ & \ \ 2 \ \ & \ \ 3 \ \ & \ \ 4 \ \ & \ \ 5 \ \ & \ \ 6 \ \ & \ \ 7 \ \ & \ \ 8 \ \ & \ \ 9 \ \ & \ \ 10 \\ \hline 1 & 0 & 1 & & & & & & & & & & \\ \hline 2 & 2 & 1 & 2 & & & & & & & & & \\ \hline 3 & 28 & 1 & 4 & 6 & 4 & & & & & & & \\ \hline 4 & 376 & 1 & 6 & 16 & 26 & 28 & 20 & 8 & & & & \\\hline 5 & 5484 & 1 & 8 & 30 & 72 & 126 & 172 & 188 & 164 & 112 & 56 & 16 \\ \hline \end{array}\)
In this section, we provide combinatorial interpretations of the Over-inversion numbers through lattice paths, overpartitions, and tilings.
Ghemit and Ahmia in [11] demonstrated that the Mahonian number \(i(n,k)\) counts the number of lattice paths from \(u_{1}=(0,0)\) to \(v_{1}=(n-1,k)\) that take at most \(j\) North steps at the level \(j\).
Following a similar approach, we provide a combinatorial interpretation for the Over-inversion numbers \(i_{B'}(n,k)\) using lattice paths.
Let \(\mathcal{P}^{B'}_{n,k}\) represent the set of lattice paths from the point \((0,0)\) to \((n-1,k)\), using only North steps (vertical steps \((0,1)\)), East steps (horizontal steps \((1,0)\)), and North-East steps (diagonal steps \((1,1)\)). These paths must satisfy the condition that, for each vertical level \(j\), the number of North steps is at most \(j\) unless a diagonal step occurs before level \(j\), in which case the number of North steps is restricted to at most \(j-1\) after the diagonal step. The levels correspond to the vertical lines ranging from \(0\) to \(n-1\), as illustrated in Figure 1.
Theorem 3.1. The Over-inversion number \(i_{B'}(n,k)\) represents the count of lattice paths from \(u_{1}=(0,0)\) to \(v_{1}=(n-1,k)\), where the path takes at most \(j\) North steps at level \(j\) before any diagonal step, and at most \((j-1)\) North steps at level \(j\) after a diagonal step. Specifically, we have \[i_{B'}(n,k)= \mid \mathcal{P}^{B'}_{n,k} \mid.\]
Proof. Since \(i_{B'}(n,k)\) counts the number of permutations of length \(n\) with exactly \(k\) overlined inversions, it suffices to show a bijection between these permutations and the lattice paths in \(\mathcal{P}^{B'}_{n,k}\). We do so as follows:
For each path \(P\in \mathcal{P}^{B'}_{n,k}\), we can uniquely determine the associated permutation. This is done by assigning the entry \(1\) to the point \((0,0)\), and then following the steps of the path. The first step must be either an East step or a North-East step. If the step is East, we move to the point \((1,0)\) and place the entry \(2\) to the right of \(1\) (resulting in the partial permutation \(12\)). If the step is North-East, we move to \((1,1)\) and place the entry \(\overline{2}\) to the left of \(1\), yielding the partial permutation \(\overline{2}1\), which introduces an inversion.
At the point \((1,0)\), there are three possible cases for the next step of \(P\):
If the next step is East, we add the entry \(3\) to the right of \(2\), resulting in the partial permutation \(123\).
If the next step is North-East, we add the entry \(\overline{3}\) to the right of \(2\) and shift \(\overline{3}\) one position to the left, producing the permutation \(1\overline{3}2\), which introduces another inversion.
If the next step is North, we shift the entry \(2\) one position to the left, yielding the permutation \(21\), which also introduces an inversion.
At the point \((1,1)\), there are two possible cases for the next step:
If the next step is East, we add the entry \(3\) to the right of \(1\), producing the permutation \(\overline{2}13\).
If the next step is North-East, we add \(\overline{3}\) to the right of \(1\) and shift \(\overline{3}\) one position to the left, resulting in the permutation \(\overline{2}\hspace{0.05cm}\overline{3}1\) which introduces an inversion.
We continue applying these rules at each step of the path until we reach the point \((n-1,k)\), which gives us the desired permutation. An example of this process is shown in Figure 2. ◻
This subsection explores combinatorial interpretations of the Over-inversion numbers using overpartitions.
We begin with two fundamental definitions:
Definition 3.2. A partition \(\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_k)\) of a number \(n\) is defined as a non-increasing sequence of positive integers, i.e., \(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k\), where the sum of the sequence equals \(n\). The function \(p(n)\) represents the number of such partitions of \(n\), with the convention that \(p(0) = 1\).
For \(1 \leq i \leq k\), \(\lambda_i\) is referred to as a part of \(\lambda\). While partitions typically consist of positive integers, we may sometimes allow “zero” as a part for specific purposes.
The length of \(\lambda\), denoted by \(l(\lambda)\), is the number of parts in \(\lambda\), and the weight of \(\lambda\), denoted by \(|\lambda|\), is the total sum of its parts.
Definition 3.3. [9, Corteel and Lovejoy] An overpartition of \(n\) is a non-increasing sequence of natural numbers whose sum is \(n\), where the first occurrence (or the last occurrence) of any number may be overlined. The function \(\overline{p}(n)\) represents the number of overpartitions of \(n\), with the convention that \(\overline{p}(0) = 1\).
For example, there are \(8\) overpartitions of \(3\), enumerated as follows: \[3,\overline{3},2+1,\overline{2}+1,2+\overline{1},\overline{2}+\overline{1},1+1+1,\overline{1}+1+1.\]
Since the bijection between lattice paths and tilings preserves weight, we derive the following interpretation of the Over-inversion numbers in terms of overpartitions:
Theorem 3.4. The Over-inversion number \(i_{B'}(n,k)\) represents the count of overpartitions into \(k\) parts, where each part \(j\) can appear at most \(j\) times if it is not overlined, and at most \(j-1\) times if it is overlined. Additionally, the largest part must satisfy \(\leq n-1\).
Proof. The term \(i_{B'}(n,k)\) represents the count of lattice paths from \((0,0)\) to \((n-1,k)\), where the paths adhere to specific rules: at most \(j\) North steps are allowed at level \(j\) if no diagonal step occurs beforehand, and at most \(j-1\) North steps are permitted at level \(j\) if a diagonal step has occurred. If we interpret the parts (resp. the overlined parts) as representing the cases above each North step (resp. North-East step) in the paths associated with \(i_{B'}(n,k)\), we can deduce a direct connection to overpartitions. Specifically, \(i_{B'}(n,k)\) enumerates the number of overpartitions of \(k\) into parts where each part \(j\) can appear at most \(j\) times if it is not overlined and at most \(j-1\) times if it is overlined, with the additional condition that the largest part must be at most \(n-1\). ◻
For instance, Figure 3 illustrates the \(16\) overpartitions with \(k=2\) parts, where the largest part is \(n-1=3\).
Ghemit and Ahmia [10] demonstrated that the Mahonian number \(i(n,k)\) represents the number of ways to tile a board of length \(n+k-1\) using \(k\) red squares and \(n-1\) blue squares, subject to the condition that no more than \(j\) consecutive red squares appear if preceded by \(j\) blue squares. Building on their findings, this subsection provides a combinatorial interpretation of the Over-inversion numbers using the same combinatorial structures.
Let \(\mathcal{T}^{B'}_{n,k}\) denote the set of all tilings of a board of length \((n+k-1)\) that satisfy the following conditions:
The tiling uses at most \(n-1\) blue squares, at most \(k\) red squares, and black rectangles (each covering an area of two squares, referred to as square pairs).
The number of consecutive red squares does not exceed \(j\) if preceded by \(j\) blue squares, and does not exceed \(j-1\) if preceded by a black rectangle.
The total number of red squares and black rectangles is exactly \(k\).
The total number of blue squares and black rectangles is exactly \(n-1\).
Each black rectangle is treated as equivalent to one blue square followed by one red square in that order.
Remark 3.5. There exists a bijection between the sets \(\mathcal{P}^{B'}_{n,k}\) and \(\mathcal{T}^{B'}_{n,k}\). Specifically, each East step corresponds to a blue square, each North step corresponds to a red square, and each diagonal step corresponds to a black rectangle. This correspondence is illustrated in Figure 4.
Based on this observation, we can derive the following tiling interpretation for the Over-inversion numbers:
Corollary 3.6. The Over-inversion number \(i_{B'}(n,k)\) is precisely the cardinality of the set \(\mathcal{T}^{B'}_{n,k}\). In other words, \(i_{B'}(n,k)=\mid\mathcal{T}^{B'}_{n,k}\mid.\)
Example 3.7. For \(n=3\) and \(k=2\), the \(i_{B'}(3,2)\) tilings consist of \(2\) blue squares, \(2\) red squares, and a black rectangle, as illustrated in Figure 5.
Log-concave and unimodal sequences frequently appear in combinatorics, geometry, and algebra. For a comprehensive overview of the various techniques used to study sequences and polynomials that are log-concave or unimodal, the reader is referred to [7,22].
A sequence of nonnegative numbers \(\lbrace x_{k}\rbrace_{k}\) is said to be log-concave if it satisfies the inequality \(x_{i-1}x_{i+1}\leq x_{i}^{2}\) for all \(i>0\), . This condition is equivalent to the following for relevant results (see [6,22]): \[x_{i-1}x_{j+1}\leq x_{i}x_{j}\hspace{0.5cm} for \hspace{0.5cm} j\geq i\geq1.\]
A finite sequence of real numbers \(a_{0},\ldots,a_{m}\) is called unimodal if there exists an index \(0\leq m^{*}\leq m\), known as the mode of the sequence, such that the sequence first increases up to \(k=m^{*}\) and then decreases thereafter. Specifically, the sequence satisfies \(a_{0}\leq a_{1}\leq \cdots\leq a_{m^{*}}\) and \(a_{m^{*}}\geq a_{m^{*}+1}\geq \cdots \geq a_{m}\). It is clear that any log-concave sequence is unimodal [6].
A polynomial is called log-concave (resp. unimodal) if its coefficients form a log-concave (resp. unimodal) sequence. Notably, Gaussian polynomials and \(q\)-multinomial coefficients are well-known examples of unimodal sequences, as established in [23, Theorem 3.11]. Additionally, it is a classic result, with proofs available in works such as [3], that the product of log-concave (resp. unimodal) polynomials remains log-concave (resp. unimodal). For instance, the polynomial \(\sum_{k=0}^{\binom{n}{2}}i(n,k)x^k\) is log-concave (resp. unimodal), meaning the sequence \(i(n,0), \ldots, i(n,\binom{n}{2})\) is log-concave (resp. unimodal).
Bóna [4] provided the first non-generating function proof of the log-concavity of the Mahonian numbers \(i(n,k)\) in \(k\), using an injection property and an induction hypothesis over n, although the injection was non-constructive. To address this, Ghemit and Ahmia [10] offered a constructive proof that replaces Bóna’s non-constructive injection.
The proof of the log-concavity (or unimodality) of the Over-inversion numbers \(\{i_{B'}(n,k)\}_{k}\) in \(k\) can be easily derived from Theorem 2.10, since the generating function \(\sum_{k=0}^{\binom{n}{2}}i_{B'}(n,k) x^k\) is the product of log-concave (or unimodal) polynomials. However, in this section, motivated by the work of Ghemit and Ahmia [10], we provide a new approach to demonstrate that the sequence of Over-inversion numbers \(\{i_{B'}(n,k)\}_{k}\) s log-concave in \(k\), and therefore unimodal, by constructing an appropriate injection.
We begin by introducing the following key definition.
Definition 4.1. Let \(\sigma\) be a permutation of length \(n\). For \(0\leq i\leq n-1\), let \(m_{i}^{\sigma}\) denote the number of times the entry \(i + 1\) appears as the first element of an overlined inversion of \(\sigma\). The total number of overlined inversions of \(\sigma\) is then given by \(\sum_{i=0}^{n-1}m_{i}^{\sigma}\).
Based on this definition, we can derive the following result regarding the log-concavity of Over-inversion numbers:
Theorem 4.2. The sequence of Over-inversion numbers \(\{i_{B'}(n,k)\}_{k}\) is log-concave in \(k\). Specifically, we have the inequality: \[\left( i_{B'}(n,k)\right) ^{2}-i_{B'}(n,k-1)i_{B'}(n,k+1)\geq0,\] for all \(0<k\leq\binom{n}{2}\).
Proof. Let \(I_{B'}(n,k)\) denote the set of permutations of length \(n\) with \(k\) overlined inversions, and let \(i_{B'}(n,k)=|I_{B'}(n,k)|\) represent the number of such permutations.
To prove the log-concavity of the sequence of Over-inversion numbers \({_{B'}(n,k)}_{k}\), it is equivalent to find an injection \(f_{n,k,k}\) from \(I_{B'}(n,k+1)\times I_{B'}(n,k-1)\) to \(I_{B'}(n,k)\times I_{B'}(n,k)\), where \(f_{n,k,k}(\sigma,\tau)=(\theta,\pi)\) with \((\sigma,\tau)\in I_{B'}(n,k+1)\times I_{B'}(n,k-1)\) and \((\theta,\pi)\in I_{B'}(n,k)\times I_{B'}(n,k)\).
Let \((\sigma,\tau) \in I_{B'}(n,k+1) \times I_{B'}(n,k-1)\). We will define \(I\) as the largest integer which satisfies the following three conditions:
\[\begin{aligned} &\sum_{j\geq I}m^\sigma_{j}\geq \sum_{j\geq I+1}m^\tau_{j}+1,\text{ if the entry }(j+1)=(I+1) \text{ of the }\sigma\text{not overlined}, \end{aligned} \tag{10}\]\[\begin{aligned} &\sum_{j\geq I}m^\sigma_{j}> \sum_{j\geq I+1}m^\tau_{j}+1,\text{ if the entry }(j+1)=(I+1) \text{of the } \sigma\text{ is overlined},\label{cond2} \end{aligned} \tag{11}\] and \[\begin{aligned} &\sum_{j\geq I}m^\tau_{j}+1-\sum_{j\geq I+1}m^\sigma_{j}\leq I,\text{ if }\sum_{j\geq I}m^\sigma_{j}<\sum_{j\geq I}m^\tau_{j}+1.\label{cond3} \end{aligned} \tag{12}\]
Now, we define the map \(f_{n,k,k}\) as follows:
\[f_{n,k,k}(\sigma,\tau)=(\theta,\pi),\] where,
\(\theta\) is obtained by the following modifications on \(\tau\):
For the entry \((j+1)\), from \((I+2)\) to \(n\) in ascending order: if the entry \((j+1)\) from \(\sigma\) is overlined, then overlined the entry \((j+1)\) from \(\tau\), else not overlined the entry \((j+1)\) from \(\tau\).
For the entry \((j+1)\), from \(n\) to \((I+2)\) in decreasing order: the entry \(j+1\) moves \(m^\tau_j\) positions to the right and overlined, if the entry \(j+1\) is overlined. Else, the entry \(j+1\) only moves \(m^\tau_j\) positions to the right.
For the entry \(j+1=I+1\): the entry \(j+1\) moves \(\left(\sum_{i=1}^Im^\sigma_i-\sum_{i=1}^Im^\tau_i-1\right)\) positions to the left and overlined, if the entry \(j+1\) is overlined. Else, the entry \(j+1\) only moves \(\left(\sum_{i=1}^Im^\sigma_i-\sum_{i=1}^Im^\tau_i-1\right)\) positions to the left.
For the entry \((j+1)\), from \((I+2)\) to \(n\) in ascending order: the entry \(j+1\) moves \(m_j^\sigma\) positions to the left and overlined, if the entry \(j+1\) is overlined. Else, the entry \(j+1\) only moves \(m_j^\sigma\) positions to the left.
\(\pi\) is obtained by the following modifications on \(\sigma\):
For the entry \((j+1)\), from \((I+2)\) to \(n\) in ascending order: if the entry \((j+1)\) from \(\tau\) is overlined, then overlined the entry \((j+1)\) from \(\sigma\), else not overlined the entry \((j+1)\) from \(\sigma\).
For the entry \((j+1)\), from \(n\) to \((I+2)\) in decreasing order: the entry \(j+1\) moves \(m^\sigma_j\) positions to the right and overlined, if the entry \(j+1\) is overlined. Else, the entry \(j+1\) only moves \(m^\sigma_j\) positions to the right.
For the entry \(j+1=I+1\): the entry \(j+1\) moves \(\left(\sum_{i=1}^Im^\sigma_i-\sum_{i=1}^Im^\tau_i-1\right)\) positions to the right and overlined, if the entry \(j+1\) is overlined. Else, the entry \(j+1\) only moves \(\left(\sum_{i=1}^Im^\sigma_i-\sum_{i=1}^Im^\tau_i-1\right)\) positions to the right.
For the entry \((j+1)\), from \((I+2)\) to \(n\) in ascending order: the entry \(j+1\) moves \(m_j^\tau\) positions to the left and overlined, if the entry \(j+1\) is overlined. Else, the entry \(j+1\) only moves \(m_j^\tau\) positions to the left.
To prove that \(f_{n,k,k}\) is well defined we only need to check that: \[\begin{aligned} 0\leq \sum_{j=1}^Im^\sigma_j-\sum_{j=1}^Im_j^\tau-1\leq m^\sigma_I , \label{eq2} \end{aligned} \tag{13}\] and \[\begin{aligned} &m_I^\tau+\sum_{j=1}^Im^\sigma_j-\sum_{j=1}^Im_j^\tau-1\leq I.\label{eq3} \end{aligned} \tag{14}\]
Now, we simplify the inequality (13) as follows: \[\begin{aligned} \sum_{j=1}^Im^\sigma_j-\sum_{j=1}^Im_j^\tau-1&=\sum_{j=1}^{n-1}m^\sigma_j-\sum_{j=I+1}^{n-1}m^\sigma_j-\sum_{j=1}^{n-1}m_j^\tau+\sum_{j=I+1}^{n-1}m_j^\tau-1\\&=\left(k+1-\sum_{j=I+1}^{n-1}m^\sigma_j\right)-\left( k-1-\sum_{j=I+1}^{n-1}m_j^\tau\right)-1\\&=1-\sum_{j=I+1}^{n-1}m^\sigma_j+\sum_{j=I+1}^{n-1}m_j^\tau.\label{eq4} \end{aligned}\]
Then inequality (14) becomes: \[\begin{aligned} m_I^\tau+\sum_{j=1}^Im^\sigma_j-\sum_{j=1}^Im_j^\tau-1&=m_I^\tau+1-\sum_{j=I+1}^{n-1}m^\sigma_j+\sum_{j=I+1}^{n-1}m_j^\tau\\&=1-\sum_{j=I+1}^{n-1}m^\sigma_j+\sum_{j=I}^{n-1}m_j^\tau. \end{aligned}\]
Now, we show inequality (13), i.e., \[\begin{aligned} 0\leq \sum_{j=1}^Im^\sigma_j-\sum_{j=1}^Im_j^\tau-1\leq m^\sigma_I. \end{aligned}\]
Here, we have two cases:
First case: If \(\sum_{j\geq I}m^\sigma_{j}\geq \sum_{j\geq I+1}m^\tau_{j}+1\), we have: \[\begin{aligned} 1-\sum_{j\geq I}m^\sigma_{j}+\sum_{j\geq I+1}m^\tau_{j}\leq0 &\Leftrightarrow 1-\sum_{j\geq I+1}m^\sigma_{j}-m^\sigma_I+\sum_{j\geq I+1}m^\tau_{j}\leq0\\&\Leftrightarrow 1-\sum_{j\geq I+1}m^\sigma_{j}+\sum_{j\geq I+1}m^\tau_{j}\leq m^\sigma_I\\&\Leftrightarrow \sum_{j=1}^{I}m^\sigma_{j}-\sum_{j=1}^{I}m_{j}^{\tau}-1\leq m_{I}^\sigma. \end{aligned}\]
Second case: If \(\sum_{j\geq I}m^\sigma_{j}>\sum_{j\geq I+1}m^\tau_{j}+1\), we have: \[\begin{aligned} 1-\sum_{j\geq I}m^\sigma_{j}+\sum_{j\geq I+1}m^\tau_{j}<0 &\Leftrightarrow 1-\sum_{j\geq I+1}m^\sigma_{j}-m^\sigma_I+\sum_{j\geq I+1}m^\tau_{j}<0\\&\Leftrightarrow 1-\sum_{j\geq I+1}m^\sigma_{j}+\sum_{j\geq I+1}m^\tau_{j}<m^\sigma_I\\&\Leftrightarrow \sum_{j=1}^{I}m^\sigma_{j}-\sum_{j=1}^{I}m_{j}^{\tau}-1< m_{I}^\sigma. \end{aligned}\] It remains to show that: \[\begin{aligned} \sum_{j=1}^Im^\sigma_j-\sum_{j=1}^Im_j^\tau-1\geq0. \end{aligned}\]
For this, we have two cases:
First case: If \(\sum_{j=I+1}^{n-1}m^\sigma_{j} < \sum_{j=I+2}^{n-1}m^\tau_{j}+1\), we have : \[\begin{aligned} -\sum_{j=I+1}^{n-1}m^\sigma_{j} > -\sum_{j=I+2}^{n-1}m^\tau_{j}-1 &\Leftrightarrow 1-\sum_{j=I+1}^{n-1}m^\sigma_{j}>-\sum_{j=I+2}^{n-1}m^\tau_{j}\\&\Leftrightarrow 1-\sum_{j=I+1}^{n-1}m^\sigma_{j}+\sum_{j=I+2}^{n-1}m^\tau_{j}>0 \\&\Leftrightarrow 1-\sum_{j=I+1}^{n-1}m^\sigma_{j}+\sum_{j=I+1}^{n-1}m^\tau_{j}>m_{I+1}^\tau\geq0\\&\Leftrightarrow 1-\sum_{j=I+1}^{n-1}m^\sigma_{j}+\sum_{j=I+1}^{n-1}m^\tau_{j}>0\\&\Leftrightarrow\sum_{j=1}^Im^\sigma_j-\sum_{j=1}^Im_j^\tau-1>0. \end{aligned}\]
Second case: If \(\sum_{j=I+1}^{n-1}m^\sigma_{j} \geq \sum_{j=I+2}^{n-1}m^\tau_{j}+1\) and \(\sum_{j=I+1}^{n-1}m^\sigma_{j} < \sum_{j=I+1}^{n-1}m^\tau_{j}+1\), we have \[\begin{aligned} 1-\sum_{j=I+1}^{n-1}m^\sigma_{j}+\sum_{j=I+1}^{n-1}m^\tau_{j}>0&\Leftrightarrow\sum_{j=1}^Im^\sigma_j-\sum_{j=1}^Im_j^\tau-1>0. \end{aligned}\]
We show the inequality (14): \(m_I^\tau+\sum_{j=1}^Im^\sigma_j-\sum_{j=1}^Im_j^\tau-1\leq I\). Here, we have two cases:
First case: If \(\sum_{j\geq I}m^\sigma_{j}< \sum_{j\geq I}m^\tau_{j}+1\), using the condition (12), we obtain: \[\begin{aligned} \sum_{j\geq I}m^\tau_{j}+1-\sum_{j\geq I+1}m^\sigma_{j}\leq I\Leftrightarrow m_{I}^\tau+\sum_{j=1}^{I}m_{j}^\sigma-\sum_{j=1}^{I}m^\tau_{j}-1\leq I. \end{aligned}\]
Second case: If \(\sum_{j\geq I}m^\sigma_{j}\geq\sum_{j\geq I}m^\tau_{j}+1\), we have : \[\begin{aligned} 1-\sum_{j\geq I}m^\sigma_{j}+\sum_{j\geq I}m^\tau_{j}\leq0 &\Leftrightarrow 1-\sum_{j\geq I+1}m^\sigma_{j}+\sum_{j\geq I}m^\tau_{j}\leq m_{I}^\sigma\leq I\\&\Leftrightarrow 1-\sum_{j\geq I+1}m^\sigma_{j}+\sum_{j\geq I}m^\tau_{j}\leq I \\&\Leftrightarrow m_{I}^\tau+\sum_{j=1}^{I}m^\sigma_{j}-\sum_{j=1}^{I}m^\tau_{j}-1\leq I. \end{aligned}\]
Now, we must check that \((\theta, \tau)\in I_{B'}(n,k)\times I_{B'}(n,k)\) which means that the number of inversions in \(\theta\) is \(k\) and the number of inversions in \(\pi\) is \(k\).
The number of inversions in \(\theta\) is calculated as follows \[\begin{aligned} \sum_{j=1}^{I}m^\tau_j+\left(\sum_{j=1}^Im^\sigma_j-\sum_{j=1}^Im^\tau_j-1\right)+\sum_{j=I+1}^{n-1}m^\sigma_j&=\sum_{j=1}^Im^\sigma_j+\sum_{j=I+1}^{n-1}m^\sigma_j-1\\ &=\sum_{j=1}^{n-1}m^\sigma_j-1\\&=(k+1)-1=k. \end{aligned}\]
The number of inversions of \(\pi\) is calculated as follows \[\begin{aligned} \sum_{j=1}^{I}m^\sigma_j-\left(\sum_{j=1}^Im^\sigma_j-\sum_{j=1}^Im^\tau_j-1)\right)+\sum_{j=I+1}^{n-1}m^\tau_j&=\sum_{j=1}^{n-1}m^\tau_j+1\\ &=(k-1)+1=k. \end{aligned}\]
Then \((\theta, \tau)\in I_{B'}(n,k)\times I_{B'}(n,k)\). Furthermore, \(f^{-1}_{n,k,k}=f_{n,k+1,k-1}\), which gives us the injectivity of \(f_{n,k,k}\) and completes the proof. ◻
Here, we give an illustrative example.
Example 4.3. Let \(\sigma=\overline{3}\hspace{0.05cm} \overline{2}\hspace{0.05cm}\overline{4}\hspace{0.05cm}\overline{5}1\) a permutation with \(5\) overlined inversions and let \(\tau =12\overline{5}\hspace{0.05cm} \overline{4}3\) a permutation with \(3\) overlined inversions.
| \(\begin{aligned}[t] &\quad m_1^\sigma =1\quad \\ &\quad m_2^\sigma =2\quad \\ &\quad m_3^\sigma =1\quad\\ &\quad m_4^\sigma =1\quad \end{aligned}\) | \(\begin{aligned}[t] &\quad m_1^\tau =0\quad \\ &\quad m_2^\tau =0\quad \\ &\quad m_3^\tau =1\quad\\ &\quad m_4^\tau =2\quad \end{aligned}\) |
First, we must find the index I, we have :
For \(I=4\), \(I+1=\overline{5}\), so \(m_4^\sigma =1=0+1\) then \(I=4\) does not satisfy the second condition (11).
For \(I=3\), \(I+1=\overline{4}\), so \(m_3^\sigma+m_4^\sigma =2<m_4^\tau+1=3\) then \(I=3\) does not satisfy the second condition (11).
For \(I=2\), \(I+1=\overline{2}\), so \(m_2^\sigma+m_3^\sigma+m_4^\sigma =4=m_3^\tau+m_4^\tau+1=4\) then \(I=2\) does not satisfy the second condition (11).
For \(I=1\), \(I+1=\overline{3}\), so \(m_1^\sigma+m_2^\sigma+m_3^\sigma+m_4^\sigma =5>m_2^\tau+m_3^\tau+m_4^\tau+1=4\) then \(I=1\) satisfies the second condition (11). Thus, \(I = 1\) and our application gives :
\(\overline{3}\hspace{0.05cm} \overline{2}\hspace{0.05cm}\overline{4}\hspace{0.05cm}\overline{5}1 \to\) \(3\overline{2}\hspace{0.05cm}\overline{4}\hspace{0.05cm}\overline{5}1\to\) \(3\overline{2}\hspace{0.05cm}\overline{4}1\hspace{0.05cm}\overline{5}\to\) \(3\overline{2}1\overline{4}\hspace{0.05cm}\overline{5}\to\) \(\overline{2}13\overline{4}\hspace{0.05cm}\overline{5}\to\) \(\overline{2}1\overline{4}3\overline{5}\to\) \(\overline{2}1\overline{5}\hspace{0.05cm}\overline{4}3\)
\(12\overline{5}\hspace{0.05cm} \overline{4}3\to\) \(12\overline{5}\hspace{0.05cm}\overline{4}\hspace{0.05cm}\overline{3}\to\) \(12\overline{4}\hspace{0.05cm}\overline{3}\hspace{0.05cm}\overline{5}\to\) \(12\overline{3}\hspace{0.05cm}\overline{4}\hspace{0.05cm}\overline{5}\to\) \(\overline{3}12\overline{4}\hspace{0.05cm}\overline{5}\to\) \(\overline{3}1\overline{4}2\overline{5}\to\) \(\overline{3}1\overline{4}\hspace{0.05cm}\overline{5}2\)
Hence, \(f_{5,4,4}(\overline{3}\hspace{0.05cm} \overline{2}\hspace{0.05cm}\overline{4}\hspace{0.05cm}\overline{5}1,12\overline{5}\hspace{0.05cm} \overline{4}3)=(\overline{2}1\overline{5}\hspace{0.05cm}\overline{4}3,\overline{3}1\overline{4}\hspace{0.05cm}\overline{5}2)\), where \(\theta=\overline{2}1\overline{5}\hspace{0.05cm}\overline{4}3\) has \(4\) overlined inversions, and \(\pi=\overline{3}1\overline{4}\hspace{0.05cm}\overline{5}2\) has \(4\) overlined inversions.
Since a log-concave sequence is unimodal [6], the previous theorem immediately leads to the following corollary:
Corollary 4.4. The sequence of Over-inversion numbers \(\{i_{B'}(n,k)\}_{k}\) is unimodal in \(k\).
Remark 4.5. Since there is a bijection between the permutations with overlined inversions and the paths as shown in Subsection 3.1, then the previous theorem can be proved using Sagan’s paths approach [20] by adding a new condition to his involution as follows. (See also the approaches proposed in [11,1]).
Let \(P_1,P_2\in P_{n,k}^{B'}\). And let \(u \overset{{P}}{\longrightarrow} v\) denote \(P\) has initial vertex \(u\) and final vertex \(v\).
Definition 4.6. Given \(u_1 \overset{{P_1}}{\longrightarrow} v_1\) and \(u_2 \overset{{P_2}}{\longrightarrow} v_2\). Then define the involution \(\varphi_I(P_1,P_2)=(P^{'}_{1},P^{'}_{2})\) where :
\[P^{'}_{1}=u_1 \overset{{P_1}}{\longrightarrow} v_0 \overset{{P_2}}{\longrightarrow} v_2 \text{\ and\ }P^{'}_{2}= u_2 \overset{{P_2}}{\longrightarrow} v_0 \overset{{P_1}}{\longrightarrow} v_1,\] i.e., switches the portions of \(P_1\) and \(P_2\) after \(v_0\) (see, Figure 6), where \(v_0\) is the last vertex of \(P_1 \cap P_2\).
In the previous section, we have established the unimodality and log-concavity properties of the sequence of Over-inversion numbers. However the number and location of the modes of this sequence remains a question to be answered. Generally, it is not easy to find the number and location of modes.
This lets us to finish this paper by the following question.
Question .Find the number and location of modes of the unimodal sequence \(\left\{ i_{B'}(n,k)\right\}_k\).
The authors would like to thank the referees for many valuable remarks and suggestions to improve the original manuscript. This work was supported by DG-RSDT (Algeria), PRFU Project C00L03UN180120220002 and PRFU Project C00L03UN190120230012.