# SymmetricGroupCombinatoricFunctions¶

sgcf.spad line 1 [edit on github]

SymmetricGroupCombinatoricFunctions contains combinatoric functions concerning symmetric groups and representation theory: list young tableaus, improper partitions, subsets bijection of Coleman.

- coleman: (List Integer, List Integer, List Integer) -> Matrix Integer
`coleman(alpha, beta, pi)`

: there is a bijection from the set of matrices having nonnegative entries and row sums*alpha*, column sums*beta*to the set of*Salpha - Sbeta*double cosets of the symmetric group*Sn*. (*Salpha*is the Young subgroup corresponding to the improper partition*alpha*). For a representing element*``pi``* of such a double coset, coleman(``alpha``, ``beta``, ``pi``) generates the Coleman-matrix corresponding to *alpha, beta, ``pi``*. Note: The permutation *``pi``* of *{1, 2, …, n}*has to be given in list form. Note: the inverse of this map is*inverseColeman*(if *`pi`

* is the lexicographical smallest permutation in the coset). For details see James/Kerber.

- inverseColeman: (List Integer, List Integer, Matrix Integer) -> List Integer
`inverseColeman(alpha, beta, C)`

: there is a bijection from the set of matrices having nonnegative entries and row sums*alpha*, column sums*beta*to the set of*Salpha - Sbeta*double cosets of the symmetric group*Sn*. (*Salpha*is the Young subgroup corresponding to the improper partition*alpha*). For such a matrix`C`

, inverseColeman(`alpha`

,`beta`

,`C`

) calculates the lexicographical smallest*``pi``* in the corresponding double coset. Note: the resulting permutation *``pi``* of *{1, 2, …, n}*is given in list form. Notes: the inverse of this map is*coleman*. For details, see James/Kerber.

- listYoungTableaus: List Integer -> List Matrix Integer
`listYoungTableaus(lambda)`

where*lambda*is a proper partition generates the list of all standard tableaus of shape*lambda*by means of lattice permutations. The numbers of the lattice permutation are interpreted as column labels. Hence the contents of these lattice permutations are the conjugate of*lambda*. Notes: the functions*nextLatticePermutation*and*makeYoungTableau*are used. The entries are from*0, …, n-1*.

- makeYoungTableau: (List Integer, List Integer) -> Matrix Integer
`makeYoungTableau(lambda, gitter)`

computes for a given lattice permutation*gitter*and for an improper partition*lambda*the corresponding standard tableau of shape*lambda*. Notes: see*listYoungTableaus*. The entries are from*0, …, n-1*.

- nextColeman: (List Integer, List Integer, Matrix Integer) -> Matrix Integer
`nextColeman(alpha, beta, C)`

generates the next Coleman matrix of column sums*alpha*and row sums*beta*according to the lexicographical order from bottom-to-top. The first Coleman matrix is achieved by*C=new(1, 1, 0)*. Also,*new(1, 1, 0)*indicates that`C`

is the last Coleman matrix.

- nextLatticePermutation: (List Integer, List Integer, Boolean) -> List Integer
`nextLatticePermutation(lambda, lattP, constructNotFirst)`

generates the lattice permutation according to the proper partition*lambda*succeeding the lattice permutation*lattP*in lexicographical order as long as*constructNotFirst*is`true`

. If*constructNotFirst*is`false`

, the first lattice permutation is returned. The result*[]*indicates that*lattP*has no successor.

- nextPartition: (List Integer, Vector Integer, Integer) -> Vector Integer
`nextPartition(gamma, part, number)`

generates the partition of*number*which follows*part*according to the right-to-left lexicographical order. The partition has the property that its components do not exceed the corresponding components of*gamma*. the first partition is achieved by*part=[]*. Also,*[]*indicates that*part*is the last partition.

- nextPartition: (Vector Integer, Vector Integer, Integer) -> Vector Integer
`nextPartition(gamma, part, number)`

generates the partition of*number*which follows*part*according to the right-to-left lexicographical order. The partition has the property that its components do not exceed the corresponding components of*gamma*. The first partition is achieved by*part=[]*. Also,*[]*indicates that*part*is the last partition.

- numberOfImproperPartitions: (Integer, Integer) -> Integer
`numberOfImproperPartitions(n, m)`

computes the number of partitions of the nonnegative integer`n`

in`m`

nonnegative parts with regarding the order (improper partitions). Example:*numberOfImproperPartitions (3, 3)*is 10, since*[0, 0, 3], [0, 1, 2], [0, 2, 1], [0, 3, 0], [1, 0, 2], [1, 1, 1], [1, 2, 0], [2, 0, 1], [2, 1, 0], [3, 0, 0]*are the possibilities. Note: this operation has a recursive implementation.

- subSet: (Integer, Integer, Integer) -> List Integer
`subSet(n, m, k)`

calculates the*k*`-`

th*m*-subset of the set*0, 1, …, (n-1)*in the lexicographic order considered as a decreasing map from*0, …, (m-1)*into*0, …, (n-1)*. See`S`

.`G`

. Williamson: Theorem 1.60. Error: if not*(0 <= m <= n and 0 < = k < (n choose m))*.

- unrankImproperPartitions0: (Integer, Integer, Integer) -> List Integer
`unrankImproperPartitions0(n, m, k)`

computes the*k*`-`

th improper partition of nonnegative`n`

in`m`

nonnegative parts in reverse lexicographical order. Example:*[0, 0, 3] < [0, 1, 2] < [0, 2, 1] < [0, 3, 0] < [1, 0, 2] < [1, 1, 1] < [1, 2, 0] < [2, 0, 1] < [2, 1, 0] < [3, 0, 0]*. Error: if`k`

is negative or too big. Note: counting of subtrees is done by numberOfImproperPartitions.

- unrankImproperPartitions1: (Integer, Integer, Integer) -> List Integer
`unrankImproperPartitions1(n, m, k)`

computes the*k*`-`

th improper partition of nonnegative`n`

in at most`m`

nonnegative parts ordered as follows: first, in reverse lexicographically according to their non-zero parts, then according to their positions (i.e. lexicographical order using*subSet*:*[3, 0, 0] < [0, 3, 0] < [0, 0, 3] < [2, 1, 0] < [2, 0, 1] < [0, 2, 1] < [1, 2, 0] < [1, 0, 2] < [0, 1, 2] < [1, 1, 1]*). Note: counting of subtrees is done by*numberOfImproperPartitionsInternal*.