Dear friends,

some time ago I shared a story here on the use of Maple to compute the cycle index of the induced action on the edges of an ordinary graph of the symmetric group permuting the vertices and the use of the Polya Enumeration Theorem to count non-isomorphic graphs by the number of edges. It can be found at the following Mapleprimes link.

I am writing today to alert you to another simple Maple program that is closely related and demonstrates Maple's capability to implement concepts from group theory and Polya enumeration. This link at Math.Stackexchange.com shows how to use the cycle index of the induced action by the symmetric group permuting vertices on the edges of a multigraph that includes loops to count set partitions of multisets containing two instances of n distinct types of items. The sequence that corresponds to these set partitions is OEIS A020555 where it is pointed out that we can equivalently count multigraphs with n labeled i.e. distinct edges where the vertices of the graph represent the multisets of the multiset partition and are connected by an edge k if the two instances of the value k are included in the sets represented by the two vertices that constitute the edge. The problem then reduces to a simple substitution into the aforementioned cycle index of a polynomial representing the set of labels on an edge including no labels on an edge that is not included.

This computation presents a remarkable simplicity while also implementing a non-trivial application of Polya counting. It is hoped that MaplePrimes users will enjoy reading this program, possibly profit from some of the techniques employed and be motivated to use Maple in their work on combinatorics problems.

Best regards,

Marko Riedel