Pólya Enumeration Theorem
Prerequisite: Permutations and Arrangements
Introduction
Pólya enumeration theorem is commonly used to solve counting problems involving "essentially distinct" configurations.
This article may involve group theory
This article may involve concepts from group theory. It will provide brief explanations of the group theory concepts involved to help readers unfamiliar with the subject understand and apply the Pólya enumeration theorem. For rigorous definitions and discussions on group theory, please refer to Basic Concepts of Abstract Algebra, Group Theory, and other related sections.
Space Symmetry Group, Symmetric Group, and Permutation Group
This article will inevitably use the names of these three types of groups. Although they may easily cause confusion, they indeed refer to different concepts. Given a geometric structure, its symmetry operations refer to geometric transformations that map the structure onto itself. The space symmetry group (symmetry group) is the set of all such symmetry operations. The symmetric group is the set of all permutations on a given set. A permutation group is a subgroup of a symmetric group, i.e., a group consisting of some (not necessarily all) permutations. Later sections will explain how to represent the space symmetry group of a given geometric structure as a permutation group and apply it to counting problems.
Burnside's Lemma
Related reading: Burnside's Lemma
The Pólya enumeration theorem is an application and generalization of Burnside's lemma. Before introducing the Pólya enumeration theorem, it is necessary to briefly review Burnside's lemma.
To summarize the general pattern, first consider a simple example.
Necklace Coloring
There is a necklace with four beads. Each bead can be colored either red or blue. Compute the number of essentially distinct colorings. (Two colorings are considered the same if one can be obtained from the other by rotating the necklace.)
Solution and Analysis
This problem is simple enough to solve by enumeration. There are 4 beads, each with 2 color choices, so there are \(2^4=16\) possible colorings in total. Group those that can be obtained from each other by rotation. There are 6 groups in total, as shown in the figure below. (The encoding of each coloring represents the colors clockwise starting from the bottom-left bead, where \(B\) denotes blue and \(R\) denotes red; colorings in the same group share the same background color.)
From this example, it can be seen that to compute the number of essentially distinct colorings, the key is to know how many different colorings correspond to each essentially identical coloring. That is, to determine the size of each group in the figure above.
Colorings that belong to the same group are those that can be transformed into each other by rotation operations. There are 4 rotation operations in total, namely
representing rotations by \(0,1,2,3\) steps, respectively. Rotating by 0 steps means no change.
First, consider the group containing coloring \(RRBB\). Applying these four operations yields
These four colorings are all distinct, so this group has 4 elements.
Next, consider the group containing coloring \(BRBR\). Applying the same four operations yields
Here, rotating twice yields the same result as no rotation, and rotating three times yields the same result as rotating once. Thus, this group has 2 elements.
For the groups containing colorings \(BBBB\) and \(RRRR\), applying any of the four operations yields the coloring itself. Therefore, each group has only 1 element.
If we denote a coloring by \(x\), and \(Gx\) as the set of color codes obtainable by applying operations from \(G\) to \(x\), then the example reveals a pattern: the effect of \(G\) on \(x\) exhibits a certain "periodicity".
Let \(|G|\) denote the total number of operations. This "periodicity" implies that if there are \(m\) distinct operations in \(G\) that map \(x\) to itself, then the results of applying \(G\) to \(x\) will repeat \(m\) times. Consequently, there are \(|G|/m\) distinct results for \(x\) under these operations, which is also the size of the group containing \(x\).
In this example, since only rotation \(r_0\) (zero steps) maps \(RRBB\) to itself, the size of its group is \(4/1=4\); both \(r_0\) and \(r_2\) map \(BRBR\) to itself, so its group size is \(4/2=2\); all rotations map \(BBBB\) to itself, so its group size is \(4/4=1\).
In the following discussion, let \(G_x\) denote the set of operations that map \(x\) to itself, so \(|G_x|\) corresponds to \(m\) above. Then, the size of the group containing \(x\) is \(|G|/|G_x|\). To compute the number of groups of colorings, it suffices to enumerate all possible colorings \(x\in X\), assign a weight of \(1/|Gx|\) to each coloring \(x\) whose group size is \(|Gx|\), and express the number of groups as
This form is not convenient for application. Let \(gx\) denote the result of applying operation \(g\in G\) to coloring \(x\in X\). Then the set \(G_x\) described above is \(\{g\in G:gx=x\}\). Exchanging the order of summation gives
Here \([\cdot]\) is the Iverson bracket. In the result after exchanging summation, \(X^g=\{x\in X:gx=x\}\) is the set of colorings \(x\) that remain unchanged under operation \(g\). In short, it is the set of fixed points of operation \(g\).
After these discussions, the number of groups can now be written as
That is, the number of groups is the average number of fixed points under the various rotation operations.
Applying this result, recompute the number of necklace colorings. The fixed points under these rotation operations are listed below.
| Operation | Fixed Points |
|---|---|
| \(r_0\) | \(X\) |
| \(r_1\) | \(\{BBBB,RRRR\}\) |
| \(r_2\) | \(\{BBBB,BRBR,RBRB,RRRR\}\) |
| \(r_3\) | \(\{BBBB,RRRR\}\) |
Thus, the number of groups is
This matches the previous result.
From this example, a general result can be deduced for solving such counting problems. For convenience, this article considers coloring problems, but the principles can be applied to other scenarios, as shown in examples at the end.
A coloring problem involves coloring each vertex of a given structure, resulting in different colorings. The structure possesses certain symmetries, such that seemingly different colorings can be transformed into each other through a series of symmetry operations. Colorings that can be transformed into each other are called essentially identical. The problem is to find the number of essentially distinct colorings.
Based on the analysis of the example, to solve such a problem, one must first identify the symmetry operations of the given structure. The set \(G\) of these symmetry operations is called the space symmetry group of the structure. In practice, it is often unnecessary to understand the formal definition of a group; one only needs to discuss all space symmetry operations exhaustively and without repetition. The structures of several common space symmetry groups are analyzed later in this article, where the group definitions are explained.
The set of all colorings is denoted by \(X\), and a single coloring is denoted by \(x\). The result of applying operation \(g\in G\) to coloring \(x\in X\) is \(gx\). Then, all results obtainable by applying some operation to \(x\) form \(Gx=\{gx:g\in G\}\), called the orbit of \(x\) under the action of group \(G\). Different colorings in the same orbit are "essentially identical" in such problems. Therefore, the number of essentially distinct colorings equals the number of distinct orbits.
The analysis in the example can be generalized.
Burnside's Lemma
Given a group action of \(G\) on a set \(X\), the number of distinct orbits is
Here, \(X^g=\{x\in X:gx=x\}\) is the set of fixed points under the action of \(g\in G\).
Its proof essentially follows the analysis in the example above. However, the example relied on the observation that the action of group \(G\) on a single element \(x\) exhibits a certain "periodicity", so the number of repetitions equals the number of operations that map \(x\) to itself. This observation holds in general, but because the structure of group \(G\) can be complex, its "periodicity" may not be as direct as in the example. To state this observation rigorously, the orbit-stabilizer theorem from group theory is needed.
In applications, as long as all symmetry operations can be enumerated and the number of fixed points for each symmetry operation can be determined, the corresponding counting problem can be solved. Here is a slightly more complex application.
Cube Coloring
Color a cube with three colors. Find the number of essentially distinct colorings (two colorings are considered the same if they can be made identical by a spatial rotation).
Solution
Since the cube has 6 faces, each with 3 color choices, there are \(3^6\) colorings in total, i.e., \(|X|=3^6\). Denote the space symmetry group of the cube as \(G\).
Next, we analyze all operations in \(G\). They can be classified as follows (for convenience, label the six faces as front, back, top, bottom, left, right):
- Identity: the identity transformation. Since all colorings remain unchanged under the identity, \(|X^g|=3^6\);
- \(90^\circ\) rotation about the axis through the centers of two opposite faces: there are 3 choices for the pair of opposite faces and 2 choices for the rotation direction, so there are 6 such permutations. Suppose the axis is through the centers of the front and back faces. Then the top, bottom, left, and right faces must have the same color for the coloring to remain unchanged. There are 3 independently colorable regions, so \(|X^g|=3^3\);
- \(180^\circ\) rotation about the axis through the centers of two opposite faces: there are 3 choices for the pair of opposite faces, and the rotation direction does not matter, so there are 3 such permutations. Suppose the axis is through the centers of the front and back faces. Then the top and bottom faces must have the same color, and the left and right faces must have the same color for the coloring to remain unchanged. There are 4 independently colorable regions, so \(|X^g|=3^4\);
- \(180^\circ\) rotation about the axis through the midpoints of two opposite edges: there are 6 choices for the pair of opposite edges, and the rotation direction does not affect the permutation, so there are 6 such permutations. Suppose the axis is through the boundary of the front and top faces and the boundary of the bottom and back faces. Then the front and top faces must have the same color, the bottom and back faces must have the same color, and the left and right faces must have the same color for the coloring to remain unchanged. There are 3 independently colorable regions, so \(|X^g|=3^3\);
- \(120^\circ\) rotation about the axis through two opposite vertices: there are 4 choices for the pair of opposite vertices and 2 choices for the rotation direction, so there are 8 such permutations. Suppose the axis is through the top-right corner of the front face and the bottom-left corner of the back face. Then the front, top, and right faces must have the same color, and the back, bottom, and left faces must have the same color for the coloring to remain unchanged. There are 2 independently colorable regions, so \(|X^g|=3^2\).
Therefore, the number of essentially distinct colorings is
Pólya Enumeration Theorem
In the statement of Burnside's lemma, the property that set \(X\) is the set of all colorings of a structure is not used. In fact, Burnside's lemma is not limited to coloring counting problems. For coloring counting problems, the Pólya enumeration theorem provides a more precise calculation method. It can be viewed as an application of the general Burnside's lemma to coloring counting problems.
Compared to Burnside's lemma, the improvement of the Pólya enumeration theorem is that it provides a specific method to compute the size of the fixed point set \(|X^g|\) in coloring counting problems.
This can be seen intuitively from the cube coloring example above. For various symmetry operations of the cube, the size of the fixed point set is of the form \(m^{c(g)}\), where \(m\) is the number of colors and \(c(g)\) is the number of independently colorable regions under operation \(g\). This observation holds in general, but further clarification is needed on how to compute \(c(g)\) for a given \(g\).
Choosing a coloring for a structure, expressed mathematically, means selecting a mapping \(f:X\rightarrow C\) from the set \(X\) of colorable objects (e.g., beads in a necklace, faces of a cube) to the color set \(C\). Therefore, the set of colorings is \(C^X\). The space symmetry group \(G\) of the structure acts on the structure and naturally induces an action on the set \(X\). Such symmetry operations always correspond to bijections on \(X\), i.e., permutations.[^perm-group]
Now analyze the structure of the fixed point set \((C^X)^g\). Given \(g\), viewed as a permutation on \(X\), similar to the example analysis, if position \(x\) in \(X\) can be moved to position \(y\) after finitely many repetitions of operation \(g\), then for a fixed point \(f\in (C^X)^g\), it must satisfy \(f(x)=f(y)\). In the language of orbits from the previous section, since positions \(x\) and \(y\) lie in the same orbit under the action[^g-act] of \(g\), they must be colored the same. In permutation language, in the cycle decomposition of permutation \(g\), positions \(x\) and \(y\) belong to the same cycle and thus must be colored the same. Different cycles in the decomposition can be colored independently, so the number of independently colorable regions is \(c(g)\), i.e., the number of cycles in the cycle decomposition of \(g\).
Thus, the number of fixed points under operation \(g\) is \(|C|^{c(g)}\). Substituting this into Burnside's lemma yields the unweighted version of the Pólya enumeration theorem.
Pólya Enumeration Theorem (Unweighted Version)
Given a group action of \(G\) on set \(X\) and a color set \(C\), the number of distinct colorings is
where \(m\) is the number of colors, and \(c(g)\) is the number of cycles in the cycle decomposition of the permutation representation of element \(g\in G\).
On the Meaning of Group \(G\)
There is slight abuse of notation here. If group \(G\) acts on \(X\), then the group action on the coloring set \(C^X\) needs to be defined separately, which is not distinguished here.
As a simple application of the Pólya enumeration theorem, the previous example is recomputed below.
Alternative Solution to Necklace Coloring Problem
Label the four beads \(1\sim 4\). Then the elements in group \(G\) from the example have the following permutation representations (written in cycle decomposition form):
- Rotation zero steps \(r_0=(1)\), with 4 cycles (note the omitted 1‑cycles);
- Rotation one step \(r_1=(1234)\), with 1 cycle;
- Rotation two steps \(r_2=(13)(24)\), with 2 cycles;
- Rotation three steps \(r_3=(1432)\), with 1 cycle.
Therefore, the number of essentially distinct colorings is
Alternative Solution to Cube Coloring Problem
Since the analysis above essentially already gave the cycle representations of the various permutations, just not explicitly written with numerical symbols, the analysis is not repeated here. Only the case of \(180^\circ\) rotation about the axis through the midpoints of opposite edges is considered as an example. Label the front, back, top, bottom, left, and right faces as \(1\sim6\) respectively. The corresponding permutation is \((13)(24)(56)\), so \(c(g)=3\). Other types of permutations can be analyzed similarly, and the final counting expression is identical to the one above.
Weighted Generalization
The unweighted version of the Pólya enumeration theorem can only count all essentially distinct colorings but is insufficient for more refined problems. For example, if the number of each available color is given, the above Pólya formula cannot be applied directly. In practice, such problems require deriving using Burnside's lemma again; summarizing these results in the form of generating functions yields the weighted version of the Pólya enumeration theorem.
Necklace Coloring (with Restrictions)
There is a necklace with four beads. Each bead can be red or blue. Exactly two red beads and two blue beads are available. Compute the number of essentially distinct colorings. (Two colorings are considered the same if one can be obtained from the other by rotating the necklace.)
Solution and Analysis
Use Burnside's lemma. With two red and two blue beads, there are \(\dbinom{4}{2}=6\) colorings in total. The space symmetry group \(G=\{r_0,r_1,r_2,r_3\}\) corresponds to rotations by \(0\sim3\) steps. Their fixed point sets are analyzed as follows:
- Rotation zero steps \(r_0=(1)\): all 6 colorings are fixed points;
- Rotation one step \(r_1=(1234)\): fixed points require all beads to have the same color, so no fixed points;
- Rotation two steps \(r_2=(13)(24)\): there are two independently colorable regions, each of size 2. They must be colored red and blue respectively, so the fixed point set size is 2;
- Rotation three steps \(r_3=(1432)\): same as rotation one step, no fixed points.
Thus, by Burnside's lemma, the number of essentially distinct colorings is
From this example, the following calculation method can be summarized. For problems with restrictions on the number of each color, the cycles of each permutation in the space symmetry group still need to be colored, but the number of colors used must exactly match the given color counts. Such combinatorial problems often lack closed-form solutions, except for special cases solvable by combinatorial methods; otherwise, they need to be treated as knapsack problems.
The answer to such counting problems can be given via generating functions. Given a permutation \(g\), if its type is \(1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}\), i.e., it has \(\alpha_k\) cycles of length \(k\), and each cycle can be colored with one of \(m\) colors, then the generating function
has coefficients where the monomial \(x_1^{\beta_1}x_2^{\beta_2}\cdots x_m^{\beta_m}\) gives the count for using \(\beta_i\) copies of color \(i\). Here, the expression \(\sum_{i=1}^mx_i^k\) in parentheses has the combinatorial meaning that for a cycle of length \(k\), the count for using color \(i\) \(k\) times is 1, and 0 otherwise; this precisely describes the requirement that all positions in the same cycle must have the same color.
Applying Burnside's lemma to each monomial of the generating function for colorings under a given permutation \(g\) yields the count of essentially distinct colorings for each color combination. Since the generating function is linear in each monomial, the generating function for the count of essentially distinct colorings is
Expanding this expression, the coefficient of each monomial gives the count of essentially distinct colorings for the given color combination.
In the above process, the generating function \(\sum_{i=1}^mx_i^k\) for coloring each cycle is not special and can be replaced by other generating functions. Thus, we have the following general version of the Pólya enumeration theorem.
Cycle Index of a Permutation Group
Given a permutation group \(G\), the cycle index of group \(G\) is defined as
where \(c_k(g)\) is the number of cycles of length \(k\) in the cycle decomposition of permutation \(g\), i.e., \(1^{c_1(g)}2^{c_2(g)}\cdots n^{c_n(g)}\) is the type of permutation \(g\).
Pólya Enumeration Theorem (Weighted Version)
Given a group action of \(G\) on set \(X\), and the generating function \(f(x_1,x_2,\cdots,x_m)\) for the count of coloring methods for each point, then the generating function for the count of essentially distinct colorings of set \(X\) is
where \(Z_G(t_1,t_2,\cdots,t_n)\) is the cycle index of group \(G\).
Here, if the generating function for coloring a single position is \(f(x_1,x_2,\cdots,x_m)\), then the generating function for coloring a cycle of length \(k\) is \(f(x_1^k,x_2^k,\cdots,x_m^k)\). This reflects that if a coloring is a fixed point under a given permutation, then all positions in the same cycle must have the same color. Evaluating the generating function at \(x_i=1\) yields the unweighted version of the Pólya enumeration theorem.
The theorem statement uses the concept of the cycle index of a permutation group. It is independent of specific coloring problems and describes the structure of the permutation group.
Alternative Solution to Restricted Necklace Coloring Problem
The cycle index of the rotation symmetry group is \(\dfrac14\left(t_1^4+t_2^2+2t_4\right)\). The generating function for coloring a single point is \(r+b\), so the generating function for all colorings is
The desired count is the coefficient of \(r^2b^2\), i.e., 2 essentially distinct colorings. Incidentally, this expression also gives counts under other restrictions.
Applications
The weighted version of the Pólya enumeration theorem plays an important role in combinatorial counting problems. Its applications are briefly discussed here; more general discussions can be found in Formal Methods for Combinatorial Problems.
Diamond Necklace
There is a necklace with four identical beads. Each bead can be set with several diamonds. If there are four diamonds in total, how many essentially distinct ways are there to set the diamonds? (Two settings are considered the same if one can be obtained from the other by rotating the necklace.)
Solution and Analysis
The space symmetry group of the necklace remains as described earlier. Ignoring the total diamond count restriction, the generating function for the setting of a single position is
Applying the weighted Pólya enumeration theorem, the generating function for all settings is
Thus, the number of settings with four diamonds is the coefficient of \(x^4\), i.e., 10 settings. As verification, enumeration yields:
Here, each quadruple of numbers represents the number of diamonds on each bead.
This example shows that the weighted Pólya enumeration theorem can solve problems far broader than coloring counting. It provides a method to extend single-point counts to essentially distinct counts on entire structures. Coloring problems are just a special case of such problems.
Common Space Symmetry Groups
One difficulty in Pólya enumeration problems is analyzing the structure of permutation groups. Here, the structures of common space symmetry groups are briefly discussed, described by their cycle indices. Note that for the same structure's space symmetry group, if the set of objects acted upon differs, the corresponding group action also differs, and thus their permutation representations differ. For example, the space symmetry group of a cube acting on its vertices, edges, and faces corresponds to the vertex permutation group, edge permutation group, and face permutation group of the cube, respectively. The numbers of vertices, edges, and faces differ, so these permutation groups and their cycle indices are naturally different. Therefore, in solving specific problems, the specification of the objects acted upon cannot be ignored.
Relationship Between Space Symmetry Groups and Permutation Groups
Although conceptually very similar, they are not the same object. In group theory terms, given a space symmetry group \(G\) and its group action on a set \(X\), the permutation representation of the group action actually provides a homomorphism \(\varphi\) from \(G\) to the symmetric group \(S_X\). In combinatorial counting contexts, this permutation representation is often faithful, i.e., \(\ker\varphi=\{e\}\), so the homomorphism \(\varphi\) is actually an embedding of \(G\) into \(S_X\). The permutation group in the text is the image of this embedding, i.e., \(\varphi(G)\), which is isomorphic to the original space symmetry group \(G\). Therefore, for the same structure's space symmetry group \(G\), if the group action is chosen differently, it will be isomorphic to different permutation groups \(\varphi(G)\), leading to different cycle indices (isomorphic permutation groups may not have the same cycle index).
Given a structure, its space symmetry group is the set of all operations that map the structure onto itself. It must satisfy the following conditions:
- Applying two symmetry operations consecutively can be viewed as applying another symmetry operation, i.e., the set of symmetry operations is closed under composition;
- Composition of symmetry operations is associative;
- There exists an identity symmetry operation, i.e., leaving the structure unchanged is also considered an operation;
- Every operation has an inverse operation that undoes its effect.
A group is an abstraction of all concepts satisfying these conditions. Discussion of group structure is the main content of group theory. The analysis here focuses on space symmetry groups, and their structure is discussed primarily from a geometric perspective. Common examples are given, and readers should grasp common approaches to analyzing such problems.
Cyclic Groups
Given a regular \(n\)-gon, the space symmetry group consisting of all rotation operations is called the cyclic group, denoted \(C_n\). Denote the operation of counterclockwise rotation by \((360/n)^\circ\) as \(r\). Then the elements of \(C_n\) can be written as
Here, \(r^k\) means applying operation \(r\) \(k\) times, i.e., counterclockwise rotation by \((360k/n)^\circ\), and \(e=r^0\) is the identity transformation.
Whether considering the action of the cyclic group on the set of all vertices or all edges of the regular \(n\)-gon, its permutation representation is the same. Taking the set of all vertices as an example to analyze the permutation representation of the group action. Its cycle index is
Here, \(\varphi(\cdot)\) is the Euler totient function in number theory.
Considering only rotations, the space symmetry group of a necklace of length \(n\) is \(C_n\).
Analysis
Label the vertex set in counterclockwise order as \(\{0,1,\cdots,n-1\}\). Then \(r^k(i)=i+k\bmod n\). The set of vertices in the cycle containing vertex \(i\) is
Clearly, \(i\equiv i+\ell k\pmod n\) if and only if
This means that the length of the cycle containing any vertex \(i\) is \(\dfrac{n}{\gcd(k,n)}\). Therefore, permutation \(r^k\) has \(\gcd(k,n)\) cycles of equal length. Considering merging like terms in the cycle index expression, for a given \(d\mid n\), there are \(\varphi(d)\) values of \(k\) satisfying \(\gcd(k,n)=n/d\), and their corresponding monomials are all of the form \(t_d^{n/d}\), yielding the above cycle index expression.
Dihedral Groups
Given a regular \(n\)-gon, the space symmetry group consisting of all rotations and reflections about symmetry axes is called the dihedral group, denoted \(D_{2n}\). Denote the operation of counterclockwise rotation by \((360/n)^\circ\) as \(r\), and reflection about a given symmetry axis (e.g., the line through the center and a vertex) as \(s\). Then the operations of \(D_{2n}\) can be written as
Here, \(r^k\) are still rotation operations, while \(sr^k\), although meaning first rotating \(k\) times and then reflecting about the given axis, can equivalently be viewed as reflection about another symmetry axis. Thus, group \(D_{2n}\) contains 1 identity transformation, \((n-1)\) rotation operations, and \(n\) reflection operations. Its group actions on the vertex set and edge set have the same permutation representation. Its cycle index is
Analysis
The analysis of the set of rotation operations \(r^k\) (including the identity) in \(D_{2n}\) is identical to that for the cyclic group \(C_n\). The key lies in analyzing the remaining reflection operations. This requires separate discussion based on the parity of the number of vertices \(n\).
When \(n=2k+1\), all reflection axes pass through a vertex and the midpoint of the opposite edge. There are \(n\) such axes. Under a reflection, the vertex on the axis remains fixed, while other vertices are swapped in pairs. Thus, there is 1 fixed point (1‑cycle) and \(k\) 2‑cycles.
When \(n=2k\), there are two types of axes. Half of the axes connect opposite vertices; reflecting about such an axis leaves the two vertices on the axis fixed and swaps the remaining vertices in pairs, yielding 2 fixed points (1‑cycles) and \((k-1)\) 2‑cycles. The other half of the axes connect midpoints of opposite edges; reflecting about such an axis swaps all vertices in pairs, yielding \(k\) 2‑cycles.
Based on this analysis, the above cycle index expression can be written.
Symmetric Groups
Given \(n\) elements, the set of all permutations on them forms a group called the symmetric group of degree \(n\), denoted \(S_n\). It describes all possible symmetries these \(n\) vertices can have. It is also the permutation representation of these symmetry operations acting on the vertex set.
According to the analysis in Permutations and Arrangements, its cycle index is
Here, the count of permutations of type \(1^{\alpha_1}2^{\alpha_2}\cdots n^{\alpha_n}\) is
It satisfies the recurrence relation
with base case \(Z(S_0)=1\). The combinatorial meaning of this recurrence is that to construct a permutation of length \(n\), first choose the length \(k\) of the cycle containing point \(n\), then construct a permutation on the remaining \((n-k)\) vertices.
Given the complete graph on \(n\) vertices, its space symmetry group is exactly \(S_n\). Its cycle index for the action on the set of all vertices is given by \(Z(S_n)\) above. However, its permutation representation for the action on the set of all edges is different. For example, the set size differs; the total number of edges is \(n(n-1)/2\). For edges, additional analysis is needed. A simple example is given here; general cases can be found in exercises.
Undirected Simple Graph Counting
Count the number of non-isomorphic undirected simple graphs with 4 vertices.
Solution
This is equivalent to coloring the complete graph
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用