# Structure coefficients of the Hecke algebra of
$(S_{2n}, \mathcal{B}_n)$

Omar Tout†

LaBRI, Université de Bordeaux, CNRS, 351 cours de la Libération, 33405 Talence, France.

**Abstract.** The Hecke algebra of the pair $(S_{2n}, \mathcal{B}_n)$, where $\mathcal{B}_n$ is the hyperoctahedral subgroup of $S_{2n}$, was introduced by James in 1961. It is a natural analogue of the center of the symmetric group algebra. In this paper, we give a polynomiality property of its structure coefficients. Our main tool is a combinatorial universal algebra which projects on the Hecke algebra of $(S_{2n}, \mathcal{B}_n)$ for every $n$. To build it, we introduce new objects called partial bijections.

**Résumé.** L'algèbre de Hecke de la paire $(S_{2n}, \mathcal{B}_n)$, où $\mathcal{B}_n$ est le sous-groupe hyperoctaédral de $S_{2n}$, a été introduite par James en 1961. C'est un analogue naturel du centre de l'algèbre du groupe symétrique. Dans ce papier, on donne une propriété de polynomialité de ses coefficients de structure. On utilise une algèbre universelle construite d'une façon combinatoire et qui se projette sur toutes les algèbres de Hecke de $(S_{2n}, \mathcal{B}_n)$. Pour la construire, on introduit de nouveaux objets appelés bijections partielles.

**Keywords:** Hecke algebra of $(S_{2n}, \mathcal{B}_n)$, partial bijections, structure coefficients

This paper is an extended abstract of [?], which contains all detailed proofs and will be submitted elsewhere.

## 1 Introduction

The center of the symmetric group algebra of $n$, denoted $Z(C[S_n])$, is a classical object in algebraic combinatorics. It is linearly generated by elements $Z_\lambda$, indexed by partitions of $n$, which are the sums of permutations of $n$ with cycle-type $\lambda$. The structure coefficients $c_{\lambda\delta}^\rho$ describe the product in this algebra:

$$Z_\lambda Z_\delta = \sum_{\rho \text{ partition of } n} c_{\lambda\delta}^\rho Z_\rho.$$

In other words, $c_{\lambda\delta}^\rho$ counts the number of pairs of permutations $(x, y)$ with cycle-type $\lambda$ and $\delta$ such that $x \cdot y = z$ for a fixed permutation $z$ with cycle-type $\rho$. It is known, see [?], that these coefficients also count numbers of graphs drawn on oriented surfaces with some additional conditions. One of the tools used to calculate these coefficients is the representation theory of the symmetric group, see [?, Lemma 3.3]. In [?, Theorem 2.1], Goupil and Schaeffer gave a cumbersome formula for $c_{\lambda\delta}^\rho$ if one of the partitions $\lambda, \delta$ and $\rho$ is equal to $(n)$. There are no formulas for $c_{\lambda\delta}^\rho$ in general.

<footnote>†This work is partially supported by the ANR – PSYCO project (ANR-11-JS02-001).</footnote>
In 1958, Farahat and Higman proved the polynomiality of the coefficients $c_{\lambda\delta}^{\rho}$ in $n$ when $\lambda, \delta$ and $\rho$ are fixed partitions, completed with parts equal to 1 to get partitions of $n$, see [?, Theorem 2.2]. This result is also proved by Ivanov and Kerov in [?] through the introduction of partial permutations. This proof provides a combinatorial description of these coefficients.

Here, we consider the Hecke algebra of the pair $(S_{2n}, \mathcal{B}_n)$, where $\mathcal{B}_n$ is the hyperoctahedral group (see definition in section 2.2). It was introduced by James in [?] and it also has a basis indexed by partitions of $n$. This algebra is a natural analogue of $Z(C[S_n])$ for several reasons. Goulden and Jackson proved in [?] that its structure coefficients count graphs drawn on non-oriented surfaces. To get formulas for these coefficients, zonal spherical functions are used instead of irreducible characters of the symmetric group, see [?, Section VII, 2].

In this paper we give a polynomiality property of the structure coefficients of the Hecke algebra of $(S_{2n}, \mathcal{B}_n)$. We prove that these coefficients can be written as the product of the number $2^{n}n!$ with a polynomial in $n$. In some specific basis, this polynomial has non-negative coefficients. Our proof is inspired by the construction of Ivanov and Kerov in [?]. However, we had to face some difficulties that do not appear in their work. In the proof, we introduce new combinatorial objects called partial bijections of $n$. These objects allow us to build in a combinatorial way a universal algebra which projects on Hecke algebra of $(S_{2n}, \mathcal{B}_n)$ for every $n$. It also gives us a combinatorial description of the coefficients of the relevant polynomials.

A weaker version of our polynomiality result (without non-negativity of the coefficients) for the structure coefficients of Hecke algebra of $(S_{2n}, \mathcal{B}_n)$ has been established by indirect approach using Jack polynomials in [?, Proposition 4.4]. There is no combinatorial description in that proof. In [?], Aker and Can considered the same question, but their article contains a mistake (the coefficient $2^{n}n!$ does not appear in their result).

The paper is organized as follows. In section 2, we put on all necessary definitions to describe the Hecke algebra of $(S_{2n}, \mathcal{B}_n)$. Then, we give our main result about its structure coefficients. We start section 3 by introducing partial bijections of $n$ then we construct our universal algebra. We use this algebra in section 4 to prove Theorem 2.1.

