Questions tagged [polya-counting-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
26 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 ...
3
votes
2answers
69 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 ...
1
vote
0answers
65 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 ...
4
votes
1answer
69 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, ...
1
vote
1answer
48 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 $...
1
vote
1answer
81 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? ...
0
votes
0answers
25 views

Counting colored graphs with balanced colors

Let $G$ be an undirected graph where each vertex has one of three colors ($a$,$b$,$c$). Given one such coloring $Y$, how many unique colorings $Y'$ are there where at least two vertices of one fixed ...
2
votes
0answers
59 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 ...
2
votes
1answer
103 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 ...
0
votes
2answers
79 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
0answers
31 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 ...
0
votes
0answers
58 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}{...
2
votes
1answer
76 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 ...
0
votes
1answer
73 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 ...
0
votes
1answer
50 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 ...
2
votes
2answers
92 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 ...
2
votes
1answer
53 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 ...
4
votes
1answer
48 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$? $...
1
vote
0answers
38 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
91 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"...
2
votes
1answer
248 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
94 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
69 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 ...
3
votes
1answer
117 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
33 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
36 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
138 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
65 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
100 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
184 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
254 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
30 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
369 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 ...
1
vote
1answer
77 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
158 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
51 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
2k 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
41 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
81 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
26 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
106 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
186 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 ...
1
vote
2answers
41 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
36 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
128 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
333 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 ...
2
votes
0answers
35 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
87 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
102 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
140 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 ...