Type B set partitions, an analogue of restricted growth functions

1. Introduction

In the preliminary section, we initially describe four fundamental statistics introduced by Wachs and White [9] using the technique of restricted growth functions as in [3], where the number of blocks $k$ of the set partition of $[n]$ turns out to be the maximal letter in the restricted growth function as observed by Sagan in [5]. In the preliminary section, we initially describe the type-B analogue of ten set partition statistics over $⟨n⟩$, which were defined by Steingrímsson over $[n]$ in case of standard and ordered both type of set partitions. We found the generating functions of the type B analogue of some of the set partition statistics defined over $⟨n⟩$ which were defined by Steingrímsson over $[n]$, for any specified number of blocks $k$ in terms of $q$-Stirling numbers of the second kind. Stirling numbers of both kinds have been extensively studied in combinatorics and have interesting applications in algebra and geometry. There are two versions of q-Stirling numbers of second kind, where one is $q^{(\genfrac{}{}{0ex}{}{k}{2})}$ times the other, as in [7]. Here we work on the version without the $q^{(\genfrac{}{}{0ex}{}{k}{2})}$ as in [6]. $q$-Stirling numbers in type B have appeared sporadically in the literature over the last several decades. In [6] Sagan and Swanson worked on various statistics over signed or type B partition using type B $q$-Stirling numbers of second kind. Haglund, Rhoades, and Shimozono [1] showed that there is a connection between ordered set partitions, generalized coinvariant algebras, and the Delta Conjecture. In related work, Zabrocki [8] conjectured that the tri-graded Hilbert series of the type A super coinvariant algebra has coefficients which are the ordered $q$-Stirling number of the second kind. Swanson and Wallach [4] made a corresponding conjecture in type B. This led them to conjecture that an alternating sum involving these ordered Stirling numbers equals one. Sagan and Swanson proved that conjecture in [6].

There is a bijection between the set partitions of $[n]$ in standard form and restricted growth functions (RGF). Wachs and White defined four fundamental statistics on those RGFs. We give some type B analogues of some statistics on set partitions studied by Wachs-White in [9] and Steingrímsson in [7]. This is done through a type B analogue of restricted growth functions in [9]. We defined an analogue of restricted growth function in case of type B set partitions of $⟨n⟩$ and we called it as Signed Restricted Growth Function (SRGF). We found a similar kind of bijection between set partitions of $⟨n⟩$ and SRGF. Recently, Bagno-Garber gave an analogue of restricted growth functions in [2] (Definition 4.11) for signed permutations with a specific number of cycles which are counted by signed Stirling numbers of the first kind. In addition, Bagno, Garber and Komatsu gave an analogue of Restricted growth words for type B in [2] with respect to certain ordering on $⟨n⟩$ in section 2.3 Definition 2.7, which has overlap with our SRGF. In [7] Steingrímsson defined ten set partition statistics over the set partitions of $[n]$. Four of these were already defined by Wachs and White as above in case of standard set partitions, and their treatment was in terms of restricted growth functions, a different way of representing partitions in standard form only. Another four statistics are mirror images of the aforementioned ones. The last two statistics, essentially defined by Foata and Zeilberger for permutations, are in fact each equal to the difference of two of the first eight statistics. In [5] Sagan has shown that the Foata bijection interchanging inversion and major index for permutations also has a version for partitions of $[n]$. In section 3, we discussed an analogue of Foata bijection and using SRGF we have shown that is interchanging the inversion and major index for type B partitions over $⟨n⟩$. In [5] Sagan has given an interpretation of major index for set partitions of $[n]$ using reduced matrices. We give an analogue of such matrices for type B set partitions and have shown that the analogue of reduced matrix is preserving the major index as done by Sagan for set partitions of $[n]$. Utilizing the idea of two inversion vectors for RGF as done in [5], we give eight vectors for SRGF corresponding to the type B analogue of Steingrímsson statistics.

2. Preliminary