# 2 Definitions and statement of the main result

## 2.1 Partitions

Since partitions index bases of the algebras studied in this paper, we recall the main definitions. A *partition* $\lambda$ is a sequence of integers $(\lambda_1, \lambda_2, \dots)$ where $\lambda_1 \ge \lambda_2 \ge \dots \ge 1$. The $\lambda_i$ are called the *parts* of $\lambda$ and the *size* of $\lambda$, denoted by $|\lambda|$, is the sum of all its parts. If $|\lambda| = n$, we say that $\lambda$ is a partition of $n$. We will also use the exponential notation $\lambda = (1^{m_1(\lambda)}, 2^{m_2(\lambda)}, 3^{m_3(\lambda)}, \dots)$, where $m_i(\lambda)$ is the number of parts equal to $i$ in the partition $\lambda$. If $\lambda$ and $\delta$ are two partitions we define the *union* $\lambda \cup \delta$ as the following partition:

$$ \lambda \cup \delta = (1^{m_1(\lambda)}+m_1(\delta), 2^{m_2(\lambda)}+m_2(\delta), 3^{m_3(\lambda)}+m_3(\delta), \dots). $$

A partition is called *proper* if it does not have any part equal to 1. The proper partition associated to a partition $\lambda$ is the partition $\bar{\lambda} := \lambda \setminus (1^{m_1(\lambda)}) = (2^{m_2(\lambda)}, 3^{m_3(\lambda)}, \dots)$.
## 2.2 Permutations and Coset type

We will denote by $[n]$ the set $\{1, \dots, n\}$. A permutation of $n$ is a bijection between the set $[n]$ and itself. For a permutation $\omega$, we use the line notation $\omega_1 \omega_2 \cdots \omega_n$, where $\omega_i = \omega(i)$. The set $S_n$ of all permutations of $n$ is a group for the composition called the symmetric group of size $n$.

To each permutation $\omega$ of $2n$ we associate a graph $\Gamma(\omega)$ with $2n$ vertices located on a circle. Each vertex is labelled by two labels (exterior and interior). The exterior labels run through natural numbers from 1 to $2n$ around the circle. The interior label of the vertex with exterior label $i$ is $\omega(i)$. We link the vertices with exterior (resp. interior) labels $2i-1$ and $2i$ by an exterior (resp. interior) edge. Since exterior and interior edges alternate, the graph $\Gamma(\omega)$ has only cycles of even lengths $2\lambda_1 \ge 2\lambda_2 \ge 2\lambda_3 \ge \dots$. The coset-type of $\omega$ denoted by $ct(\omega)$ is the partition $(\lambda_1, \lambda_2, \lambda_3, \dots)$ of $n$.

**Example 2.1.** The graph $\Gamma(\omega)$ associated to the permutation $\omega = 24931105867 \in S_{2n}$ is drawn on Figure 1. It has two cycles of length 6 and 4, so $ct(\omega) = (3, 2)$.

<figure><img src="image_1.png" /><figcaption>Fig. 1: The graph $\Gamma(\omega)$ from Example 2.1.</figcaption></figure>

For every $k \ge 1$, we set $\rho(k) := \{2k-1, 2k\}$. The hyperoctahedral group $\mathcal{B}_n$ is the subgroup of $S_{2n}$ of permutations $\omega$ such that, for every $1 \le k \le n$, there exists $1 \le k' \le n$ with $\omega(\rho(k)) = \rho(k')$. In other words $\mathcal{B}_n = \{\omega \in S_{2n} | ct(\omega) = (1^n)\}$. For example, $431265 \in \mathcal{B}_3$.

A $\mathcal{B}_n$-double coset of $S_{2n}$ is the set $\mathcal{B}_n \times \mathcal{B}_n = \{bxb' ; b, b' \in \mathcal{B}_n\}$ for some $x \in S_{2n}$. It is known, see [?, page 401], that two permutations of $S_{2n}$ are in the same $\mathcal{B}_n$-double coset if and only if they have the same coset-type. Thus, if $x \in S_{2n}$ has coset-type $\lambda$, we have:

$$ \mathcal{B}_n \times \mathcal{B}_n = \{y \in S_{2n} \text{ such that } ct(y) = \lambda\}. $$

## 2.3 The Hecke algebra of ($S_{2n}$, $\mathcal{B}_n$)

