Find the number of ways the 3 colored balls can be placed on vertices of a polygon without same color being adjacent and considered up to symmetry

Question

Give a generalized form [in the form of "n" i.e number of vertices of a polygon] of the number of combinations possible for 3 colored balls [infinite balls [it is not compulsory to use all the colors]] to be placed at vertices of a polygon with n vertices. The condition to be met is that no balls of same colored to be placed adjacent to each other. We consider two colorings the same if the can be obtained from one another by rotating or reflecting the n-gon.

Conditions:

1. No two same colors can be placed adjacent

2. We have only 3 types of balls and which can be used in any number as far as 1st condition is followed.

3. Rotation or reflection pf a coloring does not count as a new coloring.

Eg: Take a case of Triangle. Possible combinations of placing balls is 1 i.e. 1 ball of each color.

Square: we can take either 2 balls each of 2 different colors or 2 balls of one color, 1 ball each of other two colors. Which gave total combinations of 6.

Answer 1

Update: After the edit by the OP it becomes clear that the following does not answer his question. If colorings differing only by a rotation are considered equal we need the so-called Polya theory to tackle the problem.

I assume that we have $3$ colors numbered $0$, $1$, $2$ and $n$ sites numbered $0$, $1$, $\ldots$, $n-1$.

Put color $0$ on site $0$, and denote by $P(j)$ the number of ways to color the sites $0$, $\ldots$, $j$ such that site $j$ gets a color $\ne0$. Then we have $P(0)=0$ and $P(1)=2$; furthermore we have the recursion $$P(j)=2 P(j-2)+P(j-1)\qquad(j\geq2)\ .\tag{1}$$ Proof. If site $j-1$ is colored $0$ then site $j-1$ is colored $\ne0$, and we have two options for site $j$. If site $j-1$ is colored $\ne0$ then we have just one $\ne0$ option for site $j$.

The characteristic polynomial of $(1)$ is $\lambda^2-\lambda-2=0$ with the roots $2$ and $-1$. It follows that the general solution is $j\mapsto a 2^j +b(-1)^j$ with constants $a$ and $b$. The initial conditions then lead to $$P(j)={2\over3}\bigl(2^j-(-1)^j\bigr)\ .$$ Since site $0$ could have been colored with any of the three colors we finally obtain $$A(n)=3 P(n-1)=2^n+2(-1)^n\qquad(n\geq2)$$ admissible colorings.

Answer 2

The question is to enumerate bracelets with $n$ beads and $3$ colours where adjacent beads have different colours. A bracelet is a cyclic arrangement of beads considered up to dihedral symmetry (i.e. rotation and reflection). Whether we use $3$ colours or $k$ colours makes no meaningful difference in our analysis so we will be more general and use $k$ colours. Thus the question is to count the number of bracelets with $n$ beads and $k$ colours with no two adjacent beads of the same colour.

In order to achieve this, we need to make use of Burnside's Lemma:

Lemma (Burnside): Let $G$ be a group acting on a set $X$. For each $g \in G$ let $X_g := \{ x \in X : g \cdot x = x\}$ be the fixed-point set of $g$. Say two elements $x, y$ of $X$ belong to the same pattern if they are related by an element of $G$: $x = g \cdot y$. Then the number of distinct patterns in $X$ is $$ \frac{1}{|G|} \sum_{g \in G} |X_g|. $$

---

Let us start by counting only rotational symmetries. Let $C_n$ be the cyclic group of order $n$. These are all the ways to rotate an $n$-gon. For instance, pick a vertex of that $n$-gon and rotate it $s$ places counter clockwise. Call this operation $\rho_s$. Then the multiplication rule is $\rho_s \rho_t = \rho_{s + t}$ (i.e. rotating $t$ places then $s$ places is the same as rotating $s + t$ places all at once). Notice then that $\rho_s = \rho_1^s$ (i.e. rotating $s$ places is the same as rotating $1$ place $s$ times in succession).

Now if we have an $n$-gon then $$\rho_s^n = (\rho_1^s)^n = \rho_1^{ns} = (\rho_1^n)^s = \rho_n^s = \rho_0^s = \rho_0 $$ keeping in mind that $\rho_n = \rho_0$ (rotating n places is the same as rotating no places). Given $s$, let $d$ be the smallest positive number such that $\rho_s^d = \rho_0$, called the order of $\rho_s$. It is a consequence of Lagrange's Theorem that $d \mid n$ ($d$ divides $n$).

I won't prove this, but it can be shown that the number of $\rho_s$ of order $d$ for some fixed divisor $d$ of $n$ is $$ \varphi \left( d \right) $$ where $\varphi$ is Euler's totient function defined by $\varphi(m) =$ the number of integers $l$ between $1$ and $m$ for which $\gcd(m,l) = 1$ ($l$ is coprime to $m$).