In [3] a partition of $[n]$ is written as $\sigma =B_1/\cdots /B_k⊢S$ where the subsets $B_i$ are called blocks. We use the notation ${\mathrm{\Pi }}_n=\{\sigma :\sigma ⊢[n]\}$. In order to connect set partitions with the statistics of Wachs and White, they are converted into restricted growth functions as in [3] and that requires the elements of ${\mathrm{\Pi }}_n$ in standard form.

We assume all partitions in ${\mathrm{\Pi }}_n$ are written in the standard form. Associate with $\sigma \in {\mathrm{\Pi }}_n$ the word $w(\sigma )=a_1\cdots a_n$ where $a_i=j$ if and only if $i\in B_j$. For example $w(16/23478/5)=12223122.$ Let, ${\mathrm{\Pi }}_{n,k}$ be the set of all words in ${\mathrm{\Pi }}_n$ with exactly $k$ many blocks. $R_n=\{w:w$ is an RGF of length $n\}$. Let, $R_{n,k}=\{w:w$ is an RGF of length $n$ with maximal letter $k\}$.

The four statistics of Wachs and White are denoted as $lb,ls,rb$ and $rs$ where ‘‘l’’stands for ‘‘left’’, ‘‘r’’stands for ‘‘right’’, ‘‘b’’stands for ‘‘bigger’’, and ‘‘s’’stands for ‘‘smaller’’. The left-bigger statistic is described and the other three should become clear by analogy. Given a word $w=a_1\cdots a_n$ define $lb(a_j)=\mathrm{\#}\{a_i:i<j$ and $a_i>a_j\}$. It is important to note that, the cardinality of a set is taken, so if there are multiple copies of such an integer then it is only counted once. Also, clearly $lb(a_j)$ depends on the word containing $a_j$, not just $a_j$ itself. By way of example, if $w=12332412$, then $lb(a_7)=3$. Define $lb(w)=lb(a_1)+\cdots +lb(a_n)$. Continuing the above example, $lb(12332412)=0+0+0+0+1+0+3+2=6$. To simplify notation, $lb(\sigma )$ is taken instead of more cumbersome $lb(w(\sigma ))$. Accordingly, $ls(\sigma ),rb(\sigma ),rs(\sigma )$ are defined.

Now let, $O{\mathrm{\Pi }}_n$ be the set of all ordered partitions of $[n]$ (that means the set partitions are not necessarily in standard form). Let, $O{\mathrm{\Pi }}_{n,k}$ be the set of all words in $O{\mathrm{\Pi }}_n$ with exactly $k$ blocks.

In order to define the ten statistics, Steingrímsson first defined the openers and closers of the blocks for any $\pi \in O{\mathrm{\Pi }}_{n,k}$. The opener of a block is its least element and the closer is its greatest element.

Defining $ROS\pi =ros\pi +(\genfrac{}{}{0ex}{}{k}{2})$ (and $RCB,LOS,LCB$ similarly), we have

Where $[k]!=[k][k-1][k-2]\cdots [1]$ with $[k]=[k{]}_q$ (we drop the $q$ from the suffix to make the notation simpler)$=1+q+q^2+q^3+\cdots q^{k-1}$ and $S_q(n,k)$ is the $q$-Stirling numbers of second kind which can be described as in Lemma 1 in [7], $S_q(n,k)=q^{k-1}·S_q(n-1,k-1)+[k]·S_q(n-1,k)$.

3. Steingrímsson’s Statistics for type B partitions and some generating functions in terms of $q$-Stirling numbers

Note that defining inversion over an ordered signed partition of $[n]$ in the above way, matches with Steingrímsson’s ros, while the same is applied over any $\pi \in O{\mathrm{\Pi }}_{n,k}$. For example consider $\pi =47/3/159/68/2\in O{\mathrm{\Pi }}_{9,5}$. inv $$\begin{gathered} \pi =\mathrm{\#}\{(4,B_2),(4,B_3),(4,B_5),(7,B_2),(7,B_3),(7,B_4),(7,B_5),(3,B_3),(3, \\ {B}_5),(5,B_5),(9,B_4),(9,B_5),(6,B_5),(8,B_5)\}=14=ros\pi \end{gathered}$$.

This is the motivation to define in this work nine more statistics over any ordered signed partitions of $⟨n⟩$, so that they matches with Steingrímsson’s nine other statistics accordingly, while the same is applied over any $\pi \in O{\mathrm{\Pi }}_{n,k}$.

To do this, we can further define $M_i=max|S_i|$, like $m_i$. For any $\rho \in S_B^o(⟨n⟩,k)$, noting that the negetive elements and $0$ in the type B partition of $⟨n⟩$ does not contribute in $inv\rho$ we define the following:

As an example, consider the same $\pi$ above. Note that by the above definition $$lo{s}_B\pi =\{(5,B_1),(5,B_2),(9,B_1),(9,B_2),(6,B_1),(6,B_2),(6,B_3),(8,B_1),(8,B_2),(8,B_3),(2,B_3)\}=11,$$ where as by Steingrímsson’s $los\pi =0+0+0+0+2($corresponding to $(5,B_1),(5,B_2))+2($corresponding to $(9,B_1),(9,B_2))+3($corresponding to$(6,B_1),(6,B_2),(6,B_3))+3($ corresponding to$$\begin{gathered} (8,B_1),(8,B_2),(8, \\ {B}_3))+1( \end{gathered}$$corresponding to $(2,B_3),)=11$.

Note in [7], given a partition $\pi$ of $[n]$, let ${\pi }^c$ be the partition obtained by complementing each of the letters in $\pi$, that is, by replacing the letter $i$ by $n+1-i$. Then it follows that $rcb{\pi }^c=ros\pi$ and that $rcs{\pi }^c=rob\pi$. In order to have similar result for type B partitions in $S_B^o(⟨n⟩,k)$, we define the complement of any $\pi \in S_B^o(⟨n⟩,k)$ in the following way:

Then it follows that $rcb{\pi }^c=ros\pi$ and that $rcs{\pi }^c=rob\pi$, as because each $(s,S_j)$ contributing in $ros\pi$ gives $(n+1-s,S_j)$ contributing in $rcb{\pi }^c$ and conversely.

Although, as in [7] where every right statistic is equidistributed with its corresponding left statistic (since reversing the order of the blocks in an ordered partition turns a left opener into a right opener and likewise for closers), the exact same is not the case for type B partitions. We have:

4. Signed restricted growth functions

Calling the set of all such SRGF of length 2n+1 as $S{R}_n$ and $S{R}_{n,k}$ accordingly for SRGF of length 2n+1 with maximal letter $k$, we can show analogously as in RGF that there is a bijection between the set of all type B partitions of $⟨n⟩$ and $S{R}_n$, which preserves the one to one correspondence between $S{R}_{n,k}$ and $S_B(⟨n⟩,k)$. The bijection is the following: Consider any type B partition $\pi$ of $⟨n⟩$. Associate with $\pi$, the word $w(\pi )=a_0{a}_1{a}_1^{\ast }{a}_2{a}_2^{\ast }\cdots a_n{a}_n^{\ast }$, where

1. $a_0=0,a_i=a_i^{\ast }=0$, iff $i,\overline{i}\in S_0$, for $i\in \{1,2\cdots n\}$,

2. $a_i=\overline{j},a_i^{\ast }=j$ iff $i\in S_{2j}$ for $i,j\in \{1,2\cdots n\}$,

3. $a_i=j,a_i^{\ast }=\overline{j}$ iff $i\in S_{2j-1}$ for $i,j\in \{1,2\cdots n\}$.

Note that for any type B partition $\pi$ of $⟨n⟩,w(\pi )$ satisfies the condition i. and ii. in the definition of SRGF. Due to standardization of $\pi ,w(\pi )$, satisfies condition iii. and iv.

In reference [5] section 4, we observe that, if for a set partition $\pi$, a positive integer contributes in the descent set of $F(\pi )$, where $F(\pi )$ is the Foata bijection as defined in [5], then the number of it’s contribution is the number of it’s corresponding occurrence in the inversion set of $\pi$. For example, in [5] section 4, for $\pi =138/2/476/59$ the positive integer $7$ contributes $1$ in the descent of $F(\pi )=1367/2/48/59$, which is the number of it’s occurrence in the inversion set of $\pi$, namely as $(7,B_1)$. This observation motivates us to define an analogue of Foata bijection for type B set partitions in $S_B(⟨n⟩,k)$ as follows:

This bijection $F$ is analogously defined via induction on $n$, as $F$ is identity whenever $n=0$. If $\pi \in S_B(⟨n⟩,k)$, for $n>1$, let ${\pi }^{\mathrm{\prime }}=\pi$ with $n,\overline{n}$ deleted. We construct $\sigma =F(\pi )$ from ${\sigma }^{\mathrm{\prime }}=F({\pi }^{\mathrm{\prime }})$ as follows. If

1. $\pi =S_0/S_1/S_2/\cdots /S_{2k}$, with $S_{2k-1}=\{\overline{n}\}$ and $S_{2k}=\{n\}$, (due to standardization condition, the other way can’t happen), then let $\sigma ={\sigma }^{\mathrm{\prime }}$ with $\overline{n}$ and $n$ added in $S_{2k-1}$ and in $S_{2k}$ as singleton blocks respectively.

2. If $n$ is strictly contained in the block $S_{2k}$, then let $\sigma ={\sigma }^{\mathrm{\prime }}$ with $n$ added in the block $S_{2k}$ and $\overline{n}$ added in the block $S_{2k-1}$.

3. If $n$ is in $S_{2k-1}$ and if $\overline{n}$ is in $S_{2k}$, then let $\sigma ={\sigma }^{\mathrm{\prime }}$, along with both $n,\overline{n}$ added in $S_0$.

4. If $n$ or $\overline{n}$ are contained in $S_{2i}$, where $0<i<k$, then $\sigma ={\sigma }^{\mathrm{\prime }}$ with $n$ or $\overline{n}$ added in $S_{2(k-i)-1}$ and $S_{2(k-i)}$ respectively in a way so that the mutual ordering is flipped.

5. If $n,\overline{n}$ are in $S_0$, then $n$ is added in $S_{2k-1}$ and $\overline{n}$ is added in $S_{2k}$.

So, we consider the following example where $\pi =02\overline{2}/\overline{1}7/1\overline{7}/\overline{3}\overline{6}/36/\overline{4}5/4\overline{5}$

Table 1 Table for the bijection F

$n$	$\pi$	$\sigma =F(\pi )$
$0$	$0$	$0$
$1$	$0/\overline{1}/1$	$0/\overline{1}/1$
$2$	$02\overline{2}/\overline{1}/1$	$0/\overline{1}2/1\overline{2}$
$3$	$02\overline{2}/\overline{1}/1/\overline{3}/3$	$0/\overline{1}2/1\overline{2}/\overline{3}/3$
$4$	$02\overline{2}/\overline{1}/1/\overline{3}/3/\overline{4}/4$	$0/\overline{1}2/1\overline{2}/\overline{3}/3/\overline{4}/4$
$5$	$02\overline{2}/\overline{1}/1/\overline{3}/3/\overline{4}5/4\overline{5}$	$05\overline{5}/\overline{1}2/1\overline{2}/\overline{3}/3/\overline{4}/4$
$6$	$02\overline{2}/\overline{1}/1/\overline{3}\overline{6}/36/\overline{4}5/4\overline{5}$	$05\overline{5}/\overline{1}26/1\overline{2}\overline{6}/\overline{3}/3/\overline{4}/4$
$7$	$02\overline{2}/\overline{1}7/1\overline{7}/\overline{3}\overline{6}/36/\overline{4}5/4\overline{5}$	$05\overline{5}/\overline{1}26/1\overline{2}\overline{6}/\overline{3}\overline{7}/37/\overline{4}/4$

We note that inv $(\pi )$ = maj$(F(\pi ))$ =$10$ and inv$(F(\pi ))$ = maj$(\pi )$ =$14$. We have the following theorem as an analogue of Theorem 4.1 in [5]:

As an analogue of Section 2 in [5], we define $lb$ vector and $ls$ vector for SRGF induced by type B set partitions and denote them as $l{b}_B,l{s}_B$ respectively. We further extend the idea of major index as in Section 2 in [5], via $l{b}_B$ for any element in $S{R}_{n,k}$.

We define an $l{b}_B$ vector for SRGF as follows:

Observing this we define the major index of any such SRGF $$w=w(\pi )=a_0{a}_1{a}_1^{\ast }{a}_2{a}_2^{\ast }\cdots a_k{a}_k^{\ast },$$ analogously as in [5] as follows:

We define an analogue of ls vector for SRGF as follows:

Next we define an analogue of six more vectors in case of SRGF corresponding the type B analogues of six more statistics defined by Steingrímsson as follows. Consider the SRGF $w=a_0{a}_1{a}_1^{\ast }{a}_2{a}_2^{\ast }\cdots a_k{a}_k^{\ast }.$

As in [5] we can create an analogous bijection $h:S_B(⟨n⟩,k)\mapsto RR(⟨n⟩,k)$ as follows $h(\pi )=M$, where $M=(m_{i,j}{)}_{(2k+1)X(2n+1)}$, with

1. $m_{1,1}=1$ (as $0\in S_0$),

2. $m_{1,j}=\overline{1},m_{1,j+1}=1$, if $\overline{j},j\in S_0\mathrm{\forall }j\in \{1,2,\cdots 2n+1\}$,

3. For $i\in \{1,2,\cdots 2k+1\}1,m_{ij}=\overline{1}$ if $\overline{j}\in S_{i-1}$ and $m_{ij}=1$, if $j\in S_{i-1}$.

Now if we define the major index of such a matrix $M$ as $maj(M)=\sum _{m_{i,j}=1}i$, where the sum is restricted to those $1$’s which have another $1$, strictly to their south-west (as in [5]) then we have the following theorem as an analogue of Theorem 3.3 (i) as follows:

For example for our $\pi =0\overline{1}13\overline{3}/\overline{2}4/2\overline{4}/\overline{5}/5/\overline{6}\overline{8}/68/\overline{7}/7,h(\pi )$ is a $9X17$ matrix as follows:

$$\left(\begin{array}{c}\begin{array}{rrrrrrrrrrrrrrrrr}1& \overline{1}& 1& 0& 0& \overline{1}& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& \overline{1}& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& \overline{1}& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& \overline{1}& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& \overline{1}& 0& 0& \overline{1}& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& \overline{1}& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\end{array}\end{array}\right).$$

Let us define the dual descent multiset analogously as in [5] in case of type B partitions.

Accordingly, we define the natural analogue of dual major index for any type B partition as $\widehat{ma{j}_B\pi }=\sum _{i\in \widehat{Des\pi }}(i-1)$.

Afterwards, we find a reccurrence relation for the generating function of the dual major index for type B partitions as follows:

Acknowledgment

Author thanks to Bruce Sagan for introducing this area to work on and for providing several suggestions, multiple advice and helpful discussions on this topic via many communications. Author thanks to Jordan O Tirrell towards providing valuable suggestions in order to write this paper. Author thanks to Tucker Ervin for providing many great discussions, further ideas, checking the work for corrections, extending helpful advice through several communications. Author thanks to David Gajewski for helping in LaTeX. This work is partially supported via travel grants from NSF and NSA to travel in conferences in Pattern in Permutations.