Menu
In this paper, we introduce a class of restricted symmetric permutations, called half-exceeded symmetric permutations. We deduce the enumerative formula of the permutations of \(\{1,2,\ldots,2n\}\) and give it a refinement according to the distribution of the inverse pairs. As a consequence, we obtain new combinatorial interpretations of some well-known sequences, such as Stirling numbers of the second kind and ordered Bell numbers. Moreover, we introduce the ordered Stirling number of the second kind and establish a combinatorial proof of the recursive relation of the sequence.
Permutations are one of the most classical combinatorial structures and their statistics are popular research objects in combinatorics. Stanley [1] introduced several definitions and propositions about permutations and the statistics in detail, such as the cycles of permutations, (weak) excedances, descents, inversions, major index, etc. Ehrenborg and Steingrímsson [2] established a formula for the number of permutations with a certain excedance set and recursive formulas satisfied by these numbers. Chen and Zhou [3] presented a bijection between permutation tableaux of type \(B\) of length \(n\) and symmetric permutations of length \(2n\), and obtained a sign-imbalance formula for permutation tableaux of type \(B\). Lewis [4] studied the exact formulas of the number of alternating permutations of length \(2n\) and \(2n+1\) avoiding the pattern \(1234\), respectively, by establishing a bijection between permutations and standard Young tableaux of certain shapes. Mezö [5] introduced Fubini numbers (or called ordered Bell numbers) and their generating function and the recursive relation.
In this paper, we introduce a special kind of permutations of length \(2n\), called half-exceeded symmetric permutations, and give a combinatorial proof of the enumerative formula of the structure, which is closely related to Stirling numbers of the second kind and ordered Bell numbers. Especially, we construct Insertion Procedure on half-exceeded symmetric permutations by defining the inverse pairs, a new statistic of such permutations, which directly implies the recursive formula of the number of half-exceeded symmetric permutations of \(\{1, 2, \ldots, 2n\}\) with exactly \(k\) inverse pairs.
In this section, we shall derive the enumeration of half-exceeded symmetric permutations and concern about the distribution of their inverse pairs.
For \(n\geq 1\), let \([n]:=\{1,2,\ldots,n\}\) and let \(\pi=\pi(1)\pi(2)\cdots \pi(2n)\) be a permutation of \([2n]\). For any \(i\in [2n]\), if \(\pi(i)=i\), then the number \(i\) is called a fixed point of \(\pi\); if \(\pi(i)+\pi(2n+1-i)=2n+1\), then \(\pi\) is defined to be symmetric. For any \(i\in [n]\), if \(\pi(i)>\pi(2n+1-i)\), then \(\left(\pi(i),\pi(2n+1-i)\right)\) is called an inverse pair of \(\pi\). A number \(i\in [2n]\) for which \(\pi(i)>i\) is called an excedance of \(\pi\). If each \(i\in [n]\) is excedance of \(\pi\), then we call \(\pi\) a half-exceeded permutation of \([2n]\). In addition, if \(\pi\) is both half-exceeded and symmetric, then it is defined as a half-exceeded symmetric permutation of \([2n]\). For example, \(\pi_1=23(10)7654189\) is a half-exceeded symmetric permutation of \(\{1,2,\ldots,10\}\), and \((10,1),(7,4)\) and \((6,5)\) are its three inverse pairs.
Next we consider the ‘pattern’ of inverse pairs in half-exceeded symmetric permutations. For each inverse pair \((\pi(i), \pi(2n+1-i))\) of \(\pi\), we replace \(\pi(i)\) by ‘X’ and remove elements \(\pi(n+1)\pi(n+2)\cdots\pi(2n)\) from \(\pi\). Then we get a word of length \(n\), denoted by \(\omega\). Since \(\pi\) is a half-exceeded symmetric permutation, \(\omega\) is a word possibly consisting of X’s and some numbers in \(\{2,\ldots,n\}\). We define \(\omega\) as the inversion pattern of \(\pi\). For example, both \(\pi_1=23(10)7654189\) and \(\pi_2=2376(10)15489\) are half-exceeded symmetric permutations of \(\{1,2,\ldots,10\}\) and they have the same inversion pattern \(23\)XXX. Note that \(2n\) is an excedance of \(\pi\), which implies that there exists at least one inverse pair in any half-exceeded symmetric permutation. For the set of half-exceeded symmetric permutations of \([2n]\), let \(P(n,k)\) denote the number of different inversion patterns containing exactly \(k\) X’s, for \(k\geq 1\). Then we have
Theorem 1. For any \(n\geq 1\) and \(k\geq 1\), \(P(n,k)=S(n,k)\), where \(S(n,k)\) is the Stirling number of the second kind.
We shall construct a bijection \(\varphi\) between the set of inversion patterns of length \(n\) with \(k\) X’s and the set of partitions of \([n]\) with \(k\) blocks by induction.
For \(n=1\), the unique half-exceeded symmetric permutation is \(\pi=21\) and its inversion pattern is \(\omega=X\). So we set \(\varphi(\omega)=\left\{\{1\}\right\}\), the unique partition of \(\{1\}\).
For \(n\geq 2\) and \(k\geq 1\), let \(\omega=\omega(1)\cdots \omega(n)\) be an inversion pattern of length \(n\) with \(k\) X’s, where \(\omega(i)\in\{\mbox{X},2,\ldots,n\}\), \(\forall i=1,\ldots,n\). Let \(P'=\left\{\{1\},\{2\},\cdots,\{n\}\right\}\) be a partition of \([n]\) consisting of \(n\) single blocks. For any \(i=1,2,\ldots,n\), if \(\omega(i)\neq\) X, then we add \(\omega(i)\) to block \(\{i\}\) of \(P'\) and make a union of the blocks having non-empty intersections. Denote the result by \(P\). Since \(\omega\) is an inversion pattern of a half-exceeded symmetric permutation, each element \(\omega(i)\neq\) X must greater than \(i\) such that the blocks containing \(\omega(i)\) must be merged together. That is to say, if \(\omega\) consists of \(k\) X’s and \(n-k\) numbers, then \(P\) must have \(k\) blocks, which is exactly the desired partition of \([n]\).
On the other hand, given a partition \(P\) of \([n]\) with \(k\) blocks, we establish an inversion pattern of length \(n\) with \(k\) X’s by following steps. Let \(B=\{i_1,\ldots,i_t\}\) be a block of \(P\), where \(i_1<\cdots<i_t\) and \(t\geq 1\). We set \(\omega(i_t)=\) X. If \(t\geq 2\), then we set \(\omega(i_{j-1})=i_j\), for any \(j=2,\ldots,t\). Obviously, \(\omega=\omega(1)\cdots \omega(n)\) is a word of length \(n\) consisting of \(k\) X’s and \(n-k\) different numbers in \(\{2,\ldots,n\}\). Since \(\omega(i_{j-1})=i_j>i_{j-1}\), \(i_j\leq n\), and the minimum elements of each block of \(P\) does not exist in \(\omega\), the word \(\omega\) must be an inversion pattern of length \(n\) for some half-exceeded symmetric permutations. The proof is completed.
For example, as a partition of \(\{1,2,\ldots,8\}\), \(P=\left\{\{1,3,4,7,8\},\{2,5\},\{6\}\right\}\) corresponds to the inversion pattern \(\omega=3547\mbox{XX}8\mbox{X}\) of length \(8\).
Furthermore, given an inversion pattern \(\omega\) of length \(n\) with \(k\) X’s, we could easily construct \(k!\) different half-exceeded symmetric permutations of \([2n]\). As a consequence, the \(k\) blocks of the corresponding partition \(P\) can be ordered in \(k!\) different ways, such that we have \(k!\) ordered partitions of \([n]\). Thus we conclude that
Corollary 1. For \(n\geq 1,k\geq 1\), we have
the number of ordered partitions of \([n]\) is equal to the number of half-exceeded symmetric permutations of \([2n]\);
the number of ordered partitions of \([n]\) with exactly \(k\) blocks is equal to the number of half-exceeded symmetric permutations of \([2n]\) with exactly \(k\) inverse pairs.
Let \(H(n,k)\) be the number of half-exceeded symmetric permutations of \([2n]\) with exactly \(k\) inverse pairs and we call it ordered Stirling number of the second kind. Then we have
Corollary 2. For \(n\geq 1,k\geq 1\), \[H(n,k)=k!S(n,k).\tag{1}\]
Corollary 3. For \(n\geq 1\), the number of half-exceeded symmetric permutations of \([2n]\) is equal to ordered Bell number \(\widetilde{B}(n)\), i.e., \[\widetilde{B}(n)=\sum_{k=1}^n H(n,k)=\sum_{k=1}^n k!S(n,k).\tag{2}\]
In addition, based on the number of inverse pairs, we exhibit an elementary Insertion Procedure to construct half-exceeded symmetric permutations recursively.
Let \(\pi=\pi(1)\pi(2)\cdots\pi(2n)\) be a half-exceeded symmetric permutation of \([2n]\). If there exists a number \(i\in [n]\) satisfying \(\pi(i)=i+1\), then \(i\) is called a nearly fixed point of \(\pi\). According to the existence and location of those points, we construct a half-exceeded symmetric permutation of \([2n+2]\) by Insertion Procedure as follows.
Insertion Procedure£º
Initial Step:
Let \(\pi'=\pi'(1)\pi'(2)\cdots\pi'(n)\) be a word of length \(n\), where \(\pi'(i)\colon=\pi(i)+2\) if \(\pi(i)\geq n+1\), and otherwise \(\pi'(i)\colon=\pi(i)\), for \(i\in [n]\).
Procedure:
Case 1: If there does not exist any nearly fixed point in \(\pi\), then we insert \(n+1\) (or \(n+2\)) immediately to the left of \(\pi'(t)\), where \(\pi'(t)\) is any one of the elements
satisfying \(\pi'(t)>n\).
Case 2: Let \(m\) be the rightmost nearly fixed point of \(\pi\). We have three different ways of inserting element \(n+1\) (or \(n+2\)) as follows:
(2-1) Let \(\pi'(s)\) be any one of the elements satisfying both \(s>m\) and \(\pi'(s)>n\). Then we insert \(n+1\) (or \(n+2\)) immediately to the left of \(\pi'(s)\), or
(2-2) Let \(\pi'(t)\) be any one of the elements satisfying both \(t<m\) and \(\pi'(t)>n\). Then we replace \(\pi'(t)\) by \(n+1\) (or \(n+2\)), and insert \(\pi'(t)\) immediately to the right of \(\pi'(n)\), or
(2-3) We directly insert \(n+2\) immediately to the right of \(\pi'(n)\).
Here we get a word of length \(n+1\) and denote it by \(\pi''\).
Final Step:
On the basis of the above procedure and the definition of symmetric permutations, one could easily add the other \(n+1\) elements to the right of \(\pi''\), which obviously leads to a half-exceeded symmetric permutation of \([2n+2]\).
An example is given for illustration. For \(n=3\), \(\pi=635241\) is a half-exceeded symmetric permutation and it has two inverse pairs: \((6,1)\) and \((5,2)\). Since there only exists \(\pi(2)=3\), it has just one nearly fixed point \(i=2\). Let \(\pi'=837\) and according to Case 2, we could
(2-1) insert \(4\) (or \(5\)) immediately to the left of \(7\) and obtain \(\pi''=8347\) (or \(\pi''=8357\)), or
(2-2) replace \(8\) by \(4\) (or \(5\)), and insert \(8\) immediately to the right of \(7\), which deduces \(\pi''=4378\) (or \(\pi''=5378\)), or
(2-3) insert \(5\) to the right of \(7\) and get \(\pi''=8375\).
Finally, we obtain five half-exceeded symmetric permutations: \(\pi_1=83472561\), \(\pi_2=83572461\), \(\pi_3=43781265\), \(\pi_4=53781264\) and \(\pi_5=83754261\). Notice that both \(\pi_1\) and \(\pi_3\) have two inverse pairs, being the same as \(\pi\), while \(\pi_2\), \(\pi_4\) and \(\pi_5\) all have three inverse pairs.
It is clear that Insertion Procedure presents a simple proof of the recursive relation of \(H(n,k)\).
Proposition 1. For \(n\geq 1,k\geq 1\), the numbers \(H(n,k)\) satisfy the recurrence \[\label{eqHnk} H(n+1,k)=k\left[H(n,k-1)+H(n,k)\right],\tag{3}\] with the initial condition \(H(n,0)=0\) and \(H(n,k)=0\) for \(n<k\).
This work was partially supported by National Natural Science Foundation of China (11601020, 11501014), National Key Research and Development Project of China 2019YFC1606401.