# Counting the number of ways to arrange colored beads under a group action

Let's say we have a list of colored beads, e.g. [blue, red, red, yellow, blue, red, yellow], and a group G that acts on the list by permuting its elements. Is there an efficient way to calculate the number of distinct permutations up to coloring under this group G?

For example, if G was the symmetric group S7, then the number of permutations is 7!/(2!3!2!) = 210. If G was the alternating group A7, then since we have at least two beads of the same color, we also get 210 (just place the blue and red beads where you want them, which forces the placement of the yellow beads but since they are both yellow we don't lose any distinguishable permutations).

By efficient, I mean a method that doesn't need to iterate over all elements of G. We can assume G is finite but may be very large. The application I have in mind is for permutation puzzles, where if we assume each piece is distinguishable, then there are efficient methods (like Schreier-Sims) to compute the number of different scrambles given the generators for the group. But in many puzzles, pieces are grouped into like colors, so the effective number of scrambles is actually less than this, e.g. the Hungarian rings puzzle.

• Is it OK to iterate over the conjugacy classes of $G$? Commented Mar 2, 2022 at 8:43
• @joriki yes that is fine. I would be interested in anything better than just brute force of iterating over all group elements and counting the number of distinct arrangements. Commented Mar 2, 2022 at 17:31
• One idea I had was that if the group is k-transitive and there were at least (n-k) pieces of the same color, then all rearrangements of colored beads is possible. This is a generalization of the observation that all arrangements are possible for an alternating group if there are at least two identical pieces. But not sure what to do if there are fewer than (n-k) pieces of the same color. Commented Mar 2, 2022 at 17:42