Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Cycle index
Summary
In combinatorial mathematics a cycle index is a polynomial in several variables which is structured in such a way that information about how a group of permutations acts on a set can be simply read off from the coefficients and exponents. This compact way of storing information in an algebraic form is frequently used in combinatorial enumeration.
Each permutation π of a finite set of objects partitions that set into cycles; the cycle index monomial of π is a monomial in variables a1, a2, ... that describes the cycle type of this partition: the exponent of ai is the number of cycles of π of size i. The cycle index polynomial of a permutation group is the average of the cycle index monomials of its elements. The phrase cycle indicator is also sometimes used in place of cycle index.
Knowing the cycle index polynomial of a permutation group, one can enumerate equivalence classes due to the group's action. This is the main ingredient in the Pólya enumeration theorem. Performing formal algebraic and differential operations on these polynomials and then interpreting the results combinatorially lies at the core of species theory.
A bijective map from a set X onto itself is called a permutation of X, and the set of all permutations of X forms a group under the composition of mappings, called the symmetric group of X, and denoted Sym(X). Every subgroup of Sym(X) is called a permutation group of degree |X|. Let G be an abstract group with a group homomorphism φ from G into Sym(X). The , φ(G), is a permutation group. The group homomorphism can be thought of as a means for permitting the group G to "act" on the set X (using the permutations associated with the elements of G). Such a group homomorphism is formally called a group action and the image of the homomorphism is a permutation representation of G. A given group can have many different permutation representations, corresponding to different actions.
Suppose that group G acts on set X (that is, a group action exists).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.