An algorithm for the multiplication of symmetric polynomials

ABSTRACT

Although the cycle index polynomial for a permutation group can often be easily determined, expansion of the figure counting series in a Po´lya enumeration presents computational difficulties for object sets with higher degrees of symmetry and more than modest size. An algorithm that does not require algebraic symbol manipulation is derived for multiplying symmetric polynomials represented by partitions. Because the repetitive identification and collection of common terms are eliminated and storage requirements reduced, this algorithm is useful in rapidly expanding the figure counting series in such Po´lya enumeration problems as the counting of chemical isomers.

REFERENCES

• 1: GARAVELLI, J. S., AND LEONARD, J.E. Improvements in the computer enumeration of permutation isomers. Comput. Chem. 9, 2 (1985), 133-147.
• 2: GOULD, H. W. Combinatorial Identities, Revised Edition. Morgantown, W.V., 1972, p. 27, eq. 3.38.
• 3: Emi Lauer, Algorithms for symmetrical polynomials, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.242-247, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806342]
• 4: LIFSCHITZ, V., AND PITTEL, B. The number of increasing subsequences of the random permutation. J. Comb. Theory Series A 31, 1 (July 1981), 1-20.
• 5: NIJENHUIS, A., AND WILF, H.S. Combinatorial Algorithms. Academic Press, New York, 1975, pp. 21-34, 49-59.
• 6: George Pólya , R. C. H Read, Combinatorial enumeration of groups, graphs, and chemical compounds, Springer-Verlag New York, Inc., New York, NY, 1987
• 7: READ, R.C. The enumeration of acyclic chemical compounds. In Chemical Applications of Graph Theory, A. T. Balaban, Ed. Academic Press, London, 1976, Chap. 4, pp. 25-61.
• 8: WELLS, M.B. Elements of Combinatorial Computing. Pergamon, Oxford, 1971, p. 152.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory

Keywords:
Po´lya enumeration, cycle index polynomial, integer partitions, symbolic algebra, symmetric polynomials