Questions tagged [polya-counting-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
35 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 ...
0
votes
1answer
76 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"...
1
vote
1answer
40 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 ...
0
votes
1answer
65 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 ...
2
votes
2answers
30 views

Question about number of non equivalent colourings of corners of a regular tetrahedron with k colours

Due to Covid -19 , in our university quizzes are held online and it's hard to ask questions. 3 Days back in my Combinatorics quiz this question was asked on which I am struck. I couldn't solve it in ...
2
votes
1answer
52 views

Non equivalent colourings of regular hexagon( Brualdi Chapter-14 , Exercise -32)

I have a question in this exercise of Richard Brualdi's Introductory Combinatorics. Exercise is -> Determine the number of non equivalent colourings of corners of regular hexagon with colours red, ...
0
votes
1answer
21 views

Non equivalent colorings for Isosceles Triangle

Using Burnside algorithm the number of non equivalent colorings using k colors for an equilateral triangle is given as $\frac{k^3+3k^2+2k}6$. Is there any formula that has been derived for an ...
0
votes
1answer
23 views

How many unique ways can two black stones and one white stone be placed on a 5x5 grid, disregarding reflectional and rotational symmetry?

This problem has been bothering me for quite a while, but I don't think I have the combinatorics background to answer it. Considering each grid position as distinct, the overall number of possible ...
1
vote
1answer
92 views

Polya's Enumeration : Where am I going wrong?

If we write a 9 digit binary number as a $3\times3$ matrix, for example $101110101$ would be written as, $$\begin{bmatrix}1 & 0 & 1\\\ 1 & 1 & 0\\\ 1 &...
1
vote
1answer
55 views

How many ways to paint $n$ windows?

Given a building with $n$ floors and a window on each floor. You need to paint all the windows either black, white or red. How many ways are there to paint all the windows given that there have to be ...
0
votes
1answer
49 views

Finding equivalence classes under permutation symmetry

If we write a 9 digit binary number as a $3\times3$ matrix, for example $101110101$ would be written as, $$\begin{bmatrix}1 & 0 & 1\\\ 1 & 1 & 0\\\ 1 &...
6
votes
2answers
114 views

Number of $2$-colorings of edges of the $n$-dimensional cube?

I'm interested in counting the number of $2$-colorings of the edges of an $n$-cube up to rotations and reflections. For $n=1$ there are two colorings—either color the edge or don't. For $n=2$ there ...
1
vote
2answers
77 views

Using Group Actions to determine the different colourings of a grid

I am trying to find the number of different colourings of an $n \times n$ grid using $m$ colours by using group actions. The set that I am acting on is the set of $n^2$ ‘tiles’ within the square grid. ...
1
vote
1answer
23 views

Why can a group act with left action on a function in polya counting?

Consider a group $G\leq S_{n}$ and $X$, a finite set of cardinality $|X| = n $. Let $C = \{c_1,c_2,...,c_m\}$; where we call the elements of $C$ colours. We consider $f \in C^{X}$, that is a function $...
1
vote
2answers
97 views

Number of ways to color a grid

Consider a $2000 \times 2000$ matrix which is to be filled with $15$ colors. Find the number of ways to color the matrix. Two colorings are same if rotating one of them along the axis perpendicular to ...
0
votes
0answers
47 views

Unable to prove a result in Polya Theory in first course of combinatorices

I am trying to solve assignment problems but i am unable to prove this question. Question is -> Let c be a colouring in C, where C is set of colourings of set X on which G is a permutation group ...
1
vote
1answer
61 views

Polya Enumeration

I have a circle divided into 60 pieces, and I have 4 different colors $(c_1,c_2,c_3,c_4)$, and I want to know how many different "colorings" I can get. So I thought I would use the Polya Enumeration ...
2
votes
2answers
138 views

Counting directed bicliques using Burnside's lemma

Let $b_{n}$ be the number of different directed $K_{n,n}$ graphs, assuming that $G$ and $H$ are considered identical when $G$ is isomorphic either with $H$ or with its transpose $H^T$ (i.e. same graph ...
0
votes
1answer
47 views

Finding unique patter of $M$ $1$s in an $N \times N$ matrix, the rest occupied by $0$s

I am looking for a solution for a biological problem. I have a $10 \times 10$ matrix that I need to fill with $10$ molecules. They can occupy any cell in the matrix (they don't need to be next to each ...
1
vote
2answers
354 views

Given 2 red beads, 2 blue beads, 1 yellow bead, and 1 green bead, how many different necklaces can be made?

I need to write a Matlab code to determine the answer (which was given as 16) and I need to utilize loops to remove flips and circular shifts
1
vote
1answer
40 views

H-graph combinatorical problem.

Consider a H-graph. It has $6$ vertices and $5$ edges (H-graph). Now let's enumerate vertices of graph with $\mathbb{Z_{+}}$ numbers , such as sum of all numbers will give us $n$. So we want to ...
3
votes
0answers
74 views

Proper coloring of a cuboid.

Question: The different faces of a cuboid, having the measurements $1 \times 2 \times 2$ cm, is to be painted. Colors at disposal are blue, yellow, and red. In how many ways can this be done, if two ...
2
votes
0answers
23 views

Prove that the cyclical index of this activity is expressed by the formula $I_{G_1 \bigoplus G_2}=I_{G_1}\cdot I_{G_2}$

Let $T_1$ and $T_2$ will be disjoint finite sets and let $G_1$, $G_2$ will be respectively certain permutation groups of these sets. Direct sum $G_1 \oplus G_2$ in natural way works on $T_1 \cup T_2$: ...
0
votes
0answers
75 views

How many nonequivalent two-sided $n$-ominoes are there?

A two-sided $n$-omino is a $1$-by-$n$ board of $n$ squares with each square ($2n$ in all because of the two sides) colored with one of $p$ given colors (squares on opposite sides may be colored ...
5
votes
1answer
149 views

Calculate in how many different ways can rotated square

We put a square $3 \text{ x } 3$ from $9$ square tiles in two types: or which can be freely rotated (we allow also symmetries). Calculate in how many different ways you can do that if we identify ...
0
votes
0answers
18 views

Generate a list of lists that contains numbers that add up to a certain value [duplicate]

I'm not sure what kind of theorem this is called, perhaps permutation or something in the realms of that. Basically, I'm given a number and I need to generate the list of lists that contain numbers ...
1
vote
2answers
38 views

Coloring elements of $A_1, …, A_m$ where $|A_i| = n$

Let $A_1, ..., A_m$ be separable $n$-elements sets. We color elements of these sets in use of $2$ colors, but we consider two coloring as the same if one we can get from other by changing order of ...
1
vote
0answers
33 views

How many different colors see RG-color blinder and how many RBG-color blinder

RG-color blinder recognizes blue. He seeing objects red and green but he only knows that these colors are different (and that none of them is blue). RBG-color blinder sees red, blue and green objects ...
5
votes
0answers
89 views

How many essentially different Drive Ya Nuts Puzzles exist?

In the Drive Ya Nuts puzzle, we are given $7$ hexagonal nuts, whose edges have been numbered from $1$ to $6$. Each nut uses all $6$ numbers. The aim of the puzzle is to place all the nuts in a ...
-3
votes
2answers
158 views

removing a marble [closed]

A bag contains 3 red, 4 white, and 5 blue marbles. Jason begins removing marbles from the bag at random, one at a time. What is the maximum number of marbles he must remove to be sure that the bag ...
1
vote
0answers
23 views

The cross entropy of Pólya Gamma distribution

Is there analytical solution for computing the cross entropy of Pólya Gamma distribution? For example, $$\int_{\omega} P_{PG}(\omega|1,c)*\log P_{PG}(\omega|1,0)d\omega$$
5
votes
0answers
84 views

Number of $5$ full connected directed graphs

Find number of full connected directed graphs where $|V|=5$ (directed $K_5$) solution According to OEIS there are $42$ graphs like that. Let say that we have graph $G$ and we want to find how many ...
2
votes
1answer
101 views

Counting different cube with size $2$

In set of $8$ cube (each has edge with length $1$) we have $3$ cubes with exactly one white side (other sides are black) and $5$ cubes with all white sides. We make from this cubes, one big cube with ...
3
votes
0answers
116 views

Coloring directed wheel graph $W_6$ with $k$ colors

Let consider directed wheel graph $G_6$ example. We want to color each vertex on $1$ of $k$ colors. How many different coloring there are if two graphs we consider as the same if one can be ...
11
votes
1answer
205 views

Coloring $n$ chain with $k$ colors

Chains are made from beads, each in one of $k$ colors. In each chain there is $n$ beads. We claim that two chains are the same if one can be made from second by cyclic rotation (mirror reflection is ...
3
votes
3answers
712 views

How many distinct 20-bead necklaces can be made with beads of 3 different colors?

First of all, I am aware that these types of questions are very common and are around the internet in all shapes and sizes. However, in this case I was just really wondering if I'm doing the right ...
2
votes
1answer
104 views

Using Pólya counting to find number of conjugacy classes of $S_3$

So I know that $S_3$ has three conjugacy classes. However, I was reading about Pólya counting today, and am wondering how Pólya counting could be used to derive the number of conjugacy classes for $...
1
vote
0answers
55 views

Help with Polya Counting question

So I have this graph: And I want to figure out how many different (they are identical when they differ by an element of the symmetry group of the graph) iterations can be made when each node in the ...
1
vote
1answer
38 views

Finding coefficients when applying polya's theorem

When applying Polya's counting theorem one needs to find the coefficients of complicated polynomials. Example: Find the coefficient of $r^2w^3b^4$ in $4(r+b+w)^3(b^2+r^2+w^2)^3$. In this case I know ...
0
votes
1answer
230 views

Colorings of a $3\times3$ chessboard

I am having some trouble with the following problem from Brualdi's Introductory Combinatorics (Chapter 14 Exercise 47). The nine squares of a $3\times3$ chessboard are to be colored red and blue. ...
3
votes
2answers
256 views

Square coloring problem only using 2 colors

"We need to color $4×4$ square using $4$ black color and $12$ white color. Then, how many cases it may be? Flip is prohibited but rotating is ok" I tried case by case (inner square and rest) anf ...
0
votes
1answer
66 views

Polya Enumeration Theorem cycle index variable interpretation

The cycle index for a necklace with three beads up to rotations and no flips is $$P_G(x_1,x_2,x_3)=\frac{1}{3}(x_1^3+2x_3)$$ If we want to find how many such necklaces there are with four bead colors,...
0
votes
0answers
34 views

generating the combinations which are fixed under symmetry operation

I have the following problem: If I have a system with a certain symmetry, for example, a square or a 2x2 grid and each grid point can have 2 states, for example, occupied or not occupied, or colored ...
3
votes
1answer
146 views

Number of $n$-element subsets of $\{1, 2, \dotsc, 3n\}$ with sum divisible by $n$

Is there any recurrence relations/formula/algorithm to count the number of $n$-element subsets of the set $\{1, 2, \dotsc, 3n\}$ with sum divisible by $n$? How about replacing $3n$ with $kn$? I ...
0
votes
1answer
36 views

If $\phi: G \cong H, c_k: S_k \to \Bbb{N}$ s.t. $c(\pi)$ is the no. of cycles in the decomposition of $\pi$, is $c_k(\phi(g)) = c_{k'}(\phi'(g))$?

My question is essentially in group theory but came from working on a problem in Polya Theory. Let $G$ be a finite group. We know then that $G$ is isomorphic to some subgroup of $H \subseteq S_{k}$ ...
2
votes
1answer
297 views

Among all 10 digit numbers, how many are there satisfying that the product of all digits ends in at least 5 zeros? [closed]

For example, 2222255555 and 5324855555 are both such numbers. By the way, this is an interview question, and thus I think there should be a not-too-complicated way to count it. I'm sorry for that I ...
2
votes
1answer
56 views

Deriving formula for necklace like objects

I have seen people use the polya enumeration theorem/burnsides lemma to derive the formula $$\frac{1}{n}\sum_{d|n} \phi(d)2^{n/d}$$ that counts the number of length $n$ necklaces with two beads (...
6
votes
1answer
326 views

Intuition Behind Necklace Formula

Wikipedia and Wolfram MathWorld say that the formula for the number of distinct $k$-ary necklaces of length $n$ is: $$ N_k(n) = \frac{1}{n}\sum_{d|n} {\phi(d)k^{n/d}} $$ What is the intuition behind ...
0
votes
0answers
60 views

Finding the symmetries of Coronene (24 carbon atoms and 12 hydrogen)

My question is this: Coronene consists of 24 carbon atoms and 12 hydrogen atoms arranged as illustrated in the link below. If we allow some or all of the hydrogen atoms to be replaced by chlorine, ...
0
votes
1answer
206 views

Is it possible to find two distinct 4-colorings of the tetrahedron which use exactly one of each color?

I'm working on a problem for Discrete Math, and I'm having some trouble. The question is: Determine the pattern inventory for red/green/blue/yellow colorings of the vertices of a regular tetrahedron. ...