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.