A combinatorial approach to the double cosets of the symmetric group with respect to Young subgroups (Q1815402)

A bijective correspondence is constructed between double cosets of Young subgroups \(H\) and \(K\) of the symmetric group \(S_n\) and certain lists of integers of length \(n\). It is known [see Chapter 1.3 of \textit{G. D. James} and \textit{A. Kerber}, The representation theory of the symmetry group (Addison-Wesley, 1981; Zbl 0491.20010)] that these double cosets correspond to matrices of non-negative integers with row and column sums determined by \(H\) and \(K\). The list corresponding to such a matrix is obtained by reading the entries down the columns and from left to right, recording an entry \(a\) in row \(i\) of the matrix by adding \(a\) terms equal to \(i\) to the list. The parts of the list arising from the columns are then written as the rows of an array, whose shape is determined by \(K\) and content by \(H\). In terms of these arrays, an algorithm is given for computing the number of double cosets recursively. In the case where \(H\) and \(K\) are the row and column stabilisers of a Young tableau, it is shown that there is a unique element of minimum length in each double coset, and an algorithm is given for finding this element.