Fix a Young subgroup $H\_\lambda \subseteq \mathcal S\_n$, where $\lambda \vdash n$ is a partition of $n$ with $k$ blocks. Inside the group algebra $\mathbb C[\mathcal S\_n]$, consider the idempotent 
$$\varepsilon = \frac{1}{|H\_\lambda|}\sum\_{h \in H\_\lambda} h.$$


The double cosets $H\_\lambda \backslash \mathcal S\_n / H\_\lambda$ are indexed by matrices $k \times k$ with non-negative entries and row (resp. column) sums given by the blocks of $\lambda$ (see Richard Stanley's answer to [Number of double cosets of a Young subgroup](https://mathoverflow.net/questions/182150/number-of-double-cosets-of-a-young-subgroup)). For a representative $\alpha\_x \in \mathcal S\_n$ of a given coset, define the element 
$$\sigma\_x = \varepsilon \alpha\_x \varepsilon,$$
which is an element of the corresponding Hecke algebra; above, $x$ is a matrix with non-negative entries with row and column sums given by $\lambda$.


I would like to know how to find the **structure constants** of the Hecke algebra, i.e. the coefficients $\gamma\_{x,y}^z$ such that 
$$\sigma\_x \cdot \sigma\_y = \sum\_z \gamma\_{x,y}^z \sigma\_z.$$


*Example*


In the case $\mathcal S\_p \times \mathcal S\_q \subseteq \mathcal S\_{n=p+q}$, the double cosets can be indexed by integers $0 \leq x \leq \min(p,q)$, where $x$ represents the number of elements of $[1,p]$ mapped to $[p+1,p+q]$. Using basic combinatorics, I can show that 
$$\sigma\_x \sigma\_1 = \frac{1}{pq} \left( (p-x)(q-x) \sigma\_{x+1} + x^2 \sigma\_{x-1} + (x(p-x)+x(q-x))\sigma\_x \right).$$



Structure constants for the double coset algebra of a Young subgroup
There is a combinatorial rule for the structure constants. It appears in Section 2 of <https://arxiv.org/abs/1104.1959>, although it is not immediately clear that it is indeed what you are looking for.


Suppose that $V$ is a vector space of dimension at least $l(\lambda)$. Then in the setting of Schur-Weyl duality, there is a simultaneous action of $GL(V)$ and $S\_n$ on $V^{\otimes n}$. We note that the $\lambda$-weight space of $V^{\otimes n}$ is precisely the permutation module $M^\lambda$ induced from the trivial module of $H\_\lambda$.


As a representation of $\mathbb{C}S\_n$, $\mathbb{C}S\_n \varepsilon$ is $M^\lambda$. So the Hecke algebra you are implicitly considering is
$$
\mathrm{End}\_{\mathbb{C}S\_n}(M^\lambda).
$$
This is related to $\mathrm{End}\_{\mathbb{C}S\_n}(V^{\otimes n})$, which is why the Schur algebra (appearing in the paper) is relevant here.


However, the most convenient basis is given by
$$
\xi\_x = \frac{1}{|H\_\lambda|}\sum\_{g \in H\_\lambda \alpha\_x H\_\lambda} g,
$$
which is to say, double-coset sums divided by $|H\_\lambda|$, which is a different normalisation to your elements $\sigma\_x$. Explicitly,
$$
\sigma\_x = \frac{|H\_\lambda \cap \alpha\_x H\_\lambda \alpha\_x^{-1}|}{|H\_\lambda|}\xi\_x,
$$
and it is a standard lemma that if $\alpha\_x$ is a minimal-length double-coset representative, $H\_\lambda \cap \alpha\_x H\_\lambda \alpha\_x^{-1}$ is also a Young subgroup, so its size can easily be written down.


Note that the double cosets $H\_\lambda \alpha\_x H\_\lambda$ are indexed by square matrices of size $l(\lambda)$ whose row and column sums are $\lambda$. The $(i,j)$-th entry counts how many elements of $\{1,2,\ldots,n\}$ permuted by $S\_{\lambda\_j}$ are mapped by some (and therefore any) element of the double coset to elements permuted by $S\_{\lambda\_i}$.


So we let the indexing variables $x,y,z$ be matrices of that form, and write them with subscripts (e.g. $x\_{ij}$) to refer to the entries of the corresponding matrices.


To calculate the coefficient of $\xi\_z$ in $\xi\_x \xi\_y$, we consider "cubic matrices of size $l(\lambda)$" (i.e. $l(\lambda) \times l(\lambda) \times l(\lambda)$ 3-tensors) $A\_{ijk}$ with entries in $\mathbb{Z}\_{\geq 0}$. We require that
$$
\sum\_i A\_{ijk} = x\_{jk}
$$
$$
\sum\_j A\_{ijk} = z\_{ik}
$$
$$
\sum\_k A\_{ijk} = y\_{ij}
$$
Then the coefficient is
$$
\sum\_A \prod\_{i,k}\frac{(\sum\_j A\_{ijk})!}{\prod\_j A\_{ijk}!},
$$
subject to the conditions on $A$ already mentioned.


Let's check this for your example. We take the matrix $x$ to be
$$
\begin{bmatrix}
 p-x & x \\
 x & q-x
\end{bmatrix}.
$$
(Here there is an conflict of notation between the label of the double coset, and the number of elements it "mixes" between $S\_{p}$ and $S\_q$.) We take the matrix $y$ to be
$$
\begin{bmatrix}
 p-1 & 1 \\
 1 & q-1
\end{bmatrix}.
$$
So we are going to calculate $\xi\_x \xi\_y$. Typsetting a 3-tensor $A\_{ijk}$ is tricky, so let's consider the "slices" $A\_{i1k}$ and $A\_{i2k}$ separately. The row-sums of $A\_{i1k}$ are $(p-x,x)$ and the column sums are $(p-1,1)$. There are two possibilities for $A\_{i1l}$:
$$
\begin{bmatrix}
 p-x & 0 \\
 x-1 & 1
\end{bmatrix},
\begin{bmatrix}
 p-x-1 & 1 \\
 x & 0
\end{bmatrix}.
$$
Similarly, for $A\_{i2k}$ we have row-sums $(x,q-x)$ and column sums $(1,q-1)$, so we get
$$
\begin{bmatrix}
 1 & x-1 \\
 0 & q-x
\end{bmatrix},
\begin{bmatrix}
 0 & x \\
 1 & q-x-1
\end{bmatrix}.
$$
So there are four ways of combining these into the full tensor $A\_{ijk}$. For each of these, we get a multiple of $\xi\_z$, where $z = A\_{i1k}+A\_{12k}$, and the scalar multiple is a product of (very simple) binomial coefficients.


Choosing the first option for each of $A\_{i1k}$ and $A\_{i2k}$ gives $z$ with off-diagonal entries $x-1$, and the scalar multiple is $(p-x+1)(q-x+1)$.


Choosing the last of each gives $z$ with off-diagonal entries $x+1$, and the scalar multiple is $(x+1)^2$.


Each of the other two choices gives $z$ with off-diagonal entries $x$, and the scalar multiples are $x(p-x)$ and $x(q-x)$.


To recover your equation, we just need to know that if $z$ has off-diagonal entries equal to $r$, then 
$$
\sigma\_r = \frac{1}{{p \choose r}{q \choose r}} \xi\_r,
$$
so for example, you can immediately multiply your equation by $pq$ to turn $\sigma\_1$ into $\xi\_y$ (and clear a denominator on the right).


I have left out some details to keep this post from being egregiously long, but I would be happy to explain further or give references if it would be helpful.


What is described in this post is just the tip of the iceberg, for example it's possible to interpolate these structure constants to define certain "permutation module Deligne Categories", such as in <https://arxiv.org/abs/1909.04100>.


