Polya's Enumeration Theorem is a powerful tool for counting distinct colorings or configurations under group actions. It uses the cycle index polynomial to encode permutation group structures, allowing us to solve complex counting problems efficiently.

This theorem connects to the broader topic of enumerative combinatorics by providing a systematic way to count objects with symmetries. It's especially useful for problems involving graphs, molecular structures, and other symmetric arrangements.

Polya's Enumeration Theorem

Key Components and Statement

• Polya's Enumeration Theorem provides a method for counting the number of distinct ways to color or configure objects under a group action
  • The key components are:
    1. A set X of objects to be colored/configured
    2. A permutation group G acting on X
    3. A set C of colors/configurations
• The theorem states that the number of distinct colorings/configurations is given by the average number of elements fixed by each permutation in G, when the colors/configurations are permuted in all possible ways
• The cycle index polynomial Z(G) encodes the structure of the permutation group G and plays a central role in the theorem

Role of the Cycle Index Polynomial

• The cycle index of a permutation group G is a polynomial Z(G) in variables s1, s2, ..., sn that encodes the cycle structure of the permutations in G
  • For each permutation g in G, determine its cycle structure (the number of cycles of each length)
  • For each permutation g, compute the term s1^(c1) * s2^(c2) * ... sn^(cn), where ci is the number of cycles of length i in g
  • Sum the terms for all permutations in G and divide by the order of G to obtain the cycle index Z(G)
• The computed cycle index Z(G) is used in Polya's Theorem to count distinct colorings/configurations under the action of G

Applying Polya's Theorem

Steps to Apply Polya's Theorem

• Identify the set X of objects to be colored/configured and the permutation group G acting on X
• Determine the cycle structure of each permutation in G and compute the cycle index polynomial Z(G)
• Specify the set C of colors/configurations and the generating polynomial P(C) that encodes the number of colors/configurations
• Substitute the variables in Z(G) with the terms from P(C) to obtain the pattern inventory
  • Expand the pattern inventory and identify the coefficient of the term corresponding to the total number of objects in X
  • This coefficient gives the number of distinct colorings/configurations

Examples of Applying Polya's Theorem

• Counting the number of distinct colorings of the vertices of a square using 3 colors (red, blue, green)
  • X is the set of vertices of the square, G is the dihedral group D4 acting on the vertices, and C is the set of 3 colors
  • Compute Z(D4), substitute the terms of P(C) = x^3 into Z(D4), and expand to find the number of distinct colorings
• Counting the number of distinct necklaces with 6 beads, where each bead can be either black or white
  • X is the set of 6 positions on the necklace, G is the cyclic group C6 acting on the positions, and C is the set of 2 colors (black, white)
  • Compute Z(C6), substitute the terms of P(C) = x^2 into Z(C6), and expand to find the number of distinct necklaces

Cycle Indices for Polya's Theorem

Computing Cycle Indices

• To compute the cycle index Z(G) of a permutation group G:
  1. Write down each permutation g in G
  2. For each permutation g, determine its cycle structure (the number of cycles of each length)
  3. For each permutation g, compute the term s1^(c1) * s2^(c2) * ... sn^(cn), where ci is the number of cycles of length i in g
  4. Sum the terms for all permutations in G
  5. Divide the sum by the order of G to obtain the cycle index Z(G)

Examples of Cycle Indices

• The cycle index of the symmetric group S3 is:
  • Z(S3) = (1/6) (s1^3 + 3s1s2 + 2s3)
  • Derived from the cycle structures of the 6 permutations in S3: (1)(2)(3), (1,2)(3), (1,3)(2), (1)(2,3), (1,2,3), (1,3,2)
• The cycle index of the dihedral group D4 (symmetries of a square) is:
  • Z(D4) = (1/8) (s1^4 + 4s1^2s2 + 2s2^2 + 2s4)
  • Derived from the cycle structures of the 8 permutations in D4: rotations and reflections of the square

Counting with Polya's Theorem

Advanced Counting Problems

• Polya's Theorem can be used to solve advanced counting problems, such as counting non-isomorphic graphs
  • Recognize the underlying permutation group G acting on the objects in the counting problem (e.g., the symmetric group Sn acting on the edges of a complete graph Kn)
  • Identify the set C of colors/configurations relevant to the problem (e.g., the presence or absence of edges in a graph)
  • Compute the cycle index Z(G) of the permutation group G, taking into account any additional symmetries or restrictions in the problem
  • Determine the generating polynomial P(C) based on the set of colors/configurations
  • Apply Polya's Theorem by substituting the terms of P(C) into Z(G) to obtain the pattern inventory
  • Extract the coefficient of the relevant term in the expanded pattern inventory to obtain the count of distinct objects (e.g., non-isomorphic graphs with a given number of vertices and edges)

Refining the Counting Process

• In more complex problems, additional techniques may be necessary to refine the counting process:
  • The Exponential Formula can be used to count the number of non-isomorphic rooted objects (e.g., rooted trees)
  • The Redfield-Pólya Theorem extends Polya's Theorem to count the number of non-isomorphic objects with a given number of components (e.g., forests with a given number of trees)
• These techniques can be combined with Polya's Theorem to solve a wide range of advanced counting problems in combinatorics and graph theory