The symmetric group algebra of $n$ denoted by $\mathbb{C}[S_n]$ is the algebra over $\mathbb{C}$ linearly generated by all permutations of $n$. The group $\mathcal{B}_n \times \mathcal{B}_n$ acts on $\mathbb{C}([S_{2n}])$ by the following action: $(b, b') \cdot x = bxb'$, called the $\mathcal{B}_n$-double action. The Hecke algebra of $(S_{2n}, \mathcal{B}_n)$ denoted by $\mathbb{C}[\mathcal{B}_n \setminus S_{2n}/\mathcal{B}_n]$ is the sub-algebra of $\mathbb{C}[S_{2n}]$ of elements invariant under the $\mathcal{B}_n$-double action. Recall that $\mathcal{B}_n$-double cosets are indexed by
partitions of $n$. Therefore, the set

$$ \{K_{\lambda}(n) : \lambda \text{ proper partition, } |\lambda| \le n\} $$

forms a basis for $\mathbb{C}[B_n \setminus S_{2n}/B_n]$, where $K_{\lambda}(n)$ is the sum of all permutations of $S_{2n}$ with coset-type $\lambda \cup 1^{n-|\lambda|}$. So, for any two proper partitions $\lambda$ and $\delta$ with size at most $n$, there exist complex numbers $\alpha_{\lambda\delta}^{\rho}(n)$ such that:

$$ K_{\lambda}(n) \cdot K_{\delta}(n) = \sum_{\substack{\rho \text{ proper partition} \\ |\rho| \le n}} \alpha_{\lambda\delta}^{\rho}(n) K_{\rho}(n). \qquad (1) $$

## 2.4 Main result

We give in this paper a polynomiality property of the structure coefficients of the Hecke algebra of $(S_{2n}, B_n)$ that appear in (1). More precisely, we prove the following theorem. We will use the standard notation $(n)_k := \frac{n!}{(n-k)!} = n(n-1)\cdots(n-k+1)$.

**Theorem 2.1.** Let $\lambda$, $\delta$ and $\rho$ be three proper partitions, we have:

$$ \alpha_{\lambda\delta}^{\rho}(n) = \begin{cases} 2^n n! f_{\lambda\delta}^{\rho}(n) & \text{if } n \ge |\rho|, \\ 0 & \text{if } n < |\rho|, \end{cases} $$

where $f_{\lambda\delta}^{\rho}(n) = \sum_{j=0}^{|\lambda|+|\delta|-|\rho|} a_j(n - |\rho|)_j$ is a polynomial in $n$ with $a_j \in \mathbb{Q}^+$.

**Example 2.2.** Let us compute the structure coefficient $\alpha_{(2)(2)}^{\emptyset}(n)$. We have:

$$ K_{(2)}(n) = \sum_{\substack{\omega \in S_{2n} \\ \text{ct}(\omega) = (2) \cup (1^{n-2})}} \omega. $$

To find the coefficient of $K_{\emptyset}(n)$ in $K_{(2)}(n) \cdot K_{(2)}(n)$, we fix a permutation with coset-type $(1^n)$, for example $\text{Id}_{2n}$, and we look in how many ways we can obtain $\text{Id}_{2n}$ as a product of two elements $\sigma \cdot \beta$ where $\text{ct}(\sigma) = \text{ct}(\beta) = (2, 1^{n-2})$. Thus we are looking for the number of permutations $\sigma \in S_{2n}$ such that $\text{ct}(\sigma) = \text{ct}(\sigma^{-1}) = (2, 1^{n-2})$. But, for any $\sigma \in S_{2n}$ with $\text{ct}(\sigma) = (2, 1^{n-2})$, its inverse has the same coset-type. Therefore $\alpha_{(2)(2)}^{\emptyset}(n)$ is the number of permutations of coset-type $(2, 1^{n-2})$, which is by [?](page 402)

$$ \frac{(2^n n!)^2}{2^{n-1}(2 \cdot (n-2)!)} = n(n-1)2^n n! $$

## 2.5 Major steps of the proof

The idea of the proof is to build a universal algebra $A_{\infty}$ over $\mathbb{C}$ satisfying the following properties:

1. For every $n \in \mathbb{N}^*$, there exists a morphism of algebras $\theta_n : A_{\infty} \to \mathbb{C}[B_n \setminus S_{2n}/B_n]$.

2. Every element $x$ in $A_{\infty}$ is written in a unique way as an infinite linear combination of elements $T_{\lambda}$, indexed by partitions $\lambda$ and $\delta$, there exist non-negative rational numbers $b_{\lambda\delta}^{\rho}$ such that:

$$ T_{\lambda} * T_{\delta} = \sum_{\rho \text{ partition}} b_{\lambda\delta}^{\rho} T_{\rho}. \qquad (2) $$
3. The morphism $\theta_n$ sends $T_\lambda$ to a multiple of $K_{\bar{\lambda}}(n)$.

To build $\mathcal{A}_\infty$, we introduce new combinatorial objects called *partial bijections*. For every $n \in \mathbb{N}^*$, we construct an algebra $\mathcal{A}_n$ using the set of partial bijections of size $n$. The algebra $\mathcal{A}_\infty$ is defined as the projective limit of this sequence ($\mathcal{A}_n$).

The projection $p_n : \mathcal{A}_\infty \to \mathcal{A}_n$ involves coefficients which are polynomials in $n$. By defining the extension of a partial bijection of $n$ to the set $[2n]$, we construct a morphism from $\mathcal{A}_n$ to $\mathbb{C}[\mathcal{B}_n \setminus S_{2n}/\mathcal{B}_n]$. Its coefficients involve the number $2^n n!$. It turns out that the morphism $\theta_n$ is the composition of those two morphisms:

<figure><img src="image_2.png" /></figure>

The final step consists in applying the chain of morphisms in the diagram above to equation (2).

*Remark.* This method is based on Ivanov and Kerov's one to get the polynomiality of the structure coefficients of the center of the symmetric group algebra (see [?] for more details). Nevertheless, our construction is more complicated, mainly because a partial bijection does not have a unique trivial extension to a given set, see Definition 3.2.

# 3 The partial bijection algebra

In this section we define the set of partial bijections of $n$. With this set, we build the algebras and morphisms that appear in the diagram above.

## 3.1 Definition

We start by defining partial bijections of $n$ and the partial bijection algebra. Then, we introduce the notion of trivial extension of a partial bijection of $n$ and we use it to build a morphism between the partial bijection algebra of $n$ and the symmetric group algebra of $2n$.

For $n \in \mathbb{N}^*$, $\mathbf{P}_n$ denotes the following set:

$$ \mathbf{P}_n := \{\rho(k_1) \cup \cdots \cup \rho(k_i) \mid 1 \le i \le n, 1 \le k_1 < \cdots < k_i \le n\}. $$

*Definition 3.1.* A *partial bijection* of $n$ is a triple $(\sigma, d, d')$ where $d, d' \in \mathbf{P}_n$ and $\sigma : d \to d'$ is a bijection. We denote by $Q_n$ the set of all partial bijections of $n$.

It should be clear that

$$ |Q_n| = s_n = \sum_{k=0}^{n} \binom{n}{k}^2 (2k)! $$

A permutation $\sigma$ of $2n$ can be written as $(\sigma, [2n], [2n])$, so the set $S_{2n}$ can be considered as a subset of $Q_n$.

For any partial bijection $\alpha$, we will use the convention that $\sigma$ (resp. $d, d'$) is the first (resp. second, third) element of the triple defining $\alpha$. The same convention holds for $\tilde{\alpha}, \alpha_i, \hat{\alpha}...$
**Observation.** In the same way as in section 2.2, we can associate to each partial bijection $\alpha$ of $n$ a graph $\Gamma(\alpha)$ with $|d|$ vertices placed on a circle. The exterior (resp. interior) labels are the elements of the set $d$ (resp. $d'$). Since the sets $d$ and $d'$ are in $\mathbb{P}_n$, we can link $2i$ with $2i-1$ as in the case $d=d'=[2n]$. So, the definition of coset-type extends naturally to partial bijection. We denote by $ct(\alpha)$ or $ct(\sigma)$ the coset-type of a partial bijection $\alpha$.

**Definition 3.2.** Let $(\sigma, d, d')$ and $(\tilde{\sigma}, \tilde{d}, \tilde{d}')$ be two partial bijections of $n$. We say that $(\tilde{\sigma}, \tilde{d}, \tilde{d}')$ is a trivial extension of $(\sigma, d, d')$ if:

$$d \subseteq \tilde{d}, \tilde{\sigma}|_{d} = \sigma \text{ and } ct(\tilde{\sigma}) = ct(\sigma) \cup \left(1^{\frac{|\tilde{d} \setminus d|}{2}}\right).$$

We denote by $P_\alpha(n)$ the set of all trivial extensions of $\alpha$ in $Q_n$.

**Lemma 3.1.** Let $\alpha$ be a partial bijection of $n$ and $X$ an element of $\mathbb{P}_n$ such that $d \subseteq X$. The number of trivial extension $\tilde{\alpha}$ such that $\tilde{d} = X$ is

$$(2n - |d|) \cdot (2n - |d| - 2) \cdots (2n - |d| - |X \setminus d| + 2) = 2^{\frac{|X \setminus d|}{2}} \left(n - \frac{|d|}{2}\right)^{\frac{|X \setminus d|}{2}}.$$

We have the same formula for the number of trivial extension $\tilde{\alpha}$ such that $\tilde{d}' = X$.

**Proof.** We proceed by induction on the size of $X \setminus d$. If $|X \setminus d| = 2$, suppose that $X \setminus d = \rho(k)$ for some $k \in [n]$. There are $2n - |d|$ possible values for $\tilde{\sigma}(2k-1)$. If $\tilde{\sigma}(2k-1) = 2k' - 1$ (resp. $2k'$), we have $\tilde{\sigma}(2k) = 2k'$ (resp. $2k' - 1$). So, the number of trivial extensions $\tilde{\alpha}$ such that $\tilde{d} = X$ is $2n - |d|$.

We suppose that we have the result for $|X \setminus d| \le 2(r-1)$. Let $X$ be a set such that $|X \setminus d| = 2r$. We fix an element $2i-1$ of $X \setminus d$. Trivial extensions $\tilde{\alpha}$ such that $\tilde{d} = X$ are obtained as follows:

* first, take all trivial extensions $\alpha_1$ such that $d_1 = X \setminus \rho(i)$. Since $|(X \setminus \rho(i)) \setminus d| = 2(r-1)$, the number of these trivial extensions is by induction $2^{r-1}(n - \frac{|d|}{2})_{r-1}$.

* second, for every trivial extension $\alpha_1$, take all trivial extensions $\tilde{\alpha}_1$ such that $\tilde{d}_1 = X$. For a fixed $\alpha_1$, the number of trivial extensions $\tilde{\alpha}_1$ such that $\tilde{d}_1 = X$ is, by the base case of induction, $2n - |X \setminus \rho(i)| = 2n - |d| - 2r + 2$.

Every trivial extension $\tilde{\alpha}$ is obtained exactly once: as a trivial extension of $\alpha_1$, where $\alpha_1$ is $\tilde{\alpha}_{|X \setminus \rho(i)|}$. Thus, the number of trivial extension $\tilde{\alpha}$ such that $\tilde{d} = X$ is the product:

$$2^{r-1} \left(n - \frac{|d|}{2}\right)_{r-1} \cdot (2n - |d| - 2r + 2) = 2^r \left(n - \frac{|d|}{2}\right)_r.$$

This ends our induction and proves the first part of lemma. The proof of the second part (number of trivial extension $\tilde{\alpha}$ such that $\tilde{d}' = X$) is similar. $\square$

Consider $\mathcal{D}_n = \mathbb{C}[Q_n]$ the vector space with basis $Q_n$. We want to endow it with an algebra structure. Let $\alpha_1$ and $\alpha_2$ be two partial bijections. If $d_1 = d'_2$, we can compose $\alpha_1$ and $\alpha_2$ and we define $\alpha_1 * \alpha_2 = \alpha_1 \circ \alpha_2 = (\sigma_1 \circ \sigma_2, d_2, d'_1)$. Otherwise, we need to extend $\alpha_1$ and $\alpha_2$ to partial bijections $\tilde{\alpha}_1$ and $\tilde{\alpha}_2$ such that $\tilde{d}_1 = \tilde{d}'_2$. Since there exist several trivial extensions of $\alpha_1$ and $\alpha_2$, a natural choice is to take the average of the composition of all possible trivial extensions. Let $E_{\alpha_1}^{\alpha_2}(n)$ be the following set:

$$E_{\alpha_1}^{\alpha_2}(n) := \{(\tilde{\alpha}_1, \tilde{\alpha}_2) \in P_{\alpha_1}(n) \times P_{\alpha_2}(n) \text{ such that } \tilde{d}_1 = \tilde{d}'_2 = d_1 \cup d'_2\}.$$
Elements of $E_{\alpha_1}^{\alpha_2}(n)$ are schematically represented on Figure 2. We define the product of $\alpha_1$ and $\alpha_2$ as follows:

$$ \alpha_1 * \alpha_2 := \frac{1}{|E_{\alpha_1}^{\alpha_2}(n)|} \sum_{(\tilde{\alpha}_1, \tilde{\alpha}_2) \in E_{\alpha_1}^{\alpha_2}(n)} \tilde{\alpha}_1 \circ \tilde{\alpha}_2. \qquad (3) $$

By Lemma 3.1, we can see that $|E_{\alpha_1}^{\alpha_2}(n)| = 2^{\frac{|d_2'|\cdot d_1|}{2}} + \frac{|d_1\cdot d_2'|}{2} \cdot (n - \frac{|d_1'|}{2}) \cdot (n - \frac{|d_2|}{2}) \cdot (\frac{|d_1\cdot d_2'|}{2})$.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Schematic representation of elements of $E_{\alpha_1}^{\alpha_2}(n)$.</figcaption></figure>

**Proposition 3.2.** The product $*$ is associative and $\mathcal{D}_n$ is a (non-unital) algebra.

We shall not present the proof here since it is technical, and uses the same type of arguments as the proof of Proposition 3.3.

**Proposition 3.3.** The following function defines a morphism of algebras:

$$ \psi_n : \mathbb{C}[Q_n] \xrightarrow{\alpha} \mathbb{C}[S_{2n}] \xrightarrow{\frac{1}{2^{n-\frac{|d|}{2}(n-\frac{|d|}{2})!}} \sum_{\tilde{\alpha} \in S_{2n} \cap P_{\alpha}(n)} \hat{\sigma}.} \hat{\sigma} $$

*Proof.* Let $\alpha_1$ and $\alpha_2$ be two basis elements of $\mathbb{C}[Q_n]$. We refer to Figure 2 and denote $2b = |d_2| = |d_2'|$, $2c = |d_1| = |d_1'|$ and $2e = |d_2'| \cap d_1|$. We first prove that:

$$ \sum_{\tilde{\alpha}_1 \in S_{2n} \cap P_{\alpha_1}(n)} \sum_{\tilde{\alpha}_2 \in S_{2n} \cap P_{\alpha_2}(n)} \hat{\sigma}_1 \circ \hat{\sigma}_2 = 2^{n-(b+c-e)}(n-(b+c-e))! \sum_{(\tilde{\alpha}_1, \tilde{\alpha}_2) \in E_{\tilde{\alpha}_2}^{\alpha_1}(n)} \sum_{\tilde{\alpha}_1 \circ \tilde{\alpha}_2 \in S_{2n} \cap P_{\tilde{\alpha}_1 \circ \tilde{\alpha}_2}(n)} \tilde{\sigma}_1 \circ \tilde{\sigma}_2. \quad (4) $$

We fix $(\tilde{\alpha}_1, \tilde{\alpha}_2) \in E_{\tilde{\alpha}_1}^{\tilde{\alpha}_2}(n)$ and $\omega \in S_{2n} \cap P_{\tilde{\alpha}_1 \circ \tilde{\alpha}_2}(n)$, i.e.:

$$ \omega|_{\tilde{d}_2} = \tilde{\sigma}_1 \circ \tilde{\sigma}_2 \text{ and } ct(\omega) = ct(\tilde{\sigma}_1 \circ \tilde{\sigma}_2) \cup (1^{(n-(b+c-e))}). $$

We look for the number of permutations $\tilde{\sigma}_1$ and $\tilde{\sigma}_2$ in $S_{2n} \cap P_{\alpha_1}(n)$ and $S_{2n} \cap P_{\alpha_2}(n)$ such that $\tilde{\sigma}_1 \circ \tilde{\sigma}_2 = \omega$. In this equation, $\tilde{\sigma}_2$ determines $\tilde{\sigma}_1$. But the condition $\omega|_{\tilde{d}_2} = \tilde{\sigma}_1 \circ \tilde{\sigma}_2$ gives the values of $\tilde{\sigma}_2$ on $\tilde{d}_2$ ($\tilde{\sigma}_2(x) = \sigma_2(x)$ if $x \in d_2$ and $\tilde{\sigma}_2(x) = \sigma_1^{-1}(\omega(x))$ if $x \in \tilde{d}_2 \setminus d_2$). Thus, the number of ways to choose $\tilde{\sigma}_2$ is the number of ways to extend trivially $\tilde{\sigma}_2$ to be a permutation of $2n$, which is $2^{n-(b+c-e)}(n-(b+c-e))!$.
by Lemma 3.1. This proves equation (4).

Now we have:

$$
\begin{align}
\psi_n(\alpha_1)\psi_n(\alpha_2) &= \frac{1}{2^{2n-b-c}(n-c)!(n-b)!} \sum_{\widehat{\alpha_1} \in S_{2n} \cap P_{\alpha_1}(n)} \sum_{\widehat{\alpha_2} \in S_{2n} \cap P_{\alpha_2}(n)} \widehat{\sigma_1} \circ \widehat{\sigma_2} \nonumber \\
&= \frac{(n-b-c+e)!}{2^{n-e}(n-c)!(n-b)!} \sum_{(\widehat{\alpha_1}, \widehat{\alpha_2}) \in E_{\widehat{\alpha_2}}^{\alpha_1}(n)} \sum_{\widehat{\alpha_1} \circ \widehat{\alpha_2} \in S_{2n} \cap P_{\widehat{\alpha_1} \circ \widehat{\alpha_2}}(n)} \widehat{\sigma_1} \circ \widehat{\sigma_2}. \tag{5}
\end{align}
$$

On the other hand:

$$
\psi_n(\alpha_1 * \alpha_2) = \frac{1}{2^{b+c-2e}(n-c)_{(b-e)}(n-b)_{(c-e)}} \sum_{(\widehat{\alpha}_1, \widehat{\alpha}_2) \in E_{\widehat{\alpha}_2}^{\alpha_1}(n)} \psi_n((\widehat{\sigma}_1 \circ \widehat{\sigma}_2, \tilde{d}_2, \tilde{d}'_1)).
$$

But

$$
\psi_n((\tilde{\sigma}_1 \circ \tilde{\sigma}_2, \tilde{d}_2, \tilde{d}'_1)) = \frac{1}{2^{n-(b+c-e)}(n-(b+c-e))!} \sum_{\tilde{\alpha}_1 \circ \tilde{\alpha}_2 \in S_{2n} \cap P_{\tilde{\alpha}_1 \circ \tilde{\alpha}_2}(n)} \tilde{\sigma}_1 \circ \tilde{\sigma}_2.
$$

Thus,

$$
\psi_n(\alpha_1 * \alpha_2) = \frac{(n - b - c + e)!}{2^{n-e}(n-c)!(n-b)!} \sum_{(\widehat{\alpha}_1, \widehat{\alpha}_2) \in E_{\widehat{\alpha}_2}^{\alpha_1}(n)} \sum_{\widehat{\alpha}_1 \circ \widehat{\alpha}_2 \in S_{2n} \cap P_{\widehat{\alpha}_1 \circ \widehat{\alpha}_2}(n)} \widehat{\sigma}_1 \circ \widehat{\sigma}_2. \quad (6)
$$

Comparing equations (5) and (6), we see that for any two partial bijections $\alpha_1$ and $\alpha_2$ of $n$, we have
$\psi_n(\alpha_1 * \alpha_2) = \psi_n(\alpha_1)\psi_n(\alpha_2)$. In other words, $\psi_n$ is a morphism of algebras. $\square$

3.2 Action of $\mathcal{B}_n \times \mathcal{B}_n$ on $\mathcal{D}_n$

In this section, we construct the algebra $\mathcal{A}_n$ as the algebra of invariant elements by an action of $\mathcal{B}_n \times \mathcal{B}_n$
on $\mathcal{D}_n$.

*Definition* 3.3. The group $\mathcal{B}_n \times \mathcal{B}_n$ acts on $Q_n$ by:

$$
(a, b) \bullet (\sigma, d, d') = (a \sigma b^{-1}, b(d), a(d')),
$$

for any $(a, b) \in \mathcal{B}_n \times \mathcal{B}_n$ and $(\sigma, d, d') \in \mathcal{Q}_n$.

We can extend this action by linearity to get an action of $\mathcal{B}_n \times \mathcal{B}_n$ on $\mathcal{D}_n$. This action is compatible with the product of $\mathcal{Q}_n$. Namely, we can prove that, for any $(a, b) \in \mathcal{B}_n \times \mathcal{B}_n$ and for any partial bijections $\alpha_1, \alpha_2$ of $n$, we have:

$$
(a, b) \bullet (\alpha_1 * \alpha_2) = ((a, id) \bullet \alpha_1) * ((id, b) \bullet \alpha_2). \quad (7)
$$

We consider the set $\mathcal{A}_n$ of invariant elements by the action of $\mathcal{B}_n \times \mathcal{B}_n$ on $\mathcal{D}_n$:

$$
\mathcal{A}_n = \mathcal{D}_n^{\mathcal{B}_n \times \mathcal{B}_n} = \{x \in \mathcal{D}_n \mid (a, b) \bullet x = x \text{ for any } (a, b) \in \mathcal{B}_n \times \mathcal{B}_n\}.
$$

Due to equation (7), we can see that $\mathcal{A}_n$ is an algebra. The following result is easy to check.
**Proposition 3.4.** The elements $(S_{\lambda,n})_{|\lambda|=r \le n}$, where $S_{\lambda,n} = \sum_{\alpha \in Q_n, ct(\alpha)=\lambda} \alpha$, form a basis for the algebra $\mathcal{A}_n$.

**Corollary 3.5.** If $\lambda$ and $\delta$ are two partitions such that $|\lambda|, |\delta| \le n$, there exist unique constants $c_{\lambda\delta}^{\rho}(n) \in \mathbb{C}$ such that:

$$S_{\lambda,n} * S_{\delta,n} = \sum_{\substack{\rho \text{ partition} \\ \max(|\lambda|,|\delta|) \le |\rho| \le \min(|\lambda|+|\delta|,n)}} c_{\lambda\delta}^{\rho}(n)S_{\rho,n}.$$

*Proof.* We only have to prove the inequalities on the size of $\rho$. Let $\alpha_1$ and $\alpha_2$ be two partial bijections of $n$ with coset-type $\lambda$ and $\delta$. By definition (see Figure 2), every partial bijection of $n$ that appears in the sum of the product $\alpha_1 * \alpha_2$ has some coset-type $\rho$ with $|\rho| = \frac{|d_1 \cup d_2'|}{2}$. But

$$\max(\frac{|d_1|}{2}, \frac{|d_2'|}{2}) = \max(|\lambda|, |\delta|) \le |\rho| = \frac{|d_1 \cup d_2'|}{2} \le \frac{|d_1| + |d_2'|}{2} = |\lambda| + |\delta|. \quad \square$$

**Lemma 3.6.** Let $\lambda$ be a partition such that $|\lambda| = r \le n$. We have:

$$\psi_n(S_{\lambda,n}) = \frac{1}{2^{n-|\lambda|}(n-|\lambda|)!} \binom{n-|\bar{\lambda}|}{m_1(\lambda)} K_{\bar{\lambda}}(n).$$

*Proof.* For a partial bijection $\alpha \in Q_n$ such that $ct(\alpha) = \lambda$, we have:

$$\psi_n(\alpha) = \frac{1}{2^{n-|\lambda|}(n-|\lambda|)!} \sum_{\hat{\alpha} \in S_{2n} \cap P_\alpha(n)} \hat{\sigma}.$$

To conclude the proof, note that for a fixed permutation $\omega \in K_{\bar{\lambda}}(n)$, the number of partial bijections $\alpha \in A_{\lambda,n}$ such that $\omega$ is a trivial extension of $\alpha$ is $\binom{n-|\bar{\lambda}|}{m_1(\lambda)}$. $\square$

This lemma implies that $\psi_n(\mathcal{A}_n) \subseteq \mathbb{C}[\mathcal{B}_n/S_{2n}\mathcal{B}_n]$. The morphism $\mathcal{A}_n \to \mathbb{C}[\mathcal{B}_n/S_{2n}\mathcal{B}_n]$ mentioned in Section 2.5 is the morphism $\psi_{n|_{\mathcal{A}_n}}$.

## 3.3 Projective limits

In this paragraph, we first show that the sequence $(\mathcal{A}_n)$ admits a projective limit $\mathcal{A}_\infty$ by giving a morphism from $\mathcal{A}_{n+1}$ to $\mathcal{A}_n$. Then, we prove in Proposition 3.8 that every element of $\mathcal{A}_\infty$ is written in a unique way as infinite linear combination of elements indexed by partitions.

**Lemma 3.7.** The function $\varphi_n$ defined as follows:

$$\varphi_n : \begin{array}{rcl} \mathcal{A}_{n+1} & \to & \mathcal{A}_n \\ S_{\lambda,n+1} & \mapsto & \left\{ \begin{array}{ll} \frac{n+1}{(n+1-|\lambda|)}S_{\lambda,n} & \text{if } |\lambda| = r < n+1, \\ 0 & \text{if } |\lambda| = n+1, \end{array} \right. \end{array}$$

is a morphism of algebras.

*Proof.* Omitted for brevity. $\square$
Let $\mathcal{A}_{\infty}$ be the projective limit of $(\mathcal{A}_n, \varphi_n)$:

$$ \mathcal{A}_{\infty} = \{(a_n)_{n \ge 1} \mid \text{for every } n \ge 1, a_n \in \mathcal{A}_n \text{ and } \varphi_n(a_{n+1}) = a_n\}. $$

For every partition $\lambda$, we define the sequence $T_{\lambda}$ as follows:

$$ T_{\lambda} = (T_{\lambda})_{n \ge 1} = \begin{cases} 0 & \text{if } n < |\lambda|, \\ \frac{1}{\binom{n}{|\lambda|}} S_{\lambda,n} & \text{if } n \ge |\lambda|. \end{cases} $$

We can prove easily the following proposition.

**Proposition 3.8.** Every element $a \in \mathcal{A}_{\infty}$ is written in a unique way as infinite linear combination of elements $T_{\lambda}$.

This proposition shows that the algebra $\mathcal{A}_{\infty}$ satisfies the second property required in section 2.5. In particular, $T_{\lambda} * T_{\delta}$ writes as linear combination of elements $T_{\rho}$. We can be more precise.

**Corollary 3.9.** Let $\lambda$ and $\delta$ be two partitions. There exist unique constants $b_{\lambda\delta}^{\rho} \in \mathbb{Q}^{+}$ such that:

$$ T_{\lambda} * T_{\delta} = \sum_{\substack{\rho \text{ partition} \\ \max(|\lambda|, |\delta|) \le |\rho| \le |\lambda| + |\delta|}} b_{\lambda\delta}^{\rho} T_{\rho}. $$

*Proof.* The conditions on the size of partitions $\rho$ in the sum index are obtained by Corollary 3.5. We may check that $b_{\lambda\delta}^{\rho} = \frac{c_{\lambda\delta}^{\rho}(|\rho|)}{\binom{|\rho|}{|\lambda|} \binom{|\rho|}{|\delta|}}$, which explains that $b_{\lambda\delta}^{\rho} \in \mathbb{Q}^{+}$. $\square$

# 4 Proof of Theorem 2.1

In the previous section, we built all algebras and morphisms that we need in order to prove Theorem 2.1. Let $\lambda$ and $\delta$ be two proper partitions, by Corollary 3.9, we have:

$$ T_{\lambda} * T_{\delta} = \sum_{\substack{\rho \text{ partition} \\ \max(|\lambda|, |\delta|) \le |\rho| \le |\lambda| + |\delta|}} b_{\lambda\delta}^{\rho} T_{\rho}. $$

Recall that this is an equality of sequences. Taking the $n$-th term, we have:

$$ \frac{1}{\binom{n}{|\lambda|}} S_{\lambda,n} * \frac{1}{\binom{n}{|\delta|}} S_{\delta,n} = \sum_{\substack{\rho \text{ partition} \\ \max(|\lambda|, |\delta|) \le |\rho| \le \min(|\lambda| + |\delta|, n)}} b_{\lambda\delta}^{\rho} \frac{1}{\binom{n}{|\rho|}} S_{\rho,n}. $$

By applying $\psi_n$ we obtain (see Lemma 3.6):

$$ \frac{1}{2^{n-|\lambda|(n-|\lambda|)!}} K_{\lambda}(n) \cdot \frac{1}{2^{n-|\delta|(n-|\delta|)!}} K_{\delta}(n) = \sum_{\substack{\rho \text{ partition} \\ \max(|\lambda|, |\delta|) \le |\rho| \le \min(|\lambda| + |\delta|, n)}} b_{\lambda\delta}^{\rho} \frac{\binom{n}{|\lambda|} \binom{n}{|\delta|}}{n^2 2^{n-|\rho|(n-|\rho|)!}} K_{\bar{\rho}}(n). $$
After simplification, we get:

$$K_{\lambda}(n) \cdot K_{\delta}(n) = \sum_{\substack{\rho \\ \max(|\lambda|, |\delta|) \le |\rho| \le \min(|\lambda| + |\delta|, n)}} b_{\lambda\delta}^{\rho} \frac{(|\rho|)|\bar{\rho}|}{|\lambda|!|\delta|!} 2^{n+|\rho|-|\lambda|-|\delta|} n!(n - |\bar{\rho}|)_{m_1(\rho)} K_{\bar{\rho}}(n).$$

Fact. Any partition $\rho$ such that $|\rho| \le \min(|\lambda| + |\delta|, n)$ can be written in a unique way as $\rho = \tau \cup (1^j)$, where $\tau$ is a proper partition and $j \le \min(|\lambda| + |\delta|, n) - |\tau|$.

Using this fact, the product can be written as follows:

$$K_{\lambda}(n) \cdot K_{\delta}(n) = \sum_{\substack{\tau \\ |\tau| \le \min(|\lambda| + |\delta|, n)}} \alpha_{\lambda\delta}^{\tau}(n) K_{\tau}(n),$$

where

$$\alpha_{\lambda\delta}^{\tau}(n) = \frac{1}{|\lambda|!|\delta|!} \sum_{j=0}^{\min(|\lambda|+|\delta|, n)-|\tau|} b_{\lambda\delta}^{\tau \cup (1^j)} n!(n - |\tau|)_j (|\tau| + j)_{|\tau|} 2^{n+|\tau|+j-|\lambda|-|\delta|} \\ = \frac{2^n n!}{|\lambda|!|\delta|!} \sum_{j=0}^{|\lambda|+|\delta|-|\tau|} b_{\lambda\delta}^{\tau \cup (1^j)} (n - |\tau|)_j (|\tau| + j)_{|\tau|} 2^{|\tau|+j-|\lambda|-|\delta|}.$$

The change of sum index in the last equality comes from the fact that if $n < |\lambda| + |\delta|$, we have:

$$(n - |\tau|)_j = 0 \text{ for any } j \text{ with } n - |\tau| < j \le |\lambda| + |\delta| - |\tau|.$$

This ends the proof of Theorem 2.1.

**Corollary 4.1.** If $\lambda$, $\delta$ and $\rho$ are three proper partitions such that $|\rho| = |\lambda| + |\delta|$, then:

$$\alpha_{\lambda\delta}^{\rho}(n) = b_{\lambda\delta}^{\rho} \frac{|\rho|!}{|\lambda|!|\delta|!} 2^{n} n! = c_{\lambda\delta}^{\rho}(|\rho|) \frac{|\lambda|!|\delta|!}{(|\lambda| + |\delta|)!} 2^{n} n!.$$

## References