SymmetricGroupCombinatoricFunctionsΒΆ

sgcf.spad line 1

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.