Questions tagged [polya-counting-theory]
For questions about Pólya counting theorem. AKA Pólya enumeration theorem, Redfield–Pólya theorem, Pólya counting.
100
questions
4
votes
1
answer
105
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
44
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$...
5
votes
0
answers
177
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 ...
- 560
0
votes
0
answers
37
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 ...
- 124
7
votes
1
answer
185
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 ...
- 371
0
votes
0
answers
54
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
116
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 ...
- 299
0
votes
1
answer
55
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,032
6
votes
2
answers
175
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$ ...
- 525
1
vote
0
answers
67
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
69
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
56
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
0
votes
1
answer
81
views
Complete bell polynomial coefficients
I would like to know if it is possible to calculate the coefficient of a given Complete Bell Polynomial 's monomial by its indexes and powers:
$B_{n}(x_1,x_2,...,x_n)= c_n(1,n) x_1^n + c_n((1,n-2),(2,...
0
votes
1
answer
136
views
$\binom{n+1}{2} + 2 \left ( \binom{2}{2} + \binom{3}{2} + \dots + \binom{n}{2} \right ) = 1^2+2^2+\dots+n^2.$
Is there a combinatorial proof of the following identity:
$$\binom{n+1}{2} + 2 \left ( \binom{2}{2} + \binom{3}{2} + \dots + \binom{n}{2} \right ) = 1^2+2^2+\dots+n^2.$$
Note: using algebraic ...
- 492
2
votes
1
answer
108
views
Spelling Bee - real combinatorics example
The hint section of a puzzle game indicates that are eighteen words starting with G.
The number of words having four, five, six or seven letters are 7,3,7 respectively 1.
There are 6, 1, 8 and 3 words ...
- 670
2
votes
0
answers
49
views
How many non-equivalent configuration of $2 \times 2 \times 2$ Rubik cubes with $6$ distinct colors? [duplicate]
How many non-equivalent configuration of $2\times2\times2$ Rubik cube with $6$ distinct colors are there?
You can also think this question such a way that how many non-equivalent colorings are there ...
user1091909
2
votes
0
answers
43
views
Permutations of a colored grid if columns and rows are freely swappable
It's my first time posting here, so I hope I manage to bring my thoughts across clearly and accurately.
A grid of the size x×y is given alongside a set of n numbers c1, c2, c3, ..., cc that added ...
- 21
1
vote
1
answer
77
views
$3$ reds, $3$ blues and $3$ green marks to place to hexagon
We have $3$ reds, $3$ blues and $3$ green marks to place on vertices in the given picture. (Only one mark for each vertex). The hexagon is free to move in three dimensions. How many nonequivalent ...
user1085557
1
vote
1
answer
52
views
There is a circular table with $10$ seating , we want to place $6$ people to this circular table.How many ways are there?
There is a circular table with $10$ seating , we want to place $6$ people to this circular table.How many ways are there ?
My try: I thought the empty seats as identical object that will be placed by ...
user1085557
1
vote
1
answer
182
views
Coloring the faces of the regular icosahedron, again...
The calculation of the number of ways to color the faces of the regular icosehedron by 2 different colors is given in this link: Coloring the faces of a regular icosahedron with $2$ colors
My question ...
- 7,754
2
votes
1
answer
151
views
4 different colour balls, each of number four have to be arranged in a circular manner so that adjacent 3 balls are of different colour.
I have 4 red balls, 4 green balls, 4 Blue balls and 4 Yellow balls with me. I have to arrange them in a circular manner. The condition is that if we take any 3 adjacent balls, they should have to be ...
- 151
2
votes
2
answers
116
views
Counting the number of colored tetrahedra
The book “Mathematics of choice or how to count without counting” by Ivan Niven has the following question:
Problem set 1, question 15:
A man has a large supply of wooden regular tetrahedra, all the ...
1
vote
0
answers
89
views
Calculating how many loop-free non-isomorphic undirected graphs with a specific number of vertices that exist
Say you have a graph with 4 vertices, I would know that it can have a maximum of $\begin{pmatrix}4\\2\end{pmatrix} = 6$ edges. What I'm not sure about how to find is how many ways you can connect the ...
- 526
0
votes
1
answer
125
views
Compute the number of unique, non-equivalent configurations of a matrix
Consider a matrix $\mathbf{A}$ of size $m\times n$. Each element of this matrix, denoted here as $a_{ij}$, is a non-negative integer from $0$ to $s$, i.e. $a_{ij}\in\{0,1,2,...,s\}$. The problem is to ...
- 121
0
votes
0
answers
47
views
How do I use Pólya's enumeration theorem to solve this toy-swapping problem?
Say we have $n$ children sitting in a ring. Each child is given an arbitrary toy that is either red or blue. We know that children, being as they are, can be somewhat fickle and very sociable, so if a ...
- 1,309
0
votes
0
answers
60
views
Number different coloring of Tetrahedron with 2 black and 2 white colors?
How to count Number different coloring of Tetrahedron with 2 black and 2 white colors by Bernside lemma. first I count the number ways of choosing 2 and 2 faces, it is $\frac{4!}{2!2!}$. second ...
- 51
1
vote
1
answer
358
views
How many necklaces are there with a known number of beads of each color? [duplicate]
I suspect that the answer to my question might be trivially found in the Wikipedia page for the combinatorial concept of a necklace, but I'm finding that page very hard to understand.
Suppose I have $...
- 5,909
1
vote
2
answers
126
views
Find the number of different colorings of the faces of the cube with 2 white, 1 black, 3 red faces?
I tried using Polya theorem same in this https://nosarthur.github.io/math%20and%20physics/2017/08/10/polya-enumeration.html guide, using S4 group for cube faces. But i Have a $\frac{1}{24}12w^2*b*r^3$....
- 51
0
votes
1
answer
200
views
Limit of number of graphs with n vertices to isomorphism
I've been struggling with a proof for several days now and I just can't quite see how it works. I am trying to prove the limit of the number of graphs with n vertices up to isomorphism is:
$$ \frac{2^{...
- 61
2
votes
1
answer
90
views
Pairwise non-isomorphic graphs
My problems first:
An upper bound or lower bound for the number of non-isomorphic-$n$-point graphs
Construct explicitly as many as possible of them
This originates from the homework, and I am sure ...
- 355
3
votes
2
answers
236
views
How to color a cube with exactly 6 colors using Polya enumeration theory
I have seen in other questions (Painting the faces of a cube with distinct colours) , and found for myself there are 30 colorings of the cube with exactly 6 colors. My issue is when I use Polya ...
- 772
1
vote
0
answers
121
views
Number of ways to color faces of a cube with exactly 6 colors?
Consider two colorings the same, if each color has the same collection of neighboring colors. I've seen Polya enumeration theorem on how to color a cube with up to $m$ colors, but that doesn't work ...
- 772
4
votes
1
answer
124
views
Polya Enumeration: Generate Configurations off of Cycle Index
I have a 3x3 grid.
$$\begin{array}{|c|c|c|}
\hline
1 & 2 & 3\\
\hline
4 & 5 & 6\\
\hline
7 & 8 & 9\\
\hline
\end{array}$$
The symmetries are the 4 rotations (0, 90, 180, ...
- 51
1
vote
1
answer
105
views
Cycle indicator symmetric function and Polya's theorem
Let $G$ be a subgroup of the symmetric group $S_n$. Given a partition $\lambda$ of $n$, denote by $n_G(\lambda)$ the number of elements in $G$ of cycle-type $\lambda$. The cycle indicator function of $...
- 2,402
1
vote
1
answer
127
views
How many ways are there to color a $3 × 3$ grid in the same way if five squares have to be red and four squares have to be blue?
When configurations after rotations and flips are considered the same, how many ways are there to color a $3 × 3$ grid in the same way if five squares have to be red and four squares have to be blue?
...
- 21
2
votes
0
answers
63
views
How to count/enumerate equivalent colorings
I trying to solve this problem:
Given a binary matrix $B_{3x3}$ = $\begin{bmatrix}0 & 1 & 0 \\1 & 0 & 0\\1 & 0 & 0 \end{bmatrix}$
We obtain a second binary matrix $C_{2x2}$ as ...
- 21
2
votes
2
answers
292
views
Polya's Urn for Three Colors Instead of Two
Is it possible to extend Polya's Urn problem to balls with $3$ different colors instead of just $2$?
ie. An urn contains $1$ red, $1$ blue, and $1$ green ball. At each turn you draw one ball and put ...
user879357
0
votes
2
answers
83
views
What are the possibilities of a $4 \times 4 \times 4$ array that has two $0$s and two $1$s in each line?
So this is a $4$ by $4$ by $4$ cube consisting of $64$ ($1$ by $1$ by $1$) small cubes, which can have the value of $0$ or $1$.
What we call a line here is strictly straight, and not diagonal. So if ...
1
vote
0
answers
50
views
colouring vertices of cube while considering symmetry [duplicate]
Let $G$ be the rotation group of a cube $Q.$ How many ways (up to symmetry under the action of $G$) can we colour the $8$ vertices of $Q$ using $2$ colours?
I know the Burnside or Cauchy-Frobenius ...
- 1,144
0
votes
0
answers
136
views
Derivation of Cycle Index
I was going through the cycle index topic and I came across the cycle index for various types of groups. It is given that the cycle index for a cyclic group is
$$P_{C_n} (t_1 , \ldots ,t_n)= \frac{1}{...
- 221
2
votes
1
answer
166
views
Find a generating function for unlabeled graphs
Let's take a graph(undirected) of $m$ edges and $3$ vertices. Now I want to derive a polynomial for which the coefficient of $x^m$ denotes the number of unlabeled graphs of $m$ edges.
How to derive ...
- 221
0
votes
1
answer
100
views
Generating Function of P Group
Take G as group of permutations on $n$ elements. It naturally acts on the set $[n]$. Compute the cycle index polynomial of this action of partitioning the permutation into blocks of your own size.
We ...
- 221
0
votes
1
answer
206
views
Polya's Urn: Need Help Calculating Expected Value of Concentration of Red Balls at Stage n
An urn U contains $r_0$ red balls and $g_0$ green balls. At each stage a ball is selected at random from the urn, we observe its color, we return it to the urn and then we add another ball of the same ...
- 15
2
votes
2
answers
161
views
Coloring Two Faces of an Icosahedron
Suppose that you have a solid regular icosahedron (a polytope with 20 sides all of which are
equilateral triangles), and all the sides are white.
(a) In how many ways can exactly two sides be painted ...
- 73
2
votes
1
answer
95
views
Number of independant paths between a discrete set of points?
How can we calculate the total number of paths joining any pair of points in a collection of $N$ points?
Specifically, consider the following example of a set of four points (their distribution on a ...
- 312
4
votes
1
answer
58
views
counting words with a condition
Suppose we are given a sequence $x_1x_2x_3x_4x_5x_6$ where the $x_i$ are digits 0 to 9, and we want to know how many of them do we have that satisfy $x_1<x_2<x_3<x_4<x_5<x_6$?
$...
- 3,957
1
vote
0
answers
44
views
Number of 'Unique' Ways to Mix a Color Palette?
Assume all mixtures involve colors mixed in equal amounts and base colors are already on the palette. How many ways are there of mixing k distinct colors on a paint palette where each color must be ...
- 21
0
votes
1
answer
137
views
The orbits with respect to two groups from the same conjugacy class are isomorphic
On the Wikipedia page for the Symbolic Method of Flajolet and Sedgewick
https://en.m.wikipedia.org/wiki/Symbolic_method_(combinatorics)
under the heading "Classes of combinatorial structures"...
user796754
2
votes
1
answer
599
views
Application of Burnside's Lemma on the vertices of a cube
Eight congruent equilateral triangles, each of a different color, are used to construct a regular octahedron. How many distinguishable ways are there to construct the octahedron? (Two colored ...
- 1,087
0
votes
1
answer
160
views
Cycle index for necklace with 12 beads
I was trying to search for ways to calculate cycle index of a necklace with 12 beads and stumbled upon the formula that gave the answer as $\frac{{x_1}^{12} + {7x_2}^6 + {2x_3}^4 + {2x_4}^3 + {2x_6}^2 ...
- 15