ABSTRACT
The study of permutations is of central importance to mathematics. Computation with permutation groups has typically been limited to systems such as GAP and Magma. In this paper we describe cl-permutation, a system for doing computations with permutation groups in ANSI Common Lisp. Homomesies, a recent concept introduced by Propp and Roby, are elaborated upon from a group-theoretic and linear-algebraic perspective. As a result, algorithms for manipulating them and better understanding their structure are presented. Finally, these algorithms are realized using cl-permutation.
- Maxima, a Computer Algebra System. Version 5.25.1, 2011. http://maxima.sourceforge.net.Google Scholar
- American National Standards Institute and Information Technology Industry Council. American National Standard for Information Technology: programming language --- Common LISP. American National Standards Institute, 1430 Broadway, New York, NY 10018, USA, 1996. Approved December 8, 1994.Google Scholar
- W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system. I. The user language. J. Symbolic Comput., 24(3-4):235--265, 1997. Computational algebra and number theory (London, 1993). Google ScholarDigital Library
- The GAP Group. GAP -- Groups, Algorithms, and Programming, Version 4.7.4, 2014.Google Scholar
- D. E. Knuth. Efficient representation of perm groups. Combinatorica, 11(1):33--43, 1991.Google ScholarCross Ref
- J. Propp and T. Roby. Homomesy in products of two chains. DMTCS Proceedings, 2013.Google Scholar
- Á. Seress. Permutation Group Algorithms. Cambridge Tracts in Mathematics. Cambridge University Press, 2003.Google Scholar
- C. C. Sims. Computation with permutation groups. In Proceedings of the Second ACM Symposium on Symbolic and Algebraic Manipulation, SYMSAC '71, pages 23--28, New York, NY, USA, 1971. ACM. Google ScholarDigital Library
- W. Stein et al. Sage Mathematics Software (Version 6.2). The Sage Development Team, 2014. http://www.sagemath.org.Google Scholar
Index Terms
- Efficient Finite Permutation Groups and Homomesy Computation in Common Lisp
Recommendations
Proofs and generalizations of a homomesy conjecture of Propp and Roby
Let G be a group acting on a set X of combinatorial objects, with finite orbits, and consider a statistic : X C . Propp and Roby defined the triple ( X , G , ) to be homomesic if for any orbits O 1 , O 2 , the average value of the statistic is the same, ...
On the combinatorics of derangements and related permutations
Highlights- Provide a bijection combinatorial proof for the facts that The number of derangements of length n equals the number of permutations of length n that have ...
AbstractA derangement is a permutation in which no entry is at its original position. The number of derangements of [ n ] is called the “derangement number” or “de Montmort number”, and is denoted by D n. The sequence { D n } enumerates, in ...
Transitive Permutation Groups of Prime-Squared Degree
We explicitly determine all of the transitive groups of degree i>p2, i>p a prime, whose Sylow i>p-subgroup is not isomorphic to the wreath product {\Bbb Z}_p\wr{\Bbb Z}_p . Furthermore, we provide a general description of the transitive groups ...
Comments