2
$\begingroup$

How many ways are there to color the ten balls of a triangular array that is free to rotate using 2 colors?

The triangular array is arranged such that a single ball is in the apex [first row]; the next row is composed of two balls; the third row is three balls, and the fourth row is four balls. This is for a homework assignment and I am relatively new to mathematics and this class. The textbook is not very helpful in terms of explaining how to solve such a problem.

$\endgroup$
2
$\begingroup$

In order to apply Burnside's lemma we need a group to be acting on a set. Here the group will be the cyclic group of order 3. The set will be the set of $oriented$ two-colorings of the balls. Where by oriented I mean we distinguish between two different colorings that are rotations of one another. The action will be induced from the action of the group on the balls. The orbits of this action will be the set of colorings where we don't distinguish between rotations.

The identity element fixes all $2^{10}$ oriented colorings. The two rotations each fix $2^4$ oriented colorings, the $4$ comes from the $4$ orbits of these rotations on the balls themselves.

Burnsides lemma tells us that the number of orbits is $\frac{1}{3}(2^{10}+2^4 +2^4) =352$

$\endgroup$
2
$\begingroup$

We can actually solve a more general question where the triangle consists of $n$ levels and $\frac{1}{2} n (n+1)$ vertices. In order to apply Burnside we compute the cycle index $Z(G)$ of the group $G$ of the vertices under rotation. There are only three permutations here, the identity and two rotations. The identity contributes $a_1^{\frac{1}{2} n (n+1)}.$ The two rotations partition everything into three-cycles except for the center vertex when $n$ is is congruent to one modulo three. Therefore for $n=3m+1$ we get the cycle index

$$Z(G) = \frac{1}{3} \left(a_1^{\frac{1}{2} n (n+1)} + 2 a_1 a_3^{\frac{1}{6} (n-1) (n+2)}\right)$$ and for $n=3m+2$ and $n=3m+3$ we get $$Z(H) = \frac{1}{3} \left(a_1^{\frac{1}{2} n (n+1)} + 2 a_3^{\frac{1}{6} n (n+1)}\right).$$

There are two colors and the colorings must be constant on the cycles so when $n=3m+1$ we get for the count $Q_n$ of two-colorings $$Q_n = \frac{1}{3} \left(2^{\frac{1}{2} n (n+1)} + 2 \times 2 \times 2^{\frac{1}{6} (n-1) (n+2)}\right) = \frac{1}{3} \left(2^{\frac{1}{2} n (n+1)} + 2^{2+\frac{1}{6} (n-1) (n+2)}\right)$$ and for $n=3m+2$ or $n=3m+3$ we get $$Q_n = \frac{1}{3} \left(2^{\frac{1}{2} n (n+1)} + 2 \times 2^{\frac{1}{6} n (n+1)}\right) = \frac{1}{3} \left(2^{\frac{1}{2} n (n+1)} + 2^{1+\frac{1}{6} n (n+1)}\right).$$

This is the following sequence: $$2, 4, 24, 352, 10944, 699136, 89479168, 22906494976, 11728124051456 ,\ldots $$

Verification. We can verify these formulas using direct enumeration. This is based on the observation that the $\lfloor (n+2)/3 \rfloor$ nested triangles that the figure is made up of are only fixed by the three permutations if they have the same color at the corners and one of $2^{p-2}$ oriented sequences that are in agreement on the three sides (of length $p$).

This gives for $n=3m+1$ the result $$Q_n = 2 \times \prod_{q=1}^m 2 \times 2^{3q+1-2} + \frac{1}{3} \left(2^{\frac{1}{2} n (n+1)} - 2 \times \prod_{q=1}^m 2 \times 2^{3q+1-2} \right) \\ = \frac{2}{3} 2^{m+1} \times 2^{\sum_{q=1}^m 3q-1} + \frac{1}{3} \times 2^{\frac{1}{2} n (n+1)} \\ = \frac{1}{3} \left(2^{3/2\times m^2+3/2\times m+2}+2^{\frac{1}{2} n (n+1)}\right).$$ This is easily seen to match the formula from above.

For $n=3m+2$ we get the result $$Q_n = \prod_{q=0}^m 2 \times 2^{3q+2-2} + \frac{1}{3} \left(2^{\frac{1}{2} n (n+1)} - \prod_{q=0}^m 2 \times 2^{3q+2-2} \right) \\ = \frac{2}{3} 2^{m+1} 2^{\sum_{q=0}^m 3q} + \frac{1}{3} \times 2^{\frac{1}{2} n (n+1)} \\ = \frac{1}{3} \left(2^{3/2\times m^2+5/2\times m+2} + 2^{\frac{1}{2} n (n+1)}\right)$$ This also matches the formula from above.

Finally we put $n=3m+3$ to get $$Q_n = \prod_{q=0}^m 2 \times 2^{3q+3-2} + \frac{1}{3} \left(2^{\frac{1}{2} n (n+1)} - \prod_{q=0}^m 2 \times 2^{3q+3-2} \right) \\ = \frac{2}{3} 2^{m+1} 2^{\sum_{q=0}^m 3q+1} + \frac{1}{3} \times 2^{\frac{1}{2} n (n+1)} \\ = \frac{1}{3} \left(2^{3/2\times m^2+7/2\times m+3} + 2^{\frac{1}{2} n (n+1)}\right)$$ once again a match.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.