For instance, take a divisor $d$ of $n$ and consider $\rho_d$. This breaks apart the $n$-gon into $n/d$ connected segments of vertices which get rotated onto the next one. For instance with $n = 4$ and $d = 2$ we can view this as two parallel line segments getting mapped onto each other after a 180 degree rotation.

Another fact that is essential is that if $\rho_s, \rho_t$ have order $d$ then $\rho_s, \rho_t$ have the same number of fixed points. That is $|X_{\rho_s}| = |X_{\rho_t}|$. This isn't hard to show if you know group theory. Thus we only need to look at the fixed points of $\rho_d$ with $d$ a divisor of $n$.

Suppose we have a $k$-colouring of the $n$-gon which is invariant under rotating $d$ places. Then take an $n/d$ long segment from it. The first vertex is a different colour from the second, the second from the third and so on. Most importantly, the last vertex is a different colour than the first, because after rotating d places, the first vertex colour comes after the last vertex's colour. Thus the number of fixed points under $\rho_d$ is the same as the number of ways to colour an $n/d$-gon without considering symmetry. This number is $$ P_{n/d}(k) = (k - 1)^{n/d} + (-1)^{n/d}(k - 1). $$ The chromatic polynomial. A special case of $k = 3$ is given in Christian's answer.

Now applying Burnside's Lemma. The number of $k$-coloured $n$-gons with no two adjacent vertices given the same colour, and considered up to rotational symmetry, is $$ \frac{1}{n} \sum_{d \mid n} \varphi(d) P_{n/d}(k). $$ The $n$ in $\frac{1}{n}$ is because the cyclic group has $n$ elements.

---

Now for reflections. Suppose first that $n$ is odd. Then a reflection will cut through one vertex and the edge on the opposite side. But there can be no fixed points because the vertices in that edge are adjacent and being fixed under reflection would mean they have the same colour!

Now suppose $n$ is even. By the same logic, we cannot reflect on an axis cutting through two edges. Thus we must reflect through a line cutting two vertices. What happens? We give the first vertex we cut a colour. Then its two neighbours get a different colour then the two neighbours of those vertices moving down the sides of the $n$-gon have a different colour. This is essentially the same as colouring the vertices of a path $$\bullet \to \bullet \to \bullet \to \cdots \to \bullet.$$ The chromatic polynomial here is $k(k - 1)^{\text{length of path} - 1}$. I won't show this in the interest of getting to the answer.

The length of the path in question is $2 + \frac{n - 2}{2} = \frac{n + 2}{2}$. Subtract $1$ to get $n/2$. Now for the dihedral group there are $n$ rotations and $n$ reflections so the group has size $2n$. If $n$ is even then there are $n/2$ reflections cutting two vertices. Thus the final answer of the number of $k$-coloured bracelets with $n$ beads and no two adjacent beads given the same colour is $$ \frac{1}{2n} \sum_{d \mid n} \varphi(d) P_{n/d}(k) $$ if $n$ is odd, and $$ \frac{1}{2n} \sum_{d \mid n} \varphi(d) P_{n/d}(k) + \frac{1}{4}k(k - 1)^{n/2} $$ if $n$ is even. (Note that $\frac{1}{4} = \frac{n/2}{2n}$ where $2n$ is the size of the dihedral group and $n/2$ is the number of reflections of the type we want.)

---

Small caveat: this formula is only valid for $n \ge 2$. For $n = 1$ it views a $1$-gon as having its single vertex adjacent to itself and gives the answer $0$. If you don't view a $1$-gon in this way, the answer is $k$ because we can give that vertex any colour.

Answer 3

Given : N number of sots to be filled by 3 colored balls

Let’s take a function f(n) for all the possible ways to arrange the ball on the given n-slots on a circle. So

f(1) = 3 x 1 = 3

f(2) = 3 x 2 x 1 = 6

For n ≥ 3 , the number of valid combinations are follows;

Choose any position to start with, the number of way to put a ball on the position is 3. Moving

clockwise, we will have 2 ways to fill all the slots upto (n-1) slot. So the total number of possible

combinations is 2^n-1.

But there is one case where the (n) position slot has the same color of that of slot number (1). For that case, I consider, the last and the 2nd last slot as a single element where I have placed the same color and will delete all the possible combinations that have them, i.e. f(n-1).

So f(n) = 3 x 2^(n-1)- f(n-1)

For k colored balls: f(n) = k x (k-1)^(n-1) - f(n-1)

Will this work?