Questions tagged [polya-counting-theory]
For questions about Pólya counting theorem. AKA Pólya enumeration theorem, Redfield–Pólya theorem, Pólya counting.
104
questions
3
votes
1
answer
99
views
Prove $|M/G|=\sum_{x \in M} {\frac{1}{|G(x)|}}$
Let $G$ be a finite group operating on a finite set $M$. $|M/G|$ is the number of orbits. I want to prove that
$|M/G|=\sum_{x \in M} {\frac{1}{|G(x)|}}$
This question is in preparation of Burnside-...
- 189
1
vote
1
answer
64
views
In how many ways can we color the edges of a tetrahedron with black and red colors?
Task: In how many ways can we color the edges of a tetrahedron with black and red colors?
I have a problem because I computed the cycle index, considering the rotations of the tetrahedron based on its ...
- 97
0
votes
0
answers
88
views
Generalization of Pólya Enumeration Theorem by de Bruijn
I need help with this question.
Suppose that G is a group acting on a set of objects S, and that C is the set of colorings of elements of S using the colors in a set R. Let $\overline c$ denote the ...
- 1
4
votes
1
answer
118
views
Icosahedron with asymmetric coloring
I am trying to determine the number of unique solutions when placing "dots" on the sides of an icosahedron. There can be up to three dots placed symmetrically on each side. The dots are ...
- 143
0
votes
0
answers
82
views
Simple way to approach bead necklaces problem for equal number of beads
I was recently given this question on a practice test, and it was intended to be completed in ~2-3 minutes, for someone with intermediate stats/math knowledge:
For a positive integer $n$, you have $n$...
6
votes
0
answers
206
views
Counting problem about polygon triangulations
I have the following question about triangulations (by non-intersecting diagonals, and edges) of regular polygons.
What is the number of triangulations of a regular n-gon, up to all symmetry (i.e. the ...
- 754
2
votes
2
answers
93
views
Redfield-Polya enumeration, but the colors don't matter
Is there a version of Redfield-Polya enumeration with the added condition that you don't care which color is which? An illustrative example is: Count edge-colorings of $K_4$ modulo the group action of ...
- 144
7
votes
1
answer
264
views
Coloring the Square. Burnside's lemma.
Question from my last exam:
We paint the vertices of a square with five colors: A, B, C, D, and E. Two ways of painting are considered identical if one can be transformed into the other through an ...
- 675
0
votes
0
answers
75
views
Polya's enumeration theorem for edge and vertex coloring combined.
Let's say we have a tetrahedron labelled as such:
We want to find the number of distinct ways to color the vertices and edges, such that 2 vertices are green, 2 vertices are red, 4 edges are black ...
1
vote
0
answers
126
views
Number of pair of edges of a dodecahedron, up to rotational symmetry.
How many ways can we choose a pair of edges of a dodecahedron, up to rotational symmetry?
Taking $180$ rotation we have $15$ axis of rotations.
Since there are $6$ pairs of opposite faces, we have an ...
- 399
0
votes
1
answer
65
views
Why does the ratio between total solutions and unique solutions to the n-Queens Problem converge to 8?
Taking a look at the total solutions and unique solutions to the n-Queens Problem posted here (How many solutions are there to an $n$ by $n$ queens problem?) I realized that the ratio between the ...
- 1,190
6
votes
2
answers
200
views
Can we use Burnside's lemma to count partitions of an integer?
I am currently learning group theory and find that Burnside Lemma can be used to calculate partition number, although not that efficiently.
Suppose we want to distribute $n$ different balls into $n$ ...
- 605
1
vote
0
answers
72
views
Arranging triplets from an urn and partitioning them.
Say we have an urn containing 3N orbs of three different colors: red, green and blue. N of them of each color.
The orbs are Arranged necessarily in sets of three, we'll call them troikas. there are 10 ...
0
votes
1
answer
71
views
Identifying weak partitions
Recently a problem rose to me I'm not really sure what topic it belongs to:
The origin is a "labeling application". There are n objects (say files etc., n abt. 1e6). And there are t ...
- 21
1
vote
1
answer
117
views
Bracelet enumeration
Apologies if this has been asked and answered but I can't seem to find a solution! I am looking for a way to enumerate or list all of the bracelets for a given number of beads, without repetition of ...
- 11